这一节做得很郁闷,题目以动态规划为主,而本人的动规很弱,做的很勉强。。。
Longest Prefix
问题描述:
给定一堆短字符串,和一条长字符串,求用短字符串组成的长字符串的最长前缀长度。
分析:
看完题目首先想到的是DFS,写完提交上去后到第三组数据就超时了。。。看了别人的题解,原来要用动规,用dp[i]表示当前能拼到的最长前缀,然后在短字符里面寻找最长的能和长字符串继续匹配的,然后i+1!本来想第一次试试Hash,但写到一半觉得函数写得不够好,先记住了,有空了用Hash优化一遍。
Cow Pedigrees
问题描述:
给定一颗树的节点数和度,问其能构成多少种不同的数。
分析:
这题虽然明知道要用动规,但想了一下午都没想出状态转移方程来,囧~。看了网上的官方题解,一颗树显然要由一颗小树(根节点)构成,可以是左子树,也可以是右子树,分三种情况,左长,右长,左右同长。状态转移方程如下:
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
Zero Sum
问题描述:
请考虑一个由1到N(N=3, 4, 5 ... 9)的数字组成的递增数列:1 2 3 ... N。现在请在数列中插入“+”表示加,或者“-”表示减,“ ”表示空白(例如1-2 3就等于1-23),来将每一对数字组合在一起(请不在第一个数字前插入符号)。计算该表达式的结果并判断其值是否为0。请你写一个程序找出所有产生和为零的长度为N的数列。
分析:
这题在培训的时候讲过,创建一个字符串“1 2 3 4 5 6 7 8 9 ”数字间隔着空格,然后在空格位置枚举写入‘ ’,‘+’,‘-’递归(其实也就是简单的DFS)。把字符串转成数字运算,若结果为0则输出。
Money Systems
问题描述:
给出一套钱币的面值,求组成某数N有多少种方案。
分析:
这是个简单的动规,用dp[ i ] [ j ]表示仅用前i种钱币拼成j的方案数,那么仅用前i-1种钱币拼成j的方案dp[i-1][j]也满足,如果用了一枚面值为i的钱币,则dp[i][j]+=dp[i-1][j-v[i]]其中v[i]为i的面值,同理,用了两枚dp[i][j]+=dp[i-1][j-2*v[i]],一直到j-k*v[i]<=0为止。
注意,当j可以被v[i]整除时,dp[i][j]++;初始化dp[1][k*v[1]]=1,(k*v[i]<=N)
状态转移方程为:
dp[i][j] =∑dp[i-1][j-k*v[i]];(k=1..j/v[i])
Controlling Companies
问题描述:
有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。如果至少满足了以下三个条件之一,公司A就可以控制公司B了:
1.公司A = 公司B。
2.公司A拥有大于50%的公司B的股票。
3.公司A控制K(K >= 1)个公司,记为C1, ..., CK,每个公司Ci拥有xi%的公司B的股票,并且x1+ .... + xK > 50%。
给你一个表,每行包括三个数(i,j,p);表明公司i享有公司j的p%的股票。计算所有的数对(h,s),表明公司h控制公司s。至多有100个公司。
写一个程序读入三对数(i,j,p),i,j和p是都在范围(1..100)的正整数,并且找出所有的数对(h,s),使得公司h控制公司s。
分析:
这题似乎很麻烦,当你控制了一家新公司后,新公司又有可能控制着另一家公司,构成一层接一层的迭代关系。。。刚开始用DFS的时候思路就比较混乱,结果只通过了前六个测试,而且效率很低,后来细细分析了一下,其实这有点类似图的结构,题目给出的表可以看做邻接矩阵。问题就转化为,以某点作为原点出发,如果原点到某点s的距离超过50,那么把s纳入原点所在集合P,找与s距离超过50的点,再次纳入P,不断更新原点到这些点的距离。最后列出所有到原点距离超过50的点。
int Own[101][101]={0};
int current[101];
bool visit[101],flag;
int N,MAX=0,MIN=1<<30;
void Search(int n)
{ int i,j;
for(j=MIN;j<=MAX;j++)
{ current[j]+=Own[n][j];
if(current[j]>50&&!visit[j])
{ visit[j]=true;
Search(j);
}
}
}
int main()
{ memset(visit,false,sizeof(visit));
fin>>N;
int t=N,i,j,p;
while(t--)
{ fin>>i>>j>>p;
Own[i][j]+=p;
if(i>MAX)
MAX=i;
if(i<MIN)
MIN=i;
if(j<MIN)
MIN=j;
if(j>MAX)
MAX=j;
}
for(i=MIN;i<=MAX;i++)
{ memset(current,0,sizeof(current));
memset(visit,false,sizeof(visit));
Search(i);
for(j=MIN;j<=MAX;j++)
if(current[j]>50&&j!=i)
fout<<i<<" "<<j<<endl;
}
return 0;
}