本文共 3716 字，大约阅读时间需要 12 分钟。

1450A. Avoid Trygub

挺简单的题，题意是避免字符串中有子串“Trygub"

只要给字符串排序就可以了,这样一定不会出现

void solve() {    string s; int n;    cin >> n >> s;    sort(s.begin(), s.end());    cout << s << endl;}

1450B. Balls of Steel

想太多了，因为数据范围比较小，可以直接暴力比较一下就ok

void solve() {    int n, k;    cin >> n >> k;    int x[n], y[n];    for (int i = 0; i < n; ++i)        cin >> x[i] >> y[i];    bool fl = true;    for (int i = 0; i < n && fl; i++) {        fl = 0;        for (int j = 0; j < n; j++)            if (abs(x[i] - x[j]) + abs(y[i] - y[j]) > k)                fl = 1;    }    cout << (fl ? -1 : 1) << endl;}

1450C1&C2. Errich-Tac-Toe (Hard Version)

刚开始看的时候有点懵，看了一下的解释明白了。

考虑(i + j) % 3, 记 ++cnt[(i + j) % 3][s[i][j] == 'X']

最后无非选择 i, j(-1<i,j<3, i!=j) 使得 s[i][1] + s[j][0] <= k/3, 即使得每3个相邻的标记中存在两个不同的标记

一定存在这样的 i, j使得 <= k/3, 自己画个表就明白了

int _, n, m, s[2][5];char a[305][305];void solve() {    int i, j, k, t;    scanf("%d", &n);    m = 0;    memset(s, 0, sizeof(s));    for (i = 0; i < n; i++) {        scanf("%s", a[i]);        for (j = 0; j < n; j++)            if (a[i][j] != '.')                m++, s[a[i][j] == 'X'][(i + j) % 3]++;    }    for (k = 0; k < 3; k++)        for (t = 0; t < 3; t++)            if (k ^ t && s[1][k] + s[0][t] <= m / 3) {                for (i = 0; i < n; i++)                    for (j = 0; j < n; j++)                        if (a[i][j] != '.')                            if ((i + j) % 3 == k)                                a[i][j] = 'O';                            else if ((i + j) % 3 == t)                                a[i][j] = 'X';                m = -3;            }    for (i = 0; i < n; i++)        printf("%s\n", a[i]);}

1450D. Rating Compression

根据题意模拟一下，各个用户满意情况

const int N = 3e5 + 10;char s[N];vector
   
     v[N];void solve() {    int n, a, i, j;    i = 0;    // 把各位数字的出现次数标记    for (cin >> n; i != n; s[i++] = '0', cin >> a, v[a].push_back(i))        ;   	// 模拟条件    for (a = j = 1; v[a].size() == 1 && (j == v[a][0] || v[a][0] == i);         s[n - a] = '1', i == v[a++][0] ? --i : ++j)        ;    for (v[a].empty() ? '0' : s[n - a] = '1'; a <= n && v[a].size() == 1; ++a)        ;    // 设置'\0'，并且重置v数组    for (s[n] = 0, a == ++n ? s[0] = '1' : '0'; --n; v[n].clear())        ;    cout << s << endl;}
   

1450E. Capitalism

建图跑个多源floyd最短路就好,

顺便记得判个负环

// Author : RioTian// Time : 20/12/21#include 
   
    using namespace std;#define all(s) (s.being(), s.end())#define rep(i, s, n) for (int i = s; i <= n; ++i)typedef long long ll;int n, m, g[200][200];int a[2000], b[2000], c;int main(void) {    memset(g, 0x3f, sizeof(g));    scanf("%d%d", &n, &m);    for (int i = 0; i < m; i++) {        scanf("%d%d%d", &a[i], &b[i], &c);        g[a[i] - 1][b[i] - 1] = 1;        if (c == 1)            g[b[i] - 1][a[i] - 1] = -1;        else            g[b[i] - 1][a[i] - 1] = 1;    }    for (int i = 0; i < n; i++)        g[i][i] = 0;    for (int i = 0; i < n; i++)        for (int j = 0; j < n; j++)            for (int k = 0; k < n; k++)                g[j][k] = min(g[j][k], g[j][i] + g[i][k]);    int pos = -1, ans = -1;    for (int i = 0; i < n; i++) {        if (g[i][i] < 0) {            printf("NO\n");            return 0;        }        int mx = -n, mn = n;        for (int j = 0; j < n; j++) {            mx = max(mx, g[i][j]);            mn = min(mn, g[i][j]);        }        for (int j = 0; j < m; j++)            if (g[i][a[j] - 1] == g[i][b[j] - 1])                mx = -n;        if (ans < mx - mn) {            ans = mx - mn;            pos = i;        }    }    if (ans == -1)        printf("NO\n");    else {        printf("YES\n%d\n", ans);        for (int i = 0; i < n; i++)            printf("%d%c", g[pos][i] + n, i == n - 1 ? '\n' : ' ');    }    return 0;}
   

F、G、F1&F2没做出来了。等待以后重新补题