Stilwell's Blog

SPOJ classical 第59版的一套题，来源不明  Insomnia=失眠？

---

INS14A  BSTRING

给出一个01串，每次可以交换相邻的元素，问最小交换次数使有M个1相邻

Solution：最优解肯定是一段1往这段1的中位数方向移动，维护一个队列计算

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

int T,n,m,i,j,k;
int q[50005],l,r;
char s[50005];
long long ans,tmp,lnum,rnum,L,R;

int main()
{
	scanf("%d",&T);
	for(;T;--T)
	{
		scanf("%d",&m);
		scanf("%s",s+1);
		n=strlen(s+1);
		l=1;r=0;
		for(i=1;i<=n;++i)
		if(s[i]=='1')
		{
			q[++r]=i;
			if(r==m)break;
		}
		k=1+m>>1;L=R=0;
		for(j=1;j<k;++j)L+=q[j];
		for(j=k+1;j<=m;++j)R+=q[j];
		lnum=k-1;rnum=m-k;
		ans=lnum*q[k]-L+R-rnum*q[k];
		for(++i;i<=n;++i)
		if(s[i]=='1')
		{
			q[++r]=i;
			L-=q[l++];L+=q[k++];
			R-=q[k];R+=q[r];
			tmp=lnum*q[k]-L+R-rnum*q[k];
			if(tmp<ans)ans=tmp;
		}
		ans-=(lnum+1)*lnum/2+(rnum+1)*rnum/2;
		printf("%lld\n",ans);
	}
}

---

INS14B  TRISQRS

把一个n*n的正方形切成若干大小相同且面积是整数的直角三角形，问切出的个数有几种

Solution：枚举n*n的约数进行判断

#include <stdio.h>
#include <stdlib.h>
using namespace std;

int T,N,n,i,j,k,ans;

void check(int x){if((N/x)%2==0)++ans;}

int main()
{
	scanf("%d",&T);
	for(;T;--T)
	{
		scanf("%d",&n);
		N=n*n;ans=0;
		for(i=1;i<=n;++i)
		if(N%i==0)
		{
			check(i);
			if(i!=n)check(N/i);
		}
		printf("%d\n",ans);
	}
}

---

INS14C  Digo plays with Numbers

给出一个01串，两个人开始博弈，两人轮流删去串中的一个数，知道串长为M，一个人希望最后的数尽量小，一个人希望最后的数尽量大

Solution：显然的贪心，要使这个数尽量小就先取高位的1，希望这个数尽量大就先取高位的0

#include <stdio.h>
#include <stdlib.h>
using namespace std;

int T,n,m,i,j,k,w1,w2;
char s[1005];
bool del[1005],f1,f2;

int main()
{
	scanf("%d",&T);
	for(;T;--T)
	{
		scanf("%d%d",&n,&m);
		scanf("%s",s+1);
		for(i=1;i<=n;++i)del[i]=false;
		f1=f2=true;w1=w2=1;
		for(j=1;j<=n-m;++j)
		if(j%2)
		{
			if(f1)
			{
				for(;w1<=n;++w1)if(s[w1]=='1'&&!del[w1])break;
				if(w1>n)f1=false,w1=n;else del[w1]=true;
			}
			if(!f1)
			{
				for(;w1>=1;--w1)if(!del[w1])break;
				del[w1]=true;
			}
		}
		else
		{
			if(f2)
			{
				for(;w2<=n;++w2)if(s[w2]=='0'&&!del[w2])break;
				if(w2>n)f2=false,w2=n;else del[w2]=true;
			}
			if(!f2)
			{
				for(;w2>=1;--w2)if(!del[w2])break;
				del[w2]=true;
			}
		}
		for(i=1;i<=n;++i)if(!del[i])printf("%c",s[i]);
		printf("\n");
	}
}

---

INS14D  Digo Needs Guns

问一个简单N边形，最多需要多少视点才能覆盖整个多边形

Solution：画廊定理

#include <stdio.h>
#include <stdlib.h>
using namespace std;

int T,n,i,j,k;

int main()
{
	scanf("%d",&T);
	for(;T;--T)
	{
		scanf("%d",&n);
		printf("%d\n",n/3);
	}
}

---

INS14E  Glorious Gamblers

两个人进行一种游戏，从（1,1）走到（n,m）每个位置上有权值，一个人希望路径上的权值和大，一个人希望权值和小，抛一枚均匀硬币决定谁来决策，问权值和的期望

Solution：很显然的DP，f[i][j]为从（i,j）走到(n,m)的期望f[i][j]=a[i][j]+0.5*（max(f[i+1][j],f[i][j+1],f[i+1][j+1])+min(f[i+1][j],f[i][j+1],f[i+1][j+1]))

#include <stdio.h>
#include <stdlib.h>
using namespace std;

int T,n,m,i,j,k;
double f[505][505],tmp;
int a[505][505];

void Min(double &a,double b){if(b<a)a=b;}
void Max(double &a,double b){if(b>a)a=b;}

int main()
{
	scanf("%d",&T);
	for(;T;--T)
	{
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
		scanf("%d",&a[i][j]);
		for(i=n;i>=1;--i)
		for(j=m;j>=1;--j)
		{
			f[i][j]=0;
			tmp=0;
			if(i<n)Max(tmp,f[i+1][j]);
			if(j<m)Max(tmp,f[i][j+1]);
			if(i<n&&j<m)Max(tmp,f[i+1][j+1]);
			f[i][j]+=0.5*tmp;
			if(i<n)Min(tmp,f[i+1][j]);
			if(j<m)Min(tmp,f[i][j+1]);
			if(i<n&&j<m)Min(tmp,f[i+1][j+1]);
			f[i][j]+=0.5*tmp;
			f[i][j]+=a[i][j];
		}
		printf("%.6lf\n",f[1][1]);
	}
}

---

INS14F  Save CodeVillage

构造一组正整数序列，每个序列长度为K，序列中的数互不相同，且都小于等于N，要求任意两个序列有公共的数

Solution：当2K-1≤N时，就是在N个里任选K个的方案数(可以用二进制证明)，当2K-1≥N时，就确定一个公共点，在剩下的N-1个中任选K-1个

#include <stdio.h>
#include <stdlib.h>
#define p 1000000007
using namespace std;

int T,n,m,i,j,k;
long long fac[1000005],fac_inv[1000005],ans,tmp;

long long Power(long long a,long long b)
{
	long long ans=1;
	while(b)
	{
		if(b%2)ans=ans*a%p;
		a=a*a%p;
		b/=2;
	}
	return ans;
}

int main()
{
	fac[0]=1;
	for(i=1;i<=1000000;++i)fac[i]=fac[i-1]*i%p;
	fac_inv[1000000]=Power(fac[1000000],p-2);
	for(i=999999;i>=0;--i)fac_inv[i]=fac_inv[i+1]*(i+1)%p;
	scanf("%d",&T);
	for(;T;--T)
	{
		scanf("%d%d",&n,&m);
		if(n<=2*m-1)printf("%lld\n",fac[n]*fac_inv[n-m]%p);
		else printf("%lld\n",fac[m]*fac[n-1]%p*fac_inv[m-1]%p*fac_inv[n-m]%p);
	}
}

---

INS14G  Kill them All

求一种长度为n的01序列，对这个序列的任何前缀，1的个数都严格大于0的个数，求这种序列个数mod 10⁹+7

Solution：假设已知ans_i，那么i对i+1的贡献应该为ans_i+1+=2*ans_i，也就是在之前的所有可行解基础上放1或0，当然有非法情况，就是在前缀i的时候1只比0多一个，这次是不能放0的，这种情况可以用BZOJ3216话旧2做，然后常数被卡，加FastIO才过

#include <stdio.h>
#include <stdlib.h>
#define p 1000000007
using namespace std;

int T,n,i,j,k;
long long fac[1000005],fac_inv[1000005],ans[1000005];

long long Power(long long a,long long b)
{
	long long ans=1;
	while(b)
	{
		if(b%2)ans=ans*a%p;
		a=a*a%p;
		b/=2;
	}
	return ans;
}

int main()
{
	for(fac[0]=i=1;i<=1000000;++i)fac[i]=fac[i-1]*i%p;
	fac_inv[1000000]=Power(fac[1000000],p-2);
	for(i=999999;i>=0;--i)fac_inv[i]=fac_inv[i+1]*(i+1)%p;
	ans[1]=1;ans[2]=1;
	for(i=3;i<=1000000;++i)
	{
		ans[i]=(ans[i-1]+ans[i-1])%p;
		if(i%2==0)ans[i]=(ans[i]-fac[i-2]*fac_inv[i-2>>1]%p*fac_inv[i-2>>1]%p+fac[i-2]*fac_inv[i-4>>1]%p*fac_inv[i>>1]%p+p)%p;
	}
	scanf("%d",&T);
	for(;T;--T)
	{
		scanf("%d",&n);
		printf("%lld\n",ans[n]);
	}
}

---

INS14H  Virus Revisited

在一个n维的无限空间中，一开始在原点有一个细胞，每秒每个细胞都会繁殖，新的细胞出现在与原细胞曼哈顿距离为1的每个位置，旧细胞死去，问T秒后原点有多少细胞

Solution：用组合数DP转移

#include <stdio.h>
#include <stdlib.h>
#define p 1000000007
using namespace std;

long long fac[1005],fac_inv[1005],ans[105][105];
int T,n,m,i,j,k;

long long Power(long long a,long long b)
{
	long long ans=1;
	while(b)
	{
		if(b%2)ans=ans*a%p;
		a=a*a%p;
		b/=2;
	}
	return ans;
}

int main()
{
	fac[0]=1;
	for(i=1;i<=1000;++i)fac[i]=fac[i-1]*i%p;
	fac_inv[1000]=Power(fac[1000],p-2);
	for(i=999;i>=0;--i)fac_inv[i]=fac_inv[i+1]*(i+1)%p;
	ans[0][0]=1;
	for(i=1;i<=100;++i)
	for(j=0;j<=100;++j)
	for(k=0;k<=j;++k)
	ans[i][j]=(ans[i][j]+ans[i-1][k]*fac[2*j]%p*fac_inv[2*k]%p*fac_inv[2*j-2*k]%p*fac[2*j-2*k]%p*fac_inv[j-k]%p*fac_inv[j-k]%p)%p;
	scanf("%d",&T);
	for(;T;--T)
	{
		scanf("%d%d",&n,&m);
		if(m%2)printf("0\n");
		else printf("%lld\n",ans[n][m/2]);
	}
}

---

INS14I  Infinite Sequence

设这个数列为A，生成方式为放一个4，放A₁个5，放一个4，放A₂个5……，求第n项，多组数据

Solution：n有10⁹，但是我执意想用暴力过，于是把询问排序，暴力+卡常数，水过

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int T,n,i,j,k,top,done,now;
int ans[100005],num[30000005];

struct node
{
	int n,id;
}q[100005];

inline bool cmp(const node &a,const node &b){return a.n<b.n;}

int main()
{
	scanf("%d",&T);
	for(i=1;i<=T;++i)scanf("%d",&q[i].n),++q[i].n,q[i].id=i;
	sort(q+1,q+T+1,cmp);
	k=1;num[1]=1;now=1;done=1;top=1;
	while(done<=T&&q[done].n==now)ans[q[done].id]=4,++done;
	for(i=1;done<=T;++i)
	{
		if(i==num[k])
		{
			now+=5;
			while(done<=T&&q[done].n<now)ans[q[done].id]=5,++done;
			if(top<=30000000)num[++top]=now;
			while(done<=T&&q[done].n==now)ans[q[done].id]=4,++done;
			++k;
		}
		else
		{
			now+=6;
			while(done<=T&&q[done].n<now)ans[q[done].id]=5,++done;
			if(top<=30000000)num[++top]=now;
			while(done<=T&&q[done].n==now)ans[q[done].id]=4,++done;
		}
	}
	for(i=1;i<=T;++i)printf("%d\n",ans[i]);
}

---

INS14J  Checkers

题意可以转化为有n堆石子，在第i堆取x颗石子，第i-1堆石子就会增加x棵，问先手是否必胜

Solution：把编号为奇数的石子堆的石子数异或起来

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int T,n,i,j,k,sum;

struct node
{
	int x,y,z;
}t[10005];

inline bool cmp(const node &a,const node &b){return a.z<b.z;}

int main()
{
	scanf("%d",&T);
	for(;T;--T)
	{
		scanf("%d",&n);
		for(i=1;i<=n;++i)scanf("%d%d",&t[i].x,&t[i].y),t[i].z=t[i].x-t[i].y;
		sort(t+1,t+n+1,cmp);
		sum=0;
		for(i=1;i<=n;++i)
		if(i&1)sum^=min(t[i].x,t[i].y);
		if(sum)printf("Yes\n");else printf("No\n");
	}
}

---

INS14K  Digo Goes Training

在一个笛卡尔坐标系上给出n条线段，从x轴上一点向上做一条射线，问穿过几条线段

Solution：线段树水题

#include <stdio.h>
#include <stdlib.h>
using namespace std;

int T,n,m,i,j,k,l,ll,rr,a,b,opt,aim,ans;
int sum[1000005];
double pos;

void C(int p,int l,int r)
{
	if(l>=ll&&r<=rr)
	{
		++sum[p];
		return;
	}
	int mid=l+r>>1;
	if(rr<=mid)C(p<<1,l,mid);
	else if(ll>mid)C(p<<1|1,mid+1,r);
		else C(p<<1,l,mid),C(p<<1|1,mid+1,r);
}

void Q(int p,int l,int r)
{
	ans+=sum[p];
	if(l==r)return;
	int mid=l+r>>1;
	if(aim<=mid)Q(p<<1,l,mid);
	else Q(p<<1|1,mid+1,r);
}

int main()
{
	for(l=1;l<50000;l*=2);
	scanf("%d",&T);
	for(;T;--T)
	{
		for(i=2*l;i;--i)sum[i]=0;
		scanf("%d",&n);
		for(;n;--n)
		{
			scanf("%d%d%d%d",&ll,&a,&rr,&b);
			++ll;++rr;
			ll*=2;rr*=2;
			C(1,1,l);
		}
		scanf("%d",&m);
		for(;m;--m)
		{
			scanf("%d",&opt);
			if(opt==0)
			{
				ans=0;
				scanf("%lf",&pos);
				aim=(int)pos;
				if(pos>aim)aim=(aim+1)*2+1;
				else aim=(aim+1)*2;
				Q(1,1,l);
				printf("%d\n",ans);
			}
			else
			{
				scanf("%d%d%d%d",&ll,&a,&rr,&b);
				++ll;++rr;
				ll*=2;rr*=2;
				C(1,1,l);
			}
		}
	}
}

---

INS14L  Rooted Trees

给出一棵树，每次选一个u，对于以u为根的子树中的点v，权值加上dist(u,v)*k+x，询问某个子树的和

Solution：dist(u,v)*k+x=(deep_v-deep_u)*k+x=deep_v*k-deep_u*k+x，这个式子中只有deep_v一个变量，线段树维护DFS序

#include <stdio.h>
#include <stdlib.h>
#define P 1000000007
using namespace std;

int n,m,i,j,k,l,ll,rr,u,x,opt;
int fa[100005],son[100005],next[100005],deep[100005];
int st[100005],en[100005],tot;
long long add[400005],add2[400005],deepsum[400005],sum[400005],key,ans;

void dfs(int x)
{
	st[x]=++tot;
	for(int i=son[x];i;i=next[i])
	{
		deep[i]=deep[x]+1;
		dfs(i);
	}
	en[x]=tot;
}

void down(int p,int len)
{
	if(add[p])
	{
		add[p<<1]=(add[p<<1]+add[p])%P;
		add[p<<1|1]=(add[p<<1|1]+add[p])%P;
		sum[p<<1]=(sum[p<<1]+add[p]*len/2)%P;
		sum[p<<1|1]=(sum[p<<1|1]+add[p]*len/2)%P;
		add[p]=0;
	}
	if(add2[p])
	{
		add2[p<<1]=(add2[p<<1]+add2[p])%P;
		add2[p<<1|1]=(add2[p<<1|1]+add2[p])%P;
		sum[p<<1]=(sum[p<<1]+add2[p]*deepsum[p<<1])%P;
		sum[p<<1|1]=(sum[p<<1|1]+add2[p]*deepsum[p<<1|1])%P;
		add2[p]=0;
	}
}

void Add(int p,int l,int r)
{
	if(l>=ll&&r<=rr)
	{
		add[p]=(add[p]+key)%P;
		sum[p]=(sum[p]+key*(r-l+1))%P;
		return;
	}
	int mid=l+r>>1;
	down(p,r-l+1);
	if(rr<=mid)Add(p<<1,l,mid);
	else if(ll>mid)Add(p<<1|1,mid+1,r);
		else Add(p<<1,l,mid),Add(p<<1|1,mid+1,r);
	sum[p]=sum[p<<1]+sum[p<<1|1];
}

void Add2(int p,int l,int r)
{
	if(l>=ll&&r<=rr)
	{
		add2[p]=(add2[p]+key)%P;
		sum[p]=(sum[p]+key*deepsum[p])%P;
		return;
	}
	int mid=l+r>>1;
	down(p,r-l+1);
	if(rr<=mid)Add2(p<<1,l,mid);
	else if(ll>mid)Add2(p<<1|1,mid+1,r);
		else Add2(p<<1,l,mid),Add2(p<<1|1,mid+1,r);
	sum[p]=sum[p<<1]+sum[p<<1|1];
}

void Q(int p,int l,int r)
{
	if(l>=ll&&r<=rr)
	{
		ans=(ans+sum[p])%P;
		return;
	}
	int mid=l+r>>1;
	down(p,r-l+1);
	if(rr<=mid)Q(p<<1,l,mid);
	else if(ll>mid)Q(p<<1|1,mid+1,r);
		else Q(p<<1,l,mid),Q(p<<1|1,mid+1,r);
}

int main()
{
	scanf("%d",&n);
	for(i=2;i<=n;++i)
	{
		scanf("%d",&fa[i]);
		next[i]=son[fa[i]];
		son[fa[i]]=i;
	}
	dfs(1);
	for(l=1;l<n;l*=2);
	for(i=1;i<=n;++i)deepsum[l+st[i]-1]=deep[i];
	for(i=l-1;i>=1;--i)deepsum[i]=(deepsum[i<<1]+deepsum[i<<1|1])%P;
	scanf("%d",&m);
	for(;m;--m)
	{
		scanf("%d",&opt);
		if(opt==1)
		{
			scanf("%d%d%d",&u,&x,&k);
			ll=st[u];rr=en[u];
			key=(-(long long)deep[u]*k+x)%P;
			Add(1,1,l);
			key=k;
			Add2(1,1,l);
		}
		else
		{
			scanf("%d",&u);ll=st[u];rr=en[u];
			ans=0;
			Q(1,1,l);
			printf("%lld\n",(ans+P)%P);
		}
	}
}

---

INS14M  Terrorist Attack

---