CF#730 div2

Posted on Edited on In Views:
Symbols count in article: 7.5k
题目 A B C D1 D2 E
通过情况 AC AC O AC O O
难度 900 900 1900 1700 2200 2700

A.Exciting Bets

题面

给定数a和b，有两种操作（1）同时+1 （2）同时减1（不能小于1）。输出能达到的最大公约数及对应的最小操作次数。
规定：$gcd\left( x,0 \right) =0$；当最大公约数无穷大时输出 0 0 ；

解法

由 $ gcd\left( a,b \right) =gcd\left( a-b,b \right) \,\,\left( a>b \right) $ 不难看出最大公约数为两数之差的绝对值，当最大公约数时输出0 0。注意要开 long long (白被卡了半个小时qwq)

代码

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
/*
* @题目: A. Exciting Bets
* @算法: 数论 最大公约数
* @Author: Blore
* @Language: c++11
* @Date: 2021-07-07 22:33:01
* @LastEditors: Blore
* @LastEditTime: 2021-07-07 23:05:26
*/
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll read()
{
    ll p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + c - 48, c = getchar();
    return p * f;
}
int main()
{
    int t = read();
    while (t--)
    {
        ll x = read(), y = read();
        ll gcd = abs(x - y);
        if (gcd == 0)
        {
            printf("0 0\n");
            continue;
        }
        ll cnt1 = 0, cnt2 = 0;
        if (x > y)
            swap(x, y);
        if (y % gcd == 0 && x % gcd == 0)
            printf("%lld 0\n", gcd);
        else
        {
            cnt1 = (y / gcd + 1) * gcd - y;
            cnt2 = x - (x / gcd) * gcd;
            printf("%lld %lld\n", gcd, min(cnt1, cnt2));
        }
    }
    return 0;
}

B. Customising the Track

题面

略

解法

尽量平均分配即可

代码

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
/*
 @题目: B. Customising the Track
 * @算法: 数学
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-07 23:09:04
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-07 23:13:00
 */
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll read()
{
    ll p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + c - 48, c = getchar();
    return p * f;
}
int main()
{
    int t = read();
    while (t--)
    {
        ll sum = 0;
        int n = read();
        for (int i = 1; i <= n; i++)
            sum += read();
        ll cnt1 = sum - n * (sum / n);
        ll cnt2 = n - cnt1;
        printf("%lld\n", cnt1 * cnt2);
    }
 
    return 0;
}

C. Need for Pink Slips

题面

略

解法

DFS一下即可，注意浮点数比较大小时要加一个极小数来避免误差

代码

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
/*
 * @题目: C. Need for Pink Slips
 * @算法: DFS
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-13 22:36:43
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-13 23:05:45
 */
#include <cstdio>
#include <algorithm>
using namespace std;
const double eps = 1e-10;
double v, ans;
void dfs(int now, double pos, double c, double m, double p, int tim)
{
    if (now == 1)
    {
        if (c < eps)
            return;
        pos *= c;
        if (c <= v + eps)
        {
            if (m > eps)
                m += c / 2, p += c / 2;
            else
                p += c;
            c = 0;
        }
        else
        {
            c -= v;
            if (m > eps)
                m += v / 2, p += v / 2;
            else
                p += v;
        }
    }
    else if (now == 2)
    {
        if (m < eps)
            return;
        pos *= m;
        if (m <= v + eps)
        {
            if (c > eps)
                c += m / 2, p += m / 2;
            else
                p += m;
            m = 0;
        }
        else
        {
            m -= v;
            if (c > eps)
                c += v / 2, p += v / 2;
            else
                p += v;
        }
    }
    ans += pos * p * tim;
    dfs(1, pos, c, m, p, tim + 1);
    dfs(2, pos, c, m, p, tim + 1);
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        double c, m, p;
        scanf("%lf%lf%lf%lf", &c, &m, &p, &v);
        ans = p;
        dfs(1, 1, c, m, p, 2);
        dfs(2, 1, c, m, p, 2);
        printf("%.12lf\n", ans);
    }
}

D1. RPD and Rap Sheet (Easy Version)

题面

（粗糙翻译）
定义：k进制异或为对应位上 (a+b) mod k, a和b的k进制异或缩写为 $ a\oplus _kb $

给定n,需要猜一个数字x $ \left( 0\leqslant x\leqslant n-1 \right) $，当猜的数字错误时原密码y会变为z，z为 $ x\oplus _kz=y $

注：简单版的k恒为2，显然这与普通的异或（bitwise XOR）相同

解法

一个非常朴素的想法是每次询问完后消除这次询问的影响，这里利用了 $a\oplus a=0$ 的性质
官方第一种解法给的是另一种递推，这里将在Hard Version中具体阐述

代码

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
/*
 * @题目: D1. RPD and Rap Sheet (Easy Version)
 * @算法: 暴力
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-07 23:33:35
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-08 00:14:07
 */
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, k;
        int base = 0;
        std::cin >> n >> k;
        int res;
        for (int i = 0; i < n; i++)
        {
            cout << (i ^ base) << endl;
            std::cin >> res;
            base ^= (i ^ base);
            if (res == 1)
                break;
        }
    }

    return 0;
}

D2. RPD and Rap Sheet (Hard Version)

题面

同上

解法

在简单版中 我们不难得到 $x\oplus z=y\,\,\Longrightarrow \,\,z=x\oplus y$
设 $q_i$ 为第i次询问的值，x为最开始的密码值，其中q：
$\begin{cases}
q_1=\,\,0\\
q_i=\left( i-1 \right) \oplus \left( i-2 \right) , 2\leqslant i\leqslant n\\
\end{cases}$
我们可以断定，在第i次询问后，当前的密码为 $x\oplus \left( i-1 \right) $ (证明略)
那么在第x+1询问时必然可以得到答案

在困难版中，由于 $ a\oplus a=0 $ 不再成立，但是我们仍然可以利用相似的思想
对于 $x\oplus _kz=y$ ，我们可以变化为 $z=\left( y-x \right) mod\,\,k$ ，于是引入新定义 $z=y\ominus _kx$
引理1：$\left( a\ominus _kb \right) \ominus _k\left( a\ominus _kc \right) =c\ominus _kb$
引理2：$\left( b\ominus _ka \right) \ominus _k\left( c\ominus _ka \right) =b\ominus _kc$
设 $q_i$ 为第i次询问的值，x为最开始的密码值，其中q：
$\begin{cases}
q_1=\,\,0\\
q_i=\left( i-2 \right) \oplus _k\left( i-1 \right) , i\text{为奇数}\\
q_i=\left( i-1 \right) \oplus _k\left( i-2 \right) , i\text{为偶数}\\
\end{cases}$
我们可以断定，在第i次询问后，当前的密码为
$\begin{cases}
x\ominus _k\left( i-1 \right) \,\,, i\text{为偶数}\\
\left( i-1 \right) \ominus _kx\,\,, i\text{为奇数}\\
\end{cases}$
那么在第x+1询问时必然可以得到答案

小结：这种方法非常精彩，但是比较难想到，不过该题仍然可以用暴力做

代码

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
/*
 * @题目: D2. RPD and Rap Sheet (Hard Version)
 * @算法: 构造
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-08 00:20:02
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-13 12:29:54
 */
#include <cstdio>
#include <iostream>
using namespace std;
int mod;
int kXOR(int a, int b)
{
    int res = 0;
    int k = 1;
    if (a % 2 == 1)
        swap(a, b);
    while (a || b)
    {
        res += (a % mod - b % mod + mod) % mod * k;
        a /= mod, b /= mod, k *= mod;
    }
    return res;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int base = 0;
        int n, u;
        std::cin >> n >> mod;
        int res;
        for (int i = 0; i < n; i++)
        {
            if (i)
                cout << kXOR(i, i - 1) << endl;
            else
                cout << '0' << endl;
            std::cin >> res;
            if (res == 1)
                break;
        }
    }
    return 0;
}

E. The Final Pursuit

题面

略

解法

第一问：
先随便确定一个点为$0$。与这个点相连出来的点分别对应$2^1,2^2,…,2^{n-1}$。某一层的权值就等于它连接的所有上一层的点的权值的or。
第二问：
当且仅当n为2的倍数时有解（证明略）
构造：考虑一个数的二进制，如果这个数在第$i$位为$1$，就将这个数的颜色异或上$i$

代码

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
 * @题目: E. The Final Pursuit
 * @算法: 构造
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-13 10:46:05
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-13 11:40:01
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 65536
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
vector<int> g[maxn];
bool vis[maxn];
int id[maxn], idinv[maxn];
int col[maxn];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read();
        int m = n * (1 << (n - 1));
        int N = 1 << n;
        rep(i, 0, N - 1) g[i].clear(), vis[i] = id[i] = 0;
        rep(i, 1, m)
        {
            int u = read(), v = read();
            g[u].pb(v), g[v].pb(u);
        }
        int cnt = 1;
        vector<int> cur, nxt;
        vis[0] = 1, id[0] = 0;
        int power = 1;
        for (auto i : g[0])
        {
            vis[i] = 1, id[i] = power;
            cur.pb(i);
            cnt++;
            power <<= 1;
        }
        while (cnt != N)
        {
            nxt.clear();

            for (auto i : cur)
                for (auto j : g[i])
                    if (!vis[j])
                        id[j] |= id[i];
            for (auto i : cur)
                for (auto j : g[i])
                    if (!vis[j])
                        nxt.pb(j), vis[j] = 1, cnt++;
            cur = nxt;
        }
        rep(i, 0, N - 1) idinv[id[i]] = i;
        rep(i, 0, N - 1) printf("%d ", idinv[i]);
        putchar('\n');
        int f = n;
        while (!(f & 1))
            f >>= 1;
        if (f != 1)
        {
            puts("-1");
            continue;
        }
        rep(i, 0, N - 1)
        {
            int s = 0;
            rep(j, 0, n - 1) if (i & (1 << j)) s ^= j;
            col[idinv[i]] = s;
        }
        rep(i, 0, N - 1) printf("%d ", col[i]);
        putchar('\n');
    }
    return 0;
}

官方题解

https://codeforces.com/blog/entry/92582