#
2010年02月10日星期三.sgu185
ALGO:dijkstra + 流
求两条没有相同边的最短路。
直觉的想法是求一条，然后把这条相关的删掉，再求另外一条
但是这种想法是不正确的。
引用
http://www.answeror.com/archives/28474 的一组数据来说明这个问题
6 7
1 2 1
1 3 1
2 4 1
3 4 1
3 5 1
4 6 1
5 6 1
如果第一次求出的最短路是1-3-4-6, 那么第二条最短路就不存在了, 但是实际上有两条最短路,
即1-3-5-6和1-2-4-6.
所以需要调整，调整的思想让我们想到了流。
保留图中所有能构成任何一条最短路的边，将所有边的容量设为1. 然后对这个图求两次增广路。
由于容量的限制，所以求得的两条最短路一定是没有公共边的，这时按照流的方向，输出这两条
路径即可。
注意：不要按照增广时的顶点顺序输出最短路，这样是不对的，同样可以使用上面的那组数据，
如果先增广的是 1-3-4-6这条路径的话，那么输出的结果就会不正确了。 我就是这么wa@test 20 好久的。
1
2 const int N = 401;
3 const int inf = 1 << 20;
4 int dis[N],vis[N],n,m;
5 int g1[N][N],g2[N][N],p[N],f[N][N];
6
7 bool dijkstra()
8 {
9 int i,j,k;
10 memset(vis,0,sizeof(vis));
11 dis[1] = 0,vis[1] = true;
12 for (i = 2;i <= n;i++) {
13 dis[i] = g1[1][i];
14 }
15 for (k = 2;k <= n;k++) {
16 int min = inf,idx = 1;
17 for (i = 2;i <= n;i++) {
18 if (dis[i] < min && !vis[i]) {
19 min = dis[i],idx = i;
20 }
21 }
22 if (idx == 1) { break; }
23 vis[idx] = true;
24 for (i = 1;i <= n;i++) {
25 if (dis[i] > min + g1[idx][i]) {
26 dis[i] = min + g1[idx][i];
27 }
28 }
29 }
30 for (i = 1;i <= n;i++) {
31 for (j = 1;j <= n;j++) {
32 if (dis[i] + g1[i][j] == dis[j]) {
33 g2[i][j] = 1;
34 }
35 }
36 }
37 return dis[n] != inf;
38 }
39
40 bool bfs()
41 {
42 memset(vis,0,sizeof(vis));
43 memset(p,0,sizeof(p));
44 queue<int> que;
45 que.push(1),vis[1] = true;
46 while (!que.empty()) {
47 int u = que.front(); que.pop();
48 for (int v = 2;v <= n;v++) {
49 if (!vis[v] && g2[u][v]) {
50 p[v] = u,vis[v] = true;
51 if (v == n) {
52 for (v = n;v != 1;v = p[v]) {
53 u = p[v];
54 g2[u][v] --;
55 g2[v][u] ++;
56 if (f[v][u] > 0) {
57 f[v][u]--;
58 }else {
59 f[u][v] ++;
60 }
61 }
62 return true;
63 }
64 que.push(v);
65 }
66 }
67 }
68 return false;
69 }
70
71 void pr(int u)
72 {
73 if (u == n) {
74 printf("%d\n",u);
75 return;
76 }
77 for (int i = 1;i <= n;i++) {
78 if (f[u][i] > 0) {
79 f[u][i] --;
80 printf("%d ",u);
81 pr(i);
82 return ;
83 }
84 }
85 }
86
87 bool EK()
88 {
89 if (bfs() && bfs()) {
90 pr(1), pr(1);
91 return true;
92 }
93 return false;
94 }
95
96
97 int main()
98 {
99 int i,j,a,b,c;
100 scanf("%d%d",&n,&m);
101 for (i = 1;i <= n;i++) {
102 for (j = 1;j <= n;j++) {
103 g1[i][j] = inf;
104 }
105 }
106 for (i = 0;i < m;i++) {
107 scanf("%d%d%d",&a,&b,&c);
108 if (g1[a][b] > c) {
109 g1[a][b] = g1[b][a] = c;
110 }
111 }
112 if (!dijkstra() || !EK()){
113 printf("No solution\n");
114 }
115 return 0;
116 }
117
2010年02月09日星期二.pku2288
状态压缩动态规划，求一个特殊要求的哈密顿路径，注意使用long long
和判断只有一个节点的情况
推荐一篇讲这个的文章
http://www.cppblog.com/EyeOfProvidence/archive/2010/01/10/105356.html
1
2 #define bin(x) (1 <<(x))
3 const int N = 13;
4 int g[N][N],mask;
5 LL val[N];
6 LL stat[bin(N)][N][N]; //value of the path
7 LL cnt[bin(N)][N][N];
8 int m, n, sum;
9 void post()
10 {
11 memset(g, 0, sizeof(g));
12 memset(stat, 0, sizeof(stat));
13 memset(cnt, 0, sizeof(cnt));
14 sum = 0;
15 }
16
17 int main()
18 {
19 int i, j, k, testcase, a, b, u, v, w;LL fac;
20 scanf("%d", &testcase);
21 while (testcase--) {
22 scanf("%d%d", &n, &m);
23 for (i = 0; i < n; i++) {
24 scanf("%lld", val + i);
25 sum += val[i];
26 }
27 for (i = 0; i < m; i++) {
28 scanf("%d%d", &a, &b),a--,b--;
29 g[a][b] = g[b][a] = 1;
30 }
31 if (n == 1) { //!!
32 printf("%lld 1\n",val[0]);
33 post(); continue;
34 }
35 for (u = 0; u < n; u++) {
36 for (v = 0; v < n; v++) {
37 if (g[u][v]) {
38 cnt[bin(u) | bin(v)][u][v] = 1;
39 stat[bin(u) | bin(v)][u][v] = val[u] * val[v];
40 }
41 }
42 }
43 int mask = bin(n)-1;
44 for (i = 0; i <= mask; i++) {
45 for (u = 0; u < n; u++) {
46 for (v = 0; v < n; v++) {
47 if (cnt[i][u][v]) {
48 for (w = 0; w < n; w++) {
49 if (g[v][w] && !(i & bin(w))) {
50 fac = val[v] * val[w];
51 if (g[u][w]) { fac += val[u] * val[v] * val[w]; }
52 if (stat[i | bin(w)] [v][w] < stat[i][u][v] + fac) {
53 stat[i | bin(w)][v][w] = stat[i][u][v] + fac;
54 cnt[i | bin(w)][v][w] = cnt[i][u][v];
55 } else if (stat [i | bin(w)][v][w] == stat[i][u][v] + fac) {
56 cnt[i | bin(w)][v][w] += cnt[i][u][v];
57 }
58 }
59 }
60 }
61 }
62 }
63 }
64 LL res1 = 0, res2 = 0;
65 for (j = 0; j < n; j++) {
66 for (k = 0; k < n; k++) {
67 if (res1 < stat[mask][j][k]) {
68 res1 = stat[mask][j][k];
69 res2 = cnt[mask][j][k];
70 } else if (res1 == stat[mask][j][k]) {
71 res2 += cnt[mask][j][k];
72 }
73 }
74 }
75 if (res1) { res1 += sum; }
76 cout << res1 <<' ' << res2 / 2 << endl;
77 post();
78 }
79 return 0;
80 }
2010年02月08日星期一.sgu180 归并排序求逆序对
归并排序求逆序对
举例说明：
在归并排序合并两个有序链时
i为第一链的指针，j为第二个的
以下部分需要等宽字体才能正确查看
1 4 5 9↑ 2 4 7 7↑ i++--------- * * *1 4 5 9 ↑ 2 4 7 7↑ j++,res += 3---------1 4 5 9 ↑ 2 4 7 7 ↑ i++--------- * *1 4 5 9 ↑ 2 4 7 7 ↑ j++,res += 2---------1 4 5 9 ↑ 2 4 7 7 ↑ i++--------- *1 4 5 9 ↑ 2 4 7 7 ↑ j++,res += 1--------- *1 4 5 9 ↑ 2 4 7 7 ↑ j++,res += 1---------1 4 5 9 ↑ 2 4 7 7 ↑ ---------之后将两个链中没处理完的添加到buf中
1
2 const int N = 65600;
3 int n,a[N],buf[N];
4 LL res;
5
6 void mergesort(int beg,int end)
7 {
8 if (end <= beg + 1) {
9 if (a[beg] > a[end]) {
10 res ++;
11 swap(a[beg],a[end]);
12 }
13 return;
14 }
15 int mid = (beg + end)/2,i,j,k;
16 mergesort(beg,mid);
17 mergesort(mid+1,end);
18 for (i = beg,j = mid + 1,k = beg;i <= mid && j <= end;) {
19 if (a[i] > a[j]) {
20 res += mid + 1 - i;
21 buf[k++] = a[j++];
22 }else if (a[i] <= a[j]) {
23 buf[k++] = a[i++];
24 }
25 }
26 while (i <= mid) { buf[k++] = a[i++]; }
27 while (j <= end) { buf[k++] = a[j++]; }
28 for (i = beg;i <= end;i++) { a[i] = buf[i]; }
29 }
30
31 int main()
32 {
33 int i,j,k;
34 scanf("%d",&n);
35 for (i = 0;i < n;i++) {
36 scanf("%d",a + i);
37 }
38 mergesort(0,n-1);
39 cout << res << endl;
40 //printf("%d\n",res);
41 return 0;
42 }
2010年02月08日星期一.sgu160 pku2206
本人WA@ test case 8了几次，最后才发现原来输出要按照序号的升序。。。
仔细读题。。。
dp,可一维，可二维。一维的更好想，更好写，更快
其实如果没有取模的运算，完全就是一个背包的变形问题。
看下例：一个数x，乘以y取模之后可以比x大也可能比x小
......x......
....x.....x..
所以，不论是按照x升序扫描,还是降序扫描都有可能取到当前数产生的状态。
如果写二维dp就没有这个问题了。如果要写成一维dp可以记录一下这个状态是第几个数
产生的，状态转移的时候只处理由当前数之前的数生成的状态。
1
2 const int M = 1024;
3 int idx[M];
4 int pre[M];
5 int lev[M];
6 int out[M],top = 0;
7 int m,n;
8 int main()
9 {
10 int i,j,k;
11 scanf("%d%d",&n,&m);
12 pre[1] = 1;
13 lev[1] = 1;
14 for (i = 1;i <= n;i++) {
15 scanf("%d",&k);
16 for (j = 1;j <= m;j++) {
17 if (pre[j] && lev[j] <= i) {
18 int t = (j * k) % m;
19 if (!pre[t]) {
20 lev[t] = i + 1;
21 pre[t] = j;
22 idx[t] = i;
23 }
24 }
25 }
26 }
27 for (i = m - 1;i >= 1;i--) {
28 if (pre[i]) {
29 printf("%d\n",i);
30 break;
31 }
32 }
33 while (i != 1) {
34 out[top++] = idx[i];
35 i = pre[i];
36 }
37 sort(out,out + top);
38 for (i = 0;i < top;i++) {
39 printf("%d ",out[i]);
40 }
41 printf("\n");
42 return 0;
43 }
44
2010年02月08日星期一.sgu159 && pku2205 dfs
/*
* SOUR:sgu159 && pku2205
* ALGO:dfs... ...
* DATE: 2010年 02月 07日 星期日 23:16:59 CST
* COMM:4 dfs
* 如果P[n]是符合条件的那么必须有P[n-1]是符合条件的。所以可以从0位开始按位在数的前段
* 添加数，而在搜索的过程中由于P[n-1]是符合条件的所以只需要判断最高位是否符合条件即可。
* 不好想啊，我想到了这个符合条件，但是却还是没想到还能这么搜
* */
本题我的思路就是按位扩展+高精，以下精妙算法完全来自
http://162.105.81.212/JudgeOnline/showmessage?message_id=93126
1
2 const int N = 2048;
3 int n,bas,top;
4 int g[N][N];
5 int a[N];
6
7 void dfs(int idx,int sum)
8 {
9 if (idx == n) {
10 if (a[idx-1] || n == 1) {
11 for (int i = 0;i < n;i++) {
12 g[top][i] = a[i];
13 }
14 top++;
15 }
16 return ;
17 }
18 for (int i = 0;i < bas;i++) {
19 a[idx] = i;
20 int tmp = 0;
21 for (int j = 0;j <= idx;j++) {
22 tmp += a[j] * a[idx-j];
23 }
24 if ((sum + tmp) % bas == i) {
25 dfs(idx + 1,(sum + tmp) / bas);
26 }
27 }
28 }
29
30 int main()
31 {
32 int i,j,k;
33 scanf("%d%d",&bas,&n);
34 dfs(0,0);
35 printf("%d\n",top);
36 for (i = 0;i < top;i++) {
37 for (j = n - 1;j >= 0;j--) {
38 if (g[i][j] >= 10) {
39 printf("%c",g[i][j] - 10 + 'A');
40 }else {
41 printf("%d",g[i][j]);
42 }
43 }
44 printf("\n");
45 }
46 return 0;
47 }
48
2010年02月07日星期日.sgu172 判断一个图是否是二分图 黑白染色
题意解释：给出一个图的边，对这个图进行黑白染色，不能染色则输出no
能染色输出黑色或者白色的个数，并且输出点的序号
1
2 const int N = 256;
3 int g[N][N],n,m,vis[N];
4 const int black = 1;
5 const int white = 2;
6 int res ;
7
8 bool dfs(int u,int color)
9 {
10 vis[u] = color;
11 if (color == black) { res++; }
12 if (color == black) { color = white; }
13 else { color = black; }
14
15 int i;
16 for (i = 1;i <= n;i++) {
17 if (g[u][i]) {
18 if (vis[i] == 0) {
19 if(!dfs(i,color)) return false;
20 }else if (vis[i] != 0 && vis[i] != color) {
21 return false;
22 }
23 }
24 }
25 return true;
26 }
27
28 bool dyeing()
29 //染色
30 {
31 for (int i = 1;i <= n;i++) {
32 if (vis[i] == 0) {
33 if(!dfs(i,black)) {
34 return false;
35 }
36 }
37 }
38 return true;
39 }
40
41 int main()
42 {
43 int i,j,k,a,b;
44 scanf("%d %d",&n,&m);
45 for (i = 0;i < m;i++) {
46 scanf("%d%d",&a,&b);
47 g[a][b] = g[b][a] = 1;
48 }
49 if (!dyeing()) {
50 printf("no\n");
51 }else {
52 printf("yes\n");
53 printf("%d\n",res);
54 for (i = 1;i <= n;i++) {
55 if (vis[i] == black) {
56 printf("%d ",i);
57 }
58 }
59 printf("\n");
60 }
61 return 0;
62 }
63
把浮点行转换成整数计算，避免精度的损失。
double l;
LL len;
int n;
int main()
{
int i;
LL sum = 0,a,b;
scanf("%lf %d",&l,&n);
len = l * 10000 + 0.5;
for (i = 0;i < n;i++) {
cin >> a >> b;
sum = (LL)(sum + (a * 10000 * b)%len) % len;
}
LL candidate = len - sum;
LL res = min(sum,candidate);
cout << res / 10000 << '.';
printf("%04I64d\n",res % 10000);
//printf("%04lld\n",res % 10000);
return 0;
}
2010年02月07日星期日.sgu190
sgu190:
一开始想到的竟然是状态压缩dp，然后一看n，貌似大了点。
然后怎么想也没思路，上网看看,才知道原来二分图还可以这么用，我怎么从来也没想到呢。。。。
将图像国际象棋棋盘那样黑白染色，然后给对于每个颜色给每个格子一个编号。
然后选一个染色，对每个格子和他旁边的格子建边，这样构成一个二分图。
求出最大的匹配数，然后再按照题目的猥琐要求输出即可。
注意 题目中棋盘的格式是这个样子的。
(2,1) (2,2)
(1,1) (1,2)
左下角是(1,1)
如果按照平常的左上角是(1,1)来搞，需要注意一下输出
1
2 int g[801][801],n,P;
3 const int BLACK = 1;
4 const int WHITE = 2;
5 const int REMOVED = 3;
6 int num[41][41],bsp,wsp,cnt;
7 int board[41][41];
8 int bcoord[41*41][2];
9 int wcoord[41*41][2];
10 int vis[801];
11 int L[801],R[801];
12
13 bool make_graph()
14 {
15 int i,j;cnt = 0;
16 for (i = 1;i <= n;i++) {
17 for (j = 1;j <= n;j++) {
18 if (board[i][j] != REMOVED) {
19 cnt ++;
20 if ((i+j)%2==1) {
21 board[i][j] = WHITE;
22 wcoord[wsp][0] = i, wcoord[wsp][1] = j;
23 num[i][j] = wsp++;
24 }else {
25 board[i][j] = BLACK;
26 bcoord[bsp][0] = i, bcoord[bsp][1] = j;
27 num[i][j] = bsp++;
28 }
29 }
30 }
31 }
32 for (i = 1;i <= n;i++) {
33 for (j = 1;j <= n;j++) {
34 if (board[i][j] == BLACK) {
35 if (board[i+1][j] == WHITE) g[num[i][j]][num[i+1][j]] = 1;
36 if (board[i][j+1] == WHITE) g[num[i][j]][num[i][j+1]] = 1;
37 if (board[i-1][j] == WHITE) g[num[i][j]][num[i-1][j]] = 1;
38 if (board[i][j-1] == WHITE) g[num[i][j]][num[i][j-1]] = 1;
39 }
40 }
41 }
42 return true;
43 }
44
45 bool dfs(int u) {
46 for (int v = 0;v < wsp;v++) {
47 if (g[u][v] && !vis[v]) {
48 vis[v] = true;
49 if (R[v] == -1 || dfs(R[v])) {
50 L[u] = v;
51 R[v] = u;
52 return true;
53 }
54 }
55 }
56 return false;
57 }
58
59 int MaxMatch()
60 {
61 int i,res = 0;
62 memset(L,-1,sizeof(L));
63 memset(R,-1,sizeof(R));
64
65 for (i = 0;i < bsp;i++) {
66 if (L[i] == -1) {
67 memset(vis,0,sizeof(vis));
68 if (dfs(i)) {
69 res++;
70 }
71 }
72 }
73 return res;
74 }
75
76 int out[801][2],top;
77 bool proc()
78 {
79 make_graph(); if (cnt & 1) { return false; }
80 if (bsp == 0 || wsp == 0) { return false; }
81 if (bsp != wsp) { return false; }
82 return (MaxMatch() * 2 == cnt);
83 }
84
85 int main()
86 {
87 int i,j,k,a,b;
88 scanf("%d%d",&n,&P);
89 for (i = 0;i < P;i++) {
90 scanf("%d%d",&a,&b);
91 board[a][b] = REMOVED;
92 }
93 if (proc()) {
94 printf("Yes\n");
95 top = 0;
96 for (i = 0;i < bsp;i++) {
97 if (bcoord[i][1] == wcoord[L[i]][1]) {
98 if (bcoord[i][0] < wcoord[L[i]][0]) {
99 out[top][0] = bcoord[i][0];
100 out[top][1] = bcoord[i][1];
101 top++;
102 }else {
103 out[top][0] = wcoord[L[i]][0];
104 out[top][1] = wcoord[L[i]][1];
105 top++;
106 }
107 }
108 }
109
110 printf("%d\n",top);
111 for (i = 0;i < top;i++) { printf("%d %d\n",out[i][0],out[i][1]); }
112
113 top = 0;
114 for (i = 0;i < bsp;i++) {
115 if (bcoord[i][0] == wcoord[L[i]][0]) {
116 if (bcoord[i][1] < wcoord[L[i]][1]) {
117 out[top][0] = bcoord[i][0];
118 out[top][1] = bcoord[i][1];
119 top++;
120 }else {
121 out[top][0] = wcoord[L[i]][0];
122 out[top][1] = wcoord[L[i]][1];
123 top++;
124 }
125 }
126 }//http://www.cppblog.com/schindlerlee
127 printf("%d\n",top);
128 for (i = 0;i < top;i++) { printf("%d %d\n",out[i][0],out[i][1]); }
129 }else {
130 printf("No\n");
131 }
132
133
134 return 0;
135 }
136
137
2010-02-07.sgu502状态压缩dp <推荐题目>
sgu502:状态压缩dp
首先要知道这样一个事实
如果有5个数，要填充到如下x的位置上
*xx*x*x**x
那么只要这5个数产生的部分模的结果:
(x + x * 10^3 + x * 10^5 + x * 10^7 + x * 10^8) % 17
的结果相同，那么这5个数能产生这个相同结果的所有排列都是等价的。
这和使用状态压缩进行优化的哈密顿路径的搜索方法是一样的(想要详细的了解这个问题可以参考
MasterLuo的文章，我觉的写的很好， http://www.cppblog.com/EyeOfProvidence/archive/2010/01/10/105356.html
pku2288就是关于这个问题的一个应用)
如下的dfs中，
stat表示所有可用位的使用状态
mod表示前step个数产生的部分模。
step表示为第step个数。
对于刚才说的事实，如果前step个数填充的状态是相同的，那么所有模相等的状态就可以合并
也就是将前step个数的占用同样的step个位能产生的 P(step,step)个状态，减少到17个
1
2 #define bin(x) (1 << (x))
3 const int N = 20;
4 char s[N];
5 int num[N],len,out[N],ten[N],val[N];
6 bool vis[bin(19)][19];
7
8 bool dfs(int stat,int mod,int step)
9 {
10 if (vis[stat][mod]) { return false; }
11 vis[stat][mod] = true;
12
13 if (step == len) { return mod == 0; }
14 for (int i = 0;i < len; i++) {
15 if (stat & bin(i)) { continue; }
16 if (num[step] == 0 && i == len-1) { continue; } //第一位不能为0
17 out[i] = num[step];
18 if (dfs(stat | bin(i),(mod + num[step] * val[i])%17,step + 1)) {
19 return true;
20 }
21 }
22 return false;
23 }
24 //http://www.cppblog.com/schindlerlee
25 int main()
26 {
27 int i,j,k;
28 scanf("%s",s);
29 len = strlen(s);
30 val[0] = 1;
31 for (i = 1;i < len;i++) { val[i] = (val[i-1] * 10) % 17; }
32 for (i = 0;i < len;i++) { num[i] = s[i] - '0'; }
33 if(dfs(0,0,0)) {
34 for (i = len - 1;i >= 0;i--) {
35 printf("%d",out[i]);
36 }
37 printf("\n");
38 }else {
39 printf("-1\n");
40 }
41
42 return 0;
43 }
2010-02-06.sgu193
sgu193:就是求与n互质且不大于 ⌊
n/2 ⌋ 的一个数。
按照n的奇偶分别讨论，用上大数除2和减法
const int N = 2047;
int s[N];
int r[N], sl;
int main()
{
int i, j, k;
char t;
t = getchar();
while (t != 10) {
if (t >= '0' && t <= '9') {
s[sl++] = t - '0';
}
t = getchar();
}
int fac = 0;
for (i = 0; i < sl; i++) {
fac = fac * 10 + s[i];
if (fac >= 2) {
r[i] = fac / 2;
fac %= 2;
}
}
int beg = 0;
while (r[beg] == 0) { beg++; }
if (s[sl - 1] % 2 == 0) { //even
int flag = r[sl - 1] % 2 == 1;
for (i = sl - 1; i >= beg; i--) {
if (r[i] > 0) {
r[i]--;
break;
} else {
r[i] = 9;
}
}
if (flag) { //⌊n/2⌋ - 1
for (i = sl - 1; i >= beg; i--) {
if (r[i] > 0) {
r[i]--;
break;
} else {
r[i] = 9;
}
}
}
}
while (r[beg] == 0) { beg++; }
for (i = beg;i < sl;i++) {
printf("%d",r[i]);
}
printf("\n");
return 0;
}
2010-02-06.sgu196 找规律。。。
找规律。。。
1
2 const int N = 10001;
3 const int M = 100001;
4
5 int deg[N],n,m;
6 int seg[M][2];
7
8 int main()
9 {
10 int i,j,k,a,b;
11 scanf("%d%d",&n,&m);
12 for (i = 1;i <= m;i++) {
13 scanf("%d%d",&seg[i][0],&seg[i][1]);
14 deg[seg[i][0]]++, deg[seg[i][1]]++;
15 }
16 int res = 0;
17 for (i = 1;i <= m;i++) {
18 res += deg[seg[i][0]] + deg[seg[i][1]];
19 }
20 printf("%d\n",res);
21
22 return 0;
23 }
24
2010年02月05日.sgu153 经典博弈问题 substration game
sgu153:这个问题是经典的博弈论教程<<GAME THEORY>> Thomas S. Ferguson，
1.4 Subtraction Games 中有详细介绍，就是状态的逆推。
此书在
http://www.math.ucla.edu/~tom/Game_Theory/Contents.html
上有下载，是作者写的免费电子书。
本题的关键就是找出循环节，然后将n %= len;
进而求出最终的状态。
下面代码很挫，基本属于暴力。
1
2 const int N = 1024;
3 int stat[N];
4 int p[N],m,n;
5
6 bool find(int x)
7 {
8 int i;
9 for (i = 0;i <= m;i++) {
10 if (x - p[i] >= 0 && stat[x-p[i]] == 0) {
11 return true;
12 }
13 }
14 return false;
15 }
16
17 bool repeat(int mod,int offset,int depth)
18 {
19 if (depth == 0) {
20 return true;
21 }
22 int i;
23 for (i = 0;i < mod;i++) {
24 if (stat[i+offset] != stat[i+mod+offset]) {
25 return false;
26 }
27 }
28 return repeat(mod,offset + mod,depth-1);
29 }
30
31 int main()
32 {
33 int i,j,k,testcase,mod = 2;
34 stat[0] = 1, stat[1] = 0, p[0] = 1;
35 scanf("%d",&testcase);
36 while (testcase--) {
37 scanf("%d%d",&n,&m);
38 for (i = 1;i <= m;i++) { scanf("%d",p + i); }
39
40 sort(p,p+m+1);
41 for (i = 2;i <= 1024;i++) {
42 if (find(i)) {
43 stat[i] = 1;
44 }
45 }
46
47 for (i = 2;i <= 20;i++) {
48 if (repeat(i,0,10)) {
49 mod = i;
50 }
51 }
52
53 if (stat[n % mod]) {
54 puts("FIRST PLAYER MUST WIN");
55 }else {
56 puts("SECOND PLAYER MUST WIN");
57 }
58 }
59 return 0;
60 }
61
2010-02-04.ural1063-pku1756
ALGO:graph theory and IDFS
题目中给给出了m(1 ≤ m ≤ 100)条无向边，点是1-6，意思就是在这6个点上添加一些边组成欧拉回路，
并且要求点的和最小
欧拉路存在的条件:奇度数顶点的个数为0或2且图是连通的。
我一开始的想法是：
最多只有6个点，完全图的边的数量不过5+4+3+2+1=15条，我就想枚举这些边的组合。
一共 2^15 种可能才 32 × 1024种可能。看了样例才发现可以添加重边。。。
然后就只能搜了，怎么搜呢，迭代加深搜最好，但是要注意，有可能多添一条边，但是花费却变少了。
然后就是最坏的情况也只能添加5条边
6
1 1
2 2
3 3
4 4
5 5
6 6
然后就是写代码了，题目还是比较不好写正确的
1756 Domino Puzzle 42
pku只有42人过了。。
1
2 const int N = 8;
3 const int M = 512;
4 int edge[M][2],m,top;
5 int vis[N],g[N][N],deg[N];
6 int st[N],n; //the node exists in graph
7 int exist[N],res;
8 int save[M][2],sp;
9 //http://www.cppblog.com/schindlerlee/
10 void dfs2(int u)
11 {
12 vis[u] = 1;
13 for (int i = 1;i <= 6;i++) {
14 if (g[u][i] && !vis[i]) {
15 dfs2(i);
16 }
17 }
18 }
19
20 bool connected()
21 {
22 memset(vis,0,sizeof(vis));
23 dfs2(st[0]);
24 for (int i = 0;i < n;i++) {
25 if (!vis[st[i]]) {
26 return false;
27 }
28 }
29 return true;
30 }
31
32 int goaldepth;
33 bool dfs(int depth,int curres,int begi,int begj)
34 //加上begi和begj能从980ms -> 16ms
35 {
36 int i,j;
37 if (depth == goaldepth) {
38 int cnt = 0;
39 for (i = 1;i <= 6;i++) {
40 if (deg[i] & 1) {
41 cnt++;
42 }
43 }
44 if (curres < res && (cnt == 0 || cnt == 2) && connected()) {
45 res = curres;
46 sp = top - m;
47 for (i = 0;i < sp;i++) {
48 save[i][0] = edge[i+m][0];
49 save[i][1] = edge[i+m][1];
50 }
51 return true;
52 }
53 return false;
54 }
55 for (i = begi;i < n;i++) {
56 for (j = begj;j < n;j++) {
57 if (i != j) {
58 int a = st[i],b = st[j];
59 if (curres + a + b >= res) { continue; }
60 g[a][b]++;
61 g[b][a]++;
62 deg[a]++;
63 deg[b]++;
64 edge[top][0]=a, edge[top][1]=b,top++;
65 dfs(depth+1,curres + a + b,i,j);
66 top--;
67 g[a][b]--;
68 g[b][a]--;
69 deg[a]--;
70 deg[b]--;
71 }
72 }
73 }
74 }
75
76 int main()
77 {
78 int i,j,k;
79 scanf("%d",&m);
80 for (i = 0;i < m;i++) {
81 int a,b;
82 scanf("%d%d",&a,&b);
83 edge[i][0] = a;
84 edge[i][1] = b;
85 exist[a] = 1;
86 exist[b] = 1;
87 g[a][b] ++;
88 g[b][a] ++;
89 deg[a]++;
90 deg[b]++;
91 }
92 for (i = 1;i <= 6;i++) {
93 if (exist[i]) {
94 st[n++] = i;
95 }
96 }
97
98 res = maxint;
99 for (i = 0;i <= 5;i++) {
100 top = m;
101 goaldepth = i;
102 dfs(0,0,0,0);
103 }
104
105 printf("%d\n",res);
106 printf("%d\n",sp);
107 for (i = 0;i < sp;i++) {
108 printf("%d %d\n",save[i][0],save[i][1]);
109 }
110
111 return 0;
112 }
113
2010-02-03.ural1065-pku1758
这个题还是比较有意思的。
题目是要求在一个凸多边形中选几个点，要保证新组成的多边形包含m个景观点
题目中给出的凸多边形是按照顺时针顺序给出的，我们可以按照顺序找到合法的点的连接方法，然后转换成图论模型。
首先将题目中给出的点拷贝一份
p[0...n-1] 存的是原始的顺时针顺序给出的点
p[n...2n-1]是对上边的拷贝
然后
for (i = 0;i < n;i++) {
for (j = 1;j < n;j++) {
判断由p[i...i+j]组成的多变形是否包含景点。
其实也就是线段<p[i],p[j]> 是否有景点在左侧。
}
}
建图之后，由于点最多只有50个，完全可以用floyd求出所有点之间的最短距离，然后再枚举三角形
求出一个最短距离即可。
注意不能直接用floyd求出来的值dis[i][i]来找最短距离，因为会产生面积等于零的情况。
1
2 /*
3 * SOUR:ural1065 pku1758
4 * ALGO:computational and graph theory
5 * DATE:2010年 02月 01日 星期一 15:38:51 CST
6 * COMM:5//http://www.cppblog.com/schindlerlee/
7 * */
8 #include<iostream>
9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<algorithm>
13 #include<cmath>
14 using namespace std;
15 typedef long long LL;
16 const int maxint = 0x7fffffff;
17 const long long max64 = 0x7fffffffffffffffll;
18 /*#define fprintf(x
) while(0)*/
19 const int N = 128;
20 const int M = 2048;
21 int n,m, g[N][N];
22 struct point_t{
23 int x,y;
24 point_t(){}
25 point_t(int a,int b){x = a,y = b;}
26 }p[N],monu[M];
27 double dis[N][N];
28 point_t operator + (point_t a,point_t b) { return point_t(a.x + b.x,a.y + b.y);}
29 point_t operator - (point_t a,point_t b) { return point_t(a.x - b.x,a.y - b.y);}
30 int cross_mul(point_t a,point_t b) { return a.x * b.y - a.y * b.x;}
31 int dot_mul(point_t a,point_t b) { return a.x * b.x + a.y * b.y;}
32
33 bool judge(int beg,int end)
34 {
35 int i,j;
36 for (i = 0;i < m;i++) {
37 if (cross_mul(p[end]-p[beg],monu[i]-p[beg]) >= 0) {
38 return false;
39 }
40 }
41 return true;
42 }
43
44 void ckmin(double &a,double b) { if (a > b) { a = b; } }
45 #define sqr(x) ((x)*(x))
46 double dist(const point_t &a,const point_t &b) { return sqrt(0.0 + sqr(a.x-b.x) + sqr(a.y-b.y)); }
47
48 int main()
49 {
50 int i,j,k;
51 scanf("%d%d",&n,&m);
52 for (i = 0;i < n;i++) { scanf("%d %d",&p[i].x,&p[i].y); p[i+n] = p[i]; }
53 for (i = 0;i < m;i++) { scanf("%d %d",&monu[i].x,&monu[i].y); }
54 for (i = 0;i < n;i++) {
55 for (j = 1;j < n;j++) {
56 if (judge(i,i+j)) {
57 g[i][(i+j)%n] = 1;
58 }
59 }
60 }
61
62 for (i = 0;i < n;i++) {
63 for (j = 0;j < n;j++) {
64 if (g[i][j]) {
65 dis[i][j] = dist(p[i],p[j]);
66 }else if(i == j){
67 dis[i][j] = 0;
68 }else {
69 dis[i][j] = maxint;
70 }
71 }
72 }
73
74 //floyd
75 for (k = 0;k < n;k++) {
76 for (i = 0;i < n;i++) {
77 for (j = 0;j < n;j++) {
78 ckmin(dis[i][j],dis[i][k]+dis[k][j]);
79 }
80 }
81 }
82
83 //这么写完全是为了保证面积不为0
84 double res = maxint;
85 for (k = 0;k < n;k++) {
86 for (i = 0;i < n;i++) {
87 for (j = 0;j < n;j++) {
88 if (res > dis[i][j] + dis[j][k] + dis[k][i] && cross_mul(p[i]-p[k],p[j]-p[k]) != 0) {
89 res = dis[i][j] + dis[j][k] + dis[k][i];
90 }
91 }
92 }
93 }
94
95 printf("%.2f\n",res);
96 return 0;
97 }
98
2010-02-01.ural1064-pku1757
这个题。。。。
把题目中给的代码拷下来，给一个数组赋值，然后调用这个函数计算合法的所有值。
之后按照题目要求输出即可。
1
2 #define MAXN 10000
3 int A[MAXN];
4 int N,K,x;
5 int BinarySearch(int x)
6 {
7 int p, q, i, L;
8
9 p = 0; /* Left border of the search */
10 q = N-1; /* Right border of the search */
11 L = 0; /* Comparison counter */
12 while (p <= q) {
13 i = (p + q) / 2;
14 ++L;
15 if (A[i] == x) {
16 return L;
17 }
18 if (x < A[i])
19 q = i - 1;
20 else
21 p = i + 1;
22 }
23 return 0;
24 }
25
26 int vis[MAXN+10];
27 int main()
28 {
29 int i,j;
30 scanf("%d%d",&x,&K);
31 for (i = 0;i <= MAXN;i++) { A[i] = i; }
32 for (i = 1;i <= MAXN;i++) {
33 N = i;
34 if (K == BinarySearch(x)) {
35 //printf("%d accepted\n",i);
36 vis[i] = true;
37 }
38 }
39 int res = 0;
40 for (i = 1;i <= MAXN;i++) {
41 if (vis[i-1] == 0 && vis[i] == 1) { res++; }
42 }
43 printf("%d\n",res);
44 for (i = 1;i <= MAXN;i++) {
45 if (vis[i-1] == 0 && vis[i] == 1) { printf("%d ",i); }
46 if (vis[i] == 1 && vis[i+1] == 0) { printf("%d\n",i); }
47 }
48 return 0;
49 }
50