526互联

AtCoder Grand Contest 027

发布时间 2023-09-27 19:06:23作者: Zhou_JK

A - Candy Distribution Again

从小到大贪心，可以发现一定是满足一个前缀，暴力判断就行了。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=105;
int n,x;
int a[N];
int main()
{
	scanf("%d%d",&n,&x);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=a[i];
		if(sum>x)
		{
			printf("%d",i-1);
			return 0;
		}
	}
	if(sum==x) printf("%d",n);
	else printf("%d",n-1);
	return 0;
}

B - Garbage Collector

枚举倒了 \(k\) 次垃圾，每次走到某个垃圾那里然后在回来，不妨令当前到掉的垃圾为 \(p_1\lt p_2\lt \cdots \lt p_m\)，贡献大概是：

\[\sum\limits_{i=1}^{m-1} (2(m-i+1)+1)x_{p_i}+5p_m \]

那么就有一个贪心的思路，把最远的 \(2k\) 个点的贡献系数设成 \(5\)，次远的 \(k\) 个点的贡献系数设成 \(7\)，依此类推。

#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;
const int N=200005;
int n,x;
int a[N];
long long sum[N];
int main()
{
	scanf("%d%d",&n,&x);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+a[i];
	long long ans=LONG_LONG_MAX;
	for(int i=1;i<=n;i++)
	{
		__int128 res=1LL*n*x+1LL*i*x;
		for(int j=n,k=1;j>=1;j-=i,k++)
			res+=(sum[j]-sum[max(j-i,0)])*max(5,2*k+1);
		if(res<ans) ans=res;
	}
	printf("%lld",ans);
	return 0;
}

C - ABland Yard

可以发现问题就是询问有没有一个点集满足点集中的点都有连向点集中的 A 和 B 的点的出边。

按照拓扑排序的思路，每次将不满足同时有 A 和 B 出边的点删去，最后看下是否每个点都被访问过就行了。

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=200005;
int n,m;
char s[N];
vector<int>G[N];
int dega[N],degb[N];
bool vis[N];
int main()
{
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}
	for(int u=1;u<=n;u++)
		for(int v:G[u])
			if(s[v]=='A') dega[u]++;
			else if(s[v]=='B') degb[u]++;
	queue<int>q;
	for(int u=1;u<=n;u++)
		if(dega[u]==0||degb[u]==0) q.emplace(u);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int v:G[u])
		{
			if(s[u]=='A') dega[v]--;
			else if(s[u]=='B') degb[v]--;
			if(dega[v]==0||degb[v]==0) q.emplace(v);
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(!vis[i]) cnt++;
	if(cnt>0) printf("Yes");
	else printf("No");
	return 0;
}

D - Modulo Matrix

考虑将格子黑白染色，可以发现白色和白色，黑色和黑色之间是互不影响的。一个想法就是将白色格子先填完，黑色格子就是周围白色格子的 \(\operatorname{lcm} +1\)。

填的话有一个简单的想法就是将每行，每列都赋上一个质数，每个白色格子的数就等于它所在行的质数乘上它所在列的质数，但这显然过不去。但是你可以发现你换成给将每条对角线赋上一个质数就可以减少乘上的数的个数，稍微调整一下顺序就可以压到 \(10^{15}\) 以内。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=505,M=10005;
int n;
int r[N],c[N];
long long a[N][N];
bool isprime[M];
int prime[M],tot;
void init(int n=10000)
{
	fill(isprime+1,isprime+n+1,true);
	isprime[1]=false;
	for(int i=2;i<=n;i++)
	{
		if(isprime[i]) prime[++tot]=i;
		for(int j=1;j<=tot&&i*prime[j]<=n;j++)
		{
			isprime[i*prime[j]]=false;
			if(i%prime[j]==0) break;
		}
	}
	return;
}
long long gcd(long long a,long long b)
{
	return b==0?a:gcd(b,a%b);
}
long long lcm(long long a,long long b)
{
	return a/gcd(a,b)*b;
}
int main()
{
	init();
	scanf("%d",&n);
	if(n==2)
	{
		printf("4 7\n");
		printf("23 10\n");
		return 0;
	}
	int now=0;
	for(int i=1;i<=n;i+=2)
		r[i]=prime[++now];
	for(int i=n-(n%2==1);i>=1;i-=2)
		r[i]=prime[++now];
	for(int i=1;i<=n;i+=2)
		c[i]=prime[++now];
	for(int i=n-(n%2==1);i>=1;i-=2)
		c[i]=prime[++now];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if((i+j)%2==0) a[i][j]=1LL*r[(i-j)/2+(n+1)/2]*c[(i+j)/2];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if((i+j)%2==1)
			{
				a[i][j]=1;
				if(i-1>=1) a[i][j]=lcm(a[i][j],a[i-1][j]);
				if(i+1<=n) a[i][j]=lcm(a[i][j],a[i+1][j]);
				if(j-1>=1) a[i][j]=lcm(a[i][j],a[i][j-1]);
				if(j+1<=n) a[i][j]=lcm(a[i][j],a[i][j+1]);
				a[i][j]++;
			}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			printf("%lld ",a[i][j]);
		printf("\n");
	}
	return 0;
}

E - ABBreviate

将 a 看做 \(1\)，b 看作 \(2\)，可以发现无论如何操作在模 \(3\) 意义下的权值和总是不会变，令其为 \(P(s)\)。

可以发现能将 \(s\) 变成 a 的当且仅当 \(P(s)=1\) ，且 \(s\) 中有至少两个连续的相同字符。b 同理。

\(s\) 能变成 \(t\)，当且仅当把 \(s\) 分成 \(|t|\) 段，使得第 \(i\) 段的 \(P(s)\) 和 \(P(t_i)\) 相等。

然后就可以 DP 了。如果直接搞会发现一个僵硬的事情就是，有些位置段可能有一个后缀的和模 \(3\) 为 \(0\)，不妨把这些后缀都移到最后，单独成一段，那么这段的和必须为 \(0\)。

令 \(f_i\) 表示以 \(i\) 结尾的字符串 \(t\) 的方案数，枚举下一个字符填 a 还是 b 转移即可。

注意特判没有两个连续的相同字符的情况，证明就不写了。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
const int MOD=1000000007;
int n;
char s[N];
int sum[N];
int f[N];
int nxt[N][3];
bool check()
{
    for(int i=2;i<=n;i++)
        if(s[i]==s[i-1]) return false;
    return true;
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    if(check())
    {
        printf("1");
        return 0;
    }
    for(int i=1;i<=n;i++)
        if(s[i]=='a') sum[i]=(sum[i-1]+1)%3;
        else if(s[i]=='b') sum[i]=(sum[i-1]+2)%3;
    for(int j=0;j<=2;j++)
        nxt[n+1][j]=n+1;
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<=2;j++)
            nxt[i][j]=nxt[i+1][j];
        nxt[i][sum[i]]=i;
    }
    f[0]=1;
    for(int i=0;i<=n;i++)
        for(int j=1;j<=2;j++)
            f[nxt[i+1][(sum[i]+j)%3]]=(f[nxt[i+1][(sum[i]+j)%3]]+f[i])%MOD;
    int ans=0;
    for(int i=1;i<=n;i++)
        if((sum[n]-sum[i])%3==0) ans=(ans+f[i])%MOD;
    printf("%d",ans);
    return 0;
}

F - Grafting

先枚举第一次移动的点 \(u\)，枚举它移动到了 \(v\) 上，那么 \(u\) 就不能动了，将两棵树的根设为 \(u\)。

可以发现一个点 \(u\) 如果它在两棵树 \(A,B\) 中的父亲 \(fa_A(u),fa_B(u)\) 不同则说明 \(u\) 需要操作。

因为肯定是按照叶子开始顺序操作的我们可以从中得到一些约束条件：

  • 若 \(u\) 不需要操作, \(fa_A(u)\) 也不需要操作。
  • 若 \(u\) 要操作，\(u\) 必须在 \(fa_A(u)\) 前操作，\(fa_B(u)\) 后操作.

按照这个东西可以建出一张关于时间的有向图，判下图中有没有环就好了。

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=55;
const int INF=1061109567;
int T;
int n;
vector<pair<int,int>>edge;
vector<int>GA[N],GB[N];
vector<int>leaf;
void findleaf(int u,int father)
{
	int tot=(u!=1);
	for(int v:GA[u])
	{
		if(v==father) continue;
		findleaf(v,u);
		tot++;
	}
	if(tot==1) leaf.emplace_back(u);
	return;
}
vector<int>G[N];
int fab[N];
void dfsb(int u,int father)
{
	fab[u]=father;
	for(int v:GB[u])
	{
		if(v==father) continue;
		dfsb(v,u);
	}
	return;
}
bool flag;
int faa[N];
bool book[N];
int deg[N];
void dfsa(int u,int father)
{
	faa[u]=father;
	if(faa[u]!=fab[u]) book[u]=true;
	if(!book[u]&&book[father]) flag=false;
	for(int v:GA[u])
	{
		if(v==father) continue;
		dfsa(v,u);
	}
	return;
}
void dfs(int u,int father)
{
	if(book[u])
	{
		if(book[faa[u]]) G[faa[u]].emplace_back(u),deg[u]++;
		if(book[fab[u]]) G[u].emplace_back(fab[u]),deg[fab[u]]++;
	}
	for(int v:GA[u])
	{
		if(v==father) continue;
		dfs(v,u);
	}
	return;
}
int toposort()
{
	static bool vis[N];
	for(int i=1;i<=n;i++)
		vis[i]=false;
	queue<int>q;
	for(int i=1;i<=n;i++)
		if(deg[i]==0) q.emplace(i);
	int tot=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		tot++;
		for(int v:G[u])
		{
			deg[v]--;
			if(deg[v]==0) q.emplace(v); 
		}
	}
	return tot;
}
void solve()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		GA[i].clear(),GB[i].clear();
	edge.clear();
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		GA[x].emplace_back(y);
		GA[y].emplace_back(x);
		edge.emplace_back(x,y);
	}
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		GB[x].emplace_back(y);
		GB[y].emplace_back(x);
	}
	leaf.clear();
	findleaf(1,0);
	int ans=INF;
	for(int u:leaf)
	{
		dfsb(u,0);
		for(int v=1;v<=n;v++)
			if(u!=v)
			{ 
				for(int i=1;i<=n;i++)
					GA[i].clear(),book[i]=false,G[i].clear(),deg[i]=0;
				int fa=0;
				for(auto [uu,vv]:edge)
					if(uu==u) fa=vv;
					else if(vv==u) fa=uu;
				for(auto [uu,vv]:edge)
					{
						if(uu==u&&vv==fa) continue;
						if(uu==fa&&vv==u) continue;
						GA[uu].emplace_back(vv);
						GA[vv].emplace_back(uu);
					}
				GA[u].emplace_back(v);
				GA[v].emplace_back(u);
				flag=true;
				dfsa(u,0);
				dfs(u,0);
				if(!flag) continue;
				if(toposort()!=n) continue;
				int res=(v!=fa);
				for(int i=1;i<=n;i++)
					if(book[i]) res++;
				ans=min(ans,res);
			}
	}
	if(ans>=INF) printf("-1\n");
	else printf("%d\n",ans); 
	return;
}
int main()
{
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}