聊聊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,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);
for (j=1;j<=i;j++)
printf(" %d",num);
}
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;
int head,total,tail;
void add(int l,int r,int num)
{
total++;
post.l=l;
post.r=r;
post.num=num;
post.up=tail;
post.next=0;
post.next=total;
tail=total;
}
void del(int k)
{
int up;
if(k==head)
head=post.next;
else if(k==tail)
tail=post.up;
up=post.up;
post.next=post.next;
up=post.next;
post.up=post.up;
}
int main()
{
int i,j,k,n,m,num,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.up=0;post.next=0;
post.l=a;post.r=b;
post.num=1;
num=1;
for (i=1;i<m;i++)
{
scanf(\"%d %d\",&a,&b);
j=head;
k=tail;
add(a,b,i+1);
num++;
while(j<=k)
{
l=post.l;
r=post.r;
if(a<=l)
{
if(b<r)
{
if(b>=post.l)
post.l=b+1;
}else
{
num.num]--;
del(j);
}
}else if(a<=r)
{
if(b>=r)
{
post.r=a-1;
}else
{
add(b+1,r,post.num);
num.num]++;
post.r=a-1;
}
}
j=post.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 表示，两个数字的序列，当首位是f，总数是m，有多少种，
B 表示，三个数字的序列，当首位是f，总数是m，有多少种，
A和B存在一种关系
我们看看
假设m＝20 ，我们要求 a1 a2 a3
那么 a1=1,2,3...(int)20/3
我们知道a1,那么，我们可以知道，B=A+A......
即， 看一下数列，我们要求1开头的序列的数量，可以发现 1 1 a2 ,1 2 a2,1,3 a2...
而1 a2,2 a2,3 a2 ,他们可以在数组A中求得。
这样有A，就可以求得B，那么，我们可以有B，得到C，接着得到D
我们可以定义一个这样的数组， NUM;
实际上，这个数组还可以压缩，因为求B后，A就不需要用到了
我们得到NUM后，可以简单的求出答案了。 #include<stdio.h>
int add;
int main()
{
int i,j,k,a,b,c,cs,n,m,book,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=0;
for (i=1;i<=m;i++)
{
add=1;
}
if(i>1)
{
for (j=1;j<=m;j++)
{
k=1;
while(k+k<=j)
{
add=1;
k++;
}
}
}
for (i=3;i<=n;i++)
{
for(j=i;j<=m;j++)
{
for (k=1;k*i<=j;k++)
{
add=0;
a=k;
while( j-k>=a*(i-1))
{
add+=add;
a++;
}
a=k;
}
}
}
i=n;
k=1;
j=m;
book=m;
while(i>1)
{
t=add;
while( t<cs && k*i<=j)
{
k++;
t+=add;
}
book=k;
book-=k;
t-=add;
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,y;
int main()
{
int i,j,k,n,maxx,maxy,m,mx,my,f,book,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;
if(k*mm!=maxx) continue;
k=y+y;
if(k*mm!=maxy) continue;
book=1;
book=1;
break;
}
if(j==m) break;
}
if(i==m)
printf(\"yes\\n\");
else
printf(\"no\\n\");
}
return 0;
}
页:
[1]