Dashboard - Codeforces Round 776 (Div. 3) - Codeforces

A Deletions of Two Adjacent Letters

题意：看看与题目给的字符一样的字符所在的位置两边的字符能不能合并，合并是指将相邻的字符删除

思路：我们就找到目标字符的位置，判断这个字符两边的字符是否是偶数即可，只要找到一个满足即可

void solve() {
    string s;
    cin >> s;
    char op;
    cin >> op;
    vector<int> ans;
    for (int i = 0; i < s.size(); i++)if (s[i] == op)ans.push_back(i);
    for (auto i: ans) {
        if (i % 2 == 0 && (s.size() - 1 - i) % 2 == 0) {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

B DIV + MOD

题意：给定\(l\)和\(r\)以及\(a\)，找到一个数在\(l\)和\(r\)之间满足\(f_a(x)=\left\lfloor\frac{x}{a}\right\rfloor + x \bmod a\)最大

思路：我们其实可以发现，尽可能让余数变大以及除以a的倍数变大，我们可以从\(r\)开始往前找能使 \(x \bmod a\)的余数是a-1就是最大的值，因为我们往前找余数为a-1的过程中\(x/a\)最多减少1，而我们余数在这个过程中最少贡献1，最多贡献a-1，所以我们往前找不会让答案变小，如果我峨嵋你找到余数为a-1的位置在\(l\)前面，那还不如选原来的位置

void solve() {
    int l, r, a;
    cin >> l >> r >> a;
    int x=r%a;
    int rr=r-(x-1)-2;
    if(x==a-1)cout<<r/a+r%a<<endl;
    else if(rr>=l)cout<<rr/a+rr%a<<endl;
    else cout<<r/a+r%a<<endl;
}

C Weight of the System of Nested Segments

题意：问在题目所给的这些点中，构建一个题目要求的多层嵌套系统，要求这个系统所用到点的权值最小

思路：其实就是一个纯贪心，先按权值最大排个序，题目用不到的那几个点先标记了，再按坐标从小到大排序，从外层一层一层的求解答案，遇到标记过的就跳过即可

void solve() {
    vector<PII > a, b;
    int k, n;
    cin >> k >> n;
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        a.emplace_back(i, x);
        b.emplace_back(i, y);
        mp[i] = y;
    }
    sort(ALL(b), [](PII x, PII y) {
        return x.se > y.se;
    });
    sort(ALL(a), [](PII x, PII y) {
        return x.se < y.se;
    });
    vector<bool> vis(n + 1, false);
    vector<PII > ans;
    int anss = 0;
    for (int i = 0; i < n - k * 2; i++) {
        vis[b[i].fi] = true;
    }
    for (int i = 0, j = n - 1, cnt = 0; cnt < k; i++, j--, cnt++) {
        while (vis[a[i].fi] && i < j)i++;
        while (vis[a[j].fi] && i < j)j--;
        ans.emplace_back(a[i].fi, a[j].fi);
        anss += mp[a[i].fi] + mp[a[j].fi];
    }
    cout << anss << endl;
    for (auto [x, y]: ans)cout << x << ' ' << y << endl;
    cout << endl;
}

D Twist the Permutation

题意：给一个1~n的排列（没有顺序），问能不能通过题目所给的操作：At the \(i\)-th operation, Petya chose the first \(i\) elements of the array and cyclically shifted them to the right an arbitrary number of times (elements with indexes \(i+1\) and more remain in their places). One cyclic shift to the right is such a transformation that the array \(a=[a_1, a_2, \dots, a_n]\) becomes equal to the array \(a = [a_i, a_1, a_2, \dots, a_{i-2}, a_{i-1}, a_{i+1}, a_{i+2}, \dots, a_n]\).将这个排列还原为升序的，如果能输出每一步移动了多少，不能，输出-1

思路：我们可以发现，一定是有界的，不会出现无解的情况，其次我们可以到这来还原序列，那我们就让序列往左移，我们每次去找目标元素的位置，计算步数，并且更新序列，因为倒着还原前面的元素不会影响后面的元素，模拟一下即可复杂度\(O(\)\(x^{2}\)\()\)

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)cin >> a[i];
    vector<int> ans;
    int goal = n;
    for (int i = 1; i <= n; i++) {
        int pos;
        for (int j = 1; j <= goal; j++) {
            if (a[j] == goal) {
                pos = j;
                break;
            }
        }
        vector<int> temp1, temp2;
        temp1.push_back(0);
        temp2.push_back(0);
        if (pos == goal)ans.push_back(0);
        else if (pos > goal) {
            ans.push_back(pos - goal);
            for (int j = 1; j <= pos - goal; j++)temp1.push_back(a[j]);
            for (int j = pos - goal + 1; j <= goal; j++)temp2.push_back(a[j]);
            for (int j = 1; j < temp2.size(); j++)a[j] = temp2[j];
            for (int j = temp2.size(), len = 1; len < temp1.size(); j++, len++)a[j] = temp1[len];
        } else {
            ans.push_back(pos);
            for (int j = 1; j <= pos; j++)temp1.push_back(a[j]);
            for (int j = pos + 1; j <= goal; j++)temp2.push_back(a[j]);
            for (int j = 1; j < temp2.size(); j++)a[j] = temp2[j];
            for (int j = temp2.size(), len = 1; len < temp1.size(); j++, len++)a[j] = temp1[len];
        }
        goal--;
    }
    reverse(ALL(ans));
    for (auto i: ans)cout << i << ' ';
    cout<<endl;
}