Codeforces Round #746 (Div. 2)部分题解(A ~ C)

前言
大佬的视频讲解
A - Gamer Hemose(贪心)
- 题目大意
- 思路
- AC代码
B - Hemose Shopping (思维)
- 题目大意
- 思路
- AC代码
C - Bakry and Partitioning (数据结构+DFS+位运算)
- 题目大意
- 思路
- AC代码
D - Mathematics Curriculum(交互题+二分+欧拉序)
E - Train Maintenance
- 题目大意

前言

比赛当天，群里的两个大哥在那里讨论的十分火热，我看了看笔记本的电量，想起了 God Jun 的教诲：

“你只可到这里，不可越过。”

最后选择了关机。

这两次div2感觉都挺魔鬼的，虽然博主对掉分这种事已经麻木了，但俗话说得好：兔子再小也是肉(doge)。
另外博主也是终于达成百篇博客了，也是非常激动，再接再厉吧。

废话不多说，上主菜。

大佬的视频讲解

视频链接：https://www.bilibili.com/video/BV1jQ4y1C7Vc

讲的超级好，推荐大家自己去看一下。

"Mr.RainsdRop的博客怎么办？还看吗？"

大家都知道，Mr.RainsdRop就是个笑话，有大佬讲题还看这个家伙瞎扯干嘛？大伙不会觉得他很强吧？

A - Gamer Hemose(贪心)

比赛链接：https://codeforces.com/problemset/problem/1592/A

题目大意

你现在有 n n n把武器，每把武器都有自己的一个伤害值 a i a_i ai。
你家门前来了一个大怪物，现在世界聚焦于你，你决定用你的武器打败怪物。

这个怪物的血量是 H H H，每回合你可以从你的武器中任意挑一把武器对怪物造成伤害。
但是，你不能连续两回合使用同一把武器战斗。

请问，最少需要几回合可以打败怪物？

思路

一个非常简单的贪心。

首先我们需要正确理解你不能连续两回合使用同一把武器战斗。
假如第一回合我使用了A武器，那么第二回合我就不能再用A武器了。但是，第三回合我可以再用A武器。
也就是说，每把武器具有一回合的冷却时间。

那么这道题就很简单了：每次我们都选择当前伤害最高，CD已经转好的武器来砍怪，这种方法是最高效的。

那么再结合你不能连续两回合使用同一把武器战斗，我们只需要一直使用伤害最高的两把武器，轮换着用就可以了。
然后再加上一点点的思考，代码完成。

AC代码

#include
using namespace std;
typedef long long ll;
const int maxn=1050;

int a[maxn];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,h;
        cin>>n>>h;
        for(int i=0;i>a[i];
        sort(a,a+n,greater());
        if(a[0]>=h) cout<<"1"<a[0]) cout<<2*x+2< 
 
B - Hemose Shopping (思维) 
比赛链接：https://codeforces.com/problemset/problem/1592/B 
题目大意 
当前有一个长度为
    
     
      
       
        n
       
      
      
       n
      
     
    n的数组，
    
     
      
       
        H
       
       
        e
       
       
        m
       
       
        o
       
       
        s
       
       
        e
       
      
      
       Hemose
      
     
    Hemose想要对数组排序，让它变成非递减序列。
 一个
    
     
      
       
        s
       
       
        o
       
       
        r
       
       
        t
       
      
      
       sort
      
     
    sort就能解决的问题，
    
     
      
       
        H
       
       
        e
       
       
        m
       
       
        o
       
       
        s
       
       
        e
       
      
      
       Hemose
      
     
    Hemose也能想到该怎么做。 
但那样做就太无聊了，于是
    
     
      
       
        H
       
       
        e
       
       
        m
       
       
        o
       
       
        s
       
       
        e
       
      
      
       Hemose
      
     
    Hemose制定了一个排序的规则： 
 
 每次我们可以选择两个下标
     
      
       
        
         i
        
        
         ，
        
        
         j
        
       
       
        i，j
       
      
     i，j，满足
     
      
       
        
         1
        
        
         ≤
        
        
         i
        
        
         ,
        
        
         j
        
        
         ≤
        
        
         n
        
       
       
        1≤i,j≤n
       
      
     1≤i,j≤n,并且
     
      
       
        
         ∣
        
        
         i
        
        
         −
        
        
         j
        
        
         ∣
        
        
         ≥
        
        
         x
        
       
       
        |i−j|≥x
       
      
     ∣i−j∣≥x，交换
     
      
       
        
         
          a
         
         
          i
         
        
       
       
        a_i
       
      
     ai和
     
      
       
        
         
          a
         
         
          j
         
        
       
       
        a_j
       
      
     aj。 
 
现在给出数组和
    
     
      
       
        x
       
      
      
       x
      
     
    x的值，问是否可以把数组变得有序。 
思路 
一个简单的思维题。 
先把一些特殊情况特判掉： 
 
 1.序列本身就是一个不递减序列，此时
     
      
       
        
         x
        
       
       
        x
       
      
     x取值不影响，输出
     
      
       
        
         Y
        
        
         E
        
        
         S
        
       
       
        YES
       
      
     YES；
 2.不满足条件
     
      
       
        
         1
        
       
       
        1
       
      
     1，且
     
      
       
        
         x
        
        
         >
        
        
         n
        
       
       
        x>n
       
      
     x>n，则序列无法改变，输出
     
      
       
        
         N
        
        
         O
        
       
       
        NO
       
      
     NO；
 3.不满足条件
     
      
       
        
         1
        
       
       
        1
       
      
     1，但
     
      
       
        
         n
        
        
         >
        
        
         =
        
        
         2
        
        
         ∗
        
        
         x
        
       
       
        n>=2*x
       
      
     n>=2∗x，此时序列可以任意改动，输出
     
      
       
        
         Y
        
        
         E
        
        
         S
        
       
       
        YES
       
      
     YES； 
 
接下来我们分析一下其他情况。 
对于数组
    
     
      
       
        a
       
      
      
       a
      
     
    a(下标从
    
     
      
       
        1
       
      
      
       1
      
     
    1开始)来说，当我们选择
    
     
      
       
        i
       
       
        =
       
       
        1
       
      
      
       i=1
      
     
    i=1(固定左边界)时，
    
     
      
       
        j
       
      
      
       j
      
     
    j就需要满足
    
     
      
       
        j
       
       
        >
       
       
        =
       
       
        x
       
       
        +
       
       
        1
       
      
      
       j>=x+1
      
     
    j>=x+1，此时我们可以让下标在
    
     
      
       
        [
       
       
        x
       
       
        +
       
       
        1
       
       
        ，
       
       
        n
       
       
        ]
       
      
      
       [x+1，n]
      
     
    [x+1，n]区间内的数字通过
    
     
      
       
        a
       
       
        [
       
       
        1
       
       
        ]
       
      
      
       a[1]
      
     
    a[1]进行调整，最终可以让
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        x
       
       
        +
       
       
        1
       
       
        ,
       
       
        x
       
       
        +
       
       
        2
       
       
        ,
       
       
        .
       
       
        .
       
       
        .
       
       
        n
       
       
        ]
       
      
      
       [1,x+1,x+2,...n]
      
     
    [1,x+1,x+2,...n]达到非递减子序列。
 同时我们反向思考，如果我们选择
    
     
      
       
        j
       
       
        =
       
       
        n
       
      
      
       j=n
      
     
    j=n(固定右边界)，
    
     
      
       
        i
       
      
      
       i
      
     
    i就需要满足
    
     
      
       
        i
       
       
        <
       
       
        =
       
       
        n
       
       
        −
       
       
        x
       
      
      
       i<=n-x
      
     
    i<=n−x。那么我们同样可以利用
    
     
      
       
        a
       
       
        [
       
       
        n
       
       
        ]
       
      
      
       a[n]
      
     
    a[n]把下标在
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        n
       
       
        −
       
       
        x
       
       
        ]
       
      
      
       [1,n-x]
      
     
    [1,n−x]区间内的数字调整一下，最终让
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        2
       
       
        ,
       
       
        .
       
       
        .
       
       
        .
       
       
        ,
       
       
        n
       
       
        −
       
       
        x
       
       
        ,
       
       
        n
       
       
        ]
       
      
      
       [1,2,...,n-x,n]
      
     
    [1,2,...,n−x,n]达到非递减子序列。 
此时我们会发现：
    
     
      
       
        [
       
       
        n
       
       
        −
       
       
        x
       
       
        +
       
       
        1
       
       
        ，
       
       
        x
       
       
        ]
       
      
      
       [n-x+1，x]
      
     
    [n−x+1，x]区间内的数是没法确定有序的，此时我们只需要看这一段是否原本就是有序的，如果不是那么我们就没办法让它有序。 
AC代码 
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+100;

int a[maxn];
int b[maxn];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,x;
        cin>>n>>x;
        for(int i=0;i>a[i];
            b[i]=a[i];
        }
        sort(a,a+n);
        int flag=1;
        for(int i=0;in) cout<<"NO"<=2*x) cout<<"YES"< 
 
C - Bakry and Partitioning (数据结构+DFS+位运算) 
比赛链接：https://codeforces.com/problemset/problem/1592/C 
题目大意 
现在给一颗有
    
     
      
       
        n
       
      
      
       n
      
     
    n个结点，
    
     
      
       
        n
       
       
        −
       
       
        1
       
      
      
       n-1
      
     
    n−1条边的树，树上的每个结点都有自己的权值
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i]。 
现在再给一个数字
    
     
      
       
        k
       
      
      
       k
      
     
    k，问是否存在以下情况：
 在删除
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        k
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       [1,k-1]
      
     
    [1,k−1]条边之后形成的森林中，每棵树的结点的异或和的值全部相等。 
思路 
博主一直以来都不是很擅长位运算，所以在一开始做的时候博主也是被难住了好久。 
后来想起来，异或是一个很特别的运算(至少在博主看来)。 

     
      
       
        
         a
        
       
       
        a
       
      
     a ^ 
     
      
       
        
         a
        
        
         =
        
        
         0
        
       
       
        a=0
       
      
     a=0

     
      
       
        
         a
        
       
       
        a
       
      
     a ^ 
     
      
       
        
         0
        
        
         =
        
        
         a
        
       
       
        0=a
       
      
     0=a

     
      
       
        
         a
        
       
       
        a
       
      
     a ^ 
     
      
       
        
         a
        
       
       
        a
       
      
     a ^ 
     
      
       
        
         a
        
        
         =
        
        
         a
        
       
       
        a = a
       
      
     a=a 
接下来我们看题。 
如果树上所有的结点的异或和为
      
       
        
         
          0
         
        
        
         0
        
       
      0，则说明我们能找到
      
       
        
         
          1
         
        
        
         1
        
       
      1条边，把这棵树分裂成两棵异或和值相等的树；
如果树上所有的结点的异或和不为
      
       
        
         
          0
         
        
        
         0
        
       
      0，记为sum，则说明我们至少需要将树拆解成m(m>=3)棵树，那么k就至少要大于2；
再根据
      
       
        
         
          a
         
        
        
         a
        
       
      a ^ 
      
       
        
         
          a
         
        
        
         a
        
       
      a ^ 
      
       
        
         
          a
         
         
          =
         
         
          a
         
        
        
         a = a
        
       
      a=a的性质，我们可以把考虑范围缩小到我们能否把这棵树变成m(m>=3)棵异或和为sum的树即可。 
对于第三种情况我们使用DFS来搜索答案。设置一个数组
    
     
      
       
        b
       
      
      
       b
      
     
    b用来记录以当前结点为根节点的树的异或和是多少。
 从第一个点开始深搜，每次下传当前的结点编号与父亲结点编号(由哪个点来到当前点，那个点就是当前点的父亲，防止死循环)。 
AC代码 
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+100;

int a[maxn],b[maxn],cnt,xorr;
vector arr[maxn];

void dfs(int pos,int fa)
{
    b[pos]=a[pos];
    for(int i=0;i>t;
    while(t--){
        int n,k,x,y;
        xorr=0;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            arr[i].clear();
        for(int i=1;i<=n;i++){
            cin>>a[i];
            xorr^=a[i];
        }
        for(int i=0;i>x>>y;
            arr[x].push_back(y);
            arr[y].push_back(x);
        }
        if(xorr==0) cout<<"YES"<=3) cout<<"YES"< 
 
D - Mathematics Curriculum(交互题+二分+欧拉序) 
和树有关的交互题，超出孩子的接受范围了。
 暂时没有想法，有兴趣的可以去看大佬的视频讲解。 
 
E - Train Maintenance 
比赛链接：https://codeforces.com/problemset/problem/1592/E 
题目大意 
现给出一个长度为
    
     
      
       
        n
       
      
      
       n
      
     
    n的数组
    
     
      
       
        a
       
      
      
       a
      
     
    a。 
如果子序列
    
     
      
       
        a
       
      
      
       a
      
     
    a_{l
        
       
       
        l
       
      
     l},
    
     
      
       
        a
       
      
      
       a
      
     
    a_{l
        
        
         +
        
        
         1
        
       
       
        l+1
       
      
     l+1},
    
     
      
       
        a
       
      
      
       a
      
     
    a_{l
        
        
         +
        
        
         2
        
       
       
        l+2
       
      
     l+2},…,
    
     
      
       
        a
       
      
      
       a
      
     
    a_{r
        
       
       
        r
       
      
     r} 满足如下条件，我们认为它是一个好序列：
 
     
      
       
        
         a
        
       
       
        a
       
      
     a_{l
         
        
        
         l
        
       
      l} & 
     
      
       
        
         a
        
       
       
        a
       
      
     a_{l
         
         
          +
         
         
          1
         
        
        
         l+1
        
       
      l+1} & 
     
      
       
        
         a
        
       
       
        a
       
      
     a_{l
         
         
          +
         
         
          2
         
        
        
         l+2
        
       
      l+2} & … & 
     
      
       
        
         a
        
       
       
        a
       
      
     a_{r
         
        
        
         r
        
       
      r} > 
     
      
       
        
         a
        
       
       
        a
       
      
     a_{l
         
        
        
         l
        
       
      l} ⊕ 
     
      
       
        
         a
        
       
       
        a
       
      
     a_{l
         
         
          +
         
         
          1
         
        
        
         l+1
        
       
      l+1} ⊕ 
     
      
       
        
         a
        
       
       
        a
       
      
     a_{l
         
         
          +
         
         
          2
         
        
        
         l+2
        
       
      l+2} ⊕ … ⊕ 
     
      
       
        
         a
        
       
       
        a
       
      
     a_{r
         
        
        
         r
        
       
      r} 
请你输出数组
    
     
      
       
        a
       
      
      
       a
      
     
    a中最长的好序列是多长?(
    
     
      
       
        r
       
       
        −
       
       
        l
       
       
        +
       
       
        1
       
      
      
       r-l+1
      
     
    r−l+1的最大值) 
RainsdRop，无情的翻译机器。 
 
感谢阅读，希望能对你产生一点用处。 
 
 

 吾日三省吾身：日更否？刷题否？快乐否？
 

 更新了，但不是日更；已刷；happy！
 

 吾心满意足。

Codeforces Round #746 (Div. 2)部分题解(A ~ C)

C/C++/C#相关栏目本月热门文章