我：bzoj都是水题那切啥呀？

犇：我看poi的题都比bzoj好多了。

但是poi实在切无聊死了，所以切一届PA。。应该差不多吧。。

T1 Tulips

sort+unique一下即可

#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,a[20010];
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	printf("%d",15000-(unique(a+1,a+n+1)-a-1));
}

T2 Rooks

直接模拟即可

#include<cstdio>
using namespace std;
int n,i,j,fl[1010],us[1010];
char s[1010][1010];
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%s",s[i]+1);
		for(j=1;j<=n;j++)
			if(s[i][j]=='W')break;
		if(j>n)fl[i]=1;
		else us[j]=1;
	}
	for(i=1;i<=n;i++)
		if(fl[i])
		{
			for(j=1;j<=n;j++)
				if(!us[j])break;
			s[i][j]='W';us[j]=1;
		}
	for(i=1;i<=n;i++)
		puts(s[i]+1);
}

T3 Unlucky

刚刚开始样例就玩不出来

后来咨询了犇，犇10s给出样例玩法。智商梯度力

得出样例玩法正解就显然了。

那个1/3是坑人的，别去鸟他。

然后大概的玩法是，每次出发，每1e-oo就放1e-oo的水，然后让后面每次经过的时候都可以用路上的水。

除了第一次之外，每次都运k，第一次运模k的余数。

然后注意一下边界情况即可。

#include<cstdio>
using namespace std;
int s,w,k,x,n,i;
double tot;
int main()
{
	scanf("%d%d%d",&s,&w,&k);
	n=w/k;x=w%k;tot=x/(2*n+1.);
	for(i=n;i>=1&&tot+k/(2*i-1.)<=s;i--)
		tot+=k/(2*i-1.);
	if(n)printf("%.8lf",(tot-s)*(2*i-1.)+k*i);
	else printf("%.8lf",(double)w-s);
}

T4 Climbing

曾经的宁波市复赛题。

当时写了标算却因为题目描述不清而爆0，非常难过。

贪心即可。注意开long long

#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,fl,ans;
long long x,y,min1,max1,z;
int main()
{
	scanf("%d",&n);ans=n;min1=1;
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x,&y);y+=x;
		if(fl==1)min1=max(min1,z-y);
		if(fl==2)max1=min(max1,y-z);
		fl=3-fl;z=y-z;
		if(min1>max1)
		{
			fl=1;z=y;ans--;
			min1=0;max1=y;
		}
	}
	printf("%d\n",ans);
}

T5 Journey

这题也想了蛮久的。主要刚刚开始把他和之前看到过的一题联系在一起了就想不出来了。

为了之后讲述方便，给边区间规定4个值x,y,l,r，表示x~y的点向l~r连边

首先建线段树。线段树存啥呢？a~b的这个点，存x∈[a,b]的所有边区间，按照y值从小到大排。

然后比如我们要对一个点s更新。然后我们只要找到线段树上对应1~s的这段区间的点。

然后考虑，因为要满足y>=s，所以他一定是从大到小的！所以我们只要把所有满足y>=s的区间拿出来就好啦！

因为边权都是1，根据bfs的性质，一个边区间只可能被用一次，所以用完之后就可以把它删啦~

那么问题又来了。在线段树别的点上也有这个区间怎么办呢？扫到的时候忽略掉就好啦！

然后对于一个区间的更新怎么搞呢？可以用并查集呀！因为被更新的点就永远不会再被更新了所以均摊O(n)！（具体看代码）

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200010
#define T 500010
#define M 2000010
#define S 4000010
using namespace std;
char ch;
int v[S],ne[S],head[M],cnt,mid,i,dad[T],dis[T],q[T],r,n,m,l,ln;
struct stl{int x,y,z,l,r;}a[N];
int find(int x){return dad[x]!=-1?dad[x]=find(dad[x]):x;}
void read(int &x)
{
	for(ch=getchar();ch<'0';ch=getchar());
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
bool cmp(stl a,stl b)
{
	return a.y<b.y;
}
void add(int l,int r,int x,int y,int cur)
{
	v[++cnt]=y;ne[cnt]=head[cur];
	head[cur]=cnt;mid=(l+r)>>1;
	if(l==r)return;
	if(x<=mid)add(l,mid,x,y,cur<<1);
	else add(mid+1,r,x,y,cur<<1|1);
}
void play(stl a,int d)
{
	if(a.z)return;a.z=1;
	for(i=find(a.r);i>=a.l;i=find(i))
		dis[i]=d+1,q[++r]=i,dad[i]=i-1;
}
void get(int l,int r,int L,int R,int x,int cur)
{
	if(L<=l&&R>=r)
	{
		for(;a[v[head[cur]]].y>=x;head[cur]=ne[head[cur]])
			play(a[v[head[cur]]],dis[x]);
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)get(l,mid,L,R,x,cur<<1);
	if(R>mid)get(mid+1,r,L,R,x,cur<<1|1);
}
int main()
{
	memset(dad,-1,sizeof(dad));
	read(n);read(m);read(q[l=r=1]);
	dad[q[1]]=q[1]-1;
	for(i=1;i<=m;i++)
	{
		read(a[++ln].x);read(a[ln].y);
		read(a[ln].l);read(a[ln++].r);
		a[ln]=a[ln-1];
		swap(a[ln].x,a[ln].l);
		swap(a[ln].y,a[ln].r);
	}
	sort(a+1,a+ln+1,cmp);
	for(i=1;i<=ln;i++)
		add(1,n,a[i].x,i,1);
	for(;l<=r;l++)
		get(1,n,1,q[l],q[l],1);
	for(i=1;i<=n;i++)
		printf("%d\n",dis[i]);
}

T6 Pedestrian Crossing

这题之前做的~大概是把所有不可行区间对应到模意义下，然后扫一遍找有没有可以走的点就好啦~

#include<cstdio>
#include<algorithm>
using namespace std;
struct ok
{
	long long x,y;
}go[500010];
long long T,s,k,n,i,x,a[500010],flag,max1,l;
char ch;
void read(long long &x)
{
	for(ch=getchar();ch<'0';ch=getchar());
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int bj(ok x,ok y){return x.x<y.x;}
int main()
{
	read(T);
	while(T--)
	{
		read(s);read(k);read(n);l=0;a[0]=0;flag=0;
		for(i=1;i<=n;i++)
		{
			read(a[i]);
			if(i%2==0)a[i]-=s;else a[i]+=s;
			a[i]+=a[i-1];
		}
		for(i=0;i<=n;i+=2)a[i]++;
		for(i=0;i<n;i+=2)
		if(a[i]<a[i+1])
		{
			if(a[i+1]-a[i]>k){flag=1;break;}
			a[i]%=k;a[i+1]%=k;
			if(a[i]<a[i+1])go[++l].x=a[i],go[l].y=a[i+1];
			else go[++l].x=0,go[l].y=a[i+1],go[++l].x=a[i],go[l].y=k;
		}
		sort(go+1,go+l+1,bj);max1=0;
		for(i=1;i<=l;i++)
		{
			if(go[i].x>max1)break;
			max1=max(go[i].y,max1);
		}
		if(max1<k&&!flag)printf("TAK\n");else printf("NIE\n");
	}
}

T7 Fuel

简单观察可以发现他就是要找一个连通块，然后把其中最长的一条链拿出来，然后链上的点贡献算1，非链上点贡献算2，最后要求贡献<=m+1。

因为要最大化连通块的大小，所以很容易发现只要把直径拉出来，剩下的点就随便选就好啦~

#include<cstdio>
#include<algorithm>
#define N 500010
#define M 1000010
using namespace std;
int v[M],ne[M],head[N],dad[N],l,m1[N],m2[N],i,ans,n,m,x,y;
void add(int x,int y){v[++l]=y;ne[l]=head[x];head[x]=l;}
void dfs(int x)
{
	for(int i=head[x];i;i=ne[i])
	if(v[i]!=dad[x])
	{
		dad[v[i]]=x;dfs(v[i]);
		if(m1[v[i]]>=m1[x])m2[x]=m1[x],m1[x]=m1[v[i]]+1;
		else if(m1[v[i]]>=m2[x])m2[x]=m1[v[i]]+1;
	}
	if(m1[x]+m2[x]>ans)ans=m1[x]+m2[x];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1);
	if(ans>m)printf("%d\n",m+1);
	else printf("%d\n",min(n,(m+ans+2)>>1));
}

T10 Double Factorial

扩展卢卡斯加点小特技即可。

#include<cstdio>
#define p1 1000000000ll
#define p2 1000000000000000000ll
using namespace std;
long long n;
long long a1,a2,x1,x2,xx,yy,zz,ans;
void count(long long x)
{
	x1=n%x+n-x+2;x2=n/x;
	if(x1&1)x2/=2;else x1/=2;
	ans+=x1*x2;
	xx=(x1%p1)*(x2%p1);yy=(x1/p1)*(x2/p1);
	zz=(x1/p1)*(x2%p1)+(x1%p1)*(x2/p1);
	a1+=xx;
	if(a1>=p2)a2++,a1-=p2;
	a1+=zz%p1*p1;
	if(a1>=p2)a2++,a1-=p2;
	a2+=yy+zz/p1;
	if(n/5>=x)count(x*5);
}
int main()
{
	scanf("%lld",&n);
	count(5);
	if(a2)printf("%lld%018lld\n",a2,a1);
	else printf("%lld\n",a1);
}

T13 Automorphisms

hash大法好。。

表示成括号序列然后把相同的子树摞出来。。三进制自然溢出。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500010
#define M 1000010
#define mod 1000000007
using namespace std;
int n,i,x,y,dis[N],v[M],ne[M],head[N],l,q[N],r,u,V,dad[N],sz[N],tot,ss,Q[N];
unsigned long long f[N],g[M],ans,jc[N];
bool cmp(int x,int y){return f[x]<f[y];}
void add(int x,int y){v[++l]=y;ne[l]=head[x];head[x]=l;}
void dfs(int x)
{
	int i;sz[x]=2;
	for(i=head[x];i;i=ne[i])
		if(v[i]!=dad[x])dad[v[i]]=x,dfs(v[i]),sz[x]+=sz[v[i]];
	for(l=0,i=head[x];i;i=ne[i])
		if(v[i]!=dad[x])Q[++l]=v[i];
	sort(Q+1,Q+l+1,cmp);tot=1;ss=0;
	for(i=1;i<=l;i++)
	{
		ss++;
		if(f[Q[i]]!=f[Q[i-1]])
		{
			if(ss>1)(ans*=jc[ss])%=mod;
			ss=0;
		}
		f[x]+=f[Q[i]]*g[tot];
		tot+=sz[Q[i]];
	}
	if(ss)(ans*=jc[ss+1])%=mod;
	f[x]+=g[tot];
}
int main()
{
	scanf("%d",&n);g[0]=jc[0]=1;
	for(i=1;i<=n<<1;i++)
		g[i]=g[i-1]*3;
	for(i=1;i<=n;i++)
		jc[i]=jc[i-1]*i%mod;
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	memset(dis,-1,sizeof(dis));dis[1]=0;
	for(q[l=r=1]=1;l<=r;l++)
		for(i=head[q[l]];i;i=ne[i])
			if(dis[v[i]]<0)dis[v[i]]=dis[q[l]]+1,q[++r]=v[i];
	for(i=u=1;i<=n;i++)if(dis[i]>dis[u])u=i;
	memset(dis,-1,sizeof(dis));dis[u]=0;
	for(q[l=r=1]=u;l<=r;l++)
		for(i=head[q[l]];i;i=ne[i])
			if(dis[v[i]]<0)dis[v[i]]=dis[q[l]]+1,q[++r]=v[i];
	for(i=V=1;i<=n;i++)if(dis[i]>dis[V])V=i;
	for(q[l=r=1]=V;l<=r;l++)
		for(i=head[q[l]];i;i=ne[i])
			if(dis[v[i]]==dis[q[l]]-1)
			{
				q[++r]=v[i];break;
			}
	ans=1;
	if(r&1)dfs(q[r+1>>1]);
	else
	{
		dad[q[r>>1]]=q[r+2>>1];
		dad[q[r+2>>1]]=q[r>>1];
		dfs(q[r>>1]);dfs(q[r+2>>1]);
		if(f[q[r>>1]]==f[q[r+2>>1]])ans=ans*2%mod;
	}
	printf("%llu\n",ans);
}

T16 The Shortest Period

直接枚举循环节长度，然后hash判定即可。

分两种情况讨论

1、坏点不在第一个循环节内；

2、坏点在第一个循环节内。

然后调和级数暴力即可。

hash用的是ull自然溢出。27进制。

#include<cstdio>
#include<algorithm>
#define N 400000
#define ull unsigned long long
using namespace std;
int T,i,j,n,u,l,r,mid;
char s[N+10];
ull jc[N+10],ny[N+10],f[N+10],xx,yy;
ull powmod(ull x,ull y)
{
	ull ans=1;
	for(;y;y>>=1,x=x*x)
		if(y&1)ans=ans*x;
	return ans;
}
bool count(int x)
{
	for(j=x;j<n;j+=x)
	{
		u=min(n-j,x);
		if(f[u]!=(f[j+u]-f[j])*ny[j])
			break;
	}
	if(j>=n)return 1;
	l=0;r=x;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(f[mid]==(f[j+mid]-f[j])*ny[j])
			l=mid+1;else r=mid;
	}
	u=j+l;
	if(n-x>u)
		xx=f[u-1]+(f[n-x]-f[u])*ny[1];
	else xx=f[n-x-1];
	if(x<u)
		yy=(f[n]-f[u])*ny[x+1]+(f[u-1]-f[x])*ny[x];
	else yy=(f[n]-f[x+1])*ny[x+1];
	if(xx==yy)return 1;
	l=0;r=max(x,n-x);
	while(l<r)
	{
		mid=(l+r)>>1;
		if(f[mid]==(f[x+1+mid]-f[x+1])*ny[x+1])
			l=mid+1;else r=mid;
	}
	u=l;
	if(n-x>u)
		xx=f[u-1]+(f[n-x]-f[u])*ny[1];
	else xx=f[n-x-1];
	if(x<u)
		yy=(f[n]-f[u])*ny[x+1]+(f[u-1]-f[x])*ny[x];
	else yy=(f[n]-f[x+1])*ny[x+1];
	if(xx==yy)return 1;
	return 0;
}
int main()
{
	scanf("%d",&T);jc[0]=ny[0]=1;
	for(i=1;i<=N;i++)jc[i]=jc[i-1]*27;
	ny[N]=powmod(jc[N],9223372036854775807llu);
	for(i=N-1;i>=1;i--)ny[i]=ny[i+1]*27;
	while(T--)
	{
		scanf("%d%s",&n,s+1);
		for(i=1;i<=n;i++)
			f[i]=f[i-1]+jc[i-1]*(s[i]-'a');
		for(i=1;i<=n;i++)
			if(count(i))break;
		printf("%d\n",i);
	}
}

T17 Road Network 2

感觉在哪里看到过这题。

按照度数排序，然后每次把度数为1的点连向当前度数最小并大于1的点即可。

#include<bits/stdc++.h>
#define N 2000010
using namespace std;
int n,d[N],f[N],i,j,x[N],y[N];
bool cmp(int x,int y){return d[x]<d[y];}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&d[i]),f[i]=i;
	sort(f+1,f+n+1,cmp);j=1;
	for(i=1;i<n-1;i++)
	{
		for(;d[f[j]]==1&&j<=n;j++);
		if(i>=j||j>n)break;
		x[i]=f[i];y[i]=f[j];d[f[j]]--;
	}
	if(i<n-1||d[f[n-1]]>1||d[f[n]]>1)
	{
		puts("BRAK");return 0;
	}
	x[n-1]=f[n];y[n-1]=f[n-1];
	for(i=1;i<n;i++)
		printf("%d %d\n",x[i],y[i]);
}

T21 Computational Geometry

奇数个点显然不行。

点数显然必须大于2。

之后方案就考虑扭来扭去的一段再加上很长的一条即可。

#include<bits/stdc++.h>
using namespace std;
int n,x,y,i;
int main()
{
	scanf("%d",&n);
	if((n&1)||n<4){puts("NIE");return 0;}n>>=1;
	puts("0 0");x=1;y=0;
	for(i=2;i<n;i++)
	{
		x+=!(i&1),y+=i&1;
		printf("%d %d\n",x,y);
	}
	x+=(!(n&1))*(n+1);
	y+=(n&1)*(n+2);
	printf("%d %d\n",x,y);
	x-=n&1;y+=!(n&1);
	printf("%d %d\n",x,y);
	x-=(!(n&1))*(n+1);y-=(n&1)*n;
	for(i=n;i>1;i--)
	{
		x-=!(i&1),y-=i&1;
		printf("%d %d\n",x,y);
	}
}

T22 Coprime Numbers

直接调和级数大力容斥即可。

#include<cstdio>
#define N 3000010
using namespace std;
int n,i,x,a[N],m,j;
long long f[N],s[N],ans;
int main()
{
	scanf("%d",&n);ans=1ll*n*(n-1)/2;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x);
		a[x]++;if(x>m)m=x;
	}
	for(i=m;i>=1;i--)
	{
		s[i]=a[i];
		for(j=i<<1;j<=m;j+=i)
			s[i]+=a[j],f[i]+=f[j];
		f[i]=s[i]*(s[i]-1)/2-f[i];
		if(i>1)ans-=f[i];
	}
	printf("%lld\n",ans);
}

水平不够TwT太差了

——这么差还学OI，拉低OI界平均智商