Problem A URAL 1181
题目大意就是说有一个N边形，让你做N-3条边，让他们的每个三角形的三个顶点颜色都不相同。
这里有一个引理就是如果多边形三个颜色都有，而且两两相邻不同色，那么只要找到相邻的三个顶点，判断两端的两个是否相同，如果不同可以吧中间的点去掉，把两端连接起来，这样形成的新的多边形依然有解，再递归求解。证明过程可以参见我最敬佩的章爷http://blog.csdn.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 }
Problem C POJ 1845
当时第一眼看到这道题，就想着是不是有公式可以推导，于是花了半个多小时去计算。最后突然发现。。。。
一个数可以写为他的素数的幂的乘积，即若N = P1K1 * P2k2 * …… pnkn，那这样的话我们可以把它的所有因子拆分，写为
最高次 拆分情况
0 1
1 p1 + p2 + p3 + ...... +pn
2 p1^2 + p2^2 + ...... +pn^2 + p1p2 + p1p3 + ...... +pn-1pn
3 p1^3 + ... ...
......
k1+k2+...+kn p1^k1 p2^k2......pn^kn
由于上面的式子包含了 P1K1 * P2k2 * …… pnkn的所有任意k个之间的所有组合，所以不难得出上面所有因子的和就是
(1 + p1 + p1^2 + p1^3 +...... + p1^k1) * (1 + p2 + p2^2 + p2^3 + ...... + p2^k2) * ......
于是原题就变成了求n个上面蓝色和式子的乘积，而由于ki可能会很大，所以需要两次二分才能求出这个和（正好之前看到过^.^）
例：1+p^1+p^2+p^3+p^4+p^5 = (1+p^1+p^2)*(1+p^3)
这样的话计算量由原来的n=6减少到了n/2+1=4次，而后面红色部分又可以递归求出
所以复杂度就降到了O(n*log(n)*log(k))n是素因子的个数，k是最高的幂
只是可惜比赛时候没有搞出来=。=！！。。。。。。。。真是纠结。。。
代码：
1 #include <stdio.h> 2 #include <string.h> 3 #define mem(a) memset(a, 0, sizeof(a)) 4 __int64 mod = 9901; 5 __int64 a[10005],p[10005],c[10005]; 6 __int64 A,B,num; 7 8 __int64 pow_mod(__int64 m,__int64 n)//快速幂 9 { 10 if(n == 0)return 1%mod; 11 if(n == 1)return m%mod; 12 __int64 ans = pow_mod(m, n/2); 13 ans *= ans; 14 if(n%2 == 1)ans *= m; 15 return ans % mod; 16 } 17 18 void find_prime()//打印素数表 19 { 20 __int64 i,j; 21 num=0; 22 mem(a); mem(p); 23 for(i=2;i<=10000;i++) 24 { 25 if(!a[i])p[num++] = i; 26 for(j=2;i*j<=10000;j++) 27 { 28 a[i*j]=1; 29 } 30 } 31 } 32 33 __int64 add(__int64 p,__int64 k)//计算p+p^2+...+p^k 34 { 35 if(k == 0)return 1; 36 if(k%2){ 37 return (1+ pow_mod(p,k/2+1))*(add(p,k/2))%mod; 38 } 39 return ((1+ pow_mod(p,k/2+1))*(add(p, k/2-1))+pow_mod(p,k/2))%mod; 40 } 41 42 int count_C()//用于统计每个速因子的最高次数,返回素因子的个数 43 { 44 int i,countt = 0; 45 for(i=0;i<num && A >= p[i];i++) 46 { 47 if(A%p[i] == 0) 48 { 49 __int64 key =0; 50 while(A%p[i] == 0) 51 { 52 key++; 53 A/=p[i]; 54 } 55 a[countt]=p[i]; 56 c[countt]=B*key; 57 countt ++; 58 } 59 } 60 if(A!=1){a[countt] = A;c[countt++]=B;} 61 return countt; 62 } 63 64 int main() 65 { 66 find_prime(); 67 while(~scanf("%I64d%I64d", &A, &B)) 68 { 69 if(A <= 1 || B == 0){printf("1 ");continue;} 70 int i; 71 int num_prime = count_C(); 72 __int64 ans = 1; 73 for(i=0;i<num_prime;i++) 74 { 75 ans = (ans * add(a[i],c[i]))%mod; 76 } 77 printf("%I64d ", ans); 78 } 79 return 0; 80 }
Problem E POJ 3922
博弈
由于之前对博弈是完全没有概念，所以比赛时候自然也就是不可能AC的了。之后看了一点点有关博弈的思想，发现那完全不是我等人能够理解的透的，所以立马在网上寻找结题报告，经过了良久，才对这个题有了一点点认识，可以参见博客http://blog.csdn.net/acm_cxlove/article/details/7836544
于是随着这个思路写了一段代码（其实和题解的代码几乎已经是相差无几了），暂且挂在这里，慢慢捉摸
1 #include <stdio.h> 2 3 int a[2000000],b[2000000]; 4 int main() 5 { 6 int n,k; 7 int T = 0,Case = 1; 8 while(~scanf("%d",&T))while(T--) 9 { 10 scanf("%d%d",&n,&k); 11 a[0] = b[0] = 1; 12 int i=0,j=0; 13 while(n > a[i]) 14 { 15 i++; 16 a[i] = b[i-1] + 1; 17 while(a[j+1] * k < a[i]) 18 { 19 j++; 20 } 21 if(k * a[j] < a[i]) 22 { 23 b[i] = b[j] + a[i]; 24 } 25 else b[i] = a[i]; 26 } 27 printf("Case %d: ",Case++); 28 if(n == a[i])printf("lose "); 29 else 30 { 31 int ans ; 32 while(n) 33 { 34 if(n >= a[i]) 35 { 36 n -= a[i]; 37 ans = a[i]; 38 } 39 i --; 40 } 41 printf("%d ",ans); 42 } 43 } 44 return 0; 45 }
终于是把结题报告写出来了 看我的另一篇随笔 http://www.cnblogs.com/gj-Acit/p/3219280.html
Problem G HDU 4608
暴力枚举
1 #include <stdio.h> 2 #include <string.h> 3 char str[100005]; 4 5 int calc() 6 { 7 int len = strlen(str); 8 int i,ans = 0; 9 for(i=0;i<len;i++) 10 { 11 ans+=(str[i] - '0'); 12 } 13 return ans; 14 } 15 16 void add() 17 { 18 int i,ans = 1; 19 for(i=0;str[i];i++) 20 { 21 str[i]-='0'; 22 int a=str[i]+ans; 23 ans=a/10; 24 str[i]=a%10; 25 str[i]+='0'; 26 } 27 if(ans)str[i]='1'; 28 } 29 30 int main() 31 { 32 int T; 33 while(~scanf("%d", &T))while(T--) 34 { 35 memset(str,0,sizeof(str)); 36 scanf("%s",str); 37 strrev(str); 38 add(); 39 int a = calc(); 40 while(a%10) 41 { 42 add(); 43 a=calc(); 44 } 45 strrev(str); 46 printf("%s ",str); 47 } 48 return 0; 49 }