Problem A URAL 1181
题目大意就是说有一个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
题目意思是说有一个地推公式，如果直接递归下去肯定会相当耗时间，问怎么做
其实很简单。既然直接递推会超时，那是因为之间有很多重复的计算，那我们就只需要，记忆化遍历一遍，将每一步的答案都放在一个数组中，输入前便利一遍，那以后就不再需要遍历。直接一次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
当时第一眼看到这道题，就想着是不是有公式可以推导，于是花了半个多小时去计算。最后突然发现。。。。
一个数可以写为他的素数的幂的乘积，即若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是最高的幂
只是可惜比赛时候没有搞出来=。=！！。。。。。。。。真是纠结。。。
代码：
#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
博弈
由于之前对博弈是完全没有概念，所以比赛时候自然也就是不可能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
暴力枚举
#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 ;
}