源代码:ACM/OpenjudgeNow/Codeforces at master · abmcar/ACM (github.com)

更好的阅读体验: 折跃坐标

A. Doors and Keys

题目大意:

思路:

把当前得到的钥匙数存起来判断即可,可以使用isupper()和map简化

代码:

void solution()
{
    cin >> oriS;
    M.clear();
    for (char it : oriS)
    {
        M[it]++;
        if (isupper(it))
        {
            if (M[it] > M[it + 32])
            {
                cout << "NO" << endl;
                return;
            }
        }
    }
    cout << "YES" << endl;
}

B. Anti-Fibonacci Permutation

题目大意:

思路:

不难发现该排列很容易生成,当前面为1 3 2 时,后面的很容易得到所需排列

再swap第2,3个数后,使用next_permutation可以生成下一个排列

代码:

void solution()
{
    cin >> n;
    int cnt = 0;
    vector<int> V(n);
    for (int i = 0; i < n; i++)
        V[i] = i + 1;
    swap(V[1], V[2]);
    while (next_permutation(V.begin(), V.end()) && cnt < n)
    {
        bool ok = true;
        for (int i = 2; i < n; i++)
            if (V[i - 1] + V[i - 2] == V[i])
            {
                ok = false;
                break;
            }
        if (ok)
        {
            cnt++;
            for (int it : V)
                cout << it << " ";
            cout << endl;
        }
    }
}

C. Increase Subarray Sums

题目大意:

思路:

发现n只有5000,且题目需要的是连续子序列,因此我们可以做一遍前缀和,之后枚举区间,得到相同长度和最大的连续子序列

之后对于每一个k,枚举所有区间长度,加上min(k,size)*x后得到的最大值即为结果

代码:

void solution()
{
    cin >> n >> m;
    vector<int> nums(n + 1), preAns(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> nums[i];
    for (int i = 1; i <= n; i++)
        preAns[i] = preAns[i - 1] + nums[i];
    vector<int> M(n + 1, -1e18);
    vector<pair<int, int>> allSem;
    for (int len = 1; len <= n; len++)
    {
        for (int str = 1; str + len - 1 <= n; str++)
        {
            M[len] = max(M[len], preAns[str + len - 1] - preAns[str - 1]);
        }
        allSem.push_back({M[len], len});
    }
    for (int len = 0; len <= n; len++)
    {
        int nowAns = 0;
        for (auto it : allSem)
            nowAns = max(nowAns, it.first + m * min(len, it.second));
        cout << nowAns << " \n"[len == n];
    }
}

D. Cross Coloring

题目大意:

思路:

由于在后面涂的色会覆盖之前图的色,因此需要逆序处理

每涂一行/一列,把相应的行,列标记上

如果之前涂的色再行/列上会被后来的操作覆盖,则跳过

同理,如果所有行/列被覆盖,则跳过

代码:

void solution()
{
    cin >> n >> m;
    vector<int> nums(n + 1), preAns(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> nums[i];
    for (int i = 1; i <= n; i++)
        preAns[i] = preAns[i - 1] + nums[i];
    vector<int> M(n + 1, -1e18);
    vector<pair<int, int>> allSem;
    for (int len = 1; len <= n; len++)
    {
        for (int str = 1; str + len - 1 <= n; str++)
        {
            M[len] = max(M[len], preAns[str + len - 1] - preAns[str - 1]);
        }
        allSem.push_back({M[len], len});
    }
    for (int len = 0; len <= n; len++)
    {
        int nowAns = 0;
        for (auto it : allSem)
            nowAns = max(nowAns, it.first + m * min(len, it.second));
        cout << nowAns << " \n"[len == n];
    }
}