Codeforces Global Round 6 题解

作者: xht37 分类: 题解 发布时间: 2019-12-18 01:20

点击数:185

Codeforces Global Round 6

Competitive Programmer

$60$ 的倍数要求至少有一个 $0$,至少有两个数字是 $2$ 的倍数,且所有数字加起来是 $3$ 的倍数。

int main() {
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int c0 = 0, c2 = 0, S = 0;
        int l = s.length();
        for (int i = 0; i < l; i++) {
            if (s[i] == '0') c0++;
            if ((s[i] - '0') % 2 == 0) c2++;
            S += s[i] - '0';
        }
        if (c0 && c2 > 1 && S % 3 == 0) cout << "red" << endl;
        else cout << "cyan" << endl;
    }
    return 0;
}

Dice Tower

总和模 $14$ 应该在 $[1,6]$ 之间。注意开 long long,还有 $n>14$。

int main() {
    int T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        if (n > 14 && n % 14 > 0 && n % 14 < 7) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

Diverse Matrix

随便构造一下就好了,要特判 $n=1$ 和 $m=1$ 的情况。

const int N = 503;
int a[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    if (n == 1 && m == 1) return cout << 0 << endl, 0;
    if (n == 1) {
        for (int i = 1; i <= m; i++) cout << i + 1 << ' ';
        return 0;
    }
    if (m == 1) {
        for (int i = 1; i <= n; i++) cout << i + 1 << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cout << i * (j + n) << " \n"[j==m];
    return 0;
}

Decreasing Debts

最终只关心每个人的净借出/负债,构造时用个堆配对一下即可。

const int N = 1e5 + 7;
int n, m;
ll a[N];
pq< pair< ll, int > > p, q;

int main() {
    rd(n), rd(m);
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        rd(x), rd(y), rd(z);
        a[x] += z, a[y] -= z;
    }
    for (int i = 1; i <= n; i++)
        if (a[i] > 0) p.push(mp(a[i], i));
        else q.push(mp(-a[i], i));
    vector< pair < pi, ll > > ans;
    while (p.size()) {
        int x = p.top().se, y = q.top().se;
        ll s = p.top().fi, t = q.top().fi, z;
        p.pop(), q.pop();
        ans.pb(mp(mp(x, y), z = min(s, t)));
        s -= z, t -= z;
        if (s) p.push(mp(s, x));
        if (t) q.push(mp(t, y));
    }
    cout << ans.size() << endl;
    for (auto i : ans) printf("%d %d %lld\n", i.fi.fi, i.fi.se, i.se);
    return 0;
}

Spaceship Solitaire

有结论:一个位置会超出当且仅当落在这个位置上的奖励超过了需要,且超出的多少等于超过的需要。

那么用个 map 模拟即可。

const int N = 2e5 + 7;
int n, q, a[N], c[N], sz;
map< pi, int > p;
ll s;

inline void del(int x, int y) {
    --sz;
    int z = p[mp(x,y)];
    p.erase(mp(x,y));
    if (c[z] > a[z]) --s;
    c[z]--;
}

inline void add(int x, int y, int z) {
    ++sz;
    p[mp(x,y)] = z;
    ++c[z];
    if (c[z] > a[z]) ++s;
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i]), s += a[i];
    rd(q);
    while (q--) {
        int x, y, z;
        rd(x), rd(y), rd(z);
        if (p[mp(x,y)]) del(x, y);
        if (z) add(x, y, z);
        print(s - sz);
    }
    return 0;
}

Almost Same Distance

大力分类讨论即可。

Permutation Concatenation

题目太神仙了,先咕咕咕着。

Red-Blue Graph

题目太神仙了,先咕咕咕着。

发表评论

电子邮件地址不会被公开。 必填项已用*标注