题目来源：The 7th Zhejiang University Programming Contests
(ZOJ 2834—2841)
Problem B ZOJ 2835 Magic Square
水题，不解释。
代码：
View Code 
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6 int main()
7 {
8 int n,i,j,s1,s2,flag;
9 int a[11][11],b[1001];
10 while(~scanf("%d",&n))
11 {
12 memset(b,0,sizeof(b));
13 if(!n)
14 break;
15 flag=0;
16 for(i=0;i<n;i++)
17 for(j=0;j<n;j++)
18 {
19 scanf("%d",&a[i][j]);
20 b[a[i][j]]++;
21 if(b[a[i][j]]>1)
22 flag=1;
23 }
24 if(flag)
25 {
26 puts("No");
27 continue;
28 }
29 s1=0;
30 for(i=0;i<n;i++)
31 s1+=a[0][i];
32 for(i=1;i<n;i++)
33 {
34 s2=0;
35 for(j=0;j<n;j++)
36 s2+=a[i][j];
37 if(s2!=s1)
38 {
39 flag=1;
40 break;
41 }
42 }
43 s2=0;
44 if(!flag)
45 {
46 for(i=0;i<n;i++)
47 s2+=a[i][i];
48 if(s2!=s1)
49 flag=1;
50 s2=0;
51 for(i=0;i<n;i++)
52 s2+=a[n-i-1][i];
53 if(s2!=s1)
54 flag=1;
55 }
56 if(flag)
57 puts("No");
58 else
59 puts("Yes");
60 }
61 return 0;
62 }
Problem F ZOJ 2839 Find the Sequences
View Code
2 #include <cstring>
3 #include <cstdio>
4 #include <cstdlib>
5 #include <algorithm>
6 using namespace std;
7 struct point
8 {
9 int x;
10 int y;
11 }p[10001];
12 int hash[500000];
13 int cmp(const void *a,const void *b)
14 {
15 struct point *c=(struct point *)a;
16 struct point *d=(struct point *)b;
17 if(c->y!=d->y)
18 return c->y-d->y;
19 else
20 return c->x-d->x;
21 }
22 int main()
23 {
24 int i,j,k,n,m,t,c,d,l,a1,b1,c1;
25 int a[50000];
26 c=0;
27 while(~scanf("%d%d",&n,&m))
28 {
29 c++;
30 l=t=0;
31 if(n==0&&m==0)
32 break;
33 if(c!=1)
34 puts("");
35 memset(hash,0,sizeof(hash));
36 for(i=0;i<=m;i++)
37 {
38 for(j=0;j<=m;j++)
39 {
40 d=i*i*i+j*j*j;
41 if(!hash[d])
42 {
43 hash[d]=1;
44 a[t++]=d;
45 }
46 }
47 }
48 sort(a,a+t);
49 for(i=0;i<t;i++)
50 {
51 for(j=i+1;j<t;j++)
52 {
53 a1=a[i];
54 b1=a[j]-a[i];
55 for(k=3;k<=n;k++)
56 {
57 c1=a1+(k-1)*b1;
58 if(c1>a[t-1]||!hash[c1])
59 break;
60 }
61 if(k>n)
62 {
63 p[l].x=a1;
64 p[l].y=b1;
65 l++;
66 }
67 }
68 }
69 printf("Case %d:\n",c);
70 if(!l)
71 {
72 puts("NONE");
73 continue;
74 }
75 qsort(p,l,sizeof(p[0]),cmp);
76 for(i=0;i<l;i++)
77 {
78 printf("%d %d\n",p[i].x,p[i].y);
79 }
80 }
81 return 0;
82 }
View Code
2 #include <cstring>
3 #include <iostream>
4 using namespace std;
5 int main()
6 {
7 int n,m,i,j,p,f,k,t,l1,l2,c=1;
8 char s[100][65],s1[65];
9 while(~scanf("%d%*c",&n))
10 {
11 for(i=0;i<n;i++)
12 scanf("%s",s[i]);
13 if(c!=1)
14 puts("");
15 c++;
16 scanf("%d%*c",&m);
17 while(m--)
18 {
19 scanf("%s",s1);
20 l1=strlen(s1);
21 for(i=0;i<l1;i++)
22 {
23 if(s1[i]=='*')
24 {
25 p=i;
26 break;
27 }
28 }
29 t=0;
30 if(!p)
31 {
32 for(i=0;i<n;i++)
33 {
34 l2=strlen(s[i]);
35 if(l2<l1-1)
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)
49 printf(", ");
50 t++;
51 printf("%s",s[i]);
52 }
53 }
54 }
55 else if(p==l1-1)
56 {
57 for(i=0;i<n;i++)
58 {
59 f=0;
60 l2=strlen(s[i]);
61 if(l2<l1-1)
62 continue;
63 for(j=0;j<l1-1;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)
74 printf(", ");
75 t++;
76 printf("%s",s[i]);
77 }
78 }
79 }
80 else
81 {
82 for(i=0;i<n;i++)
83 {
84 l2=strlen(s[i]);
85 if(l2<l1-1)
86 continue;
87 f=0;
88 for(j=0;j<p;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)
110 printf(", ");
111 printf("%s",s[i]);
112 t++;
113 }
114 }
115 }
116 if(!t)
117 printf("FILE NOT FOUND");
118 puts("");
119 }
120 }
121 return 0;
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页