SPOJ classical 第55版的一套题，Argentinian Programming Tournament（阿根廷编程竞赛），直接给度娘翻译竟然会被识别成葡萄牙语
TAP2013A On the side of the road
一个笛卡尔坐标系上（第一象限上）有很多棕榈树，一个人在X轴上走，问他能看到多少种数量的棕榈树（这个人可以位于X轴上的所有位置）
Solution：枚举两个点，作一条直线，求出这条直线和X轴的交点，分数表示，排序后统计一下
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int n,m,i,j,k,ans,num;
long long a[1005],b[1005],tmp;
bool app[1005];
struct node
{
long long a,b;
int c;
}t[1000005];
long long gcd(long long a,long long b){if(!b)return a;return gcd(b,a%b);}
inline bool cmp(const node &a,const node &b)
{
if(a.a!=b.a)return a.a<b.a;
if(a.b!=b.b)return a.b<b.b;
return a.c<b.c;
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;++i)scanf("%I64d%I64d",&a[i],&b[i]);
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
if(b[i]!=b[j])
{
++m;
t[m].a=a[i]*(b[i]-b[j])-b[i]*(a[i]-a[j]);
t[m].b=b[i]-b[j];
tmp=gcd(t[m].a,t[m].b);
t[m].a/=tmp;
t[m].b/=tmp;
if(t[m].b<0)t[m].b=-t[m].b,t[m].a=-t[m].a;
if(b[i]>b[j])t[m].c=i;else t[m].c=j;
}
sort(t+1,t+m+1,cmp);
num=0;
for(i=1;i<=m;++i)
if(i==1||t[i].a!=t[i-1].a||t[i].b!=t[i-1].b)
{
if(!app[num])++ans,app[num]=true;
num=1;
}else
{
if(t[i].c!=t[i-1].c)++num;
}
if(!app[num])++ans;
printf("%d\n",ans);
}
TAP2013B Elections(tutorial)
一个人能当选总统的条件是：得票比其他人高；得票占总票数45%以上or(得票占总票数45%以上and得票比其他的任何人都高总票数的10%以上)。问能否选出总统
Solution：模拟。（怪不得这道题只能是tutorial）
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int n,i,j,k,Max1,Max2,a,sum;
int main()
{
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d",&a);
if(a>=Max1)Max2=Max1,Max1=a;
else if(a>Max2)Max2=a;
sum+=a;
}
if(Max1*100>=sum*45||(Max1*100>=sum*40&&(Max1-Max2)*10>=sum))
printf("1\n");else printf("2\n");
}
TAP2013C Little Red-Cap
给出一张DAG，每个点的权值是这个点到终点的路径条数，求权值最大的路径的权值
Solution：在DAG上DP
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int n,m,i,j,k,u,v;
int son[100005],next[100005],ed[100005];
long long num[100005],ans[100005];
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)
{
scanf("%d%d",&u,&v);
next[i]=son[u];son[u]=i;ed[i]=v;
}
num[n]=1;
for(i=n;i>=1;--i)
for(j=son[i];j;j=next[j])
num[i]+=num[ed[j]];
for(i=2;i<=n;++i)ans[i]=-1;
for(i=1;i<=n;++i)
if(ans[i]>=0)
{
ans[i]+=num[i];
for(j=son[i];j;j=next[j])
if(ans[i]>ans[ed[j]])
ans[ed[j]]=ans[i];
}
printf("%I64d\n",ans[n]);
}
TAP2013D Watching the game
一个环上，每个点有一种颜色，修改一个点后询问这个点顺时针和逆时针与它最近的颜色相同的点的距离
Solution：把序列平摊再倍长，线段树维护
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int n,m,F,i,j,k,a,b,c,aim,ll,rr,ans_Max,ans_Min;
int e[100005];
bool opt;
struct node
{
int l,r,Min,Max;
}t[10000005];
int root[1000005],tot;
void C(int &p,int l,int r)
{
if(!p)p=++tot;
if(l==r)
{
if(opt)t[p].Max=t[p].Min=l;
else t[p].Max=0,t[p].Min=n+n;
return;
}
int mid=l+r>>1;
if(aim<=mid)C(t[p].l,l,mid);
else C(t[p].r,mid+1,r);
t[p].Max=0;t[p].Min=n+n;
if(t[p].l)
{
if(t[t[p].l].Max>t[p].Max)t[p].Max=t[t[p].l].Max;
if(t[t[p].l].Min<t[p].Min)t[p].Min=t[t[p].l].Min;
}if(t[p].r)
{
if(t[t[p].r].Max>t[p].Max)t[p].Max=t[t[p].r].Max;
if(t[t[p].r].Min<t[p].Min)t[p].Min=t[t[p].r].Min;
}
}
void Q(int p,int l,int r)
{
if(!p)return;
if(l>=ll&&r<=rr)
{
if(t[p].Max>ans_Max)ans_Max=t[p].Max;
if(t[p].Min<ans_Min)ans_Min=t[p].Min;
return;
}
int mid=l+r>>1;
if(rr<=mid)Q(t[p].l,l,mid);
else if(ll>mid)Q(t[p].r,mid+1,r);
else Q(t[p].l,l,mid),Q(t[p].r,mid+1,r);
}
int main()
{
scanf("%d%d",&n,&F);
scanf("%d%d%d",&a,&b,&c);
e[1]=a;
for(i=2;i<=n;++i)e[i]=((long long)e[i-1]*b+c)%F;
for(i=1;i<=n;++i)
{
opt=true;
aim=i;C(root[e[i]],1,n+n);
aim=i+n;C(root[e[i]],1,n+n);
}
scanf("%d",&m);
for(;m;--m)
{
scanf("%d",&i);
opt=false;
aim=i;C(root[e[i]],1,n+n);
aim=i+n;C(root[e[i]],1,n+n);
scanf("%d",&e[i]);
opt=true;
aim=i;C(root[e[i]],1,n+n);
aim=i+n;C(root[e[i]],1,n+n);
ll=i+1;rr=i+n-1;
ans_Max=i;ans_Min=i+n;
Q(root[e[i]],1,n+n);
printf("%d %d\n",i+n-ans_Max,ans_Min-i);
}
}
TAP2013E Escaping from escaping
给出一个01串，询问没有出现过的最短的子串的长度
Solution：Hash判断
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
int T,t,l,i,j,k,ans,tot;
char s[100005];
int app[1000005];
unsigned int sum[100005];
int main()
{
scanf("%d",&T);
for(;T;--T)
{
scanf("%s",s+1);
l=strlen(s+1);
for(i=1;i<=l;++i)sum[i]=sum[i-1]*2+s[i]-'0';
for(tot=2,ans=1;tot<=l;tot*=2,++ans)
{
k=0;++t;
for(i=ans;i<=l;++i)
if(app[sum[i]-sum[i-ans]*(1<<ans)]!=t)
{
app[sum[i]-sum[i-ans]*(1<<ans)]=t;
++k;
}
if(k<tot)break;
}
printf("%d\n",ans);
}
}
TAP2013F Flowers of Babylon
笛卡尔坐标系上n个点，求至少覆盖m个点的最小圆半径
Solution：二分答案，每个点扩张成圆，圆两两求交，在圆周上求区间并
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
int T,n,m,i,j,k,shi,tot,sum;
int x[505],y[505];
double l,r,mid,a,d,pi,pi2,u,v;
struct node
{
double x;
int val;
}t[10005];
double Abs(double x){if(x<0)return -x;return x;}
double sqr(double x){return x*x;}
inline bool cmp(const node &a,const node &b)
{
if(a.x!=b.x)return a.x<b.x;
return a.val>b.val;
}
int main()
{
pi=atan2(0,-1);pi2=2*pi;
scanf("%d",&T);
for(;T;--T)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
l=0;r=200000;
for(shi=50;shi;--shi)
{
mid=(l+r)/2;
for(i=1;i<=n;++i)
{
tot=0;
for(j=1;j<=n;++j)
if(sqr(y[j]-y[i])+sqr(x[j]-x[i])<=sqr(2*mid))
{
a=atan2(y[j]-y[i],x[j]-x[i]);
d=acos(sqrt(sqr(y[j]-y[i])+sqr(x[j]-x[i]))/2/mid);
u=a-d+pi;v=a+d+pi;
if(u<0)
{
++tot;t[tot].x=u+pi2;t[tot].val=1;
++tot;t[tot].x=pi2;t[tot].val=-1;
u=0;
}
if(v>pi2)
{
++tot;t[tot].x=0;t[tot].val=1;
++tot;t[tot].x=v-pi2;t[tot].val=-1;
v=pi2;
}
++tot;t[tot].x=u;t[tot].val=1;
++tot;t[tot].x=v;t[tot].val=-1;
}
sort(t+1,t+tot+1,cmp);
sum=0;
for(j=1;j<=tot;++j)
{
sum+=t[j].val;
if(sum>=m)break;
}
if(sum>=m)break;
}
if(i<=n)r=mid;else l=mid;
}
printf("%.4lf\n",mid);
}
}
TAP2013G War
有两支军队要开战，其中一只知道了对方的出场排列，士兵的1V1的，只有力量严格大于对方才能获胜，问最大可能的获胜士兵数
Solution：二分答案，用炮灰解决对方最强的
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int n,i,j,k,l,r,mid,ans;
int A[100005],B[100005];
int main()
{
scanf("%d",&n);
for(i=1;i<=n;++i)scanf("%d",&A[i]);
for(i=1;i<=n;++i)scanf("%d",&B[i]);
sort(A+1,A+n+1);
sort(B+1,B+n+1);
l=0;r=n;
while(l<=r)
{
mid=l+r>>1;
for(i=1;i<=mid;++i)
if(A[i]>=B[n-mid+i])
break;
if(i>mid)l=mid+1,ans=mid;
else r=mid-1;
}
printf("%d\n",ans);
}
TAP2013H Horace and his primes
每次操作把一个数变为它的所有质因子的和，当这个数变为质数时停止，问n∈[A,B]有多少操作k次
Solution：欧拉筛预处理每个数的操作次数，操作次数最大为12，做成前缀和
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int T,n,m,A,B,i,j,k;
int p[1000005],psum[1000005],prime[1000005],tot;
int ans[1000005],sum[1000005][13];
int main()
{
n=1000000;
for(i=2;i<=n;++i)
{
if(p[i]==0)prime[++tot]=p[i]=i;
for(j=1;(prime[j]<=n/i)&&(prime[j]<=p[i])&&(j<=tot);++j)p[prime[j]*i]=prime[j];
}
for(i=2;i<=n;++i)
if(p[i]==p[i/p[i]])psum[i]=psum[i/p[i]];
else psum[i]=p[i]+psum[i/p[i]];
for(i=2;i<=n;++i)ans[i]=ans[psum[i]]+1;
for(i=2;i<=n;++i)
{
for(j=0;j<=12;++j)sum[i][j]=sum[i-1][j];
++sum[i][ans[i]];
}
scanf("%d",&T);
for(;T;--T)
{
scanf("%d%d%d",&A,&B,&m);
if(m<=12)printf("%d\n",sum[B][m]-sum[A-1][m]);
else printf("0\n");
}
}
TAP2013I Treasure Island
一个人在(1,1)要走到(n,m)，走到(i,j)的时间不能超过h[i][j]，问最多能在(1,1)停留多久
Solution：用SPFA算每个位置最迟什么时候开始移动能走到(n,m)
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int n,m,i,j,k,x,y;
int h[505][505],dist[505][505];
int qx[1000005],qy[1000005],l,r;
bool inq[505][505];
void add(int x,int y,int d)
{
if(dist[x][y]>=d)return;
if(dist[x][y]==h[x][y])return;
if(d<=h[x][y])dist[x][y]=d;
else dist[x][y]=h[x][y];
if(inq[x][y])return;
++r;if(r==1000000)r=1;
qx[r]=x;qy[r]=y;inq[x][y]=true;
}
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
scanf("%d",&h[i][j]),--h[i][j];
qx[1]=n;qy[1]=m;l=0;r=1;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
dist[i][j]=-1;
dist[n][m]=h[n][m];
while(l!=r)
{
++l;if(l==1000000)l=1;
x=qx[l];y=qy[l];
inq[x][y]=false;
add(x-1,y,dist[x][y]-1);
add(x+1,y,dist[x][y]-1);
add(x,y-1,dist[x][y]-1);
add(x,y+1,dist[x][y]-1);
}
printf("%d\n",dist[1][1]);
}
TAP2013J Game of stones
有一个博弈游戏，每次把一堆石子分成两堆，不能操作的人输，问n个石子能组成多少先手必胜局面
Solution：奇数石子的sg是0，偶数石子的sg是1，f[i][j]表示i个石子sg是j的方案数，用无限背包转移
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int T,n,i,j,k;
int f[1005][2];
int main()
{
f[0][0]=1;
for(i=1;i<=1000;++i)
{
if(i&1)k=0;else k=1;
for(j=i;j<=1000;++j)
f[j][0]=(f[j][0]+f[j-i][k])%1000000007,
f[j][1]=(f[j][1]+f[j-i][!k])%1000000007;
}
scanf("%d",&T);
for(;T;--T)
{
scanf("%d",&n);
printf("%d\n",f[n][1]);
}
}
评论 (0)
