【AtCoder】AtCoder Grand Contest 027 解题报告

点此进入比赛

(A)：Candy Distribution Again（点此看题面）

• 有(n)个小孩，第(i)个小孩当且仅当得到恰好(a_i)颗糖时才会满意。
• 你有(x)颗糖，需要全部分给这(n)个小孩。
• 问最多能让多少个小孩满意。
• (nle100,1le a_i,xle10^9)

贪心

显然先将(a_i)从小到大排序一下，然后贪心满足(a_i)较小的要求。

唯一要注意的就是若(xgesum_{i=1}^na_i)，需要判断一下(x)是否恰好等于(sum_{i=1}^na_i)。

代码：(O(nlogn))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100
using namespace std;
int n,m,a[N+5];
int main()
{
	RI i;for(scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",a+i);sort(a+1,a+n+1);//读入+排序
	for(i=1;i<=n&&m>=a[i];++i) m-=a[i];return printf("%d
",i<=n?i-1:(m?n-1:n)),0;//贪心，注意最后特判
}

(B)：Garbage Collector（点此看题面）

• 一条数轴上有(n)个垃圾，分别位于(0<x_1<x_2<...<x_nle10^9)。
• 从原点出发，每走到一个位置可以捡起该位置上的垃圾，你需要分若干批次把所有垃圾运回原点。
  • 当你拿着(k)个垃圾行走(1)个单位长度，会消耗((k+1)^2)的代价。
  • 当你捡起一个垃圾，或者将垃圾放在原点（无论多少个），都消耗(X)的代价（(X)为常数）。
• 求最少花费多少的代价。
• (nle2 imes10^5)

枚举搬运次数

考虑我们枚举搬运次数(t)，那么最优的方案自然就是每隔(t)个垃圾就放在同一次中搬运。

容易发现，每相邻(t)个垃圾的贡献都是一样的，所以只需要枚举(lceilfrac n t ceil)次，总复杂度为调和级数。

据说运算过程可能会爆(long long)，因此可以开__int128。

代码：(O(nln n))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
#define LL long long
using namespace std;
int n,m,a[N+5];LL s[N+5];
int main()
{
	RI i,t;for(scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",a+i),s[i]=s[i-1]+a[i];//s统计前缀和
	RI x,y;LL ans=1e18;__int128 res;for(t=1;t<=n;++t)
	{
		res=1LL*(n+t)*m+2*(s[n]-s[n-t]);//计算初始代价
		for(y=2,i=n;i>0;i-=t) x=max(i-t,0),res+=(2LL*y-1)*(s[i]-s[x]),++y;//每相邻t个代价相同
		res<ans&&(ans=res);
	}return printf("%lld
",ans),0;
}

(C)：ABland Yard（点此看题面）

• 给定一张(n)个点(m)条边的无向图，每个点有一个字符A或B。
• 你可以从任何一个点出发，在图上任意行走，并将经过的点上的字符连成一个字符串。
• 问是否能得到所有由A和B组成的字符串。
• (n,mle2 imes10^5)

找规律

首先，通过画图我们可以发现，合法的充要条件就是存在一个由若干(A-A-B-B)组成的环。

但只有这个条件依然是很难搞的。

考虑我们给边赋权，令相同字符之间边权为(0)，不同字符之间边权为(1)，显然就变成了寻找长度为(4)的倍数的(0-1)环。

然后我们发现，由于每有一个(1)字符就会变一次，因此环上必然有偶数个(1)。因此任意一个(0-1)环，长度必然为(4)的倍数！

综上，合法的充要条件就是存在一个(0-1)环。

拓扑

一个非常诡异的做法。

考虑进行一个类似于拓扑的过程，每次把所有边权相同的点删去。

如果最后还有点剩余，说明有解，否则无解。

证明可以自己画画图。

代码：(O(n))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
#define add(x,y,v) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y,++d[y][e[ee].op=v])
using namespace std;
int n,m,ee,lnk[N+5],vis[N+5],q[N+5],d[N+5][2];struct edge {int to,nxt,op;}e[2*N+5];char p[N+5];
int main()
{
	RI i,x,y;for(scanf("%d%d%s",&n,&m,p+1),i=1;i<=m;++i)
		scanf("%d%d",&x,&y),add(x,y,p[x]!=p[y]),add(y,x,p[x]!=p[y]);//建边
	RI H=1,T=0;for(i=1;i<=n;++i) (!d[i][0]||!d[i][1])&&(vis[q[++T]=i]=1);//初始化队列
	W(H<=T) for(i=lnk[q[H++]];i;i=e[i].nxt)//类似拓扑的过程
		!vis[e[i].to]&&!--d[e[i].to][e[i].op]&&(vis[q[++T]=e[i].to]=1);
	return puts(T^n?"Yes":"No"),0;//判断是否有点剩余
}

(D)：Modulo Matrix（点此看题面）

• 给定一个正整数(n)。
• 要求构造一个(n imes n)的矩阵，满足下列条件：
  • 没有重复的元素，且所有元素均为不超过(10^{15})的正整数。
  • 对于任意两个相邻的数(x,y)，都满足(max{x,y} mod min{x,y})等于(m)（(m)可自己定）。
• (2le nle500)

大致思路

显然(m)越小越好，因此直接取(m=1)。

考虑我们必然是以一种交错的方式，对于所有(i)和(j)奇偶性相同的((i,j))根据某种策略填上一个数，对于所有(i)和(j)奇偶性不同的((i,j))直接令其等于四周数的(lcm+1)。

这道题的关键是不能重复，因此我们要想办法找到一种填数方式使得(lcm)不会相同。

自然而然想到利用质数。

考虑我们给每条斜线（两种方向都包括）一个质数，然后对于每个(i)和(j)奇偶性相同的((i,j))，都让它等于经过它的两条斜线上的质数之积。

然后发现每个(i)和(j)奇偶性不同的((i,j))，应该是(4)个质数的乘积加(1)，不会超出限制。

注意特判(n=2)。

代码：(O(n^2))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 2000
using namespace std;
int n,p[N+5],a[N+5],b[N+5];
I bool IsP(CI x) {for(RI i=2;i*i<=x;++i) if(!(x%i)) return 0;return 1;}
int main()
{
	RI i,j,m=0;for(scanf("%d",&n),i=2;m<2*n;++i) IsP(i)&&(p[++m]=i);//暴力找质数
	if(n==2) return puts("4 7
23 10"),0;a[0]=a[n+1]=b[0]=b[n+1]=1;//特判n=2
	for(i=1;i<=n;++i) (i&1)?(a[i]=p[i]):(b[i]=p[i]);//分配质数，这里采取了一种大小交错的分发
	for(i=1;i<=n;++i) (i&1)?(b[i]=p[m-i+1]):(a[i]=p[m-i+1]);
	#define P1(x,y) ((x)+(y)>>1)//求出左下-右上的斜线编号
	#define P2(x,y) ((x)-(y)+n+1>>1)//求出左上-右下的斜线编号
	for(i=1;i<=n;++i,putchar('
')) for(j=1;j<=n;++j)//枚举格子
		printf("%lld ",(i^j)&1?1LL*a[P1(i,j)]*b[P2(i,j)]:(1LL*a[P1(i-1,j)]*a[P1(i,j+1)]*b[P2(i-1,j)]*b[P2(i,j-1)]+1));//根据i与j奇偶性是否相同讨论
	return 0;
}

(E)：ABBreviate（点此看题面）

• 给定一个由a和b组成的字符串，可以任意进行下列两种操作：
  • 将一对连续的aa替换为b。
  • 将一对连续的bb替换为a。
• 问能生成多少种不同的字符串。
• 字符串长度(le10^5)

神奇思路

一个非常神奇的思路。

不妨令(a=1,b=2)，发现两种操作均不影响整个序列和模(3)的余数！

然后要证明一个结论：一个字符串(s)能变成一个字符(x)的充要条件是字符串(s)之和模(3)的余数与(x)对应的值相同且(s)中有可变换的位置（即不是完全由ab重复构成）。

证明的过程简单来说就是考虑如果我们转化到某一步让(s)无法再变换了，我们可以退回到上一步并改为合并另外一对位置，自己画画图就可以发现必然存在悔改的方案。

有了这个结论剩下的就非常容易了，直接(DP)即可。

代码：(O(n))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define X 1000000007
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
using namespace std;
int n,f[N+5],lst[3];char s[N+5];
int main()
{
	RI i,t=0;scanf("%s",s+1),n=strlen(s+1),f[0]=1,lst[1]=lst[2]=-1;
	for(i=1;i^n&&s[i]^s[i+1];++i);if(i==n) return puts("1"),0;//特判无可变换位置
	for(i=1;i<=n;++i) t=(t+(s[i]=='a'?1:2))%3,!t&&i^n&&(f[i]=1),//t记录前缀和，直接DP
		t=++t%3,~lst[t]&&Inc(f[i],f[lst[t]]),t=++t%3,~lst[t]&&Inc(f[i],f[lst[t]]),lst[t=++t%3]=i;
	return printf("%d
",f[n]),0;//输出答案
}

(F)：Grafting（点此看题面）

• 给定两棵(n)个节点的树(A,B)，一开始(A)中的节点全是白色的。
• 你可以进行任意次操作，每次选择一个白色的叶节点，断开它原先的边，随意给它连上一条新边，然后将它染黑。
• 问最少通过几次操作，才能使(A)与(B)相同（忽略颜色、考虑编号）。
• 数据组数(le20)，(nle50)

无根化有根

首先考虑到两棵无根树既不好判相同，也不好操作，所以我们要先把它变成有根树。

具体地，我们去枚举((x,y))表示第一次操作将叶节点(x)与(y)连边，然后令(x)成为树的根。

接下来就好操作了许多。

拓扑

对于树(A)，除去与父节点连边正确的节点之外，显然每一个节点都必须在其子节点都被操作过之后操作。

对于树(B)，同样除去正确的节点，每一个节点都必须在其子节点之前就先被操作。

（注意，还需要先判断如果某个错误的节点子树内存在正确的节点，必然无解）

容易发现这形成了一种拓扑关系，那么就可以建出一张图。

而我们的目的是找到一个合法的操作方案，也就是说只要这张图中不存在环就可以了。

这样一来这题就做完了。

代码：(O(Tn^3))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 50
#define add(x,y) (e[++ee].nxt=lnk[x],++d[e[lnk[x]=ee].to=y])
using namespace std;
int n,res,ans,f[N+5],g[N+5],d[N+5],ee,lnk[N+5];struct edge {int to,nxt;}e[N<<1];
struct Tree//存树
{
	int ee,lnk[N+5];struct edge {int to,nxt;}e[N<<1];
	I void Clear() {ee=0,memset(lnk,0,sizeof(lnk));}//清空
	I void Add(CI x,CI y) {e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y;}//连边
	I int operator [] (CI x) Con {return lnk[x];}
	I edge operator () (CI x) Con {return e[x];}
}A,B;
I void dfsA(CI rt,CI x,CI lst)//以rt为根，遍历A，记下每个点的父亲
{
	f[x]=lst;for(RI i=A[x];i;i=A(i).nxt) A(i).to^lst&&A(i).to^rt&&(dfsA(rt,A(i).to,x),0);
}
I bool dfsB(CI x,CI lst,RI tg=1)//遍历B，判断每个点是否正确
{
	if(f[x]^lst) g[x]=tg=0,++res;else {if(!tg) return 0;g[x]=1;}//如果错误的节点子树内有正确的节点，直接返回
	for(RI i=B[x];i;i=B(i).nxt) if(B(i).to^lst&&!dfsB(B(i).to,x,tg)) return 0;return 1;
}
I void LinkA(CI rt,CI x,CI lst)//对于A建边
{
	!g[lst]&&add(x,lst);for(RI i=A[x];i;i=A(i).nxt) A(i).to^lst&&A(i).to^rt&&(LinkA(rt,A(i).to,x),0);//子节点连向父节点
}
I void LinkB(CI x,CI lst)//对于B建边
{
	lst&&!g[lst]&&add(lst,x);for(RI i=B[x];i;i=B(i).nxt) B(i).to^lst&&(LinkB(B(i).to,x),0);//父节点连向子节点
}
int q[N+5];I bool Topo(CI x,CI y)//拓扑
{
	RI i,H=1,T=0;for(ee=0,i=1;i<=n;++i) d[i]=lnk[i]=0;LinkA(x,y,x),LinkB(x,0);
	for(i=1;i<=n;++i) !d[i]&&(q[++T]=i);
	W(H<=T) for(i=lnk[q[H++]];i;i=e[i].nxt) !--d[e[i].to]&&(q[++T]=e[i].to);return T==n;//所有点都在序列中说明无环
}
int main()
{
	RI Tt,i,j,x,y;scanf("%d",&Tt);W(Tt--)
	{
		scanf("%d",&n),A.Clear(),B.Clear(),ans=n+1;
		for(i=1;i^n;++i) scanf("%d%d",&x,&y),A.Add(x,y),A.Add(y,x);
		for(i=1;i^n;++i) scanf("%d%d",&x,&y),B.Add(x,y),B.Add(y,x);
		for(i=1;i<=n;++i) if(!A(A[i]).nxt) for(f[i]=0,j=1;j<=n;++j)//枚举第一次操作
			i^j&&(res=A(A[i]).to!=j,dfsA(i,j,i),dfsB(i,0)&&res<ans&&Topo(i,j)&&(ans=res));//注意答案的初始化，判断这条边是否原本就存在
		printf("%d
",ans>n?-1:ans);
	}return 0;
}