B题

Problem - B - Codeforces

题意是第一行给出n，k，代表n个数，然后选择数组中的一个数，每个数都减去这个数，看最后剩下的数是否是k

经过分析，每次减去同一个数，所以最后差值不变，所以只需要看是否有两个数差值为k就好了

注意，数据结构用map，unordered_map会超时

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 10;

int t, n, k;
int a[N];

map<int, int> mp;

main()
{
    cin >> t;

    while (t -- )
    {
        mp.clear();
        cin >> n >> k;

        for (int i = 1; i <= n; i ++)
        {
            cin >> a[i];
            mp[a[i]] = 1;
        }

        int flag = 0;
        for (int i = 1; i <= n; i ++)
        {
            if (mp[a[i] + k] && !flag)
            {
                puts("YES");
                flag = 1;
                break;
            }
        }
        if (!flag)
        {
            puts("NO");
        }
    }
}

因此想到可以使用二分来降低查找的复杂度：

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 10;

int t, n, k;
int a[N];

main()
{
    cin >> t;

    while (t -- )
    {
        cin >> n >> k;

        for (int i = 1; i <= n; i ++)
        {
            cin >> a[i];
        }
        sort(a + 1, a + n + 1);

        int flag = 0;
        for (int i = 1; i <= n; i ++)
        {
            if (binary_search(a + 1, a + n + 1, a[i] + k) && !flag)
            {
                puts("YES");
                flag = 1;
                break;
            }
        }
        if (!flag)
        {
            puts("NO");
        }
    }
}

可以看到时间复杂度下降

C题

Problem - C - Codeforces

题意是给出n个数，把每个数都对k取余，经过无限次操作使剩下的相等

经过分析发现，经过无限次操作最后剩下的无非是0和1，当原来数列中有0，那么最终把所有数变为0才满足情况输出YES，当原来数列中存在1，则把所有都变为1才能满足情况，0和1同时出现则输出NO

那么再分析除1以外的数，当有1存在，并且还有两数差值为1，那么输出NO，因为k>=2，则取余的话必然一个变0一个变1；若无1存在，则直接输出YES，因为可以从最大的数开始依次对最大数取余，可以全变0

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N];

int main()
{
    int t;
    cin >> t;
    
    while (t --)
    {
        int n;
        cin >> n;
        int one = 0, zero = 0;
        for (int i = 1; i <= n; i ++)
        {
            cin >> a[i];
            if (a[i] == 1)
                one++;
            if (a[i] == 0)
                zero++;
        }
        if (one == 0)
            cout << "YES\n";
        else if (one && zero)
        {
            cout << "NO\n";
        }
        else
        {
            sort(a + 1, a + n + 1);
            bool flag = false;
            for (int i = 2; i <= n; i ++)
                if (a[i] - a[i - 1] == 1)
                    flag = true;
            if (flag)
                cout << "NO\n";
            else
                cout << "YES\n";
        }
        
    }
}

D题

推公式，附上网上嫖来的公式

若k为奇数，则k-1+2t为偶数；若k为偶数，则k-1+2t为奇数，所以只需要满足一奇一偶则有解，否则输出-1

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n, t;

void solve()
{
    int n;
    cin >> n;
    int cnt = 1;
    while (n % 2 == 0)
    {
        n /= 2;
        cnt *= 2;
    }
    if (n == 1)
    {
        cout << "-1\n";
    }
    else
    {
        cout << min(n, cnt * 2) << endl;
    }
}

main()
{
    cin >> t;
    while (t --)
        solve();
}