A Gamer Hemose

题目大意

给定一个n, m和长度为n的数组，不能连续取两次相同的数，问取多少次才能使和大于等于m

主要思路

判断最大的两个数取几次能得到结果即可

AC代码

#include <bits/stdc++.h>

#define int long long
using namespace std;
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef long long ll;
const int N = 200010, mod = 1e9+7;
int n, m, k, a[N];
int f[N];

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        sort(a + 1, a + 1 + n);
        int ans = m / (a[n] + a[n - 1]) * 2;

        if(ans / 2 * (a[n] + a[n - 1]) == m) ;
        else if(ans / 2 * (a[n] + a[n - 1]) + a[n] >= m) ans++;
        else ans += 2;
        cout << ans << endl;
    }
    return 0;
}

B Hemose Shopping

题目大意

给定一个长度为n的数组和一个数x，我们只能交换距离大于等于x的两个数，问能否让数组变成非递减数组

主要思路

• 当x小于等于n/2时，我们一定能得到非递减数组
• 当x大于n/2时，在数组中间的几个数无法被交换，其余数可以任意交换，所以考虑中间无法被交换的几个数是否与排序后的数组相同即可

AC代码

#include <bits/stdc++.h>

#define int long long
using namespace std;
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef long long ll;
const int N = 200010, mod = 1e9+7;
int n, x, a[N], b[N];

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n >> x;
        for(int i = 0; i < n; i++) cin >> a[i], b[i] = a[i];
        if(x <= n / 2) cout << "YES" << endl;
        else
        {
            bool flag = true;
            sort(a, a + n);
            
            for(int i = n - x; i < x; i++)
            {
                if(a[i] != b[i]) flag = false;
            }
            
            if(flag) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
    return 0;
}

C Bakry and Partitioning

题目大意

给定一棵树，每个点上有权值，问能否通过减少1~k-1条边让每棵树的权值^值相同

主要思路

由于是一棵树，我们可以以任意点作为根节点，假设1号点为根，那么整棵树就能确定

• 如果减边之前整棵树的异或值为0，那么一定可以通过减掉任意一条边让两棵树的异或值相同
• 如果整棵树的异或值不为0，那么k == 2时一定不能通过减1条边让两棵树异或值相同
• 我们从1号点dfs整棵树，每个点表示以这个点为根的数的异或和，如果有树与根节点的异或值相同，那么数量+1，假设数量 >= 2我们就可以从中任选两棵树将其从树上拆分下来成为单独的树，这样三棵树的异或值一定相同

AC代码

#include <bits/stdc++.h>

#define int long long
using namespace std;
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef long long ll;
const int N = 100010, mod = 1e9+7;
int n, k;
int h[N], e[N * 2], ne[N * 2], idx;
int a[N];

int cnt, res;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int root, int father)
{
    int sum = a[root];
    for(int i = h[root]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        sum ^= dfs(j, root);
    }
    if(sum == res) cnt++, sum = 0;
    return sum;
}

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while(T--)
    {
        idx = 0;
        cin >> n >> k;
        
        res = 0;
        for(int i = 1; i <= n; i++) cin >> a[i], res ^= a[i], h[i] = -1;
            
        for(int i = 0; i < n - 1; i++)
        {
            int a, b;
            cin >> a >> b;
            add(a, b);
            add(b, a);
        }
        
        cnt = 0;
        dfs(1, 0);
        
        if(res == 0) cout << "YES" << endl;
        else if(k == 2) cout << "NO" << endl;
        else if(cnt < 2) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}