Contest 7.23（不知道算什么）

Problem A   URAL 1181

Cutting a Painted Polygon

题目大意就是说有一个N边形，让你做N-3条边，让他们的每个三角形的三个顶点颜色都不相同。

这里有一个引理就是如果多边形三个颜色都有，而且两两相邻不同色，那么只要找到相邻的三个顶点，判断两端的两个是否相同，如果不同可以吧中间的点去掉，把两端连接起来，这样形成的新的多边形依然有解，再递归求解。证明过程可以参见我最敬佩的章爷http://blog.csdn.net/l383137093/article/details/9501019

相邻三点的两种判断情况

还有这些天来做题的一个总结就是，不管有多急，还是得吧代码写得简明一些，好懂一些，有时候自己的都看不懂，以后做题得好好思量一下了

 #include <stdio.h>
 #include <string.h>
 #define mem(a) memset(a,0,sizeof(a))
 #define MAXN 1005
 int Color(char a){return  (a == 'R') ?  : ((a == 'G')?  : );}//判断颜色

 struct node{int color,next;} point[MAXN];//用于构建循环链表
 int N,num[];
 char str[MAXN];

 int main()
 {
     while(~scanf("%d", &N))
     {
         mem(num); mem(str);
         scanf("%s",str);
         int i,flag = ;
         for(i=;i<N;i++)
         {
             if(str[i]==str[(i+)%N]){flag = ;break;}//如果有两个相邻的相等的话（其实题目数据不会有这样的情况）
             num[Color(str[i])]++;//相应颜色的值加1
             point[i].color = Color(str[i]);
             point[i].next = (i<N-) ? i+ : ;//使构成环形链表
         }
         if(flag || !num[] || !num[] || !num[])//如果只有两种颜色或则有相邻的相同
         {
             printf("0\n");
             continue;
         }
         printf("%d\n",N-);
         int now = ;//从第0个开始往后找
         while()
         {
             int next1 = point[now].next;//next1是now的下一个点，
             int next2 = point[next1].next;//next2是后两个点
             if(num[] ==  || num[] ==  || num[] == )//如果某一个颜色的点的个数等于1就直接把它与其他相对的顶点链接
             {//在这里我被坑惨了，以为只需要判断当前点的颜色是不是会是1，结果TLE了N回，桑都必须的判断！！！！！
                 while(num[point[now].color]!=)now = point[now].next;//找到某个颜色的顶点个数只为1个点
                 next1 = point[now].next;//下面是将这个点与其他对顶点链接
                 next2 = point[next1].next;
                 while(point[next2].next != now)
                 {
                     printf("%d %d\n",now+, next2+);
                     next2 = point[next2].next;
                 }
                 break;//全部已经连接完全，结束
             }
             if(point[now].color != point[next2].color)//如果某个三角形三个顶点都不相同的话
             {
                 num[point[next1].color] --;//吧中间的点去掉
                 point[now].next = next2;//当前点的下一个成为后两个的点
                 printf("%d %d\n",now+, next2+);
             }
             now = point[now].next;
         }
     }
     return ;
 }

Problem B  POJ 1579

Function Run Fun

题目意思是说有一个地推公式，如果直接递归下去肯定会相当耗时间，问怎么做

其实很简单。既然直接递推会超时，那是因为之间有很多重复的计算，那我们就只需要，记忆化遍历一遍，将每一步的答案都放在一个数组中，输入前便利一遍，那以后就不再需要遍历。直接一次0Ms过

 #include <stdio.h>

 int d[][][];
 int vis[][][];

 int dfs(int a,int b,int c)
 {
     if(vis[a][b][c])return d[a][b][c];
     vis[a][b][c] = ;
     if(a<= || b<= || c<=)return d[a][b][c] =  ;
     if(a<b && b<c) return d[a][b][c] = dfs(a,b,c-)+dfs(a,b-,c-)-dfs(a,b-,c);
     return d[a][b][c] = dfs(a-, b, c) + dfs(a-, b-, c) + dfs(a-, b, c-) - dfs(a-, b-, c-);
 }
 int main()
 {
     dfs(,,);
     int a,b,c;
     while(~scanf("%d%d%d",&a,&b,&c))
     {
         if(a==- && b==- && c==-)break;
         printf("w(%d, %d, %d) = ", a, b, c);
         if(a<= || b<= || c<=)
         {
             printf("1\n");
             continue;
         }
         if(a> || b> || c>)a=b=c=;
         printf("%d\n",dfs(a,b,c));
     }
     return ;
 }

Problem C   POJ 1845

Sumdiv

当时第一眼看到这道题，就想着是不是有公式可以推导，于是花了半个多小时去计算。最后突然发现。。。。

一个数可以写为他的素数的幂的乘积，即若N = P₁^K1  *  P₂^k2  *  ……  p_n^kn，那这样的话我们可以把它的所有因子拆分，写为

最高次                    拆分情况

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

由于上面的式子包含了   P₁^K1  *  P₂^k2  *  ……  p_n^kn的所有任意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是最高的幂

只是可惜比赛时候没有搞出来=。=！！。。。。。。。。真是纠结。。。

代码：

 #include <stdio.h>
 #include <string.h>
 #define mem(a) memset(a, 0, sizeof(a))
 __int64 mod = ;
 __int64 a[],p[],c[];
 __int64 A,B,num;

 __int64 pow_mod(__int64 m,__int64 n)//快速幂
 {
     if(n == )return %mod;
     if(n == )return m%mod;
     __int64 ans = pow_mod(m, n/);
     ans *= ans;
     if(n% == )ans *= m;
     return ans % mod;
 }

 void find_prime()//打印素数表
 {
     __int64 i,j;
     num=;
     mem(a);   mem(p);
     for(i=;i<=;i++)
     {
         if(!a[i])p[num++] = i;
         for(j=;i*j<=;j++)
         {
             a[i*j]=;
         }
     }
 }

 __int64 add(__int64 p,__int64 k)//计算p+p^2+...+p^k
 {
     if(k == )return ;
     if(k%){
         return (+ pow_mod(p,k/+))*(add(p,k/))%mod;
     }
     return ((+ pow_mod(p,k/+))*(add(p, k/-))+pow_mod(p,k/))%mod;
 }

 int count_C()//用于统计每个速因子的最高次数,返回素因子的个数
 {
     int i,countt = ;
     for(i=;i<num && A >= p[i];i++)
     {
         if(A%p[i] == )
         {
             __int64 key =;
             while(A%p[i] == )
             {
                 key++;
                 A/=p[i];
             }
             a[countt]=p[i];
             c[countt]=B*key;
             countt ++;
         }
     }
     if(A!=){a[countt] = A;c[countt++]=B;}
     return countt;
 }

 int main()
 {
     find_prime();
     while(~scanf("%I64d%I64d", &A, &B))
     {
         if(A <=  || B == ){printf("1\n");continue;}
         int i;
         int num_prime = count_C();
         __int64 ans = ;
         for(i=;i<num_prime;i++)
         {
             ans = (ans * add(a[i],c[i]))%mod;
         }
         printf("%I64d\n", ans);
     }
     return ;
 }

Problem E POJ 3922

A simple stone game

博弈

由于之前对博弈是完全没有概念，所以比赛时候自然也就是不可能AC的了。之后看了一点点有关博弈的思想，发现那完全不是我等人能够理解的透的，所以立马在网上寻找结题报告，经过了良久，才对这个题有了一点点认识，可以参见博客http://blog.csdn.net/acm_cxlove/article/details/7836544

于是随着这个思路写了一段代码（其实和题解的代码几乎已经是相差无几了），暂且挂在这里，慢慢捉摸

 #include <stdio.h>

 int a[],b[];
 int main()
 {
     int n,k;
     int T = ,Case = ;
     while(~scanf("%d",&T))while(T--)
     {
         scanf("%d%d",&n,&k);
         a[] = b[] = ;
         int i=,j=;
         while(n > a[i])
         {
             i++;
             a[i] = b[i-] + ;
             while(a[j+] * k < a[i])
             {
                 j++;
             }
             if(k * a[j] < a[i])
             {
                 b[i] = b[j] + a[i];
             }
             else b[i] = a[i];
         }
         printf("Case %d: ",Case++);
         if(n == a[i])printf("lose\n");
         else
         {
             int ans ;
             while(n)
             {
                 if(n >= a[i])
                 {
                     n -= a[i];
                     ans = a[i];
                 }
                 i --;
             }
             printf("%d\n",ans);
         }
     }
     return ;
 }

终于是把结题报告写出来了 看我的另一篇随笔 http://www.cnblogs.com/gj-Acit/p/3219280.html

Problem G  HDU 4608

I-number

暴力枚举

 #include <stdio.h>
 #include <string.h>
 char str[];

 int calc()
 {
     int len = strlen(str);
     int i,ans = ;
     for(i=;i<len;i++)
     {
         ans+=(str[i] - '');
     }
     return ans;
 }

 void add()
 {
     int i,ans = ;
     for(i=;str[i];i++)
     {
         str[i]-='';
         int a=str[i]+ans;
         ans=a/;
         str[i]=a%;
         str[i]+='';
     }
     if(ans)str[i]='';
 }

 int main()
 {
     int T;
     while(~scanf("%d", &T))while(T--)
     {
         memset(str,,sizeof(str));
         scanf("%s",str);
         strrev(str);
         add();
         int a = calc();
         while(a%)
         {
             add();
             a=calc();
         }
         strrev(str);
         printf("%s\n",str);
     }
     return ;
 }