A. Doors and Keys

Code

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

string s;
int cnt[26];

int main()
{
    int T;
    cin >> T;
    
    while (T--)
    {
        memset(cnt, 0, sizeof cnt);

        bool flag = true;
        cin >> s;
        for (int i = 0; i < s.length(); i++)
        {
            if (islower(s[i])) cnt[s[i] - 'a']++;
            else 
            {
                if (!cnt[s[i] - 'A'])
                {
                    puts("NO");
                    flag = false;
                    break;
                }   
            }
        }
        if (flag)  puts("YES");
    }
    return 0;
}

B. Anti-Fibonacci Permutation

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 55;

int n, a[N];

void solve()
{
    cin >> n;
    int now = 1;
    for (int i = n; i >= 1; i--)    a[i] = now++;
    
    for (int i = 1; i <= n; i++)    cout << a[i] << ' ';
    cout << endl;
    
    int cnt = 0;
    
    for (int i = n; i >= 2; i--) 
    {
        swap(a[i - 1], a[i]);

        for (int i = 1; i <= n; i++)    cout << a[i] << ' ';
        cout << endl;

        swap(a[i - 1], a[i]);
    }
}

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

C. Increase Subarray Sums

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 5050;
typedef long long ll;

ll n, x;
ll a[N], pre[N], ans[N];  // ans[i]是长度为i的子区间最大和

void solve()
{
    cin >> n >> x;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i]; 
    }

    for (int i = 1; i <= n; i++)    ans[i] = -1e-18;
    ans[0] = 0;

    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++)
            ans[r - l + 1] = max(ans[r - l + 1], pre[r] - pre[l - 1]);  // 求出各长度的最大子段和
    
    cout << *max_element(ans, ans + 1 + n)  <<  ' ';  // 先输出 k = 0 的情况
    for (int i = 1; i <= n; i++)
    {
       for (int j = 0; j <= n; j++)
            if (j >= i) ans[j] += x;  // 每个区间最多能加的x次数不能超过这个区间的长度
        cout << *max_element(ans, ans + 1 + n) << ' ';
    }
    cout << endl;
}

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

D. Cross Coloring(思维)

题目大意

题意：现 $n * m$ 的矩阵中，所有格子均为白色，现还给出 $k$ 种不同的颜色（非白色）。
需要执行 $q$ 次操作，每次操作给定 $x, y$ ：

• 在 $k$ 种颜色里任选一种颜色，将第 $y$ 行和第 $y$ 列的所有格子染成这种颜色。这种染色操作将覆盖之前的颜色。
  问，进行 $q$ 次操作后，矩阵的可能颜色状态有多少种？

解题思路

参考本视频1:32:33 - 1:35:16
需要倒着处理每个操作，因为最后操作的肯定不会被覆盖

Code

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N = 200020, mod = 998244353;

ll n, m, k, q, ans;
PII p[N];

void solve()
{
    ans = 1;
    cin >> n >> m >> k >> q;
    for (int i = 1; i <= q; i++)    cin >> p[i].x >> p[i].y;

    set<int> row, col;
    for (int i = q; i >= 1; i--)  // 倒着处理
    {
        bool flag = false;
        if (!row.count(p[i].x) && col.size() != m)  flag = true;
        if (!col.count(p[i].y) && row.size() != n)  flag = true;

        row.insert(p[i].x), col.insert(p[i].y);

        if (flag)   ans = ans * k % mod;
    }

    cout << ans << endl;
}

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