随笔-72  评论-126  文章-0  trackbacks-0
昨天的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的出题人给水了。。。
4945477 notonlysuccess 3492 Accepted 264K 63MS C++ 2115B 2009-04-09 14:06:29
4945435 notonlysuccess 3492 Accepted 252K 79MS C++ 2137B 2009-04-09 13:59:19
4945000 notonlysuccess 3492 Accepted 248K 188MS C++ 1984B 2009-04-09 12:44:34


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ǎ崽 阅读(306) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理