完整代码:https://github.com/abmcar/ACM/tree/master/OpenjudgeNow/Codeforces/Codeforces%20Round%20%23761%20(Div.%202)

A. Forbidden Subsequence

在这里插入图片描述
题目大意:给你一个字符串s和t,t是”abc“的排列,求字典序最小的s的排列且t不是他的子串
思路:
当t不为”abc“是按照a-z的顺序直接给出最小字典序
当t为"abc"时,若abc都存在,则按照acb-z的顺序输出
代码:

void work()
{
    string s1, s2;
    cin >> s1 >> s2;
    map<char, int> M;
    for (char it : s1)
        M[it]++;
    string ans = "";
    if (s2 == "abc" && M['a'] && M['b'] && M['c'])
    {
        for (int i = 1; i <= M['a']; i++)
            ans += 'a';
        for (int i = 1; i <= M['c']; i++)
            ans += 'c';
        for (int i = 1; i <= M['b']; i++)
            ans += 'b';
        for (char i = 'd'; i <= 'z'; i++)
            for (int j = 1; j <= M[i]; j++)
                ans += i;
    }
    else
        for (char i = 'a'; i <= 'z'; i++)
            for (int j = 1; j <= M[i]; j++)
                ans += i;
    cout << ans << endl;
}

B. GCD Problem

在这里插入图片描述
题目大意:给你一个n,让你求a+b+gcd(a,b) = n的方案
思路:
设定gcd(a,b) = 1
1.暴力a=2,3,4.... 计算b=n-a-1 之后chekck gcd是否为1
(不会超时,因为算不了多少个,但不会证明
2.随机a,计算b=n-a-1,之后计算gcd(原理同1
3.构造
在这里插入图片描述
代码:

void work()
{
    cin >> n;
    if (n % 2 == 0)
    {
        cout << n / 2 << " " << n / 2 - 1 << " " << 1 << endl;
    }
    else
    {
        int nowNum = n / 2;
        if (nowNum % 2)
            cout << nowNum - 2 << " " << nowNum + 2 << " " << 1 << endl;
        else
            cout << nowNum - 1 << " " << nowNum + 1 << " " << 1 << endl;
    }
}

C. Paprika and Permutation

在这里插入图片描述
题目大意:给你一个数组,你可以选择让其中的任意一个数%x,问最少多少次能使其成为排列
思路:
我们知道n%x < n/2,因此我们需要让多余的小的数去mod成缺的小的数,先对数组判重排序找出多余的,对多余的排序去填缺少的
代码:

void work()
{
    cin >> n;
    vector<int> nums(n);
    vector<int> unuse, targetNum;
    map<int, bool> M;
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
        if (!M[nums[i]] && nums[i] <= n)
            M[nums[i]] = true;
        else
            unuse.push_back(nums[i]);
    }
    sort(tALL(unuse));
    for (int i = 1; i <= n; i++)
    {
        if (M[i])
            continue;
        targetNum.push_back(i);
    }
    // cout << unuse.size() << " " << targetNum.size() << endl;
    for (int i = 0; i < unuse.size(); i++)
    {
        int nowNum = unuse[i];
        int tarNum = targetNum[i];
        if ((nowNum-1) / 2 < tarNum)
        {
            cout << "-1" << endl;
            return;
        }
    }
    cout << unuse.size() << endl;
}

D1. Too Many Impostors (easy version)

在这里插入图片描述
题目大意:有n个玩家玩among us,有k个平民和n-k个狼,你一次可以询问a,b,c三个玩家中狼多还是平民多,让你在2n次询问内给出所有的狼
思路:10101010010
把01串看成是平民还是狼,我们对每一个连续的三个玩家进行询问,
如果query(i) != query(i+1),则我们可以知道i+1和i+2是一狼一平民,
之后用i+1和i+2询问其他人,可以得到除他们2个之外所有人的角色,之后在其他角色中找一个狼一个平民来询问i+1和i+2,可以在2
n此询问内得到所有人的角色
代码:

int query(int pos)
{
    cout << "? " << pos << " " << pos + 1 << " " << pos + 2 << endl;
    int tar;
    cin >> tar;
    return tar;
}

int query(int pos, int p1, int p2)
{
    cout << "? " << pos << " " << p1 << " " << p2 << endl;
    int tar;
    cin >> tar;
    return tar;
}

void work()
{
    cin >> n;
    vector<int> nums(n + 1);
    vector<int> qAns(n + 1);
    vector<int> ans(n + 1);
    for (int i = 1; i + 2 <= n; i++)
        qAns[i] = query(i);
    int p1, p2, p3;
    p1 = p2 = p3 = -1;
    for (int i = 1; i + 3 <= n; i++)
        if (qAns[i] != qAns[i + 1])
        {
            if (p1 == -1)
                p1 = i + 1;
        }
    for (int i = 1; i <= n; i++)
    {
        if (i == p1 || i == p1 + 1)
            continue;
        ans[i] = query(i, p1, p1 + 1);
    }
    for (int i = 1; i + 1 <= n; i++)
    {
        if (i == p1 || i == p1 + 1)
            continue;
        if (ans[i] == 0)
            p2 = i;
        else
            p3 = i;
    }
    ans[p1] = query(p1, p2, p3);
    ans[p1 + 1] = query(p1 + 1, p2, p3);
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        cnt += ans[i];
    cout << "! " << n - cnt << " ";
    for (int i = 1; i <= n; i++)
        if (ans[i] == 0)
            cout << i << " ";
    cout << endl;
}