Codeforces Round #747 (Div. 2) – 解题报告

A – Consecutive Sum Riddle

思博题，没什么好讲的。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        ll n;
        scanf("%lld", &n), printf("%lld %lld\n", -n + 1, n);
    }
    return 0;
}

B – Special Numbers

算乘方的题，没什么好讲的。直接二进制分解后类似快速幂做就行了。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

int fpow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, k;
        scanf("%d%d", &n, &k);
        int ret = 0, bas = 1;
        while (k)
        {
            ret = (0LL + ret + bas * (k & 1)) % mod;
            bas = 1LL * bas * n % mod;
            k >>= 1;
        }
        printf("%d\n", ret);
    }
    return 0;
}

C – Make Them Equal

显然答案只有三种。零的结果显而易见，就是全 c 的情况。我们现在来分辨 1 和 2 的情况。

首先我们可以注意到，操作 n 和 n – 1 就可以把整个序列整理完，所以最差情况就是 2。

如何判断 1？

我们可以用调和级数的时间来标记那些非 c 位置的倍数，然后找一个没被标记的即可。

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 200;

int T, n;
char str[MAX_N], cmdlet[10], rc;
bool vis[MAX_N];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%s%s", &n, cmdlet, str + 1), rc = cmdlet[0];
        bool flag1 = true;
        for (int i = 1; i <= n; i++)
            flag1 &= (str[i] == rc);
        if (flag1)
            puts("0");
        else
        {
            if (str[n] == rc)
                printf("1\n%d\n", n);
            else
            {
                for (int i = 1; i <= n; i++)
                    vis[i] = true;
                for (int i = 1; i <= n; i++)
                    for (int j = i; j <= n; j += i)
                        if (str[j] != rc)
                        {
                            vis[i] = false;
                            break;
                        }
                int pos = -1;
                for (int i = 1; i <= n; i++)
                    if (vis[i])
                        pos = i;
                if (pos != -1)
                    printf("1\n%d\n", pos);
                else
                    printf("2\n%d %d\n", n - 1, n);
            }
        }
    }
    return 0;
}

D – The Number of Imposters

用并查集随便搞下啦。

// D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200;

int T, n, m, ufs[MAX_N], siz[MAX_N];
char cmdlet[20];

int find(int x) { return ufs[x] == x ? x : ufs[x] = find(ufs[x]); }

void merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy)
        ufs[fx] = fy, siz[fy] += siz[fx];
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= (n << 1); i++)
            ufs[i] = i, siz[i] = (i <= n);
        for (int i = 1, u, v; i <= m; i++)
        {
            scanf("%d%d%s", &u, &v, cmdlet + 1);
            if (cmdlet[1] == 'i')
                merge(u, v + n), merge(u + n, v);
            else
                merge(u, v), merge(u + n, v + n);
        }
        bool flag = true;
        for (int i = 1; i <= n; i++)
            flag &= (find(i) != find(i + n));
        if (flag)
        {
            int ans = 0;
            for (int i = 1; i <= n; i++)
                if (find(i) == i)
                    ans += max(siz[find(i)], siz[find(i + n)]);
            for (int i = n + 1; i <= (n << 1); i++)
                if (find(i) == i)
                    ans += max(siz[find(i)], siz[find(i - n)]);
            ans >>= 1;
            printf("%d\n", ans);
        }
        else
            puts("-1");
    }
    return 0;
}

E – Rubik’s Cube Coloring

两个版本放到一起讲。

首先，从 E1 可知，一个深度为 \(x\) 的子树的方案数为：

\[ 4^{2^x – 1} \]

那么对于 E2 而言，我们可以用类似 Trie 树的方式建出一个虚树，然后做一个 DP 就行了。范围很小，可以随便写。

实现起来有些细节，可以看代码。

// E2.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200, mod = 1e9 + 7, opp[6] = {1, 0, 3, 2, 5, 4};

typedef long long ll;

int k, n, nodes[MAX_N][2], ptot, dep[MAX_N], tag[MAX_N], dp[MAX_N][6];
char cmdlet[10];

int mapper(char c)
{
    switch (c)
    {
    case 'w':
        return 0;
    case 'y':
        return 1;
    case 'g':
        return 2;
    case 'b':
        return 3;
    case 'r':
        return 4;
    case 'o':
        return 5;
    }
    return -1;
}

int fpow(int bas, int tim, int modulo)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % modulo;
        bas = 1LL * bas * bas % modulo;
        tim >>= 1;
    }
    return ret;
}

void insert(ll x, int typ)
{
    int p = 1;
    vector<int> seq;
    while (x)
        seq.push_back(x & 1LL), x >>= 1;
    seq.pop_back();
    reverse(seq.begin(), seq.end());
    for (int c : seq)
    {
        if (nodes[p][c] == 0)
            nodes[p][c] = ++ptot, dep[ptot] = dep[p] + 1;
        p = nodes[p][c];
    }
    tag[p] = typ;
}

void dfs(int u)
{
    int udp[2][6], sum[2];
    memset(udp, 0, sizeof(udp)), sum[0] = sum[1] = 0;
    for (int dir = 0; dir < 2; dir++)
        if (nodes[u][dir])
        {
            dfs(nodes[u][dir]);
            for (int d = 0; d < 6; d++)
                udp[dir][d] = dp[nodes[u][dir]][d];
        }
    for (int d = 0; d < 6; d++)
        sum[0] = (0LL + sum[0] + udp[0][d]) % mod, sum[1] = (0LL + sum[1] + udp[1][d]) % mod;
    for (int d = 0; d < 6; d++)
        if (d == tag[u] || tag[u] == -1)
        {

            int ls, rs;
            if (nodes[u][0] == 0)
                ls = fpow(4, (0LL + fpow(2, k - dep[u], mod - 1) + mod - 2) % (mod - 1), mod);
            else
                ls = (0LL + sum[0] + (mod - udp[0][d]) % mod + (mod - udp[0][opp[d]]) % mod) % mod;
            if (nodes[u][1] == 0)
                rs = fpow(4, (0LL + fpow(2, k - dep[u], mod - 1) + mod - 2) % (mod - 1), mod);
            else
                rs = (0LL + sum[1] + (mod - udp[1][d]) % mod + (mod - udp[1][opp[d]]) % mod) % mod;
            dp[u][d] = 1LL * ls * rs % mod;
        }
}

int main()
{
    memset(tag, -1, sizeof(tag)), dep[1] = ptot = 1;
    scanf("%d%d", &k, &n);
    for (ll i = 1, u; i <= n; i++)
        scanf("%lld%s", &u, cmdlet + 1), insert(u, mapper(cmdlet[1]));
    dfs(1);
    int ans = 0;
    for (int d = 0; d < 6; d++)
        ans = (0LL + ans + dp[1][d]) % mod;
    printf("%d\n", ans);
    return 0;
}