论坛 › 【编程】编程圣殿 › PKU 2005 ACM Team Exercise 3

小康 发表于 2005-8-5 22:18

PKU 2005 ACM Team Exercise 3

http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1154
大家聊聊罗

小康 发表于 2005-8-5 22:20

今天11题,我们可以做的有6题,另外G题虽然是图论算法,但也是很典型的二分匹配,实际上,我们应该也做出来.
今天总共做5题.
但多数都是只做了I题

joe_233 发表于 2005-8-5 22:25

小康加油喔^_^

小康 发表于 2005-8-5 22:27

I题很简单,只要搞清楚对应规则就行了,注意"\"的分布情况和我们普通的键盘不大一样.但是我们几个全部都搞了很久才A,这也从一个方面说明我们的编码能力总体不够吧,这么简单的几个对应规则,都有遗忘.
我的代码如下:
#include<stdio.h>
int main()
{
        char c;
        char s={"1VXSWDFGUHJKNBIOXEARYCQZTO"};
        freopen("in.txt","r",stdin);
        while(scanf("%c",&c)!=EOF)
        {
                if(c>='A' && c<='Z')
                {
                        printf("%c",s);
                        continue;
                }
                if(c>='2' && c<='9')
                {
                        printf("%c",c-1);
                        continue;
                }
                if(c=='0')
                        printf("9");
                else if(c=='1') printf("`");
                else if(c=='-') printf("0");
                else if(c=='=') printf("-");
                else if(c=='\\') printf("]");
                else if(c=='[') printf("P");
                else if(c==']') printf("[");
                else if(c==';') printf("L");               
                else if(c==',') printf("M");
                else if(c=='.') printf(",");
                else if(c=='\'') printf(";");
                else if(c=='/') printf(".");
                else if(c==' ') printf("%c",c);
                else if(c==10) printf("%c",c);

                       

        }
        return 0;
}

小康 发表于 2005-8-5 22:31

谢谢楼上的.
F这道题也很简单,但是要注意一句话 and was called as "hardest" by nobody
另外要注意一种输入 1 1 1 1 1 1 1 这样的输出结果是0
还有题目要求separated by spaces,所以最后一个数字后面不能有空格.
这道题因为这些小问题而WR,实在可惜.

#include<stdio.h>
int main()
{
        int i,j,k,n,m,num,p,max;
        freopen("in.txt","r",stdin);
        while(scanf("%d %d",&n,&m)!=EOF)
        {
                for (i=0;i<m;i++) p=0;
                for (i=0;i<n;i++)
                {
                        k=100001;
                        max=-1;
                        for (j=0;j<m;j++)
                        {
                                scanf("%d",&num);
                                if(num<k)
                                        k=num;
                                if(num>max)
                                        max=num;
                        }
                        for (j=0;j<m;j++)
                        {
                                if(num==k) p++;
                                if(num==max) p=-100;
                        }
                        j=j;
                }
                k=n/2+1;
                j=0;
                for (i=0;i<m;i++) if(p>=k)
                {
                        if(j>0) printf(" ");
                        j++;
                        printf("%d",i+1);
                }
                if(j==0) printf("0\n");else printf("\n");

        }
        return 0;

}

小康 发表于 2005-8-5 22:32

D是最长升序,这是很典型的DP问题了.找NOIP初中组好像有过.
我迟点讲详细算法

joe_233 发表于 2005-8-5 22:35

坚持啊~开学大三了吧？

小康 发表于 2005-8-5 22:40

A题是搜索或者说是贪心多一点,不难只是编码起来要认真一点.
由于题目说 unique EnglishLETTER,
所以,最多只有26块.那么我们可以有这样一种思路:
首先,我们找到一种规则,某块是否是"最下面",
我们从这块的每个位置每一列,向下搜索,如果没有遇到其他块,那么这块肯定是先下来的一块.
这样子,我们可以从A开始,找到所有"最下面"中,字母顺序靠前的,我们找到他,记录下他,然后把他从图中去掉,然后我们继续找,找到没有得找,我们就找到答案了.

是不是很容易拉,大家试试.

代码如下,写得不是很好.

#include<stdio.h>
int n,slen,x,y,books,link,head,delx,dely,deln;
char m;
char book,s;

int check(int dep,int x,char s)
{
        int i;       
        if(dep<0 || dep==n || x<0 || x==20) return 1;
        if(m!=s) return 1;
        delx=x;
        dely=dep;
        m='.';

        for (i=dep;i<n;i++)
        if(m==s) break;
        else
                if( m!='.')
        {
                m=s;
                return 0;

        }       
        if (check(dep+1,x,s)==0)
        {
                m=s;
                return 0;
        }
        if (check(dep-1,x,s)==0)
        {
                m=s;
                return 0;
        }
        if (check(dep,x+1,s)==0)
                {
                m=s;
                return 0;
        }
        if (check(dep,x-1,s)==0)
                {
                m=s;
                return 0;
        }
        return 1;
}
int dos(int dep)
{
        int i,j,p,pp;
        do
        {
                j=0;
                for (i=0;i<slen;i++) if (link-65]>0)
                {
                       
                        if(m]]!='.')
                        {
                                deln=0;
                                if (check(y,x,s) ==1)
                                {
                                        j++;
                                        book=s;
                                        link-65]=0;
                                       
                                        break;
                                }else
                                {
                                        for (j=0;j<deln;j++)
                                        {
                                                m]]=s;                                               
                                        }
                                }

                        }

                }
        }
        while(j);       

        return 0;
}
int main()
{
        int i,j,k;
        freopen("in.txt","r",stdin);

        while(scanf("%d",&n)!=EOF)
        {
                getchar();
                slen=0;
                books=0;
                for(i=0;i<26;i++) link=0;
                for (i=0;i<n;i++)
                {
                        scanf("%s",m);                       
                       
                }
                                       
                for (i=n-1;i>=0;i--)
                        for (j=0;j<20;j++) if(m!='.' && link-65]==0)
                        {
                                //找到某一个块,记录下这个块的一个字符为止就行,link是一个帮助查询的数组
                                x=j;
                                y=i;
                                s=m;
                                link-65]=1;
                        }

                for (i=0;i<slen;i++)
                        for (j=i+1;j<slen;j++)if(s<s)
                        {
                                k=x;x=x;x=k;
                                k=y;y=y;y=k;
                                k=s;s=s;s=k;               
                        }

                dos(n-1);
                book=0;
                printf("%s\n",book);               
        }
        return 0;
}

小康 发表于 2005-8-5 22:42

是啊.
大三了,很快又会过去了,感觉这两年浪费了时间,没有学到多少东西.所以好好学习.
哈哈

小康 发表于 2005-8-5 22:57

D题,大家可以搜索 "最长不下降序列"可以找到相关的资料
我们来分析一个数据
7
1 7 3 5 9 4 8
1 2 3 4 5 6 7
int num
num 表示, 从第i到最后一个数字,最长的序列.
这里我们可以发现一个问题, 假设i<j 如3<4,对应的数字3<5,符合这个条件:在3后,数字大于3的还有{5 9 4 8},假设我们已经知道了他们对应的num num num num
我们可以知道,那么num=max(num...num)+1,max为取最大值
为什么可以这么直接快呢,以内num,num,他们后面接什么数,和num的值没有关系,我们只要找到一个最大值就好.
这就是动态规划的无后效性.
1 7 3 5 9 4 8
我们先置
8:num=1
4:num=max(num)+1=2
9:num=max()+1=1
5:num=max(num,num)+1=2
3:num=max(num,num,num,num)+1=3
7:num=max(num,num)+1=2
1:num=max(num,num,num.num,num,num)=4

小康 发表于 2005-8-5 23:07

H题是一道稍微难的题目.
这里我们可以求出简单求出 符合条件的数字的个数/除以所有的数字
所有数字,很好求,(k+1)^n,排列组合的简单知识.
至于求符合条件的数字,可以用搜索,但是由于n=100,k=9答案会比较大.我们要做一个优化.其实这道题的优化思路,也是动态规划,和上次的A差不多.
我们看,一个数, a1 a2 a3 a4 假设我们知道 a1=5,那么,怎么求得第4为5,的数字的个数呢? 我们知道三个就知道了 4 a3 a4 ,5 a3 a5 ,6 a3 a5
我用 num i表示多少位,j表示为某一个数字
如a1a2 a3 a4 就是求num
5 a2 a3 a4 就是求 num
num=num+num+num
是不是有思路了?
这样,即使n=100,也可以很快求出来,而且几乎不用1毫秒.

另外要小心,要用double保存数字.因为题目要求7位精度,所以可以用double保存总数.

#include<stdio.h>
int main()
{
        int i,j,k,n;
        double add,max,total;
        freopen("in.txt","r",stdin);
        while(scanf("%d %d",&k,&n)!=EOF)
        {               
                max=k+1;
                for (i=1;i<n;i++)
                        max=max*(k+1);
               
                for (i=0;i<=k;i++) add=1;
                add=0;
                for (i=1;i<n;i++)
                {
                        add=0;
                        add=add+add;
                        for (j=1;j<=k;j++)
                        {
                                add=add+add+add;               
                        }
                }
                total=0;
                for (i=0;i<=k;i++)total=total+add;
                printf("%0.5lf\n",(double)total*100/max);

               
        }
        return 0;
}

查看完整版本: PKU 2005 ACM Team Exercise 3