昨天的PK就是考人的膽量，敢不敢用暴力。。。
http://acm.tju.edu.cn/toj/showp3237.html進(jìn)制轉(zhuǎn)化，天涯3分鐘敲好，我5分鐘才好，數(shù)組開太小WA了，后來一氣之下按好好多個(gè)999，結(jié)果開太大MLE了，悲劇啊。。
http://acm.tju.edu.cn/toj/showp3238.html很簡(jiǎn)單的n^2吧(x^2+y^2)預(yù)處理下，再O(n)的吧(n-z^2)掃一遍。。。賽后竟然發(fā)現(xiàn)n^3的算法都能過
http://acm.tju.edu.cn/toj/showp3239.html開始的時(shí)候就一直在猜。公式推不出。。唉，后來知道數(shù)據(jù)太挫了，開10000的數(shù)組背包下都能過
我一直在想極限數(shù)據(jù)2 5000 4999.。。。這個(gè)你怎么背，汗。。。。
后來得到了風(fēng)的啟發(fā)
研究了一個(gè)下午。。終于用正常的方法過了。。哈哈
獻(xiàn)上我的代碼。。按照余數(shù)路徑找的。。用了bellman_ford算法找到最小點(diǎn)。。
#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北大也有一道一模一樣的題目，數(shù)據(jù)一定不水。。。我的程序bellman哪里寫的太挫了，三個(gè)循環(huán)，導(dǎo)致了超時(shí)。。。
做了點(diǎn)小小的優(yōu)化后就AC了。。還排到了PKU的第一頁(yè)，哈哈，爽
這么好的題就被TOJ的出題人給水了。。。
http://acm.tju.edu.cn/toj/showp3240.html曹操和劉備的題（出現(xiàn)了我所喜歡的大耳和曹操）。。題目意思理解后又是水題。。找區(qū)間最大值線性掃描能過。。出題人。。你開這么大的數(shù)據(jù)范圍都是嚇人的啊？
http://acm.tju.edu.cn/toj/showp3241.html很簡(jiǎn)單的，素?cái)?shù)篩法篩下就好了。。因?yàn)橐瞧鏀?shù)，一定要有個(gè)2^2,我不小心RE了一小下。。
說實(shí)話。。昨天PK賽的水平連選拔賽都比不上
賽后一群人對(duì)C無語(yǔ)掉。。
。。。。
posted on 2009-04-06 13:21
shǎ崽 閱讀(309)
評(píng)論(0) 編輯 收藏 引用