Codeforces Round 897 (Div. 2)

A. green_gold_dog, array and permutation

分析:

由题意:

\(c_i\)种类最多就是\(n\)个数都不同。

若\(a_i\)不断变大，\(b_i\)不断变小，那么\(c_i\)会不断变大。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
typedef pair<pair<ll, ll>, ll> piii;
#define fi first
#define se second
using i128 = __int128;
int n, m;

int lowbit(int x)
{
    return x & -x;
}

void solve()
{
    scanf("%d", &n);
    vector<pii> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i].fi);
        a[i].se = i;
    }
    sort(a.begin() + 1, a.end());
    vector<int> b(n + 1);
    int cnt = n;
    for (int i = 1; i <= n; i++)
    {
        b[a[i].se] = cnt--;
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%d ", b[i]);
    }
    printf("\n");
}

int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

B. XOR Palindromes

分析:

如何获得回文串：

1. 对半分，通过操作使左右两侧一样。
2. 全部变成1或0

注意，如果总字符数为奇数，那么每个左右两边一样后，我们还可以将中间的字符进行一次翻转操作。

使得左右两边一样，除了将两边不同的变成相同的，还可以将两边相同的同时翻转。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
typedef pair<pair<ll, ll>, ll> piii;
#define fi first
#define se second
using i128 = __int128;
int n, m;

int lowbit(int x)
{
    return x & -x;
}

void solve()
{
    scanf("%d", &n);
    string s;
    cin >> s;
    int l = 0;
    int r = s.size() - 1;
    int cnt = 0;
    while (l < r)
    {
        if (s[l] != s[r])
        {
            cnt++;
        }
        l++;
        r--;
    }
    unordered_map<int, int> q;
    for (int i = 0; i < n; i++)
    {
        int x = s[i] - '0';
        q[x]++;
    }
    string ans;
    for (int i = 0; i <= n; i++)
    {
        ans += '0';
    }
    for (int i = cnt; i <= n / 2; i++)
    {
        if (i == cnt)
        {
            ans[i] = '1';
        }
        else
        {
            int t = i - cnt;
            ans[cnt + t * 2] = '1';
        }
    }
    if (n & 1)
    {
        for (int i = n - 1; i >= 0; i--)
        {
            if (ans[i] == '1')
            {
                ans[i + 1] = '1';
            }
        }
    }

    ans[q[0]] = '1';
    ans[q[1]] = '1';
    cout << ans << endl;
}

int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

C. Salyg1n and the MEX Game

分析:

直接贪心了，第一次添加\(MEX(S)\),之后删了啥加啥。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
typedef pair<pair<ll, ll>, ll> piii;
#define fi first
#define se second
using i128 = __int128;
int n, m;

int lowbit(int x)
{
    return x & -x;
}

void solve()
{
    scanf("%d", &n);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    int cur = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == cur)
        {
            cur++;
        }
        else
        {
            break;
        }
    }
    while (true)
    {
        printf("%d\n", cur);
        fflush(stdout);
        scanf("%d", &cur);
        if (cur == -1)
        {
            return;
        }
    }
}

int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}