题解：CF1363C Game On Leaves

样例太难崩了，根本无法从样例上推出任何东西。

这里提供一组较为强力的样例。

输入：

PLAIN

输出：

PLAIN

Ayush

为了方便说明，我们将 Ayush 称为 A，Ashish 称为 B。

模拟样例：

A 先手。A 想要删除 $2$ 这个点，就必须先使它周围的 $3$ 个点中的 $2$ 个点被删除。于是先删除 $5$ 这个点（点 $4$ 也可以）
此时到 B 操作。根据上一条推论，B 应删除 $4$ ，但是若他真的删除了 $4$ ，则下一步 A 可以直接删掉 $2$ 获得胜利，所以他只能删除不与目标点直接相连的点。
到 A 操作时。同上一条 B 的思路，只能继续删除不与 $2$ 直接相连的点。
等到所有不与 $2$ 直接相连的点被删完时，设此时操作者是 $X$ ，剩余 $k$ 个点。此时 $X$ 只能与对方一个一个地删除掉与 $2$ 直接相连的点。则第 $k-1$ 手操作者获胜。（注意：当与 $2$ 点直接相连的点只剩一个时，直接删除 $2$ 即可，无需继续删除那一个点）

在如上过程中，可以总结出，获胜者与除了目标点和与之直接相连的点的剩余个数的奇偶性和目标点和与之直接相连的点个数的奇偶性相关。具体见如下核心代码：

CPP

    int tmp=n-d[x]-1;//除了目标点和与之直接相连的点的剩余个数
	if(tmp&1){
		if(d[x]&1)
			cout<<"Ashish"<<endl;
		else
			cout<<"Ayush"<<endl;
	}
	else{
		if(d[x]&1)
			cout<<"Ayush"<<endl;
		else
			cout<<"Ashish"<<endl;
  }

然后此时你会获得 WA。

所以记得特判只有一个点的情况和目标点为叶子节点的情况。

AC code：

CPP

// Problem: E. Game On Leaves
// Contest: Codeforces - 超新星战队 C 队第 42 周作业题
// URL: https://codeforces.com/gym/642406/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date: 2025-10-15 20:46:22 (UTC+8)
// 
// by WoodReal12
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
// #include <atcoder/all>
#define int long long 
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define pc putchar
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
using namespace std;
// using namespace atcoder;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T> inline bool read(T &x){
    x=0;int f=1;char c=gc();
    for(;c!=EOF&&!isdigit(c);c=gc())if(c=='-')f=-1;
    if(c==EOF)return 0;
    for(;c!=EOF&&c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c^48);
    x*=f;return 1;
}
template <typename T,typename ...Targs>
inline bool read(T &x,Targs& ...args){return read(x)&&read(args...);}
template <typename T> void print(T x){
    if(x<0)pc('-'),x=-x;
    if(x>=10)print(x/10);
    pc(x%10+'0');
}
int n,x;
int d[1005];
void sol(){
	for(int i=0;i<1005;i++)
		d[i]=0;
	read(n,x);
	for(int i=1;i<n;i++){
		int u,v;
		read(u,v);
		d[u]++,d[v]++;
	}
	if(d[x]==1||n==1){
		cout<<"Ayush"<<endl;
		return ;
	}
	int tmp=n-d[x]-1;//除了目标点和与之直接相连的点的剩余个数
	if(tmp&1){
		if(d[x]&1)
			cout<<"Ashish"<<endl;
		else
			cout<<"Ayush"<<endl;
	}
	else{
		if(d[x]&1)
			cout<<"Ayush"<<endl;
		else
			cout<<"Ashish"<<endl;
	}
}
int T;
signed main(){
	read(T);
	while(T--)
		sol();
	return 0;
}

题解：CF1363C Game On Leaves

文章操作

相关推荐

评论

题解：CF1363C Game On Leaves