2025年HDU - 5963 朋友（思维题）

大家好，我是讯享网，很高兴认识大家。

题干

B君在围观一群男生和一群女生玩游戏，具体来说游戏是这样的：
给出一棵n个节点的树，这棵树的每条边有一个权值，这个权值只可能是0或1。在一局游戏开始时，会确定一个节点作为根。接下来从女生开始，双方轮流进行操作。
当一方操作时，他们需要先选择一个不为根的点，满足该点到其父亲的边权为1; 然后找出这个点到根节点的简单路径，将路径上所有边的权值翻转（即0变成1，1 变成0 )。
当一方无法操作时(即所有边的边权均为0)，另一方就获得了胜利。
如果在双方均采用最优策略的情况下，女生会获胜，则输出“Girls win!”，否则输出“Boys win!”。
为了让游戏更有趣味性，在每局之间可能会有修改边权的操作，而且每局游戏指定的根节点也可能是不同的。
具体来说，修改边权和进行游戏的操作一共有m个，具体如下：

“0 x”表示询问对于当前的树，如果以x为根节点开始游戏，哪方会获得胜利。
“1 x y z ”表示将x和y之间的边的边权修改为z。

B君当然知道怎么做啦！但是他想考考你。

Input

包含至多5组测试数据。
第一行有一个正整数，表示数据的组数。
接下来每组数据第一行，有二个空格隔开的正整数n,m，分别表示点的个数，操作个数。保证n,m< 40000。
接下来n-1行，每行三个整数x,y,z，表示树的一条边。保证1<x<n, 1<y< n, 0 <= z <= 1。
接下来m行，每行一个操作，含义如前所述。保证一定只会出现前文中提到的两种格式。
对于操作0，保证1 <= x <= n ;对于操作1，保证1 <= x <= n, 1 <= y <= n, 0 <= z <= 1，保证树上存在一条边连接x和y。

Output

对于每组数据的每一个询问操作，输出一行“Boys win!”或者“Girls win!”。

讯享网

Example

test in: 2 2 3 1 2 0 0 1 1 2 1 1 0 2 4 11 1 2 1 2 3 1 3 4 0 0 1 0 2 0 3 0 4 1 2 1 0 0 1 0 2 0 3 1 3 4 1 0 3 0 4 test out: Boys win! Girls win! Girls win! Boys win! Girls win! Boys win! Boys win! Girls win! Girls win! Boys win! Girls win!

讯享网

又到了唠嗑的时间了

仔细想一想，这个游戏获胜的关键是“堵”。有点像什么？井字棋，还有五子棋。这样的游戏，我们都知道是有所谓的“必胜法”的（当然五子棋规模太大了），所以解决这道题的关键也是找到它的“必胜法”。

每局游戏都是女生先手，这是一个很关键的地方。我刚才说到游戏的关键在于“堵”，首先要搞明白的是，我们堵的是什么？毫无疑问，是“1” 。打个比方，对于这个游戏而言，“1”就好比是我们在玩五子棋时的空白格子，“0”就是已经被占用了的格子，我们的目标就是让对方无路可走。由于我们每走一步都要从根出发，所以获胜的条件就是要保证树上除了根节点以外的每个点，在到达根节点的路径上至少存在一个边权为“0”的边。所以说，回到本题，我们每走一步，就是把从根节点到某一个子节点的路径都反转一下，也就是说，我们是肯定要经过某一个与根节点相连的边的，也就是说，这个边一定会被反转。那我们想一下，如果这个边是“0”，那我们反转一下，岂不是给对手创造了机会，自寻死路吗？所以我们一旦要反转从根节点到某个节点，要反转的这条路径上的边权一定是连续的“1”。从根节点向外延伸的边是有限的，这时我们会发现，当我们每次反转了一条权值为“1”的链，对方每次也反转一条权值为“1”的链，那么当向外延伸的“1”链的条数为奇数条时，那么必然是先手的那方先翻完全部的连续为“1”的链，也就是说先手获胜；那么，当从根节点向外延伸的“1”链的条数为偶数条时，当然就是后手赢，因为当先手反转了一条“1”链，此时根节点向外延伸的“1”链的条数就会变为奇数条，后手也就成了刚才的先手。

到这里，这道题就差不多结束了，最后我们相当于只需要考虑与根节点相连的边中权值为“1”的边的个数，如果是奇数，则女生赢，如果是偶数（0当然也是偶数），则男生赢。

代码如下：

讯享网#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<map> using namespace std; const int maxn=40000+10; int cnt[maxn];//记录每个点相邻的边权为一的边有多少 map<int,int> tree;//记录每条边的权值 int n,m; int main(){ 
    int t; cin>>t; while(t--){ 
    memset(cnt,0,sizeof(cnt)); tree.clear(); scanf("%d%d",&n,&m); for(int i=1;i<n;i++){ 
    int u,v,z; scanf("%d%d%d",&u,&v,&z); if(z==1){ 
    cnt[u]++; cnt[v]++; tree[u*n+v]=1; tree[v*n+u]=1; } } for(int i=1;i<=m;i++){ 
    int fl,u,v,z; scanf("%d",&fl); if(fl==1){ 
    scanf("%d%d%d",&u,&v,&z); if(z==1&&tree[u*n+v]==0){ 
   //边权原来可能就是1，我们要避免重复计算 cnt[u]++; cnt[v]++; tree[u*n+v]=tree[v*n+u]=1; } else if(z==0&&tree[u*n+v]==1){ 
   //同上 cnt[u]--; cnt[v]--; tree[u*n+v]=tree[v*n+u]=0; } } else{ 
    scanf("%d",&u); if(cnt[u]%2==1){ 
    printf("Girls win!\n"); } else{ 
    printf("Boys win!\n"); } } } } }

2025年HDU - 5963 朋友（思维题）

题干

Input

Output

Example

又到了唠嗑的时间了

相关推荐