思维大挑战这一块。
题目链接：https://codeforces.com/contest/2241

A - Divide and Conquer#

大致题意：给定 $x$ 和 $y$ ， $x$ 通过执行任意次（包括零次）除以自己任意的约数（因数）的操作可以得到 $y$ 。判断这 $x$ 和 $y$ 是否满足这个条件。
思路：通过题意我们可以知道其实只有当 $y$ 是 $x$ 的因数的时候才满足条件。在这种情况下 $y$ 一定能和 $x$ 的另一个因数相乘得到 $x$ 。我们判断 $y$ 是 $x$ 的因数时就输出 $YES$ ，否则就 $NO$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
void solved() {
12
    int x, y;
13
    cin >> x >> y;
14
    if(x % y == 0) cout << "YES" << endl;
15
    else cout << "NO" << endl;
16
}
17

18
int main() {
19
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
20
    int _ = 1;
21
    cin >> _;
22
    while (_--) {
23
        solved();
24
    }
25
    return 0;
26
}

B - Good times Good times#

大致题意：给定一个好数 $x$ （所有十进制位上的出现的不同数字最多包含两种不同的数字），我们要找出另外一个好数 $y$ ，使得 $x \times y$ 也是好数。
思路：这里我想到的构造方法是根据 $x$ 的十进制位数 $L$ 来构造一个 $y = 10 ^ L + 1$ ，这样的 $y$ 只有 $0$ 和 $1$ ，所以满足是好数的条件。举个例子对于 $73$ 我们生成 $101$ ，相乘结果为 $7373$ ，满足题意。对于 $299$ 我们生成 $1001$ ，相乘结果为 $299299$ ，个位的 $1$ 乘以 $x$ 后就将最高位和个位之间的 $0$ 全填满了，保证不会出现 $0$ ，由此能构造出满足条件的好数 $y$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
void solved() {
12
    string x; cin >> x;
13
    ll y = 1;
14
    for(int i = 0; i < (int)x.size();i++) y *= 10;
15
    cout << y + 1 << endl;
16
}
17

18
int main() {
19
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
20
    int _ = 1;
21
    cin >> _;
22
    while (_--) {
23
        solved();
24
    }
25
    return 0;
26
}

C - RemovevomeR#

大致题意：对于一个只包含 $0$ 和 $1$ 的字符串 $s$ ，可以进行任意次下面的操作：选一个 $s$ 里长度至少为 $2$ 的回文子串，从这个回文子串里删掉一个字符，剩下的字符拼接成新的字符串 $s$ ，求任意次操作完之后的 $s$ 最短是多少。
思路：首先全 $1$ 和全 $0$ 的 $s$ 最终结果为 $1$ 。然后我们通过手动模拟这样的操作可以发现一个规律：如果子串存在一个 $xox$ (比如 $101$ ，或者 $010$ )的结构，那么就可以通过一定的操作使得最终的 $s$ 的长度为 $1$ 。反之除了这两种情况之外都会剩下 $0$ 和 $1$ 两个字符各一个，结果为 $2$ 。所以特判这两个特殊情况为 $1$ ，其他都是 $2$ 即可。
这里的实现我可能写的比较复杂，原理就是 $pos1$ 和 $pos0$ 分别记录 $1$ 和 $0$ 的下标。然后有如果其中一个为空就说明是全 $0$ 或全 $1$ 的情况直接输出 $1$ 。否则就根据第一个元素是 $0$ 或 $1$ 来遍历对应 $0$ 或 $1$ 的下标数组的元素找下标。如果这个数组里所有的元素都是递增的就说明没有出现 $xox$ 的结构，最终就输出 $2$ 。否则就直接输出 $1$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
void solved() {
12
    int n; cin >> n;
13
    vector<int> pos0, pos1;
14
    string s; cin >> s;
15
    for(int i = 0; i < (int)s.size();i++){
16
        if(s[i] == '0') pos0.push_back(i);
17
        else pos1.push_back(i);
18
    }
19
    if(!pos1.size() || !pos0.size()){
20
        cout << 1 << endl;
21
        return;
22
    }
23
    char first = s[0];
24
    vector<int> pos = (first == '0' ? pos0 : pos1);
25
    for(int i = 0;i < (int)pos.size() - 1;i++){
26
        if(pos[i] + 1 == pos[i + 1]) continue;
27
        else{
28
            cout << 1 << endl;
29
            return;
30
        }
31
    }
32
    cout << 2 << endl;
33
}
34

35
int main() {
36
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
37
    int _ = 1;
38
    cin >> _;
39
    while (_--) {
40
        solved();
41
    }
42
    return 0;
43
}

D - An Alternative Way#

大致题意：给定连两个长度都为 $n$ 的数组 $a$ 和 $b$ ，你可以通过对 $a$ 进行任意次一下操作：选择两个索引 $l$ 和 $r$ ，满足 $1 <= l <= r <= n$ ，对 $l$ 到 $r$ 之间的索引 $i$ ，执行 $i - l$ 为计数则 $a_i = a_i + 1$ ，如果 $i - l$ 为偶数则 $a_i = a_i + 1$ 。问最终能否使得 $a$ 变成 $b$ 。
思路：我们注意到这个操作实现了一个交替加减 $(1,-1,1,-1...)$ 的操作。我们用一个 $c[i] = b[i] - a[i]$ 记录每一个 $a[i]$ 变成 $b[i]$ 需要的变化值。比如 $a：1, 4, 5, 2$ 和 $b：1, 5, 4, 3$ 的 $c$ 就是 $0, 1, -1, 1$ 。这个样例是可以通过操作 $[2,4]$ 一步变成 $b$ 的，故输出 $YES$ 。
此外更重要的是，我们注意到这个 $c$ 数组形成的前缀和中的每一项总是大于等于 $0$ 的。 $c$ 的前缀和 $pre$ 数组为 $0, 1, 0, 1$ ，对于一个 $pre[i]$ ，它的含义其实是在以当前 $i$ 为左端点的区间需要操作多少次,所以 $pre[i]$ 的值必须大于等于 $0$ ，反之如果小于 $0$ 就无法通过这样操作最终变成 $b$ 。所以我们直接判断每一个 $c$ 的前缀和是否小于 $0$ ，如果小于 $0$ 就输出 $NO$ ，否则就输出 $YES$ 即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
void solved() {
12
    int n; cin >> n;
13
    vector<ll> a(n + 1), b(n + 1);
14
    for(int i = 1; i <= n;i++) cin >> a[i];
15
    for(int i = 1; i <= n;i++) cin >> b[i];
16

17
    ll pref = 0;
18
    for(int i = 1; i <= n;i++){
19
        pref += b[i] - a[i];
20
        if(pref < 0){
21
            cout << "NO" << endl;
22
            return;
23
        }
24
    }
25
    cout << "YES" << endl;
26
}
27

28
int main() {
29
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
30
    int _ = 1;
31
    cin >> _;
32
    while (_--) {
33
        solved();
34
    }
35
    return 0;
36
}

Mkrari的个人博客

A - Divide and Conquer#

B - Good times Good times#

C - RemovevomeR#

D - An Alternative Way#