国庆10.5

T1 World

一个世界中互杀。。。刷样例30。。。。

正解是递归+模拟只不过要细心一点哈???奈何我连题目都没看懂??

T2 City

计算所有能从景点u到景点v的最短路径上的景点数量的和。。。。

直接 floyd。输出的时候统计路上节点即可。。。。。就是注意答案要+2,加上起点和终点两个点。。。统计如下。。

for(int j=1;j<=n;j++)

for(int j=1;j<=n;j++)

if(f[a][j]+f[j][b]==f[a][b]) sum++;

考试时floyd打出来了,不知道怎么统计。。爆零了。。。

T3 Game

相同字母可以一次性全部消除,清除出一条从上到下的道路,求最少的点击次数。。。

最短路模版题,但我没见过。。。

T4 Password

求两串密码的最长上升公共子序列。。。我用DP,用f[i][j]表示a串前i个字母和b串前j个字母中最长上升公共子序列,40分的核代如下。。

for(i=1;i<=l;i++)

for(j=1;j<=r;j++)

if(f[i][j]&&(a[jl]<a[i]||f[i-1][j-1]==0))

{

f[i][j]=f[i-1][j-1]+1;

jl=i;

}

else f[i][j]=max(f[i-1][j],f[i][j-1]);

printf("%d\n",f[l][r]);

求教。。。。

70分的一天,Ծ‸ Ծ

发表评论

电子邮件地址不会被公开。 必填项已用*标注