Codeforces-Round-776-Div-3

一定会补上剩下的题的，恩，一定会

CodeForces 1650A. Deletions of Two Adjacent Letters—原题链接

题目标签：思维题

思路：
除去只有一个字母的特殊情况，字符串中对出现的目标字母左右字符个数进行统计，只要满足一个字母的左右都是偶数，也就是能两个两个消掉就成立，否则不成立

#include <bits/stdc++.h>
using namespace std;

int TIMES;

void solve()
{
    string s;
    char c;
    cin >> s >> c;

    if(s.size() == 1 && s[0] == c)
    {
        puts("YES");
        return;
    }
    else if(s.size() == 1 && s[0] != c)
    {
        puts("NO");
        return;
    }

    for(int i=0; i<s.size(); i++)
    {
        if(s[i] == c)
        {
            int l = i, r = s.size() - i - 1;
            // cout << l << "-" << r << endl;
            if((l & 1) == 0 && (r & 1) == 0)
            {
                puts("YES");
                return;
            }
        }
    }
    puts("NO");
}

int main()
{
    cin >> TIMES;
    while(TIMES -- )
    {
        solve();
    }
    return 0;
}

---

CodeForces 1650B. DIV + MOD—原题链接

题目标签：数学

思路：
目标函数有两部分组成：
前半部分是单调递增的一次函数，后半部分是值域在[0, a-1]的周期函数，并且每个周期内递增
所以最大值有两个情况，要么是最右端，要么是周期函数中最靠右的峰值对应的点
注意定义域要在[l, r]之间

#include <bits/stdc++.h>
using namespace std;

int TIMES;
int l, r, n;

int f(int x)
{
    return (x / n) + (x % n);
}

void solve()
{
    cin >> l >> r >> n;
    int a = f(r);
    int t = r - r % n - 1;
    int b = f(t);
    if(t >= l) a = max(a, b);
    cout << a << endl;
}

int main()
{
    cin >> TIMES;
    while(TIMES -- )
    {
        solve();
    }
    return 0;
}

---

CodeForces 1650C. Weight of the System of Nested Segments—原题链接

题目标签：贪心

思路：
反复排序求贪心即可，非常暴力的做法，总感觉会被hack…

#include <bits/stdc++.h>
using namespace std;

int TIMES;
int n, m;

struct node
{
    int id, dx, w, mark;
};

bool cmp1(node a, node b)
{
    return a.w < b.w;
}

bool cmp2(node a, node b)
{
    return a.dx < b.dx;
}

void solve()
{
    cin >> n >> m;
    node nodes[m+1];
    int maxx = -1e9, minn = 1e9;
    for(int i=1; i<=m; i++)
    {
        int a, b;
        cin >> a >> b;
        nodes[i] = {i, a, b, 0};
    }
    
    sort(nodes+1, nodes+1+m, cmp1);
    for(int i=1; i<=m; i++)
    {
        nodes[i].mark = i;
    }

    sort(nodes+1, nodes+1+m, cmp2);
    int res = 0, cnt = n;
    int i=1, j=m;
    queue<pair<int, int>> q;
    while(cnt)
    {
        while(nodes[i].mark > 2 * n) i++;
        while(nodes[j].mark > 2 * n) j--;
        q.push({nodes[i].id, nodes[j].id});

        res = res + nodes[i].w + nodes[j].w;

        i++;
        j--;
        cnt--;
    }

    cout << res << endl;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        cout << t.first << " " << t.second << endl;
    }
    cout << endl;


    // for(int i=1; i<=m; i++)
    // {
    //     cout << nodes[i].dx << " : " << nodes[i].w << endl;
    // }
}

int main()
{
    cin >> TIMES;
    while(TIMES -- )
    {
        solve();
    }
    return 0;
}

---

CodeForces 1650D. Twist the Permutation—原题链接

题目标签：暴力 | 模拟

思路：
按照题目要求，恩模拟就完了，难点在于边界判断啊……
不得不说，虽然没有什么技术含量在里面，但是不看题解啃出来还是蛮有成就感

#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 10;
int TIMES, n;

void solve()
{
    cin >> n;
    vector<int> a(n+1);
    vector<int> ans(n+1);
    for(int i=1; i<=n; i++) cin >> a[i];

    for(int i=n; i>0; i--)
    {
        int point = 0;
        for(int j=1; j<=i; j++)
        {
            if(a[j] == i)
            {
                point = j;
                break;
            }
        }
        if(point == i) ans[i] = 0;
        else ans[i] = point;
        vector<int> b(n+1);
        for(int j=1; j<=i; j++)
        {
            int t = j - point + i;
            if(t >= i+1) t -= i;
            b[t] = a[j];
        }
        a = b;
    }
    ans[1] = 0;
    for(int i=1; i<=n; i++) cout << ans[i] << " ";
    cout << endl;
}

int main()
{
    cin >> TIMES;
    while(TIMES -- )
    {
        solve();
    }
    return 0;
}

---