Codeforces Global Round 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)

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

考虑(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
", a[i]);
}

1450D. Rating Compression

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

const int N = 3e5 + 10;
char s[N];
vector<int> 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)
        ;
    // 设置''，并且重置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 <bits/stdc++.h>
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
");
            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
");
    else {
        printf("YES
%d
", ans);
        for (int i = 0; i < n; i++)
            printf("%d%c", g[pos][i] + n, i == n - 1 ? '
' : ' ');
    }
    return 0;
}

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