Codeforces Round #597 (Div. 2)题解。

A. Good ol’ Numbers Coloring

        根据这个染色规则，可以得知只要$gcd(a,b)=1$，那么就是有限个黑色块。
        这是因为凡是满足$xa+yb$的数均是白色，当$gcd(a,b)=1$时，方程$kxa+yb=c$在$c>ab-a-b$时总是有非负解的，这意味着所有大于$ab-a-b$的数都是白色，因此只会有有限个黑色。
        然而，当$gcd(a,b)=d\not =1$时，对于$d$非因子的数$c$都是无解的（更不用说非负解），那么黑色块就是无限多。
        关于这个结论的证明见这篇文章的注解部分（赛瓦维斯特定理）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    // DEBUG;
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (gcd(a, b) == 1)
            printf("Finite\n");
        else
            printf("Infinite\n");
    }
    return 0;
}

B. Restricted RPS

        这个的话，直接贪心就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define S(x) (x % 2 ? x / 2 + 1 : x / 2)
using namespace std;
int n, a, b, c, sc[101], ans[101], num[3];
char op[105];
const char *P = "RPS";
inline int to(char e)
{
    if (e == 'R')
        return 0;
    else if (e == 'P')
        return 1;
    return 2;
}
int main()
{
    // DEBUG;
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        scanf("%d%d%d", num, num + 1, num + 2);
        scanf("%s", op);
        memset(ans, -1, sizeof(ans));
        int maxn = 0;
        for (int i = 0; op[i]; i++)
        {
            if (num[(to(op[i]) + 1) % 3])
            {
                --num[(to(op[i]) + 1) % 3];
                ++maxn;
                ans[i] = (to(op[i]) + 1) % 3;
            }
        }
        for (int i = 0; op[i]; i++)
        {
            if (ans[i] == -1)
            {
                if (num[0])
                    ans[i] = 0, --num[0];
                else if (num[1])
                    ans[i] = 1, --num[1];
                else
                    ans[i] = 2, --num[2];
            }
        }
        if (maxn >= S(n))
        {
            printf("YES\n");
            for (int i = 0; i < n; i++)
                printf("%c", P[ans[i]]);
            printf("\n");
        }
        else
        {
            printf("NO\n");
        }
    }
    return 0;
}

C. Constanze’s Machine

        简单的DP。
        只需要用一个类似斐波那契数列的递推方程就可以轻松解决此题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
char op[100005];
int len, dp[100005];
long long ans = 1;
int main()
{
    scanf("%s", op);
    len = strlen(op);
    for (int i = 0; i < len; i++)
    {
        if (op[i] == 'w' || op[i] == 'm')
        {
            printf("0\n");
            return 0;
        }
    }
    dp[0] = 1, dp[1] = 2;
    for (int i = 2; i <= 100000; i++)
        dp[i] = (dp[i - 2] + dp[i - 1]) % MOD;
    for (int i = 0; i < len;)
    {
        if (op[i] != 'n' && op[i] != 'u')
            ++i;
        else
        {
            int pos = i;
            while (i + 1 < len && op[i + 1] == op[i])
                ++i;
            int s = i - pos + 1;
            ans = ans * dp[s - 1] % MOD;
            ++i;
        }
    }
    printf("%d", ans);
    return 0;
}

D. Shichikuji and Power Grid

        这个题的话，思维确实很巧妙。
        首先建立一张完全图，边权按照题目定义给出。
        对于供电这一要求，我们引入一个点，与这个点连接的点都会有电。将这个点与所有其他点连起来，边权为供电所需代价。
        在这个图上跑kruskal求最小生成树即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
struct Edge
{
    int from, to;
    long long v;
    Edge(int a, int b, long long c) : from(a), to(b), v(c) {}
    bool operator<(Edge e)
    {
        return v < e.v;
    }
};
vector<Edge> vec, vv;
int x[2005], y[2005], fa[2005], k[2005], c[2005], n;
long long ans;
inline int dis(int a, int b)
{
    return abs(x[a] - x[b]) + abs(y[a] - y[b]);
}
int ff(int x)
{
    return fa[x] == x ? x : fa[x] = ff(fa[x]);
}
int main()
{
    // DEBUG;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", x + i, y + i);
    for (int i = 1; i <= n; i++)
        scanf("%d", c + i);
    for (int i = 1; i <= n; i++)
        scanf("%d", k + i);
    for (int i = 1; i <= n; i++)
    {
        vec.push_back(Edge(i, n + 1, c[i]));
        for (int j = i + 1; j <= n; j++)
        {
            vec.push_back(Edge(i, j, 1ll * (k[i] + k[j]) * dis(i, j)));
        }
    }
    for (int i = 1; i <= n + 1; i++)
        fa[i] = i;
    sort(vec.begin(), vec.end());
    for (auto s : vec)
    {
        if (ff(s.from) != ff(s.to))
        {
            fa[ff(s.from)] = ff(s.to);
            vv.push_back(s);
            ans += s.v;
        }
    }
    printf("%lld\n", ans);
    int num = 0;
    for (auto s : vv)
    {
        if (s.to == n + 1)
        {
            ++num;
        }
    }
    printf("%d\n", num);
    for (auto s : vv)
    {
        if (s.to == n + 1)
        {
            printf("%d ", s.from);
        }
    }
    printf("\n%d\n", n - num);
    for (auto s : vv)
    {
        if (s.to != n + 1)
        {
            printf("%d %d\n", s.from, s.to);
        }
    }
    return 0;
}

E. Hyakugoku and Ladders

        这题就是个二维DP了，确实没什么好说的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
double dp[15][15];
int op[15][15];
inline void getXY(int &x, int &y, int fx, int fy, int step)
{
    if (fx % 2)
    {
        if (fy - 1 >= step)
        {
            x = fx;
            y = fy - step;
        }
        else
        {
            x = fx - 1;
            y = step - fy + 1;
        }
    }
    else
    {
        if (10 - fy >= step)
        {
            x = fx;
            y = fy + step;
        }
        else
        {
            x = fx - 1;
            y = 21 - fy - step;
        }
    }
}
double DP(int x, int y)
{
    if (x == 1 && y == 1)
        return 0;
    if (dp[x][y] >= 0)
        return dp[x][y];
    dp[x][y] = 0;
    int tox, toy;
    if (x == 1 && y < 7)
    {
        for (int i = 1; i <= y - 1; i++)
        {
            getXY(tox, toy, x, y, i);
            if (op[tox][toy])
                dp[x][y] += min(DP(tox, toy), DP(tox - op[tox][toy], toy)) + 1;
            else
                dp[x][y] += DP(tox, toy) + 1;
        }
        dp[x][y] = (dp[x][y] + 7 - y) / (y - 1);
    }
    else
    {
        for (int i = 1; i <= 6; i++)
        {
            getXY(tox, toy, x, y, i);
            if (op[tox][toy])
                dp[x][y] += min(DP(tox, toy), DP(tox - op[tox][toy], toy)) + 1;
            else
                dp[x][y] += DP(tox, toy) + 1;
        }
        dp[x][y] /= 6;
    }
    return dp[x][y];
}
int main()
{
    for (int i = 1; i <= 10; i++)
    {
        for (int j = 1; j <= 10; j++)
        {
            scanf("%d", &op[i][j]);
            dp[i][j] = -1;
        }
    }
    printf("%.10f", DP(10, 1));
    // PAUSE;
    return 0;
}

F. Daniel and Spring Cleaning

        易知$a + b = a \oplus b$等价于$a$和$b$的按位与为0，这样跑一遍数位$DP$即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
long long dp[35][2][2];
int n1, n2;
inline int bit(int x, int pos)
{
    return (x & (1 << pos)) >> pos;
}
long long DP(int at, int o1, int o2)  // 1可以超过,0不可以超过
{
    if (at == -1)
        return 1;
    if (~dp[at][o1][o2])
        return dp[at][o1][o2];
    dp[at][o1][o2] = 0;
    int m1 = 0, m2 = 0;
    if (o1 || bit(n1, at))
        m1 = 1;
    if (o2 || bit(n2, at))
        m2 = 1;
    for (int i = 0; i <= m1; i++) {
        for (int j = 0; j <= m2; j++) {
            if (i && j)
                break;
            int a1 = 0, a2 = 0;
            if (o1 || i < m1)
                a1 = 1;
            if (o2 || j < m2)
                a2 = 1;
            dp[at][o1][o2] += DP(at - 1, a1, a2);
        }
    }
    return dp[at][o1][o2];
}
 
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int l, r;
        scanf("%d%d", &l, &r);
        long long ans = 0;
        memset(dp, -1, sizeof(dp));
        n1 = r, n2 = r;
        ans = DP(31, 0, 0);
        if (l == 0) {
            printf("%lld\n", ans);
            continue;
        }
        n1 = l - 1, n2 = r;
        memset(dp, -1, sizeof(dp));
        ans -= 2ll * DP(31, 0, 0);
        n1 = l - 1, n2 = l - 1;
        memset(dp, -1, sizeof(dp));
        ans += DP(31, 0, 0);
        printf("%lld\n", ans);
    }
    return 0;
}