昨天的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ǎ崽 閱讀(312)
評論(0) 編輯 收藏 引用