聊聊Contest - PKU 2005 ACM Team Exercise 2

小康

http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1153

总共8题，按题目AC人数，我们一组人应该要做上5道题，目前我们做出了4道，
分别事A C F G 还差E

我简单说说A C F G 4题的思路，不对的地方请大家指正

F是我认为的，最简单的。

F的一题，就是求那个多项式的余数。
由于除数只有很简单的两个“单位”x^k+1 x没有系数。我们可以采用一种快速的谈心算法。从被除数最高位起计算到最低位，每次被除数的系数，就是商的系数，这样肯定相减为0，而我们只要计算1×商（注意系数也要），然后加回到被除数就好。这样最后剩下的被除数（k-1为到个位）就是余数

代码如下

#include<stdio.h>
int main()
{
        int num[100000],i,j,k,n,m,u;
        freopen("in.txt","r",stdin);
        while(1)
        {
                scanf("%d %d",&n,&k);
                if(n==-1 && k==-1) break;
                for (i=0;i<=n;i++)
                {
                        scanf("%d",&num);
                }       
               
                for (i=n;i>=k;i--)
                {
                        u=i-k;//除数的1，相对应的被除数               
                        num=num-num;
                        num=0;

                }
                i=n;
                while(i && num==0) i--;                               
                {
                        printf("%d",num[0]);
                        for (j=1;j<=i;j++)
                                printf(" %d",num[j]);
                }
                i=0;
                printf("\n");

        }
        return 0;
}

小康

C也不难，大家都做对了C。
C的做法是标号法
同一组，给一个组号。
如果两个组合并为同一组，就把任意一组的组号全部该为另外一组的。这里要注意些技巧，不好超时，因为最大的数字是n＝5万，很可能会写成o(n*m)＝o(n*n*(n-1)/2),的算法，
我到现在还没有A，不知道为什么，A的请贴贴

小康

G也不难，但是做对的人不多。
如果范围不是1千万，是1百万或者更小，我们可以用标号法，不断覆盖数组上的值。
这道题是1千万，显然要有一个比较好的数据结构，我选用的是一个链表，其中为了加快删除结点速度，我用双向链表。
每贴一张海报，看看是否与前面的海报发生覆盖事件，大概有3种情况
覆盖了一张海报的左边或右边，修改下原来的海报的尺寸
覆盖了海报的中间，海报分为左边右边两部分，那么要新增一个结点，把原来的海报修改为海报的左边，新增海报右边部分到队尾。
完全覆盖了一张海报，删除原来海报
最后做一个统计
我的算法还是比较慢的，有更快的思路请帖出来共享一下

#include<stdio.h>
struct node
{
        int l,r,up,next,num;
} post[100000];
int head,total,tail;
void add(int l,int r,int num)
{
        total++;
        post[total].l=l;
        post[total].r=r;
        post[total].num=num;
        post[total].up=tail;
        post[total].next=0;
        post[tail].next=total;
        tail=total;
}
void del(int k)
{
        int up;
        if(k==head)
                head=post[k].next;
        else if(k==tail)
                tail=post[k].up;
        up=post[k].up;
        post[up].next=post[k].next;
        up=post[k].next;
        post[up].up=post[k].up;
}
int main()
{
        int i,j,k,n,m,num[10000],a,b,l,r;
        head=1;
        freopen(\"in.txt\",\"r\",stdin);
        scanf(\"%d\",&n);
        while(n--)
        {
                scanf(\"%d\",&m);
                for (i=0;i<=m;i++) num=0;
                scanf(\"%d %d\",&a,&b);
                head=1;total=1;tail=1;
                post[1].up=0;post[1].next=0;
                post[1].l=a;post[1].r=b;
                post[1].num=1;
                num[1]=1;
                for (i=1;i<m;i++)
                {
                        scanf(\"%d %d\",&a,&b);
                       
                        j=head;
                        k=tail;
                        add(a,b,i+1);
                        num[i+1]++;
                        while(j<=k)
                        {                               
                                l=post[j].l;
                                r=post[j].r;
                               
                               
                                if(a<=l)
                                {
                                        if(b<r)
                                        {
                                                if(b>=post[j].l)
                                                        post[j].l=b+1;
                                        }else
                                        {               
                                                num[post[j].num]--;
                                                del(j);                                               
                                        }

                                }else if(a<=r)
                                {
                                        if(b>=r)
                                        {
                                                post[j].r=a-1;

                                        }else
                                        {
                                                add(b+1,r,post[j].num);
                                                num[post[j].num]++;
                        post[j].r=a-1;
                                        }
                                }

                                j=post[j].next;
                        }//while

                }//for
                k=0;               
                for (i=1;i<=m;i++) if(num>0) k++;
               
                printf(\"%d\\n\",k);               
        }
        return 0;
}

小康

A题用搜索一点都不难，10分钟可以写一个超时的代码出来。
由于数据太大，我们要做一个优化，我用的是动态规划思想，把重复计算的部分保存下来。
我们看这样一组数据，m=20，n=5，我们会有这些序列
1 2 a1 a2 a3 (a1+a2+a3=17)
1 3 a1 a2 a3  (=16)
4 4 a1 a2 a3(=12)
我们可以发现，对于a2 a3，会重复计算到 (a2=4 a5=x)
1 2 a1 4 a3
1 3 a1 4 a3
1 4 a1 4 a4
那么我们可以定义一个数组，
A[m][f] 表示，两个数字的序列，当首位是f，总数是m，有多少种，
B[m][f] 表示，三个数字的序列，当首位是f，总数是m，有多少种，
A和B存在一种关系
我们看看
假设m＝20 ，我们要求 a1 a2 a3
那么 a1=1,2,3...(int)20/3
我们知道a1,那么，我们可以知道，B[m][a1]=A[m-a1][a1]+A[m-a1][a1+1]......
即， 看一下数列，我们要求1开头的序列的数量，可以发现 1 1 a2 ,1 2 a2,1,3 a2...
而1 a2,2 a2,3 a2 ,他们可以在数组A中求得。
这样有A，就可以求得B，那么，我们可以有B，得到C，接着得到D
我们可以定义一个这样的数组， NUM[1][221][221];
实际上，这个数组还可以压缩，因为求B后，A就不需要用到了
我们得到NUM[11[221][221]后，可以简单的求出答案了。

小康

#include<stdio.h>
int add[11][250][230];
int main()
{
        int i,j,k,a,b,c,cs,n,m,book[11],t,cases;
        freopen(\"in.txt\",\"r\",stdin);
        scanf(\"%d\",&cases);
        while(cases--)
        {
                scanf(\"%d %d %d\",&m,&n,&cs);               
                for (c=1;c<3;c++)
                for (i=0;i<=m;i++)
                        for (j=0;j<=m;j++)
                                add[c][j]=0;
                for (i=1;i<=m;i++)
                {                       
                        add[1]=1;
                       
                       
                }
                if(i>1)
                {
                        for (j=1;j<=m;j++)
                        {
                                k=1;
                                while(k+k<=j)
                                {
                                        add[2][j][k]=1;
                                        k++;
                                }
                        }

                }
                for (i=3;i<=n;i++)
                {
                       
                        for(j=i;j<=m;j++)
                        {
                                for (k=1;k*i<=j;k++)
                                {
                                        add[j][k]=0;
                                        a=k;
                                        while( j-k>=a*(i-1))
                                        {
                                                add[j][k]+=add[i-1][j-k][a];
                                                a++;
                                        }
                                        a=k;
                                }
                        }
                }
                i=n;
                k=1;
                j=m;
                book[1]=m;
                while(i>1)
                {                               
                       
                       
                        t=add[j][k];
                        while( t<cs && k*i<=j)
                        {                               
                                k++;                       
                                t+=add[j][k];
                        }
                        book=k;
                        book[1]-=k;
                       
                                                                       

                                t-=add[j][k];
                                                                j-=k;
                                cs-=t;
                       
                        i--;
                       
                }
                i=n;
                for (i=n;i>0;i--)
                {
                        j=book;
                        printf(\"%d\\n\",j);
                }
               
               
        }

        return 0;

}

小康

在大象同学的启发下，想出了E的做法，至此，我们完成了5道题，能完成5道题的帐号有32个，不过我们是超时的。
E中，如果输入的点数是1，那么很简单，是中心点是自己，如果点数是偶数，
我们把所有的点的，x，y坐标分别加起来，肯定为他中心点的n/2倍。
这个很容易证明。假设有n/2对，那么这些点肯定是不重复的，任意一对点的x坐标的和的1/2为中心点，那么把所有的点加起来，不就正好是n/2倍吗。

如果是奇数点，那么我们可以找到肯定有一个技术点为中心点，不然我们可以马上知道无解。然后加上这个点，当作偶数点进行处理。
接下来知道中心点的坐标，我们就可以很快搜索了。

我们找一个为匹配的点，搜寻其他未匹配的点，判断他们的和的n/2倍，是否为中心点的n/2倍，如果是，则寻找下一个点

代码如下

#include<stdio.h>
int x[11111],y[11111];

int main()
{
        int i,j,k,n,maxx,maxy,m,mx,my,f,book[11111],mm;
        freopen(\"in.txt\",\"r\",stdin);
        i=10000000000;
        scanf(\"%d\",&n);
        while(n--)
        {
                scanf(\"%d\",&m);               
                maxx=maxy=0;
                for (i=0;i<m;i++)
                {
                        scanf(\"%d %d\",&x,&y);
                        maxx+=x;
                        maxy+=y;
                }

                if(n==1)
                {
                        printf(\"yes\\n\");
                        continue;
                }
               
                f=0;
                mm=m/2;
                for (i=0;i<m;i++) book=0;
                if((m&1)==1)
                {
                        for (i=0;i<m;i++) if(x*m==maxx && y*m==maxy)
                                break;
                        book=1;
                        if(i==m)
                        {
                                printf(\"no\\n\");
                                continue;
                        }
                        maxx-=x;
                        maxy-=y;

                }

                for (i=0;i<m;i++) if(book==0)
                {
                        for (j=i+1;j<m;j++) if(book==0)
                        {
                                k=x+x[j];
                                if(k*mm!=maxx) continue;
                                k=y+y[j];
                                if(k*mm!=maxy) continue;
                                book=1;
                                book[j]=1;
                                break;
                        }
                        if(j==m) break;
                       
                }
                if(i==m)
                        printf(\"yes\\n\");
                else
                        printf(\"no\\n\");
               
        }
        return 0;


}