C++博客-AClayton's ACM/ICPC Life 只切菜题菜鸟乱飞

腾讯2009年重庆笔试附加题

流牛ζ木马 — Thu, 23 Oct 2008 11:28:00 GMT

摘要: 题目描述：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1,w2,...,wn.希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。要求：用非递归的方法。便于理解，先说说递归算法。 &nbs... 阅读全文

流牛ζ木马 2008-10-23 19:28 发表评论

在微软亚洲研究院实习，暂停做算法。实习生活博客http://sixsix.net.ms

流牛ζ木马 — Fri, 15 Feb 2008 06:23:00 GMT

很多朋友问起为什么我现在不做ACM了。
呵呵，其实我也很想做了，只是时间不够了。
现在我在微软亚洲研究院实习。
博客地址是http://sixsix.net.ms
这个算法博客就暂停更新了。希望各位朋友谅解。

流牛ζ木马 2008-02-15 14:23 发表评论

ACM PKU 1915 Knight Moves 典型的宽度优先搜索 BFS

流牛ζ木马 — Fri, 16 Nov 2007 07:37:00 GMT

摘要: http://acm.pku.edu.cn/JudgeOnline/problem?id=1915发现用vector来做宽搜的队列,要比自己弄一个队列来记录方便得多,呵呵程序很简单,关键地方我都注释上了 Source CodeProblem: 1915 User: lnmm Memory: 1560K ... 阅读全文

流牛ζ木马 2007-11-16 15:37 发表评论

ACM PKU 3356 AGTC 简单动态规划-仿最长公共子序列

流牛ζ木马 — Fri, 16 Nov 2007 06:36:00 GMT

http://acm.pku.edu.cn/JudgeOnline/problem?id=3356

和最长公共子序列类似
如果s1[i]==s2[j] f[i][j] =min{不操作; 在i中删除操作;在j中插入操作 }
否则 f[i][j]=min{改变; 在i中删除操作;在j中插入操作 }

初始化的时候和最长公共子序列不同

Source Code

Problem: 3356  User: lnmm
Memory: 3992K  Time: 31MS
Language: C++  Result: Accepted

Source Code
#include "stdio.h"
int f[1002][1002];
int min(int a,int b,int c)
{
    int temp;
    temp=a<=b?a:b;
    return c<=temp?c:temp;
}
void main()
{    int i,j;
  int len1,len2;
  char str1[1002],str2[1002];
  while(scanf("%d",&len1)!=EOF)
  {
// scanf("%d",&len1);
  scanf("%s",str1+1);
  scanf("%d",&len2);
  scanf("%s",str2+1);


      for(i=0;i<=len1;i++)
          f[i][0]=i;
      for(j=0;j<=len2;j++)
          f[0][j]=j;
      for(i=1;i<=len1;i++)
          for(j=1;j<=len2;j++)
          {
              if(str1[i]==str2[j])
          f[i][j]=min(f[i-1][j-1],f[i-1][j]+1,f[i][j-1]+1);
          else  f[i][j]=min(f[i-1][j-1]+1,f[i-1][j]+1,f[i][j-1]+1);
         }
          printf("%d\n",f[len1][len2]);

  }
}

流牛ζ木马 2007-11-16 14:36 发表评论

ACM PKU 1458 Common Subsequence 经典且简单动态规划

流牛ζ木马 — Thu, 15 Nov 2007 06:56:00 GMT

http://acm.pku.edu.cn/JudgeOnline/problem?id=1458
当初看<算法导论>的时候觉得这很神奇,题做多了,反而觉得很容易了. 这都是菜题,不是我们的目标.

Source Code

Problem: 1458  User: lnmm
Memory: 856K  Time: 0MS
Language: C++  Result: Accepted

Source Code
#include"stdio.h"
#include"string.h"
#define MAX 1000
char sz1[MAX],sz2[MAX];
int aMaxLen[MAX][MAX];
void main()
{
    while(scanf("%s%s",sz1+1,sz2+1)!=EOF)
    {
        int len1,len2;
        len1=strlen(sz1+1);
        len2=strlen(sz2+1);

        int i,j;
        for(i=0;i<len1;i++)aMaxLen[i][0]=0;
        for(j=0;j<len1;j++)aMaxLen[0][j]=0;
        for(i=1;i<=len1;i++)
            for(j=1;j<=len2;j++)
                if(sz1[i]==sz2[j])
                    aMaxLen[i][j]=1+aMaxLen[i-1][j-1];
                else aMaxLen[i][j]=aMaxLen[i-1][j]>aMaxLen[i][j-1]?aMaxLen[i-1][j]:aMaxLen[i][j-1];
        printf("%d\n",aMaxLen[len1][len2]);

    }
}

流牛ζ木马 2007-11-15 14:56 发表评论

ACM PKU 3420 Quad Tiling 很难的动态规划,需要灵活应用矩阵`

流牛ζ木马 — Thu, 15 Nov 2007 06:03:00 GMT

摘要: http://acm.pku.edu.cn/JudgeOnline/problem?id=3420好几个人都问我这道题,可是我自己也不会做,真是惭愧啊...太落后了..别人都飞机大炮了,我还在小米加步枪.... 太羞愧了 ..不过还好,除了Felicia的程序以外(http://www.cppblog.com/felicia/archive/2007/10/08/33740.html),我还读了两... 阅读全文

流牛ζ木马 2007-11-15 14:03 发表评论

ACM PKU 2663 Tri Tiling 简单的动态规划有趣

流牛ζ木马 — Wed, 14 Nov 2007 17:06:00 GMT

http://acm.pku.edu.cn/JudgeOnline/problem?id=2663
开始想复杂了,其实是个递推,或者说是个简单的动态规划

T(2)=3 ;
T(0)=1;
T(2*k-1)=0
T(2*k)=3*T(2*k-2)+2*(T(2*k-4)+T(2*k-6)+..+T(2) )

#include <stdio.h>
long T[31];
long t(int n)
{
    int i;
    if(n==2)return 3;
    if(T[n]!=0)return T[n];
    else
    {
        T[n]=3*t(n-2)+2;
        for(i=n-4;i>=2;i=i-2)
         T[n]+=2*t(i);
    }


    return T[n];
}
void main()
{
    int input;
    scanf("%d",&input);
    while(input!=-1){
        if(input%2==1)printf("0\n");
        else if(input==0)printf("1\n");
        else printf("%ld\n",t(input));
        scanf("%d",&input);
    }
}

流牛ζ木马 2007-11-15 01:06 发表评论

ACM PKU 1887 Testing the CATCHER 最长下降(上升)子序列一维动态规划

流牛ζ木马 — Wed, 14 Nov 2007 09:38:00 GMT

http://acm.pku.edu.cn/JudgeOnline/problem?id=1887
题目太罗嗦了,简单的说就是求最长下降子序列;
这是一通用题,还有最长上升子序列,都是一样的解法.
状态转移方程:
Max(1)=1;
Max( i )=Max{ Max(j): 1<=j二十分钟AC,下面是源代码

Source Code

Problem: 1887  User: lnmm
Memory: 372K  Time: 78MS
Language: C++  Result: Accepted

Source Code
#include"stdio.h"
void main()
{
    int i,j,tempMax;
    int nCase=1;
    int a[32767];
    int totalMax[32767];
    int temp;
    while(scanf("%d",&temp))
    {
        if(temp==-1)break;
        a[1]=temp;
        totalMax[1]=1;
        for(i=1;;)
        {
            scanf("%d",&temp);
            if(temp==-1)break;
            else
            {
                a[++i]=temp;
                tempMax=0;             //找到i之前的totalMax[j]最大且a[j]>a[i]的j值
                for(j=1;j<i;j++)
                    if(a[i]<a[j]&&tempMax<totalMax[j])tempMax=totalMax[j];
                totalMax[i]=tempMax+1;   //i取的是上面得到的值,加上本身(因为有a[j]>a[i]),所以+1
            }
        }
        temp=0;
        for(j=1;j<=i;j++)
            if(totalMax[j]>temp)temp=totalMax[j];
        printf("Test #%d:\n",nCase++);
        printf("  maximum possible interceptions: %d\n\n",temp);

    }
}

流牛ζ木马 2007-11-14 17:38 发表评论

ACM PKU 1054 The Troublesome Frog　　学会剪枝

流牛ζ木马 — Tue, 13 Nov 2007 14:24:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1054

有的说是入门级剪枝，有的说是剪枝条件很强，，呵呵，无论怎样，今天我终于成功剪枝了．　以前也是做了很久的．
注意qsort和bsearch 的使用
#include "stdio.h"

#include "stdlib.h"

struct PLANT
{
       int x, y;
}plant[5001];

int row, col, n;

int cmp(const void *a, const void *b)
{
       PLANT *x = (PLANT *)a, *y = (PLANT *)b;
       if(x->x == y->x)    return x->y - y->y;
       return x->x - y->x;
}

void input()
{
       int i;
       scanf("%d %d", &row, &col);
       scanf("%d", &n);
       for(i=0; i<n; i++)
              scanf("%d %d", &plant[i].x, &plant[i].y);
}

int solve();

int main()
{
       input();
       qsort(plant, n, sizeof(PLANT), cmp);
       int temp = solve();
       if(temp > 2)                                //题目要求答案一定大于等于3
              printf("%d\n", temp);
       else
              printf("0\n");
       return 0;
}

int solve()
{
    int max = 0, temp;
    int i, j;
    PLANT n1, n2, jump, next;

    for(i=0; i<n; i++)
    {
        for(j=i+1; j<n; j++)
        {
            temp = 2;
            n1 = plant[i];
            n2 = plant[j];
            jump.x = plant[j].x - plant[i].x;
            jump.y = plant[j].y - plant[i].y;
            if(n1.x - jump.x > 0 && (n1.y - jump.y >0 && n1.y - jump.y <=col) )
            //只能从外面逃入
                continue;
            if(n1.x + max*jump.x > row || n1.y + max*jump.y > col || n1.y + max*jump.y <= 0)
            //超出范围
                continue;
            next.x = plant[j].x + jump.x;
            next.y = plant[j].y + jump.y;
            while(next.x <= row && next.y <= col && next.x > 0 && next.y > 0)
            {
                PLANT * a = (PLANT *) bsearch( &next, plant, n, sizeof(PLANT), cmp);

                //bsearch 二分法
                if(a == NULL)
                {
                    temp = 0;
                    break;
                }
                temp ++;
                next.x += jump.x;
                next.y += jump.y;
            }
            if(temp > max)    max = temp;
        }
    }
    return max;
}

流牛ζ木马 2007-11-13 22:24 发表评论

ACM PKU 1543 Perfect Cubes 简单题,简单剪枝

流牛ζ木马 — Tue, 13 Nov 2007 12:34:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1543

完完全全的O(n4)算法
注意几个剪枝条件

Source Code

Problem: 1543  User: lnmm
Memory: 64K  Time: 15MS
Language: C++  Result: Accepted

Source Code
#include"stdio.h"

void main()
{
    long int cube[101];
    int n,i,a,b,c,d;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        cube[i]=i*i*i;
    for(a=6;a<=n;a++)
        for(b=2;b<n;b++)
        {
            if(cube[a]<cube[b]+cube[b+1]+cube[b+2])break;
            for(c=b+1;c<a;c++)
            {
                if(cube[a]<cube[b]+cube[c]+cube[c+1])break;
                for(d=c+1;d<a;d++)
                if(cube[a]==cube[b]+cube[c]+cube[d])
                    printf("Cube = %d, Triple = (%d,%d,%d)\n",a,b,c,d);

            }
        }

}

流牛ζ木马 2007-11-13 20:34 发表评论

ACM　PKU 1013 Counterfeit Dollar 以前做了很久都没ａｃ的简单题

流牛ζ木马 — Tue, 13 Nov 2007 12:09:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1013

以前没做好是自己结构没有想清楚，再加上竟然没有想到用strchr这个函数．．．

Source Code

Problem: 1013  User: lnmm
Memory: 64K  Time: 0MS
Language: C++  Result: Accepted

Source Code
#include"stdio.h"
#include"string.h"
char left[3][7],right[3][7],result[3][5];

bool isHeavy(char x )
{
    int i;
    for(i=0;i<3;i++)
    {
        switch(result[i][0])
        {
        case 'u':if(strchr(left[i],x)==NULL)return false;break;
        case 'e':if(strchr(left[i],x)!=NULL||strchr(right[i],x)!=NULL)return false;break;
        case 'd':if(strchr(right[i],x)==NULL)return false;break;
        }
    }
    return true;
}

bool isLight(char x )
{
    int i;
    for(i=0;i<3;i++)
    {
        switch(result[i][0])
        {
        case 'u':if(strchr(right[i],x)==NULL)return false;break;
        case 'e':if(strchr(left[i],x)!=NULL||strchr(right[i],x)!=NULL)return false;break;
        case 'd':if(strchr(left[i],x)==NULL)return false;break;
        }
    }
    return true;
}

void main()
{
    int n;
    char c;
    int i;
    scanf("%d",&n);
    while(n>0)
    {
        for( i=0;i<3;i++)
            scanf("%s%s%s",left[i],right[i],result[i]);
        for(c='A';c<='L';c++)
        {
            if(isLight(c))
            {
                printf("%c is the counterfeit coin and it is light.\n",c);
                break;
            }
            if(isHeavy(c))
            {
                printf("%c is the counterfeit coin and it is heavy.\n",c);
                break;
            }

        }
        n--;

    }
}

流牛ζ木马 2007-11-13 20:09 发表评论

ACM PKU 2080 Calendar 日期处理典型题目

流牛ζ木马 — Tue, 13 Nov 2007 09:34:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=2080

巧妙的方法
首先要知道起始日期是星期几
将判断闰年的代码抽象为函数, 便于作为数组索引

Source Code

Problem: 2080  User: lnmm
Memory: 64K  Time: 625MS
Language: C++  Result: Accepted

Source Code
#include"stdio.h"
char week[7][10]={"Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday","Friday"};
int year[2]={365,366};
int month[2][12]={31,28,31,30,31,30,31,31,30,31,30,31,31,29,31,30,31,30,31,31,30,31,30,31};

int type(int m)
{if((m%4==0&&m%100!=0)||(m%400==0))return 1;else return 0;
}
void main()
{
    int days,dayofweek;
    int i=0,j=0;
    while(scanf("%d",&days)&&days!=-1)
    {
        dayofweek=days%7;
        for(i=2000;days>=year[type(i)];i++)
            days-=year[type(i)];
        for(j=0;days>=month[type(i)][j];j++)
            days-=month[type(i)][j];
        printf("%d-%02d-%02d %s\n",i,j+1,days+1,week[dayofweek]);

    }
}

流牛ζ木马 2007-11-13 17:34 发表评论

ACM PKU 1629 Fillword 纯字母字符串的处理和计数典型题

流牛ζ木马 — Tue, 13 Nov 2007 09:00:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1629

Source Code

Problem: 1629  User: lnmm
Memory: 116K  Time: 0MS
Language: C++  Result: Accepted

Source Code
#include"stdio.h"
void main()
{
    int characters[26];
    int n,m,p;
    int i,j;
    for(i=0;i<26;i++)
        characters[i]=0;
    scanf("%d%d%d",&n,&m,&p);
    for(i=0;i<n;i++)
    {
        char str[11];
        scanf("%s",str);
        for(j=0;str[j]!='\0';j++)
            characters[str[j]-'A']++;

    }
    for(i=0;i<p;i++)
    {
        char str[200];
        scanf("%s",str);
        for(j=0;str[j]!='\0';j++)
            characters[str[j]-'A']--;
    }

    for(i=0;i<26;i++)
        if(characters[i]!=0)
            for(j=0;j<characters[i];j++)
                printf("%c",i+'A');
            printf("\n");
}

流牛ζ木马 2007-11-13 17:00 发表评论

ACM PKU 1565 Skew Binary 简单题

流牛ζ木马 — Tue, 13 Nov 2007 08:50:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1565

Source Code

Problem: 1565  User: lnmm
Memory: 64K  Time: 0MS
Language: C++  Result: Accepted

Source Code
#include"stdio.h"
#include"string.h"
void main()
{
    int i,k,base[31],sum;
    char skew[32];
    base[0]=1;
    for(i=1;i<31;i++)base[i]=2*base[i-1]+1; //递推,将进制基数储存,避免重复计算
    while(1)
    {
        scanf("%s",skew);
        if(strcmp(skew,"0")==0)break;
        sum=0;
        k=strlen(skew);
        for(i=0;i<strlen(skew);i++)
        {
            k--;
            sum+=(skew[i]-'0')*base[k];

        }

    printf("%d\n",sum);
    }

}

流牛ζ木马 2007-11-13 16:50 发表评论

ACM PKU 1298 The Hardest Problem Ever 　小小的难点：传递字符串参数

流牛ζ木马 — Tue, 13 Nov 2007 08:14:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1298
很简单，几乎没有＂算法＂可言
注意：　1.不要用scanf()来读字符串，因为scanf()会把空格当作分隔符，在本题中是不符合题意的；2.注意传递字符串参数后，有个gets()相当精髓．

Source Code

Problem: 1298  User: lnmm
Memory: 56K  Time: 0MS
Language: C++  Result: Accepted

Source Code
#include"stdio.h"
#include"string.h"

void decipher(char * message)
{
    char plain[]="VWXYZABCDEFGHIJKLMNOPQRSTU";
    char cipherEnd[201];
    int i,cipherLen;
      gets(message);  //史上最精髓的一个gets()
    cipherLen=strlen(message);
    for(i=0;i<cipherLen;i++)
        if(message[i]>='A'&&message[i]<='Z')message[i]=plain[message[i]-'A'];
        gets(cipherEnd);
        return;
}

void main()
{
    char message[201];
    gets(message);
    while(strcmp(message,"START")==0){
        decipher(message);
        printf("%s\n",message);
        gets(message);
    }
}

流牛ζ木马 2007-11-13 16:14 发表评论

ACM　PKU 1226 Substrings　较复杂字符串操作（但不繁琐）

流牛ζ木马 — Tue, 13 Nov 2007 07:46:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1226

注意几点：　１．对字符串复制使用strcpy和strncpy 　2.strstr　查找子串；　３.strrev对字符串反序　　4.strncpy后要在末尾加上'\0'   5.二维数组放在全局位置

#include"stdio.h"
#include"string.h"

int n;
char str[100][100];
int searchMaxSubString(char * source)
{
    int subStrLen=strlen(source),sourceStrLen=strlen(source);
    int i,j;
    bool foundMaxSubStr;
    char subStr[101],revSubStr[101];

    while(subStrLen>0)
    {
        for(i=0;i<=sourceStrLen-subStrLen;i++)
        {
            strncpy(subStr,source+i,subStrLen);
            strncpy(revSubStr,source+i,subStrLen);
            subStr[subStrLen]=revSubStr[subStrLen]='\0';
            strrev(revSubStr);

            foundMaxSubStr=true;
            for(j=0;j<n;j++)
                if(strstr(str[j],subStr)==NULL&&strstr(str[j],revSubStr)==NULL){foundMaxSubStr=false;break;}
            if(foundMaxSubStr) return subStrLen;

        }
        subStrLen--;
    }
    return 0;
}

void main()
{
    int i,nCase,minStrLen,subStrLen;
    char minStr[101];
    scanf("%d",&nCase);
    while(nCase--)
    {

    scanf("%d",&n);
    minStrLen=101;
    for(i=0;i<n;i++)
    {
        scanf("%s",str[i]);
        if(strlen(str[i])<minStrLen){strcpy(minStr,str[i]);minStrLen=strlen(minStr);}

    }
    printf("%d\n",searchMaxSubString(minStr));
    }

}

流牛ζ木马 2007-11-13 15:46 发表评论

ACM PKU 1002 487-3279 较复杂字符串比较操作

流牛ζ木马 — Tue, 13 Nov 2007 07:06:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1002

读入字符串-将字符串统一格式- qsort- 查找重复并记录-输出

Source Code

Problem: 1002  User: lnmm
Memory: 944K  Time: 529MS
Language: C++  Result: Accepted

Source Code
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
char map[]="22233344455566677778889999";
char str[80],telNumber[100000][9];
int compare(const void *p1,const void *p2)
{
    return(strcmp((char*)p1,(char*)p2));
}

void standardizeTel(int n)
{
    int j,k;
    k=-1;j=-1;
    while(k<8)
    {

    j++;
    if(str[j]=='-') continue;
    k++;
    if(k==3){telNumber[n][k]='-';k++;}
        if(str[j]>='A'&&str[j]<='Z'){telNumber[n][k]=map[str[j]-'A'];continue;}
    telNumber[n][k]=str[j];
    }

     telNumber[n][8]='\0';
     return;
}

void main()
{
    int n,i,j;
    bool noduplicate;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%s",str);
        standardizeTel(i);

    }
    qsort(telNumber,n,9,compare);
    noduplicate=true;
    i=0;
    while(i<n)
    {
        j=i;
        i++;
        while((i<n)&&strcmp(telNumber[i],telNumber[j])==0)i++;
        if(i-j>1)
        {
            printf("%s %d\n",telNumber[j],i-j);
            noduplicate=false;

        }

    }
        if(noduplicate==true)
            printf("No duplicates.\n");
}

流牛ζ木马 2007-11-13 15:06 发表评论

ACM PKU 1323 Game Prediction 贪心算法

流牛ζ木马 — Thu, 08 Nov 2007 08:28:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1323

贪心是肯定可以的,不过据说也可以用动归?
我的贪心算法如下: 从n*m 到1依次计算,如果手里有那个数, now++ ,否则now--; 记录下now出现过的最大值,最后输出最大值
嗯也可以有其他贪心

Source Code

Problem: 1323  User: lnmm
Memory: 64K  Time: 0MS
Language: C++  Result: Accepted

Source Code
#include"stdio.h"

int a[51];
int i,j,m,n,max,now,cas=0;

bool have(int x)
{
    for(j=1;j<=n;j++)
        if(x==a[j])return true;
    return false;

}

void main()
{

    while(1)
    {
        cas++;
    scanf("%d%d",&m,&n);
    if(m==0&&n==0)return;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    max=0;now=0;
    for(i=n*m;i>=1;i--)
    {

        if(have(i)){now++;if(now>max)max=now;}
        else now--;

    }

    printf("Case %d: %d\n",cas,max);

    }
}

流牛ζ木马 2007-11-08 16:28 发表评论

ACM PKU 1147 Binary codes 好狡猾的题...强烈推荐值得反复思考

流牛ζ木马 — Thu, 08 Nov 2007 05:42:00 GMT

http://acm.pku.edu.cn/JudgeOnline/problem?id=1147

开始我是这样猜测的:
输入的最后一列的元素是第一行出现的元素,所以直接排序输出即可.
WA

研究了n久,原来是题意理解有问题.,,
这句话很诡异 Then rows of the matrix are sorted in alphabetical order, where ‘0’ is before ‘1’'

经过研究,发现题意原来是这样的 : 1.所有行都是经过某一行的rotated versions 2.即上面这句话的理解:将所有的rotated versions 排序.... 3.由1和2,所以行的顺序和生成rotated versions 的顺序相比,是混乱的....

注意到有一点是确定的,同一行中最后一个数和第一个数的关系.

方法: 因为是经过按照row排序的,所以第一列肯定是排好序.第一列和最后一列对照,可得出以上说的"混乱"的顺序,保存在next数组里. 最后按照next数组的顺序排列input数据...


这题费了我一个半小时,网上也找不到任何代码和算法,确实是经典啊~~
a[] 放输入数据,即最后一列
b[]放第一列
next[]是根据这两列比较得到的顺序

输出的时候注意这个通用的小技巧

Source Code

Problem: 1147  User: lnmm
Memory: 104K  Time: 152MS
Language: C++  Result: Accepted

Source Code
#include"stdio.h"
int a[3001];
int b[3001];
int next[3001];
bool used[3001];
void main()
{

    int n,i,j,k=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==1)k++;
        used[i]=false;
    }
    for(i=1;i<=n-k;i++)
        b[i]=0;
    for(i=n-k+1;i<=n;i++)
        b[i]=1;


    for(i=1;i<=n;i++)
    {
        j=1;
        while((b[i]!=a[j])||(used[j]==true))j++;
        used[j]=true;
        next[i]=j;
    }

    k=1;
    for(i=1;i<=n;i++)
    {
        k=next[k];
        printf("%d ",a[k]);
    }

}

流牛ζ木马 2007-11-08 13:42 发表评论

ACM　PKU　1695　Magazine Delivery　三维动态规划

流牛ζ木马 — Wed, 07 Nov 2007 17:35:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1695
第一次做三位动态规划，看了谢迪的《浅谈动态规划》，写出如下程序

#include "stdio.h"

int f[33][33][33];
int d[33][33];
int maxint=99999;

void main()
{
    int T,i,j,k,n,opt;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=1;i<=n-1;i++) //读数据
            for(j=i+1;j<=n;j++)
            {
                scanf("%d",&d[i][j]);
                d[j][i]=d[i][j];

            }

        for(i=1;i<=n;i++)//初始化
            for(j=1;j<=n;j++)
                for(k=1;k<=n;k++)
                    f[i][j][k]=maxint;

         f[1][1][1]=0;

         for(k=2;k<=n;k++)
             for(i=1;i<k;i++)
                 for(j=1;j<k;j++)
                     if(f[i][j][k-1]!=maxint)
                     {
                         if(f[i][j][k-1]+d[i][k]<f[j][k-1][k])
                          f[j][k-1][k]=f[i][j][k-1]+d[i][k];

                         if(f[i][j][k-1]+d[j][k]<f[i][k-1][k])
                          f[i][k-1][k]=f[i][j][k-1]+d[j][k];

                         if(f[i][j][k-1]+d[k-1][k]<f[i][k-1][k])
                         f[i][j][k]=f[i][j][k-1]+d[k-1][k];
                     }

         opt=f[1][1][n];
         for(i=1;i<n;i++)
             for(j=1;j<n;j++)
                 if(f[i][j][n]<opt)opt=f[i][j][n];
         printf("%d\n",opt);




    }
}

本地调试成功,不过提交上去总是wa,郁闷了我一个多小时了.
唉..
不过总算是自己做了一次三维动态规划了.希望哪个牛人可以告诉我这个程序哪里出问题了.

流牛ζ木马 2007-11-08 01:35 发表评论

ACM PKU 1163 The Triangle 简单的动态规划就像是APM小于等于100的WAR3玩家

流牛ζ木马 — Wed, 07 Nov 2007 16:19:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1163
简单的动态规划就像是APM小于等于100的WAR3玩家,可以变着戏法来随便虐待.
递推式的动归、记忆化搜索，或者稍微优化一下的搜索……

呵呵，

a[i][j]是i排第j个数
f[i][j]是到达a[i][j]时可以得到的最大总和.
显然只能从a[i-1][j-1]和a[i-1][j]两条路来到a[i][j]
故状态转移方程为 f[i][j]=max{a[i-1][j],a[i-1][j-1]}+a[i][j]
注意边界条件即可

#include "stdio.h"
int a[100][100];
int f[100][100];

int max(int x,int y)
{
    if(x>y)return x;
    else return y;
}

void main()
{

    int result;
    int i,j;
    int m;

    scanf("%d",&m);
    for(i=1;i<=m;i++)
        for(j=1;j<=i;j++)
            scanf("%d",&a[i][j]);

    f[0][0]=0; f[0][1]=0;
    for(i=1;i<=m;i++)
    {
        f[i][0]=0;f[i][i+1]=0;
        for(j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
    }

    result=f[m][1];
    for(i=1;i<=m;i++)
        if(f[m][i]>result)result=f[m][i];
    printf("%d\n",result);

}

流牛ζ木马 2007-11-08 00:19 发表评论

ACM PKU 1028 Web Navigation 字符串数组处理

流牛ζ木马 — Tue, 06 Nov 2007 10:09:00 GMT

Source Code

Problem: 1028  User: lnmm
Memory: 176K  Time: 15MS
Language: C++  Result: Accepted

Source Code
#include<iostream>
#include<cstring>
using namespace std;

int main()
{
    char temp[8],stack[255][255]={"http://www.acm.org/"};
    int k=0,n;
    while(cin>>temp)
    {
        if(temp[0]=='Q')
            break;
        else if(temp[0]=='V')
        {
            k++;
            cin>>stack[k];
            cout<<stack[k]<<endl;
            n=k;
        }
        else if(temp[0]=='B')
        {
            k--;
            if(k<0)
            {
                cout<<"Ignored\n";
                k=0;
            }
            else
                cout<<stack[k]<<endl;
        }
        else
        {
            k++;
            if(k>n)
            {
                cout<<"Ignored\n";
                k=n;
            }
            else
                cout<<stack[k]<<endl;
        }
    }
    return 0;
}

http://acm.pku.edu.cn/JudgeOnline/problem?id=1028

如果想用字符串,请记得
#include
#include
using namespace std;

以避免不不要的麻烦. (否则cin字符串的时候容易出错)

流牛ζ木马 2007-11-06 18:09 发表评论

ACM PKU 1562 Oil Deposits 深度优先搜索

流牛ζ木马 — Tue, 06 Nov 2007 08:51:00 GMT
     摘要:   阅读全文

流牛ζ木马 2007-11-06 16:51 发表评论

ACM PKU 2244 Eeny Meeny Moo 约瑟夫问题

流牛ζ木马 — Tue, 06 Nov 2007 07:46:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=2244
     在没有明白约瑟夫问题之前,只能用模拟来做.
      约瑟夫问题是这样的:
      假设n个人,编号为1到n,排成一个圈,顺时针从1开始数字m,数到m的人杀了,剩下的人继续游戏.活到最后的一个人是胜利者.一般来说需要编程求解最后一个人的编号.
      思路是这样的:
     假设当前剩下i个人(i<=n),显然这一轮m要挂(因为总是从1开始数).经过这一轮,剩下的人是:1 2 3 ... m- 1 m + 1 ... i, 我们将从m+1开始的数映射成1，则m+2对应2， n对应i - m， 1对应成i - m + 1  m - 1对应i - 1，那么现在的问题变成了已知i - 1个人进行循环报数m，求出去的人的序号。假设已经求出了i- 1个人循环报数下最后一个出去的人的序号X0，那么它在n个人中的序号X1=(X0+ m - 1) % n + 1, 最初的X0=1 ,反复迭代X0和X1可以求出.
     简单约瑟夫问题的解法:

#include <stdio.h >
main()
{
    int n, m,i, s=0;
    printf( "N  M  =  "); scanf("%d%d ",&n,&m);
    for(i=2;i<=n;i++)s=(s+m)%i;
    printf("The winner is %d\n ", s+1);
}

      这倒题其实不是完全的约瑟夫问题,而是稍微变了形.呵呵,聪明的读者自己发现!这一点费了我很久的时间,还害我逃了课被点名...
    这道题的我解法是这样的.

#include   <stdio.h >
int y(int n,int m)
{
    int s=1,i;
    for(i=2;i<=n-1;i++)
        s=(s+m-1)%i+1;
    return s+1;

}

main()
{
    int m,n;

    while(1)
    {
    scanf("%d",&n);
    if(n==0)break;
     for(m=1;;)
     {
         if(y(n,m)==2)break;
         m++;
     }


    printf("%d\n",m);

    }
}

       读一个数处理一个数, Memory 68K,时间31MS,如果觉得效率不高. 优化的办法是打表~



流牛ζ木马 2007-11-06 15:46 发表评论

ACM PKU 1160 Post Office 经典动态规划

流牛ζ木马 — Fri, 21 Sep 2007 16:54:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1160
用opt[i][j]记录把前i个邮局建到前j个村庄中的最优解
用cost[i][j]记录所有在i到j村庄中，建1个邮局的最小代价。显然邮局应该设到中点。

让前i个邮局覆盖前j个村庄，第i+1个邮局覆盖第j+1至j+k个村庄(j+k<=n)，则状态转移方程为
opt[i+1][j+k]=min{opt[i][j]+cost[j+1][j+k];} (k+j<=n)

#include"stdio.h"
long cost[301][301];
long opt[301][301];        //把前i个邮局建到前j个村庄中的最优解
int v[301];

void pre(int m,int n)
{
    int i,j,mid,k;              //记录所有在i到j村庄中，建一个邮局的最小代价。显然邮局应该设到中点。
    for (i=1;i<=m;i++)
        for(j=i;j<=m;j++)         //j>=i
        {
            cost[i][j]=0;
            mid=(i+j)/2;
            for(k=i;k<=mid;k++)
                cost[i][j]+=v[mid]-v[k];
            for(k=mid+1;k<=j;k++)
                cost[i][j]+=v[k]-v[mid];
        }

}
void main()
{

    int i,j,k;
    int m,n;

    scanf("%d%d",&m,&n);
    for(i=1;i<=m;i++)
        scanf("%d",&v[i]);
    pre(m,n);

    for(i=0;i<=n;i++)
        for(j=0;j<=m;j++)
            opt[i][j]=3000000;
    opt[0][0]=0;
     for(i=0;i<=n;i++)
       for(j=0;j<=m;j++)
           if(opt[i][j]<3000000)
        {
            for(k=1;j+k<=m;k++)
                if(opt[i+1][j+k]>opt[i][j]+cost[j+1][j+k])       //状态转移.   让前i个邮局覆盖前j个村庄，第i+1个邮局覆盖第j+1到第j+k个村庄。
                   opt[i+1][j+k]=opt[i][j]+cost[j+1][j+k];
        }
       printf("%d\n", opt[n][m]);


}

流牛ζ木马 2007-09-22 00:54 发表评论

ACM PKU 1953 World Cup Noise

流牛ζ木马 — Fri, 21 Sep 2007 07:21:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1953
假设字符串是s[1..n]，第n位的解数是a[n]
当s[n]= =0时，a[n]= =a[n-1]；
当s[n]= =1时,   s[n-1]= =0;s[n]和s[n-1]都固定，则a[n]= =a[n-2]

综上,除了a[1]和a[2]外，a[n]=a[n-1]+a[n-2]
代码如下

#include"stdio.h"
long a[46];

void main()
{
    int n,m;
    int i;
    a[1]=2;a[2]=3;
    for(i=3;i<=45;i++)
    {
        a[i]=a[i-1]+a[i-2];
    }

    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&m);
        printf("\nScenario #%d:\n",i);
        printf("%ld\n",a[m]);

    }

}

流牛ζ木马 2007-09-21 15:21 发表评论

ACM PKU 1936 All in All 字符串处理

流牛ζ木马 — Thu, 20 Sep 2007 18:49:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1936
其实我是比较讨厌字符串处理的题目的,因为在C++里面没办法使用C的string.h ,而且直接使用C++的string类又不太灵活;让我在VC++里用C写处理字符串的程序,确实很尴尬,因为我宁愿用的原始的字符指针.

初看到这道题时,自己写了一个类似string.h里strlen()的方法.代码如下.

#include"stdio.h"

int length(char *s)
{
    int i=0;
    char *p;
    p=s;
    while(*p){p++;i++;}
    return i;

}

main()
{
    char *s1=new char[100010];
    char *s2=new char[100010];
    int i,j;

    while(scanf("%s %s",s1,s2)!=EOF)
    {
        i=0;
        for(j=0;j<length(s2);j++)
            if(s1[i]==s2[j])i++;

        if(i==length(s1))printf("Yes\n");
        else printf("No\n");

    }

}

没想到竟然TLE了....

还是回归字符指针的方式.... 原来可以184K 0MS就解决了...汗...

#include"stdio.h"
main()
{
    char *s1=new char[100001];
    char *s2=new char[100001];
    char *s11,*s22;
    while(scanf("%s %s",s1,s2)!=EOF)
    {
        s11=s1;
        for(s22=s2;*s22;s22++)
            if(*s11==*s22)s11++;

        if(!(*s11))printf("Yes\n");
        else printf("No\n");
    }
}

进一步优化代码 ,呵呵, 还把代码的长度挤进了这道题的Top 10

#include<stdio.h>
main(){char*a=new char[100010],*b=new char[100010];while(scanf("%s%s",a,b)!=-1){char*C=a;for(char*d=b;*d;d++)if(*C==*d)C++;if(*C)printf("No\n");else printf("Yes\n");}}

流牛ζ木马 2007-09-21 02:49 发表评论

ACM PKU 2726 Holiday Hotel

流牛ζ木马 — Thu, 20 Sep 2007 17:35:00 GMT

和PKU1828原理相同;唯一不同的是1828要求的是x>=maxx||y>=maxy ，这道题却相反.
时间复杂度仍然是O(NlogN)

#include"stdio.h"
#include"stdlib.h"

typedef struct{
    int D;
     int C;
}node;
node nodes[10001];

int cmp(const void *pl, const void *pr){   //按照D从小到大排序
    node *p1 = (node*)pl;
     node *p2 = (node*)pr;
     if(p1->D == p2->D)
         return p1->C - p2->C;
    return p1->D - p2->D;
}

int main(){
     int num,i;
     while(scanf("%d",&num) && num){
         for(int i=0;i<num;i++)
             scanf("%d%d",&nodes[i].D,&nodes[i].C);
         qsort(nodes, num, sizeof(node), &cmp); //按照D从小到大排序

       int total=1;
         int min=nodes[0].C;
        for(i=1;i<=num-1;i++){
             if(min>nodes[i].C){
                min=nodes[i].C;
                 total++;
             }
         }
         printf("%d\n",total);
     }
     return 0;
}

流牛ζ木马 2007-09-21 01:35 发表评论

ACM PKU 1828 Monkeys' Pride

流牛ζ木马 — Thu, 20 Sep 2007 17:14:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1828
看了discuss,很多同学对题意理解有误(刚开始我也理解错了)
主要是这句:If a monkey lives at the point (x0, y0), he can be the king only if there is no monkey living at such point (x, y) that x>=x0 and y>=y0

成为猴王的条件是,没有任何的一个猴子的x坐标和y坐标都大于它,而不是说猴王的x和y都要最大.
ok,算法也出来了,简单地说: 先对x快速排序,然后统计y , 时间效率是O（n^lgn）
具体细节要自己体会,这题挺经典的.另外快速排序的方法,虽然我也不是第一次用到了,但是仍然不熟练,到网上查了语法再做的.

#include"stdio.h"
#include"stdlib.h"

typedef struct{
    int x;
     int y;
}node[50001];

int cmp(const void *pl, const void *pr){   /**////按照x从小到大排序
    node *p1 = (node*)pl;
     node *p2 = (node*)pr;
     if(p1->x == p2->x)
         return p1->y - p2->y;
    return p1->x - p2->x;
}

void main(){
     int num,i,total,maxy;
     while(scanf("%d",&num) && num){
         for(i=0;i<num;i++)
             scanf("%d%d",&nodes[i].x,&nodes[i].y);
         qsort(nodes, num, sizeof(node), &cmp); //按照x从小到大排序
       total=1;           //最后一个猴子的x最大,所以至少有一个猴王. 往前扫描,如果出现某个猴子的y大于当前最大y,total+1
         maxy=nodes[num-1].y;
        for(i=num-2;i>=0;i--){
             if(maxy<nodes[i].y){
                maxy=nodes[i].y;
                 total++;
             }
         }
         printf("%d\n",total);
     }
     return;
}

另外,在PKU上编译器效率的问题:

同样的程序,我测试了3次.
include的时候,如果用iostream,在 C++编译器下测试,Memory是476K ,时间280MS
换成 stdio.h + stdlib.h ,在C编译器下Memory是464K ,时间171MS
如果是stdio.h + stdlib.h在C++的编译器下测试呢?Memory是464K ,时间155MS

也就是说,同样的测试数据,要达到最好的效率,应该用纯C的方式写程序,并选择C++编译器judge程序.

流牛ζ木马 2007-09-21 01:14 发表评论

七种qsort排序方法

流牛ζ木马 — Thu, 20 Sep 2007 16:33:00 GMT

七种qsort排序方法

<本文中排序都是采用的从小到大排序>
一、对int类型数组排序
程序代码程序代码
int num[100];
Sample:
int cmp ( const void *a , const void *b )
{
     return *(int *)a - *(int *)b;
}
qsort(num,100,sizeof(num[0]),cmp);

二、对char类型数组排序（同int类型）
程序代码程序代码
char word[100];
Sample:
int cmp( const void *a , const void *b )
{
    return *(char *)a - *(char*)b;
}
qsort(word,100,sizeof(word[0]),cmp)

三、对double类型数组排序（特别要注意）
程序代码程序代码
double in[100];
int cmp( const void *a , const void *b )
{
    return *(double *)a > *(double *)b ? 1 : -1;
} qsort(in,100,sizeof(in[0]),cmp)；

四、对结构体一级排序
程序代码程序代码
struct In {
double data;
int other;
}s[100]
//按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种，
参考上面的例子写
int cmp( const void *a ,const void *b)
{
     return (*(In *)a).data > (*(In *)b).data ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),cmp);

五、对结构体二级排序
程序代码程序代码
struct In {
   int x; int y;
}s[100];
//按照x从小到大排序，当x相等时按照y从大到小排序
int cmp( const void *a , const void *b )
{
    struct In *c = (In *)a;
    struct In *d = (In *)b;
    if(c->x != d->x) return c->x - d->x;
    else return d->y - c->y;
}
qsort(s,100,sizeof(s[0]),cmp);

六、对字符串进行排序
程序代码程序代码
struct In {
   int data; char str[100];
}s[100];
//按照结构体中字符串str的字典顺序排序
int cmp ( const void *a , const void *b )
{
    return strcmp( (*(In *)a)->str , (*(In *)b)->str );
}
qsort(s,100,sizeof(s[0]),cmp);

七、计算几何中求凸包的cmp
程序代码程序代码
int cmp(const void *a,const void *b)
//重点cmp函数，把除了1点外的所有点，旋转角度排序
{
    struct point *c=(point *)a;
    struct point *d=(point *)b;
    if( calc(*c,*d,p[1]) < 0) return 1;
    else if( !calc(*c,*d,p[1])
   && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y))
   //如果在一条直线上，则把远的放在前面
   return 1; else return -1;
}

PS: 其中的qsort函数包含在的头文件里，strcmp包含在的头文件里

流牛ζ木马 2007-09-21 00:33 发表评论

ACM PKU 1775 Sum of Factorials 又是一个做男人不容易系列

流牛ζ木马 — Thu, 20 Sep 2007 15:03:00 GMT

刚那到题目时以为是搜索题,分析一下又觉得是动归或者记忆化搜索...
其实都不是的,是一道白痴题.
题目中的陷阱很多, 做男人就是不容易啊,没有女孩子细心,我竟然为它的每一个陷阱都贡献了一个以上WA..
以下是题目中较生猛陷阱,需要细心的:
.
The input is terminated by a line with a negative integer   (习惯上会认为以-1结束)
For a given n, you'll check if there are some xi, and let n equal to Σ_1<=i<=tx_i!. (t >=1 1, xi >= 0, xi = xj iff. i = j). 这个条件..太强悍了..关于0时是YES还是NO的问题,我贡献了3个WA才看清!

代码如下
:

#include"stdio.h"

int fun(int x)
{

    int temp=1;
    int y=1;
    while(y<=x)
    {
        temp=temp*y;
        y++;

    }
    return temp;

}

void main()
{

    int n;
    int i;
    int a[12];


    for(i=0;i<=11;i++)
        a[i]=fun(i);

    while(1)
    {
    scanf("%d",&n);
    if(n==0){printf("NO\n");continue;}
    if(n<0)return;

        i=11;
        while(i>=0&&n>=0)
        {
            if(n>=a[i])n=n-a[i];
            i--;
        }
        if(n==0)printf("YES\n");
        else printf("NO\n");

    }
    return ;
}

流牛ζ木马 2007-09-20 23:03 发表评论

ACM PKU 1731 Orders STL最基本应用

流牛ζ木马 — Thu, 20 Sep 2007 13:58:00 GMT

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    string str;
    while(cin>>str)
    {
        sort(&str[0],&str[0]+str.length());//先排序
        cout<<str<<endl;//输出排序后的
        while(next_permutation(&str[0],&str[0]+str.length()))
        {
            cout<<str<<endl;
        }
    }
    return 0;
}

流牛ζ木马 2007-09-20 21:58 发表评论

ACM PKU 2105 IP Address 简单题，读数据时细心

流牛ζ木马 — Thu, 20 Sep 2007 10:10:00 GMT

#include"stdio.h"

int fun(int m,int n)
{
    int i;
    if(n==0)return m;
    for(i=1;i<=n;i++)
        m*=2;

    return m;
}

void main()
{
    int T;
    int i;
    char b[33];
    int a[33];
    char temp;
    int p1,p2,p3,p4;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",b);
        p1=0;
        p2=0;
        p3=0;
        p4=0;
        for(i=0;i<32;i++)
        {
            a[i+1]=(b[i]-'0');
        }


        for(i=1;i<=8;i++)
        p1+=fun(a[i],8-i);

        for(i=9;i<=16;i++)
        p2+=fun(a[i],16-i);

            for(i=17;i<=24;i++)
            p3+=fun(a[i],24-i);

                for(i=25;i<=32;i++)
            p4+=fun(a[i],32-i);

     printf("%d.%d.%d.%d\n",p1,p2,p3,p4);

    }

}

流牛ζ木马 2007-09-20 18:10 发表评论

ACM PKU 1663 Number Steps 小学数奥...

流牛ζ木马 — Wed, 19 Sep 2007 06:15:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1663
经过分析,得到以下规律

n              x , y

n%4==0 n/2,n/2
n%4==1 (n+1)/2,(n+1)/2
n%4==2 (n+2)/2,(n+2)/2-2
n%4==3 (n+1)/2+1,(n+1)/2-1
一次ac

Source

Problem: 1663  User: lnmm
Memory: 72K  Time: 15MS
Language: C++  Result: Accepted

#include"stdio.h"
void main()
{
    int T;
    int m;
    int x,y;
    int temp;
    scanf("%d",&T);
    {
        for(m=0;m<T;m++)
        {
            temp=-1;
            scanf("%d%d",&x,&y);
            if(x==y)
            {
                if(x*2%4==0)temp=x*2;
                if((x*2-1)%4==1)temp=x*2-1;

            }
            else
            {
                if((x==y+2)&&(x*2-2)%4==2)temp=x*2-2;
                if((x==y+2)&&((x-1)*2-1)%4==3)temp=(x-1)*2-1;
            }
            if(temp==-1)printf("No Number\n");
            else printf("%d\n",temp);

        }

    }
}

流牛ζ木马 2007-09-19 14:15 发表评论

ACM PKU 1658 Eva's Problem 弱智题

流牛ζ木马 — Wed, 19 Sep 2007 05:56:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1658

#include"stdio.h"

void main()
{
    int n;
    long a[5];
    int i,j;
    scanf("%d",&n);
for(j=0;j<n;j++)
{
    for(i=0;i<4;i++)
    {
      scanf("%ld",&a[i]);
      printf("%ld ",a[i]);
    }
    if(a[3]/a[2]==a[2]/a[1]&&a[1]/a[0]==a[2]/a[1])printf("%d\n",a[3]*a[3]/a[2]);
    else printf("%d\n",a[3]+a[3]-a[2]);

}
}

流牛ζ木马 2007-09-19 13:56 发表评论

ACM PKU 1597 Uniform Generator 数论

流牛ζ木马 — Tue, 18 Sep 2007 17:16:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1597
初看题目时,让人很有想使用暴力的冲动.
细想,其实是很容易的数论问题

#include"stdio.h"
void main()
{
long m,n,k,i;
while(scanf("%ld%ld",&m,&n)!=-1)
{ printf("%10ld%10ld    ",m,n);
    k=1;
for(i=2;i<=(m>n?n:m);i++)
{
if(m%i==0&&n%i==0)
k=i;
}
if(k==1)
     printf("Good Choice\n\n");
        else
            printf("Bad Choice\n\n");

}
}

流牛ζ木马 2007-09-19 01:16 发表评论

求助 ACM PKU 1595 Prime Cuts 做男人不容易啊,需要细心

流牛ζ木马 — Tue, 18 Sep 2007 16:55:00 GMT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1595
做男人不容易啊,需要细心,说来丢脸，这道题调试了50分钟才过。。。。
刚开始题目意思都理解有偏差，到最后判断条件又写得不对。。。唉，，太粗心了
代码如下

Source

Problem: 1595  User: lnmm
Memory: 92K  Time: 15MS
Language: C++  Result: Accepted

#include"stdio.h"
#include"math.h"
int p[2001];

void main()
{
    int n,c,n1;
    int i,j;
    int tol;
    int flag;
    while(scanf("%d%d",&n,&c)!=-1)
    {


        p[1]=1;
        tol=1;
        for(i=2;i<=3000;i++)
        {
            flag=1;
           for(j=2;j<=sqrt(i);j++)
           {
               if(i%j==0){flag=0;break;}
           }
         if(flag==0)continue;
         else if(i>n)break;
         else
         {
             tol++;
             p[tol]=i;

         }

        }


        //此时质数的个数是tol,第一个质数是1
        printf("%d %d:",n,c);
        if(tol%2==0&&tol>=c*2)
        {
            for(i=1;i<=c*2;i++)
            {
                j=(tol-c*2)/2;
                printf(" %d",p[j+i]);

            }
            printf("\n\n");
        }

        if(tol%2==0&&tol<c*2)
        {
            for(j=1;j<=tol;j++)
                printf(" %d",p[j]);
            printf("\n\n");
        }

        if(tol%2==1&&tol>=c*2-1)
        {
            for(i=1;i<=c*2-1;i++)
            {
                j=(tol-c*2+1)/2;
                printf(" %d",p[i+j]);
            }
                printf("\n\n");
        }

        if(tol%2==1&&tol<c*2-1)
        {
            for(j=1;j<=tol;j++)
            {
                printf(" %d",p[j]);
            }
                printf("\n\n");
        }

    }
}

流牛ζ木马 2007-09-19 00:55 发表评论

ACM PKU 1579 Function Run Fun 记忆化搜索

流牛ζ木马 — Tue, 18 Sep 2007 15:21:00 GMT

Source

Problem: 1579  User: lnmm
Memory: 108K  Time: 0MS
Language: C++  Result: Accepted

#include"stdio.h"
int s[21][21][21];

int w(int a,int b,int c)
{
    if(a<=0||b<=0||c<=0) return 1;
    else if(a>20||b>20||c>20) return w(20,20,20);
    else if(s[a][b][c]>0) return s[a][b][c];
    else if(a<b&&b<c) s[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    else s[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);

    return s[a][b][c];
}

void main()
{
    int a,b,c;
    int k;
    int o,p,q;
    while(scanf("%d%d%d",&a,&b,&c)&&(a!=-1||b!=-1||c!=-1))
    {
        for(o=0;o<21;o++)
            for(p=0;p<21;p++)
                for(q=0;q<21;q++)
                    s[o][p][q]=-1;

        k=w(a,b,c);
        printf("w(%d, %d, %d) = %d\n",a,b,c,k);
    }
return;
}

这道题直接递归显然是TLE的.
记忆化搜索就是好啊,呵呵,有固定模式了,解题就是快.
不过要切忌粗心.

流牛ζ木马 2007-09-18 23:21 发表评论

ACM PKU 1552 Doubles 简单题

流牛ζ木马 — Tue, 18 Sep 2007 14:20:00 GMT

#include "stdio.h"
int a[16];
int n;

int solve(int n)
{
    int k=0;
    int i,j;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
          if(a[j]==2*a[i])k++;
    }
        return k;
}

void main()
{
    int temp;

    while(1)
    {
     n=0;
    while(scanf("%d",&a[n])&&a[n]!=0&&a[n]!=-1)n++;
        if(a[n]==-1)return;
        temp=solve(n);
        printf("%d",temp);
        printf("\n");
    }
}

流牛ζ木马 2007-09-18 22:20 发表评论

ACM PKU 1547 Clay Bully 简单题

流牛ζ木马 — Tue, 18 Sep 2007 13:47:00 GMT

#include "stdio.h"
int a[9],b[9],c[9];
int T;
int i,j;
char name[9][256];

int max(int n)
{
    int i,j,k;
    int temp=0;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(a[i]*b[i]*c[i]>temp)
            {   k=i;
                temp=a[i]*b[i]*c[i];
            }
    return k;
}

int min(int n)
{
    int i,j,k;
    int temp=32767;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(a[i]*b[i]*c[i]<temp)
            {
                temp=a[i]*b[i]*c[i];
                   k=i;
            }
    return k;
}

void main()
{


    while(scanf("%d",&T)&&T!=-1)
    {

        for(i=0;i<T;i++)
            scanf("%d%d%d%s",&a[i],&b[i],&c[i],name[i]);

        printf("%s took clay from %s.\n",name[max(T)],name[min(T)]);


    }

}

流牛ζ木马 2007-09-18 21:47 发表评论

C++博客-AClayton's ACM/ICPC Life 只切菜题 菜鸟乱飞

腾讯2009年重庆笔试附加题

在微软亚洲研究院实习，暂停做算法。实习生活博客http://sixsix.net.ms

ACM PKU 1915 Knight Moves 典型的宽度优先搜索 BFS

ACM PKU 3356 AGTC 简单动态规划-仿最长公共子序列

ACM PKU 1458 Common Subsequence 经典且简单动态规划

ACM PKU 3420 Quad Tiling 很难的动态规划,需要灵活应用矩阵`

ACM PKU 2663 Tri Tiling 简单的动态规划 有趣

ACM PKU 1887 Testing the CATCHER 最长下降(上升)子序列 一维动态规划

ACM PKU 1054 The Troublesome Frog 学会剪枝

ACM PKU 1543 Perfect Cubes 简单题,简单剪枝

ACM PKU 1013 Counterfeit Dollar 以前做了很久都没ａｃ的简单题

ACM PKU 2080 Calendar 日期处理典型题目

ACM PKU 1629 Fillword 纯字母字符串的处理和计数典型题

ACM PKU 1565 Skew Binary 简单题

ACM PKU 1298 The Hardest Problem Ever 小小的难点：传递字符串参数

ACM PKU 1226 Substrings 较复杂字符串操作（但不繁琐）

ACM PKU 1002 487-3279 较复杂字符串比较操作

ACM PKU 1323 Game Prediction 贪心算法

ACM PKU 1147 Binary codes 好狡猾的题...强烈推荐 值得反复思考

ACM PKU 1695 Magazine Delivery 三维动态规划

ACM PKU 1163 The Triangle 简单的动态规划就像是APM小于等于100的WAR3玩家

ACM PKU 1028 Web Navigation 字符串数组处理

ACM PKU 1562 Oil Deposits 深度优先搜索

ACM PKU 2244 Eeny Meeny Moo 约瑟夫问题

ACM PKU 1160 Post Office 经典动态规划

ACM PKU 1953 World Cup Noise

ACM PKU 1936 All in All 字符串处理

ACM PKU 2726 Holiday Hotel

ACM PKU 1828 Monkeys' Pride

七种qsort排序方法

ACM PKU 1775 Sum of Factorials 又是一个做男人不容易系列

ACM PKU 1731 Orders STL最基本应用

ACM PKU 2105 IP Address 简单题，读数据时细心

ACM PKU 1663 Number Steps 小学数奥...

ACM PKU 1658 Eva's Problem 弱智题

ACM PKU 1597 Uniform Generator 数论

求助 ACM PKU 1595 Prime Cuts 做男人不容易啊,需要细心

ACM PKU 1579 Function Run Fun 记忆化搜索

ACM PKU 1552 Doubles 简单题

ACM PKU 1547 Clay Bully 简单题

C++博客-AClayton's ACM/ICPC Life 只切菜题菜鸟乱飞

ACM PKU 2663 Tri Tiling 简单的动态规划有趣

ACM PKU 1887 Testing the CATCHER 最长下降(上升)子序列一维动态规划

ACM PKU 1054 The Troublesome Frog　　学会剪枝

ACM　PKU 1013 Counterfeit Dollar 以前做了很久都没ａｃ的简单题

ACM PKU 1298 The Hardest Problem Ever 　小小的难点：传递字符串参数

ACM　PKU 1226 Substrings　较复杂字符串操作（但不繁琐）

ACM PKU 1147 Binary codes 好狡猾的题...强烈推荐值得反复思考

ACM　PKU　1695　Magazine Delivery　三维动态规划