昨天的PK就是考人的胆量，敢不敢用暴力。。。
http://acm.tju.edu.cn/toj/showp3237.html进制转化，天涯3分钟敲好，我5分钟才好，数组开太小WA了，后来一气之下按好好多个999，结果开太大MLE了，悲剧啊。。
http://acm.tju.edu.cn/toj/showp3238.html很简单的n^2吧(x^2+y^2)预处理下，再O(n)的吧(n-z^2)扫一遍。。。赛后竟然发现n^3的算法都能过
http://acm.tju.edu.cn/toj/showp3239.html开始的时候就一直在猜。公式推不出。。唉，后来知道数据太挫了，开10000的数组背包下都能过
我一直在想极限数据2 5000 4999.。。。这个你怎么背，汗。。。。
后来得到了风的启发
研究了一个下午。。终于用正常的方法过了。。哈哈
献上我的代码。。按照余数路径找的。。用了bellman_ford算法找到最小点。。
#include<stdio.h>
#include<string>
#include<stdlib.h>
#define inf 0x7FFFFFFF
int hash[5001];
int num[5001];
int mod[5001];
int gcd(int a,int b)
{
while(a)
a ^= b ^= a ^= b %= a;
return b;
}
int cmp(const void *a,const void *b)
{ return *(int *)a - *(int *)b; }
int main()
{
int T,n,i,j,buf;
bool flag,flag1;
while(scanf("%d",&n)==1)
{
flag1 = false;
for(i=0;i<n;i++)
{
scanf("%d",&num[i]);
if(num[i]==1)
flag1 = true;
}
if(flag1) {
puts("0");
continue;
}
if(n==1)
goto loop;
buf = gcd(num[0],num[1]);
for(i=2;i<n;i++)
{
if(buf==1)
break;
buf = gcd(buf,num[i]);
}
if(buf!=1)
goto loop;
qsort(num,n,sizeof(num[0]),cmp);
for(i=1;i<num[0];i++)
mod[i] = inf;
mod[0] = 0;
for(i=1;i<n;i++)
{
buf = num[i] % num[0];
if(buf && mod[buf] == inf)
mod[buf] = num[i];
}
flag = true;
while(flag)
{
flag = false;
for(i=1;i<num[0];i++)
{
if(mod[i]!=inf)
{
for(j=1;j<num[0];j++)
{
if(mod[j]!=inf && mod[i] + mod[j] < mod[ (i+j)%num[0] ])
{
mod[ (i+j)%num[0] ] = mod[i] + mod[j];
flag = true;
}
}
}
}
}
qsort(mod,num[0],sizeof(mod[0]),cmp);
printf("%d\n",mod[ num[0] - 1 ] - num[0]);
continue;
loop:
puts("INF");
}
}
http://acm.pku.edu.cn/JudgeOnline/problem?id=3492北大也有一道一模一样的题目，数据一定不水。。。我的程序bellman哪里写的太挫了，三个循环，导致了超时。。。
做了点小小的优化后就AC了。。还排到了PKU的第一页，哈哈，爽
这么好的题就被TOJ的出题人给水了。。。
http://acm.tju.edu.cn/toj/showp3240.html曹操和刘备的题（出现了我所喜欢的大耳和曹操）。。题目意思理解后又是水题。。找区间最大值线性扫描能过。。出题人。。你开这么大的数据范围都是吓人的啊？
http://acm.tju.edu.cn/toj/showp3241.html很简单的，素数筛法筛下就好了。。因为要是奇数，一定要有个2^2,我不小心RE了一小下。。
说实话。。昨天PK赛的水平连选拔赛都比不上
赛后一群人对C无语掉。。
。。。。
posted on 2009-04-06 13:21
shǎ崽 阅读(307)
评论(0) 编辑 收藏 引用