Codeforces Round 930 (Div. 2)

发表于 更新于 分类于 ，

Codeforces Round 930 (Div. 2)

Complete problemset

A. Shuffle Party

题意

给定数组 $a_n=$ { $1,2,3,…,n$ }，对于每个 $i\in\lbrace ^{i=2}_n$，定义 $j$ 为 $a_i$ 最大且 $\ne a_i$ 的因数（若存在 $k=x*y$ 且 $x$、$y$ 均为不为 $0$ 的整数，则称 $x$ 和 $y$ 都是 $k$ 的因数），交换 $a_i$ 、$a_j$，问全部交换完后 $a_1$ 所处的位置。

多测，$1\leq t\leq 10^4$，$1\leq n\leq 10^9$

思路

1被2移动到2位置

2被4移动到4位置

8被4移动到8位置

n的二进制最高位为i则答案是$2^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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    void sol() {
    int n;
    cin >> n;
    int t = n;
    for (; n; n &= (n - 1))
        t = n;
    cout << t << "\n";
}
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

B. Binary Path

题意

给你一个 $2 \times n$ 网格，网格中充满了 0 和 1。假设第 $i$ 行和第 $j$ 列的交叉点上的数字是 $a_{ij}$ 。

在左上角的 $(1, 1)$ 格中有一只蚱蜢，它只能向右或向下跳一格。它想到达右下方的 $(2, n)$ 单元。考虑长度为 $n+1$ 的二进制字符串，它由写在路径单元格中的数字组成，且不改变它们的顺序。

您的目标是

  1. 通过选择任意一条可用路径，找出词典上最小的 $^\dagger$ 字符串；
  2. 找出能得到这个词典最小字符串的路径数。

$^\dagger$ 如果两个字符串 $s$ 和 $t$ 的长度相同，那么当且仅当在 $s$ 和 $t$ 不同的第一个位置上，字符串 $s$ 的元素小于 $t$ 中的相应元素时， $s$ 在词法上小于 $t$ 。

思路

在位置$a_{0,j}$时，我们选择$a_{1,j}$或$a_{0,j+1}$，取决于谁更小。

如果$a_{1,j} < a_{0,j+1}$，移动到$a_{1,j}$则不会再增加路径。

如果$a_{1,j} = a_{0,j+1}$，移动到$a_{0,j+1}$，可选路径cnt++。

如果$a_{1,j} > a_{0,j+1}$，移动到$a_{0,j+1}$，先前统计的路径cnt累计到答案中，cnt=0重新计数。

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    int n;
    cin >> n;
    vector<string> a(2);
    cin >> a[0] >> a[1];
    string s;
    s.push_back(a[0][0]);
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (a[0][i] == a[1][i - 1])
            cnt++, s.push_back(a[0][i]);
        if (a[0][i] < a[1][i - 1])
            cnt = 1, s.push_back(a[0][i]);
        if (a[0][i] > a[1][i - 1]) {
            for (int j = i - 1; j < n; j++) {
                s.push_back(a[1][j]);
            }
            break;
        }
    }
    if (s.size() != n + 1)
        s.push_back(a[1][n - 1]);
    cout << s << "\n";
    cout << cnt << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

C. Bitwise Operation Wizard

题意

**这是一个互动问题。

有一个秘密序列 $p_0, p_1, \ldots, p_{n-1}$ ，它是 $\lbrace 0,1,\ldots,n-1\rbrace $ 的排列组合。

你需要找到任意两个索引 $i$ 和 $j$ 使 $p_i \oplus p_j$ 最大化，其中 $\oplus$ 表示 [bitwise XOR operation] (https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。

为此，您可以提出查询。每个查询的形式如下：选取任意索引 $a$ 、 $b$ 、 $c$ 和 $d$ ( $0 \le a,b,c,d<n$ )。( $0 \le a,b,c,d<n$ ).接下来，评审团计算 $x = (p_a \mid p_b)$ 和 $y = (p_c \mid p_d)$ ，其中 $|$ 表示 bitwise OR 运算。最后，你会得到 $x$ 和 $y$ 的比较结果。换句话说，你会被告知是 $x<y$ 、 $x>y$ 还是 $x = y$ 。

请找出任意两个索引 $i$ 和 $j$ ｝( $0 \le i,j<n$ )，使得 $p_i \oplus p_j$ 在所有这样的索引对中最大，最多使用 $3n$ 个查询。如果有多对索引满足条件，您可以输出其中任何一个。

思路

由于x|x=x，首先遍历所有y，用mxp mxp y y的形式查询，找到最大值n-1的索引mxp

然后再次遍历所有y，找到能与n-1形成或和最大的数的集合C

C中元素或上n-1都是最大的，那么接下来找出C中元素最小的一个，就是异或上n-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
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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

vector<int> a = {0, 3, 1, 2};

int ask(int p1, int p2, int p3, int p4) {
    cout << "? " << p1 << " " << p2 << " " << p3 << " " << p4 << endl;
   // if ((a[p1] | a[p2]) < (a[p3] | a[p4]))
   //     return -1;
   // if ((a[p1] | a[p2]) > (a[p3] | a[p4]))
   //     return 1;
   // return 0;
    string ans;
    cin >> ans;
    if (ans == "<")
        return -1;
    if (ans == ">")
        return 1;
    return 0;
}

void sol() {
    int n;
    cin >> n;
    int mxp = 0;
    for (int i = 1; i < n; i++) {
        int rt = ask(mxp, mxp, i, i);
        if (rt == -1)
            mxp = i;
    }
    int mn = 0;
    vector<int> v;
    v.push_back(0);
    for (int i = 1; i < n; i++) {
        int rt = ask(mxp, mn, mxp, i);
        if (rt == -1) {
            v.clear();
            v.push_back(i);
            mn = i;
        } else if (rt == 0) {
            v.push_back(i);
        }
    }
    int mnp = 0;
    for (int i = 1; i < v.size(); i++) {
        int rt = ask(v[mnp], v[mnp], v[i], v[i]);
        if (rt == 1)
            mnp = i;
    }
    cout << "! " << v[mnp] << " " << mxp << endl;
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

D. Pinball

题意

有一个长度为 $n$ 的一维网格。网格的 $i$-th单元格包含一个字符 $s_i$ ，这个字符要么是”<”，要么是”>“。

当一个弹球被放置在其中一个单元格上时，它会按照以下规则移动：

  • 如果弹球位于 $i$-th单元格上，且 $s_i$ 为”<”，那么弹球会在下一秒向左移动一格。如果 $s_i$ 为”>“，则向右移动一格。
  • 弹球移动后，字符 $s_i$ 会被反转(即如果 $s_i$ 原来是’<’，则会变成’>‘，反之亦然)。
  • 当弹球离开网格时就会停止移动：无论是从左边界还是从右边界。

您需要回答 $n$ 个独立查询。在 $i$ -th 查询中，弹球将被放置在 $i$ -th 单元格中。请注意，我们总是在初始网格上放置一个弹球。

对于每个查询，计算弹球离开网格需要多少秒。可以证明，弹球总是会在有限步数内离开网格。

思路

对于每个位置i，i左侧的'>'以及i右侧的'<'将会导致弹球方向改变。

我们从左向右遍历，对于所有'>'其位置到开头的距离的前缀和，从右向左遍历，对于所有'<'其位置到结尾的后缀和，

对于i位置，左侧如果有cl个'>'，右侧有cr个'<'，我们需要首先移除min(cl,cr)个离i最近的'<' '>'。可以用前缀和得到所需要行走的步数。最后根据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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    ll n;
    string s;
    cin >> n;
    cin >> s;
    s = "#" + s;
    vector<ll> la(1), ra(1);
    for (ll i = n; i >= 1; i--) {
        if (s[i] == '<') {
            la.push_back(la.back() + i);
        }
    }
    for (ll i = 1; i <= n; i++) {
        if (s[i] == '<')
            la.pop_back();
       // cout << i << ":" << s[i] << endl;
       // cout << ra << endl;
       // cout << la << endl;
        ll c = min(la.size(), ra.size());
        ll stp = (ra.back() - ra[ra.size() - c] - (n - i + 1) * (c - 1)) * 2 +
                 (la.back() - la[la.size() - c] - i * (c - 1)) * 2;
        if (s[i] == '>') {
            if (la.size() == c)
                stp += n + 1 - i;
            else
                stp += (la[la.size() - c] - la[la.size() - c - 1]) * 2 - i;
        } else {
            if (ra.size() == c)
                stp += i;
            else
                stp += (ra[ra.size() - c] - ra[ra.size() - c - 1]) * 2 -
                       (n + 1 - i);
        }
        cout << stp << " ";
        if (s[i] == '>')
            ra.push_back(ra.back() + n - i + 1);
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

E. Pokémon Arena

题意

思路

代码

1
2


F. Bitwise Paradox

题意

思路

代码

1
2