【题目记录】——Codeforces Round #746 (Div. 2)

秒速五厘米 2022-09-14 12:28 133阅读 0赞

### 文章目录 ###

*  A Gamer Hemose
 *  B. Hemose Shopping
 *  C. Bakry and Partitioning

题目集地址 [Codeforces Round \#746 (Div. 2)][Codeforces Round _746 _Div. 2]

# A Gamer Hemose #

题目地址[A Gamer Hemose][]  
题目大意： 有n把武器和血量为h的敌人，每把武器有固定的伤害值，每个回合只能选择一把武器，连续的两个回合使用的武器不能相同的武器，问杀死敌人的最少回合数。  
思路：简单题目，就是找到伤害最高的那把武器是否大于等于h，如果是那就是只需要一个回合，如果不是那就找到伤害第二高的武器轮流使用这两把武器，计算出使用的次数即可。  
AC代码：

#include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N=2e3+5;
    int w[N];
    bool com(int a, int b)
    { 
        return a > b;
    }
    void solve()
    { 
        int n,h;
        scanf("%d%d",&n,&h);
        for(int i = 1;i <= n;i++)
        { 
            scanf("%d",w+i);
        }
        sort(w+1,w+1+n,com);
        int ans = 0;
        if(w[1] >= h)
        { 
            printf("1\n");
        }
        else
        { 
            ans = h/(w[1]+w[2])*2;
            int t = h%(w[1]+w[2]);
            if(t)
            { 
                if(w[1]>=t)
                { 
                    ans++;
                }
                else
                { 
                    ans+=2;
                }
            }
            printf("%d\n",ans);
        }
    }
    
    int main()
    { 
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

# B. Hemose Shopping #

题目地址[B. Hemose Shopping][]  
题目大意：给定一个数组长度为n，每次交换值的时候，只能交换下标相差大于等于x的两个值，问最后能否将数组排序成为非递减数组。  
思路：  
当x>=n的时候我们发现，数组的所有值都不能交换，必须满足原数组本身就是非递减才能排序成非递减数组。  
当x<n的时候，区间\[n-x,x\]内的值都无法交换，因此只需要找到排序后的数组与原数组中这部分内容比较，如果相同就输出YES，否则就是NO  
AC代码：

#include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N=1e5+5;
    const int M = 1e9+9;
    int a[N],b[N];
    void solve()
    { 
        int n, x;
        scanf("%d%d",&n,&x);
        for(int i = 1;i <= n;i ++)
        { 
            scanf("%d",a+i);
            b[i]=a[i];
        }
        sort(a+1,a+1+n);
        if(x <= n/2)
        { 
            printf("YES\n");
            return;
        }
        int f = 1;
        for(int i = 1;i <= n;i++)
        { 
            if(a[i]!=b[i])
            { 
                f=0;
            }
        }
        if(f)
        { 
            printf("YES\n");
            return;
        }
        if(n <= x)
        { 
            printf("NO\n");
            return;
        }
        else
        { 
            for(int i = n-x+1;i <= x;i++)
            { 
                if(a[i]!=b[i])
                { 
                    printf("NO\n");
                    return;
                }
            }
        }
        printf("YES\n");
    }
    
    int main()
    { 
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

# C. Bakry and Partitioning #

题目地址[C. Bakry and Partitioning][]  
题目大意：给一颗n个结点的树，删掉最少1条边和最多k-1条边，问能不能删掉边后的所有连通分量的所有结点的异或值相同。  
思路：利用异或的性质，两个相同的数异或为0，任意一个数异或0都是它本身  
如果我们将整棵树的值异或起来如果为0，那么我们随便删掉1条边，剩下的两个连通分量的异或值一定是相同的。  
如果我们将整棵树的值异或得到了一个值x，那么最后每个连通分量的异或值也一定是这个值x，这样我们可以通过一次dfs每得到一个x就记录一次，并且将这个连通分量从树中删去，然后继续搜索，这样最后会得到一个值为x的连通分量的个数，只要这个个数大于3就是YES。  
这里我用vector存的树，但是我一开始用的是链式前向星存的树结果超内存了，不知道为什么。。  
AC代码：

/* ** */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 1e5+5;
    int a[N];
    vector<int> g[N];
    int sumor[N];
    int dfs(int u,int fa,int val)
    { 
        sumor[u]=a[u];
        int num=0;
        for(int i = 0;i<g[u].size();i++)
        { 
            int v = g[u][i];
            if(v==fa) continue;
            num+=dfs(v,u,val);
            sumor[u]^=sumor[v];
        }
        if(sumor[u]==val)
        { 
            sumor[u]=0;
            num++;
        }
        return num;
    }
    void solve()
    { 
        int n, k;
        scanf("%d%d",&n,&k);
        for(int i = 1;i <= n;i++)
        { 
            g[i].clear();
        }
        int r = 0;
        for(int i = 1;i <= n;i++)
        { 
            scanf("%d",a+i);
            r^=a[i];
        }
        for(int i = 1;i <= n-1;i++)
        { 
            int from, to;
            scanf("%d%d",&from,&to);
            g[from].push_back(to);
            g[to].push_back(from);
        }
        if(r==0)
        { 
            printf("YES\n");
        }
        else
        { 
            if(k == 2)
            { 
                printf("NO\n");
                return;
            }
            int num = dfs(1,0,r);
            if(num >= 3)
            { 
                printf("YES\n");
            }
            else
            { 
                printf("NO\n");
            }
        }
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // int t = 1;
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

[Codeforces Round _746 _Div. 2]: https://codeforces.com/contest/1592
[A Gamer Hemose]: https://codeforces.com/contest/1592/problem/A
[B. Hemose Shopping]: https://codeforces.com/contest/1592/problem/B
[C. Bakry and Partitioning]: https://codeforces.com/contest/1592/problem/C