USACO 2.3

  • 最长前缀 Longest Prefix
  • 奶牛家谱 Cow Pedigrees
  • 零的数列 Zero Sum
  • 货币系统 Money Systems
  • 控制公司 Controlling Companies

P1470 最长前缀 Longest Prefix

dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

/*
ID: ylx14274
PROG: prefix
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
string s,ss,c[251];
int n,i,j,m;//n:元素个数
int a[251];//元素长度
int f[200000];
int main()
{
freopen("prefix.in","r",stdin);
freopen("prefix.out","w",stdout);
while (true)
{
m++;//计数器+1
cin>>c[m];//读入
if (c[m].size()-1]=='.')//结束
{
m--;//计数器多算了
break; //退出
}
a[m]=c[m].size(); //记位数
}
while (cin>>ss)//读入
{
s+=ss; //连起来
}
n=s.size();//存s的长度
s=' '+s;//每一位都往后挪一位,方便操作
f[0]=1;//初始值
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (i-a[j]>=0)//因为f数组没有负数下标,所以判断
{
if (f[i-a[j]]==1)//i-a[j]位能由该集合的元素组成
if (s.substr(i+1-a[j],a[j])==c[j])
//i+1-a[j]~i位由c[j]组成
f[i]=1;//标记
}
for (i=n;i>=0;i--)
if (f[i]==1)
{
printf("%d\n",i); //输出最大的
return 0;
}
}

P1472 奶牛家谱 Cow Pedigrees

既然NOCOW描述得很清楚了,为何不直接引用呢?
这是一个DP问题。我们所关心的树的性质是深度和节点数,所以我们可以做这样一张表:

table[i][j]表示深度为i、节点数为j的树的个数。根据给定的约束条件,j必须为奇数。你如何构造一棵树呢?当然是由更小的树来构造了。一棵深度为i、节点数为j的树可以由两个子树以及一个根结点构造而成。当i、j已经选定时,我们选择左子树的节点数k。

这样我们也就知道了右子树的节点数,即j-k-1。至于深度,至少要有一棵子树的深度为i-1才能使构造出的新树深度为i。有三种可能的情况:左子树深度为i-1 ,右子树深度小于i-1;右子树深度为i-1,左子树深度小于i-1;左右子树深度都为i-1。事实上,当我们在构造一棵深度为i的树时,我们只关心使用的子树深度是否为i-1或更小。

因此,我们使用另一个数组smalltrees[i-2][j]记录所有深度小于i-1的树,而不仅仅是深度为i-2的树。知道了上面的这些,我们就可以用以下三种可能的方法来建树了:

1
2
3
4
5
6
table[i][j] = smalltrees[i-2][k]*table[i-1][j-1-k];
// 左子树深度小于i-1,右子树深度为i-1
table[i][j] = table[i-1][k]*smalltrees[i-2][j-1-k];
// 左子树深度为i-1,右子树深度小于i-1
table[i][j] = table[i-1][k]*table[i-1][j-1-k];
// 左右子树深度都为i-1

另外,如果左子树更小,我们可以对它进行两次计数,因为可以通过交换左右子树来得到不同的树。总运行时间为O(K*N^2),且有不错的常数因子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int a[240][240];
int sa[240][240];
int main()
{
freopen("nocows.in","r",stdin);
freopen("nocows.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);//n:节点数 m:树高度
a[1][1]=1;//初始化
for (int i=2;i<=m;i++)
{
for (int j=1;j<=n;j+=2)//要么有2个孩子要么没有孩子所以节点数一定是奇数
for (int k=1;k<=j-1-k;k+=2)//简单的优化,k>一半的时候可以*2,j-1是减去爸爸
{
int x=2;
if (k==j-1-k) x=1;//一半一半的话就不用*2了
a[i][j]+=x*((sa[i-2][k]*a[i-1][j-1-k])%9901//左子树深度小于i-1,右子树深度为i-1
+(a[i-1][k]*sa[i-2][j-1-k])%9901//左子树深度为i-1,右子树深度小于i-1
+(a[i-1][k]*a[i-1][j-1-k])%9901);//左右子树深度都为i-1
a[i][j]%=9901; //记得取摸
}
for (int k=0;k<=n;k++)//加上去
{
sa[i-1][k]+=sa[i-2][k]+a[i-1][k];
sa[i-1][k]%=9901;//记得取摸
}
}
cout<<a[m][n]%9901<<endl;
return 0;
}

P1473 零的数列 Zero Sum

啊,这么小的范围?暴搜!

当然这道题也可以打表。
这题主要是空格的情况不好处理,如果无空格情况的话就可以在标记符号的同时把下一位加上,
这个的话必须找到下一个符号,再将上一个数加上或减去。
比如:
1+2 3 搜到+的时候,把1加上去,搜到空的时候继续往下搜,结尾的时候再把23给加上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
ID: ylx14274
PROG: zerosum
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int n,sum;
char a[9];//存8个间隔的符号,‘+’‘-’‘ ’
void dfs(int t,int x,int he)
//t存深度,x存本个数字的长度(没有计算),he存上一位符号1为+,2为-
{
if (t==n)//搜到了
{
int s=sum;
if (he==1) s+=x; else s-=x;//最后一个数字得算进去
if (s==0)//和为0
{
for (int ii=1;ii<n;ii++)//输出数字和符号
{
printf("%d%c",ii,a[ii]);
}
printf("%d\n",n);//最后一个数单独输出
}
return;
}
/**************空号这种情况**************/
a[t]=' ';//标记
if (he==1)//如果前面那个符号是加号
dfs(t+1,x*10+t+1,1);
else dfs(t+1,x*10+t+1,2);
/**************+号这种情况**************/
a[t]='+';//标记
if (he==1)//如果前面那个符号是加号
{
sum+=x;
dfs(t+1,t+1,1);
sum-=x;
}
else
{
sum-=x;
dfs(t+1,t+1,1);
sum+=x;
}
/**************-号这种情况**************/
a[t]='-';
if (he==1)
{
sum+=x;
dfs(t+1,t+1,2);
sum-=x;
}
else
{
sum-=x;
dfs(t+1,t+1,2);
sum+=x;
}
return;
}
int main()
{
scanf("%d",&n);
dfs(1,1,1);//暴搜
return 0;
}

P1474 货币系统 Money Systems

最简单的完全背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include<iostream>
#include<cstdio>
using namespace std;
long long v,n,i,j;
long long a[25];
long long f[10010];
int main()
{
scanf("%lld%lld",&v,&n);
f[0]=1;
for (i=1;i<=v;i++)
{
scanf("%lld",&a[i]);
for (j=a[i];j<=n;j++)
f[j]+=f[j-a[i]];
}
printf("%lld",f[n]);
return 0;
}

P1475 控制公司 Controlling Companies

公司A = 公司B。也就是自己可以控制自己。

公司A拥有大于50%(不包括等于50%)的公司B的股票。

公司A控制K(K >= 1)个公司,记为C1, …, CK,每个公司Ci拥有xi%的公司B的股票,并且x1+ …. + xK > 50%。A公司控制的公司(包括自己)共有B公司一半以上的股票。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*
ID: ylx14274
PROG: concom
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int x,y,k,n,t,i,j;
int a[201][201];//a[i][j]表示i公司控制j公司的股权数量
int pd[201];//判重
int he[201];
void dfs(int c)//c是i公司控制的公司
{
pd[c]=1;//标记
int i;
for (i=1;i<=n;i++)
{
he[i]+=a[c][i];//加上c公司拥有i的股权
if (he[i]>50)//c拥有公司i
{
if (pd[i]==0)//没被搜过
dfs(i);//搜
}
}
return;
}
int main()
{
freopen("concom.in","r",stdin);
freopen("concom.out","w",stdout);//文件
scanf("%d",&t);//读入
n=0;
for (i=1;i<=t;i++)
{
scanf("%d%d%d",&x,&y,&k);
if (x>n) n=x;
if (y>n) n=y;//找公司数量?标号最大?
a[x][y]+=k;//标记
}
for (i=1;i<=n;i++)
{
for (j=1;j<=200;j++) pd[j]=0;//数组赋初值
for (j=1;j<=200;j++) he[j]=0;//数组赋初值
dfs(i); //搜,自己控制自己
for (j=1;j<=n;j++)
if (he[j]>50&&i!=j)//不能是自己
printf("%d %d\n",i,j); //输出
}
return 0;
}