PKU 2005 ACM Team Exercise 3

小康

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

小康

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

joe_233

小康加油喔^_^

小康

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

小康

谢谢楼上的.
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[111],p[111],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[j]);
                                if(num[j]<k)
                                        k=num[j];
                                if(num[j]>max)
                                        max=num[j];
                        }
                        for (j=0;j<m;j++)
                        {
                                if(num[j]==k) p[j]++;
                                if(num[j]==max) p[j]=-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;

}

小康

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

joe_233

坚持啊~开学大三了吧？

小康

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

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

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

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

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

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

        }       
        if (check(dep+1,x,s)==0)
        {
                m[dep][x]=s;
                return 0;
        }
        if (check(dep-1,x,s)==0)
        {
                m[dep][x]=s;
                return 0;
        }
        if (check(dep,x+1,s)==0)
                {
                m[dep][x]=s;
                return 0;
        }
        if (check(dep,x-1,s)==0)
                {
                m[dep][x]=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[s-65]>0)
                {
                       
                        if(m[y][x]!=\'.\')
                        {
                                deln=0;
                                if (check(y,x,s) ==1)
                                {
                                        j++;
                                        book[books++]=s;
                                        link[s-65]=0;
                                       
                                        break;
                                }else
                                {
                                        for (j=0;j<deln;j++)
                                        {
                                                m[dely[j]][delx]=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[j]!=\'.\' && link[m[j]-65]==0)
                        {
                                //找到某一个块,记录下这个块的一个字符为止就行,link是一个帮助查询的数组
                                x[slen]=j;
                                y[slen]=i;
                                s[slen++]=m[j];
                                link[m[j]-65]=1;
                        }

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

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

小康

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

小康

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

小康

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[j] i表示多少位,j表示为某一个数字
如a1  a2 a3 a4 就是求num[4][a4]
5 a2 a3 a4 就是求 num[4][5]
num[4][5]=num[3][4]+num[3][5]+num[3][6]
是不是有思路了?
这样,即使n=100,也可以很快求出来,而且几乎不用1毫秒.

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

#include<stdio.h>
int main()
{
        int i,j,k,n;
        double add[111][12],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[0]=1;
                add[0][k+1]=0;
                for (i=1;i<n;i++)
                {
                        add[k+1]=0;
                        add[0]=add[i-1][0]+add[i-1][1];
                        for (j=1;j<=k;j++)
                        {
                                add[j]=add[i-1][j-1]+add[i-1][j]+add[i-1][j+1];               
                        }
                }
                total=0;
                for (i=0;i<=k;i++)  total=total+add[n-1];
                printf(\"%0.5lf\\n\",(double)total*100/max);

               
        }
        return 0;
}