Contest 7.23（不知道算什么）
Problem A URAL 1181
题目大意就是说有一个N边形，让你做N-3条边，让他们的每个三角形的三个顶点颜色都不相同。
这里有一个引理就是如果多边形三个颜色都有，而且两两相邻不同色，那么只要找到相邻的三个顶点，判断两端的两个是否相同，如果不同可以吧中间的点去掉，把两端连接起来，这样形成的新的多边形依然有解，再递归求解。证明过程可以参见我最敬佩的章爷http://blog.****.net/l383137093/article/details/9501019
相邻三点的两种判断情况
还有这些天来做题的一个总结就是，不管有多急，还是得吧代码写得简明一些，好懂一些，有时候自己的都看不懂，以后做题得好好思量一下了
1 #include <stdio.h> 2 #include <string.h> 3 #define mem(a) memset(a,0,sizeof(a)) 4 #define MAXN 1005 5 int Color(char a){return (a == 'R') ? 0 : ((a == 'G')? 1 : 2);}//判断颜色 6 7 struct node{int color,next;} point[MAXN];//用于构建循环链表 8 int N,num[3]; 9 char str[MAXN]; 10 11 int main() 12 { 13 while(~scanf("%d", &N)) 14 { 15 mem(num); mem(str); 16 scanf("%s",str); 17 int i,flag = 0; 18 for(i=0;i<N;i++) 19 { 20 if(str[i]==str[(i+1)%N]){flag = 1;break;}//如果有两个相邻的相等的话（其实题目数据不会有这样的情况） 21 num[Color(str[i])]++;//相应颜色的值加1 22 point[i].color = Color(str[i]); 23 point[i].next = (i<N-1) ? i+1 : 0;//使构成环形链表 24 } 25 if(flag || !num[0] || !num[1] || !num[2])//如果只有两种颜色或则有相邻的相同 26 { 27 printf("0 "); 28 continue; 29 } 30 printf("%d ",N-3); 31 int now = 0;//从第0个开始往后找 32 while(1) 33 { 34 int next1 = point[now].next;//next1是now的下一个点， 35 int next2 = point[next1].next;//next2是后两个点 36 if(num[0] == 1 || num[1] == 1 || num[2] == 1)//如果某一个颜色的点的个数等于1就直接把它与其他相对的顶点链接 37 {//在这里我被坑惨了，以为只需要判断当前点的颜色是不是会是1，结果TLE了N回，桑都必须的判断！！！！！ 38 while(num[point[now].color]!=1)now = point[now].next;//找到某个颜色的顶点个数只为1个点 39 next1 = point[now].next;//下面是将这个点与其他对顶点链接 40 next2 = point[next1].next; 41 while(point[next2].next != now) 42 { 43 printf("%d %d ",now+1, next2+1); 44 next2 = point[next2].next; 45 } 46 break;//全部已经连接完全，结束 47 } 48 if(point[now].color != point[next2].color)//如果某个三角形三个顶点都不相同的话 49 { 50 num[point[next1].color] --;//吧中间的点去掉 51 point[now].next = next2;//当前点的下一个成为后两个的点 52 printf("%d %d ",now+1, next2+1); 53 } 54 now = point[now].next; 55 } 56 } 57 return 0; 58 }
Problem B POJ 1579
题目意思是说有一个地推公式，如果直接递归下去肯定会相当耗时间，问怎么做
其实很简单。既然直接递推会超时，那是因为之间有很多重复的计算，那我们就只需要，记忆化遍历一遍，将每一步的答案都放在一个数组中，输入前便利一遍，那以后就不再需要遍历。直接一次0Ms过
1 #include <stdio.h> 2 3 int d[22][22][22]; 4 int vis[22][22][22]; 5 6 int dfs(int a,int b,int c) 7 { 8 if(vis[a][b][c])return d[a][b][c]; 9 vis[a][b][c] = 1; 10 if(a<=0 || b<=0 || c<=0)return d[a][b][c] = 1; 11 if(a<b && b<c) return d[a][b][c] = dfs(a,b,c-1)+dfs(a,b-1,c-1)-dfs(a,b-1,c); 12 return d[a][b][c] = dfs(a-1, b, c) + dfs(a-1, b-1, c) + dfs(a-1, b, c-1) - dfs(a-1, b-1, c-1); 13 } 14 int main() 15 { 16 dfs(20,20,20); 17 int a,b,c; 18 while(~scanf("%d%d%d",&a,&b,&c)) 19 { 20 if(a==-1 && b==-1 && c==-1)break; 21 printf("w(%d, %d, %d) = ", a, b, c); 22 if(a<=0 || b<=0 || c<=0) 23 { 24 printf("1 "); 25 continue; 26 } 27 if(a>20 || b>20 || c>20)a=b=c=20; 28 printf("%d ",dfs(a,b,c)); 29 } 30 return 0; 31 }