Codeforces Round #542 (Div. 1)

似乎是一周前的比赛了QwQ，然而立过flag要每周写一场来着，就来补一补QwQ。

A1/A2. Toy Train

翻译

有\(n\)个点排成一圈，有\(m\)个货物，第\(i\)个货物要从\(a_i\)运到\(b_i\)，在每个车站只能装一个货物，求从第\(i\)个车站出发，运送完所有货物的最短的时间。

题解

如果当前有多个元素，那么必须多走一圈回来拿。所以需要考虑的只有每个车站的最后一个被拿走的东西，显然这个东西就是目标位置离当前位置最近的那个货物。
然后大力讨论一下就好了。

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 5050
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n,m,cnt[MAX],d[MAX];
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;++i)d[i]=n+1;
	for(int i=1;i<=m;++i)
	{
		int l=read(),r=read();if(r<l)r+=n;
		cnt[l]+=1;d[l]=min(d[l],r-l);
	}
	int mx=0;for(int i=1;i<=n;++i)mx=max(mx,cnt[i]);
	for(int i=1;i<=n;++i)if(cnt[i]<max(1,mx-1))d[i]=0;
	for(int i=1;i<=n;++i)
	{
		int ans=(mx-1)*n,mxx=0;
		for(int j=1;j<=n;++j)
			if(cnt[j]==mx)
			{
				int dis=i<=j?j-i:j-i+n;
				dis+=d[j];mxx=max(mxx,dis);
			}
			else if(cnt[j]==mx-1)
			{
				int dis=j<i?i-j:i-j+n;
				mxx=max(mxx,d[j]-dis);
			}
		printf("%d ",ans+mxx);
	}
	puts("");return 0;
}

B. Wrong Answer

翻译

给了你一个假贪心，你要构造一组数据把它卡掉，并且使得这组数据的结果和贪心的结果之差恰好为\(k\)。

题解

不难发现可以让前面构造一段连续大于\(0\)的数，中间构造一段负数，然后再构造一段正数，贪心的结果就是两段正数的和乘上长度，答案是全局的和乘上长度，
那么令前两个数是\(1,-2\)，设一共有\(n\)个数，剩下的\(n-2\)个数的和是\(S\)。
那么有等式：\((S-1)*n-S*(n-2)=k\)，解出来\(2S=k+n\)。
那么枚举所有的\(n\)，判断一下能否放\(n-2\)个数使得他们的和为\(S\)即可。

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int k;scanf("%d",&k);
	for(int n=1;n<=1998;++n)
		if((k+n)%2==0)
			if((k+n+2+1999999)/2000000<=n)
			{
				printf("%d\n",n+2);
				printf("1 -2 ");
				int S=(k+n+2)/2;
				for(int j=1;j<n;++j)
					if(j==n-1&&S<=1000000)printf("%d ",S/2),S-=S/2;
					else printf("1000000 "),S-=1e6;
				printf("%d\n",S);return 0;
			}
	puts("-1");
	return 0;
}

C. Morse Code

翻译

长度为\(1,2,3,4\)的二进制串一共有\(30\)个，除了\(0011,0101,1110,1111\)之外，每一个都对应着一个字母。
现在给定一个串\(S\)，对于每一个\(i\)，询问\(S[1,i]\)中的所有子串中，本质不同的对应着一个英文字母串的拆分方案数。

题解

设\(f[l][r]\)表示\(l,r\)这段区间的拆分方案数，显然枚举最后一个字母是什么就好了。
然后要求解的是本质不同的方案数，所以随便找个东西去去重就好了。
可以写哈希，我写的\(SAM\)。

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
#define MOD 1000000007
#define MAX 3030
int m,S[MAX],f[MAX][MAX],top,ans;
bool check(int l,int r)
{
	if(r-l+1<4)return true;
	if(S[l]==0&&S[l+1]==0&&S[l+2]==1&&S[l+3]==1)return false;
	if(S[l]==0&&S[l+1]==1&&S[l+2]==0&&S[l+3]==1)return false;
	if(S[l]==1&&S[l+1]==1&&S[l+2]==1&&S[l+3]==0)return false;
	if(S[l]==1&&S[l+1]==1&&S[l+2]==1&&S[l+3]==1)return false;
	return true;
}
struct Node{int son[2],ff,len;set<int> vis;}t[MAX<<1];
int tot=1,last=1;
void extend(int c)
{
	int np=++tot,p=last;last=tot;
	t[np].len=t[p].len+1;
	while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].ff;
	if(!p)t[np].ff=1;
	else
	{
		int q=t[p].son[c];
		if(t[q].len==t[p].len+1)t[np].ff=q;
		else
		{
			int nq=++tot;
			t[nq]=t[q];t[nq].len=t[p].len+1;
			t[q].ff=t[np].ff=nq;
			while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff;
		}
	}
}
int main()
{
	scanf("%d",&m);
	for(int i=1;i<=m;++i)scanf("%d",&S[i]);
	for(int i=m;i;--i)extend(S[i]);
	for(int i=1;i<=m;++i)
		for(int j=i;j>=max(1,i-3);--j)
			if(check(j,i))
			{
				f[j][i]=(f[j][i]+1)%MOD;
				for(int k=j-1;k;--k)
					f[k][i]=(f[k][i]+f[k][j-1])%MOD;
			}
	for(int i=1;i<=m;++i)
	{
		for(int j=i,u=1;j;--j)
		{
			u=t[u].son[S[j]];
			if(t[u].vis.count(i-j+1))continue;
			t[u].vis.insert(i-j+1);
			ans=(ans+f[j][i])%MOD;
		}
		printf("%d\n",ans);
	}
	return 0;
}

D. Isolation

翻译

把一个数组分成不相交的若干段，使得每一段中出现了恰好\(1\)次的数的个数至多是\(k\)个。
求划分方案数。

题解

设\(f[i]\)表示前\(i\)个数的划分方案数。
每次考虑一个\(j\)，如果\([j+1,i]\)是合法划分，那么\(f[j]\rightarrow f[i]\)。
考虑一个数值\(v\)什么时候会产生贡献，假设在\(i\)左侧第一次出现的位置是\(x\)，第二次出现的位置是\(y\)，那么当\(j\in [y+1,x]\)时，就会产生\(1\)的贡献。
对于每个块维护一个区间加法标记以及每个权值的\(f\)的和，然后每次暴力维护区间加法就好啦。
时间复杂度\(O(n\sqrt n)\)。

#include<iostream>
#include<cstdio>
using namespace std;
#define MOD 998244353
#define MAX 100100
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
const int blk=800,py=MAX-10;
int S[130][MAX*3],tag[130],Sum,val[MAX],bel[MAX];
int n,k,a[MAX],lst[MAX],pre[MAX],f[MAX];
void Modify(int l,int r,int w)
{
	for(int &i=l;i<=r&&bel[i-1]==bel[i];++i)
	{
		int K=k-tag[bel[i]];
		add(S[bel[i]][val[i]+py],MOD-f[i-1]);
		if(val[i]+tag[bel[i]]>=0&&val[i]<=K)add(Sum,MOD-f[i-1]);
		val[i]+=w;add(S[bel[i]][val[i]+py],f[i-1]);
		if(val[i]+tag[bel[i]]>=0&&val[i]<=K)add(Sum,f[i-1]);
	}
	for(int &i=r;i>=l&&bel[i+1]==bel[i];--i)
	{
		int K=k-tag[bel[i]];
		add(S[bel[i]][val[i]+py],MOD-f[i-1]);
		if(val[i]+tag[bel[i]]>=0&&val[i]<=K)add(Sum,MOD-f[i-1]);
		val[i]+=w;add(S[bel[i]][val[i]+py],f[i-1]);
		if(val[i]+tag[bel[i]]>=0&&val[i]<=K)add(Sum,f[i-1]);
	}
	if(l>r)return;
	for(int i=bel[l];i<=bel[r];++i)
	{
		int R=k-tag[i],L=0-tag[i];
		if(w==1)add(Sum,MOD-S[i][R+py]),add(Sum,S[i][L-1+py]);
		else add(Sum,MOD-S[i][L+py]),add(Sum,S[i][R+1+py]);
		tag[i]+=w;
	}
}
int main()
{
	n=read();k=read();
	for(int i=1;i<=n;++i)a[i]=read(),pre[i]=lst[a[i]],lst[a[i]]=i;
	for(int i=0;i<=n+1;++i)bel[i]=(i+blk-1)/blk;
	f[0]=Sum=S[1][py]=1;
	for(int i=1;i<=n;++i)
	{
		int a=pre[i],b=pre[a];
		Modify(a+1,i,1);if(a)Modify(b+1,a,-1);
		f[i]=Sum;add(Sum,f[i]);
		add(S[bel[i+1]][py],f[i]);
	}
	printf("%d\n",f[n]);
	return 0;
}

E. Legendary Tree

翻译

有一棵\(n\)个节点的树，每次可以询问两个点集\(S,T\)以及一个单点\(v\)，交互库会返回有多少对\((s,t)\)满足\(s\in S,t\in T\)，且\(s,t\)的路径经过了\(v\)。
询问次数不超过\(11111\)。

题解

首先随便钦定一个点作为根节点，假装是\(1\)。
然后询问\(S=\{1\},T=U-S-\{v\},v\)，其中\(U\)是全集，这样子就可以知道每棵子树的大小。
我们按照子树大小从小往大处理，显然就是对于每一个点，在子树大小比他小的点中找它的儿子。如果找到了儿子可以直接把儿子在前面的点集中删去，那么每次把点集分成两半，如果左边有就往左边走，如果右边有就往右边走。
不妨令每次恰好只找一个儿子，可以证明只需要\(log\)次询问就可以确定一个儿子。
所以这样子的复杂度不会超过\(nlogn\)

然后我自己还有一个奇怪的想法，不知道能不能优化：
把所有点按照子树大小排序，显然子树最大的那个点\(x\)一定是\(1\)号点的一个儿子。
然后对于个点询问\(S=\{1\},T=\{u\},v=x\)，那么就可以知道一个点是不是\(x\)的儿子。
然后把这棵子树分开就可以递归处理下去。然而这样子需要询问\(O(n^2)\)次（菊花）。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
#define MAX 505
int n,p[MAX],fa[MAX],size[MAX];
set<int> S;
bool cmp(int a,int b){return size[a]<size[b];}
void Solve(int u,set<int>::iterator it,int tot)
{
	if(tot==1){fa[*it]=u;S.erase(it);return;}
	int mid=tot>>1,x;set<int>::iterator tmp=it;
	printf("%d\n",mid);for(int i=1;i<=mid;++i,++it)printf("%d ",*it);puts("");
	printf("1\n1\n%d\n",u);fflush(stdout);
	scanf("%d",&x);if(x)Solve(u,tmp,mid);tmp=it;
	printf("%d\n",tot-mid);for(int i=mid+1;i<=tot;++i,++it)printf("%d ",*it);puts("");
	printf("1\n1\n%d\n",u);fflush(stdout);
	scanf("%d",&x);if(x)Solve(u,tmp,tot-mid);
}
int main()
{
	scanf("%d",&n);if(n==2){printf("ANSWER\n1 2\n");return 0;}
	for(int i=2;i<=n;++i)
	{
		printf("1\n%d\n%d\n",1,n-2);
		for(int j=2;j<=n;++j)if(i^j)printf("%d ",j);puts("");
		printf("%d\n",i);fflush(stdout);
		scanf("%d",&size[i]);
	}
	for(int i=2;i<=n;++i)p[i-1]=i;
	sort(&p[1],&p[n],cmp);
	for(int i=1;i<n;++i)
	{
		int u=p[i];
		if(!size[u]){S.insert(u);continue;}
		Solve(u,S.begin(),S.size());
		S.insert(u);
	}
	for(set<int>::iterator it=S.begin();it!=S.end();++it)fa[*it]=1;
	puts("ANSWER");
	for(int i=2;i<=n;++i)printf("%d %d\n",i,fa[i]);
	return 0;
}