题目来源:The 7th Zhejiang University Programming Contests
(ZOJ 2834—2841)
Problem BZOJ 2835Magic Square
水题,不解释。
代码:
View Code1#include
2#include
3#include
4#include
5usingnamespacestd;
6intmain()
7{
8intn,i,j,s1,s2,flag;
9inta[11][11],b[1001];
10while(~scanf("%d",&n))
11{
12memset(b,0,sizeof(b));
13if(!n)
14break;
15flag=0;
16for(i=0;i<n;i++)
17for(j=0;j
\\19\scanf(\"\\%d\\"\,&a[i][j]);\
\\20\b[a[i][j]]++;\
\\21\\if\(b[a[i][j]]>1)
22flag=1;
23}
24if(flag)
25{
26puts("No");
27continue;
28}
29s1=0;
30for(i=0;i<n;i++)
31s1+=a[0][i];
32for(i=1;i<n;i++)
33{
34s2=0;
35for(j=0;j<n;j++)
36s2+=a[i][j];
37if(s2!=s1)
38{
39flag=1;
40break;
41}
42}
43s2=0;
44if(!flag)
45{
46for(i=0;i<n;i++)
47s2+=a[i][i];
48if(s2!=s1)
49flag=1;
50s2=0;
51for(i=0;i<n;i++)
52s2+=a[n-i-1][i];
53if(s2!=s1)
54flag=1;
55}
56if(flag)
57puts("No");
58else
59puts("Yes");
60}
61return0;
62}
Problem FZOJ 2839Find the Sequences
View Code1#include
2#include
3#include
4#include
5#include
6usingnamespacestd;
7structpoint
8{
9intx;
10inty;
11}p[10001];
12inthash[500000];
13intcmp(constvoida,constvoidb)
14{
15structpoint c=(structpoint )a;
16structpoint d=(structpoint )b;
17if(c->y!=d->y)
18returnc->y-d->y;
19else
20returnc->x-d->x;
21}
22intmain()
23{
24inti,j,k,n,m,t,c,d,l,a1,b1,c1;
25inta[50000];
26c=0;
27while(~scanf("%d%d",&n,&m))
28{
29c++;
30l=t=0;
31if(n==0&&m==0)
32break;
33if(c!=1)
34puts("");
35memset(hash,0,sizeof(hash));
36for(i=0;i<=m;i++)
37{
38for(j=0;j<=m;j++)
39{
40d=iii+jjj;
41if(!hash[d])
42{
43hash[d]=1;
44a[t++]=d;
45}
46}
47}
48sort(a,a+t);
49for(i=0;i<t;i++)
50{
51for(j=i+1;j<t;j++)
52{
53a1=a[i];
54b1=a[j]-a[i];
55for(k=3;k<=n;k++)
56{
57c1=a1+(k-1)*b1;
58if(c1>a[t-1]||!hash[c1])
59break;
60}
61if(k>n)
62{
63p[l].x=a1;
64p[l].y=b1;
65l++;
66}
67}
68}
69printf("Case %d:n",c);
70if(!l)
71{
72puts("NONE");
73continue;
74}
75qsort(p,l,sizeof(p[0]),cmp);
76for(i=0;i<l;i++)
77{
78printf("%d %dn",p[i].x,p[i].y);
79}
80}
81return0;
82}
View Code1#include
2#include
3#include
4usingnamespacestd;
5intmain()
6{
7intn,m,i,j,p,f,k,t,l1,l2,c=1;
8chars[100][65],s1[65];
9while(~scanf("%d%c",&n))
10{
11for(i=0;i<n;i++)
12scanf("%s",s[i]);
13if(c!=1)
14puts("");
15c++;
16scanf("%d%c",&m);
17while(m--)
18{
19scanf("%s",s1);
20l1=strlen(s1);
21for(i=0;i
\\23\\if\(s1[i]==\'\\*\\'\)\
\\24\{\
\\25\p=i;\
\\26\\break\;\
\\27\}\
\\28\}\
\\29\t=\0\;\
\\30\\if\(!p)\
\\31\{\
\\32\\for\(i=\0\;i\
\\34\l2=strlen(s[i]);\
\\35\\if\(l2\
\\36\\continue\;\
\\37\f=\0\;\
\\38\\for\(j=l1-\1\,k=l2-\1\;j>=\1\&&k>=\0\;j--,k--)\
\\39\{\
\\40\\if\(s1[j]!=s[i][k])\
\\41\{\
\\42\f=\1\;\
\\43\\break\;\
\\44\}\
\\45\}\
\\46\\if\(!f)\
\\47\{\
\\48\\if\(t>0)
49printf(",");
50t++;
51printf("%s",s[i]);
52}
53}
54}
55elseif(p==l1-1)
56{
57for(i=0;i<n;i++)
58{
59f=0;
60l2=strlen(s[i]);
61if(l2<l1-1)
62continue;
63for(j=0;j
\\64\{\
\\65\\if\(s1[j]!=s[i][j])\
\\66\{\
\\67\f=\1\;\
\\68\\break\;\
\\69\}\
\\70\}\
\\71\\if\(!f)\
\\72\{\
\\73\\if\(t>0)
74printf(",");
75t++;
76printf("%s",s[i]);
77}
78}
79}
80else
81{
82for(i=0;i<n;i++)
83{
84l2=strlen(s[i]);
85if(l2
\\86\\continue\;\
\\87\f=\0\;\
\\88\\for\(j=\0\;j\\\89\{\
\\90\\if\(s1[j]!=s[i][j])\
\\91\{\
\\92\f=\1\;\
\\93\\break\;\
\\94\}\
\\95\}\
\\96\\if\(!f)\
\\97\{\
\\98\\for\(j=l1-\1\,k=l2-\1\;j>p;j--,k--)\
\\99\{\
\\100\\if\(s1[j]!=s[i][k])\
\\101\{\
\\102\f=\1\;\
\\103\\break\;\
\\104\}\
\\105\}\
\\106\}\
\\107\\if\(!f)\
\\108\{\
\\109\\if\(t>0)
110printf(",");
111printf("%s",s[i]);
112t++;
113}
114}
115}
116if(!t)
117printf("FILE NOT FOUND");
118puts("");
119}
120}
121return0;
122}
附:
官方题解:
A - Maximize Game Time - by cyang 中等题
一颗节点带权的树,每次可以任意访问一个未被访问过的节点,求访问到节点n - 1时的最大权值和,限制条件是当某个节点有两个儿子被访问时,得立即访问该节点。
树形dp,关键是要理清整个过程,恰当表示各种状态。很显然在访问第二个儿子节点前应尽可能多地访问其余节点。仔细观察可以发现,第一个儿子节点及其子树均可被访问,其余的则必须在保证该节点不被访问的前提下最优化其子树。如果用last[v]表示最后访问节点v的最优解,hold[v]表示以v为根的子树在不访问v的前提下的最优解,subTree[v]表示以v为根的子树的权值和
那么状态转移方程
last[v] = max(last[v1] + subTree[v2] + sum{ hold[v other] })
hold[v] = max(last[v1] + sum{ hold[v other] })
trick是有可能是森林。
B Magic Square - by riveria简单题
给定n*n的方阵,判断是否是幻方
C Number Puzzle - by maone简单题
给定一组数,求不大于m并且至少能被其中之一整除的数的个数,类似的题目应该很常见,就是列出所有组合然后用容斥原理计算。
D Left Library Lift - by xuezaiyue 中等题
从一楼出发,掷筛子决定每次移动的步数,到了顶楼或者底楼则改变方向继续前进,直到到达目标楼层为止,求投掷的期望次数。从目标楼层逆序考虑,这样可以将其余的楼层同等对待。除底楼和顶楼外,每个楼层有两个变量,分别表示上行和下行方向到达该楼层的期望值,这样每个楼层及其之前的六个楼层都可以列出一个方程。最后解方程组即可
E Utopia - by liuyaoting 偏难
题目模型很简单,给一棵高达50000节点的树,每次查询给定点C是否在其余两点A、B之间的路径上,最多有500000次查询
观察可以发现:
1、如果点C当且仅当是其中一个节点的祖先时,那么C肯定在路径上
2、如果C是AB两点的共同祖先即CA(Common Ancestor),只要判断C是否为最低公共祖先(LCA)即可。
3、否则不在路径上
对于问题1,只要dfs一遍记录每个节点的入栈时间intime及出栈时间outtime,然后判断其包含关系即可。
对于问题2,注意到某个节点的所有儿子节点从左到右的intime和outtime是递增的,因此可以二分查找这个CA是否有更低的CA,如果有,说明其不是LCA…其实这题也可以直接用RMQ求LCA。
F Find the Sequences - by adai 简单题,偏难?
给定项数n(n <= 10),求出所有形如p^3+q^3(0 <= p, q <= m, m <= 50)的等差数列。m,n非常小,暴力就可以了。
首先列出所有p^3 + q^3这样的数,排序后枚举数列的一二项。
G File Searching - by inspire 简单题
给出一堆文件名,求dir命令所匹配的文件。命令中只有一个*。最后时刻补充的一道简单题目,没过估计大部分是被这组数据卡了
Seateadir
Seat*tea
H Galaxy War - by guanyao 难题
给一个弦图及n种颜色,求着色方案,相邻点的颜色不能相同
参考资料参见
《算法艺术与信息学竞赛》270页
原文链接: https://www.cnblogs.com/pony1993/archive/2012/07/28/2613672.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/57121
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!