A. Notelock#

给定一个长度为 $n$ 的二进制字符串 $s$ 和一个正整数 $k$ ，进行以下操作：

首先选择一些位置进行保护
然后对于 $s_i$ $s_{i}$ ，如果满足以下条件，可以将其修改为 $0$ $0$ 。
- $s_i=1$ ，
- $s_i$ 未受保护。
- 当前位置的前 $k-1$ 个元素不包含 $1$ 。

要求找到最少的保护位置数使得 $s$ 不被修改。

题目解析#

贪心即可。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define MULTI_CASES
4
#define ll long long
5
#define int ll
6
#define endl '\n'
7
#define vi vector<int>
8
#define PII pair<int, int>
9
const int MaxN = 2e5 + 100;
10
const int INF = 1e9;
11
const int mod = 1e9 + 7;
12
int T = 1, N, M;
13
int a[MaxN];
14
inline void Solve()
15
{
16
    cin >> N >> M;
17
    string s;
18
    cin >> s;
19
    int pos = -1;
20
    int sum = 0;
21
    for (int i = 0; i < N; i++)
22
    {
23
        if (s[i] == '1')
24
        {
25
            if (i > pos)
26
            {
27

28
                sum++;
29
            }
30
            pos = i + M - 1;
31
        }
32
    }
33
    cout << sum << endl;
34
}
35
signed main()
36
{
37
#ifdef NOI_IO
38
    freopen(".in", "r", stdin);
39
    freopen(".out", "w", stdout);
40
#endif
41
    ios::sync_with_stdio(0);
42
    cin.tie(nullptr), cout.tie(nullptr);
43
#ifdef MULTI_CASES
44
    cin >> T;
45
    while (T--)
46
#endif
47
        Solve();
48
    return 0;
49
}

B. Make it Zigzag#

给定一个长度为 $n$ 的数组 $a$ ，可以执行两种操作：

操作 $1$ ：选择一个位置 $i$ ，使得 $a_i:=\max(a1,...,a_i)$ 。
操作 $2$ ：选择一个位置 $i$ ，使得 $a_i:=a_i-1$ 。要求将此数组转化为符合 $a_1<a_2>a_3<a_4>a_5...$ 的格式。同时要求最小化操作 $2$ 的次数。

题目解析#

首先，由于操作 $1$ 不会对答案产生贡献，且操作 $1$ 对于偶数位是有利的。

因此我们可以先对所有的偶数位执行操作 $1$ ，这样可以保证对于所有偶数位的 $a_i$ 一定大于等于前一位 $a_{i-1}$ 。

接下来考虑操作 $2$ ，对于每个奇数位上的 $a_i$ ，一定满足 $a_i\leq a_{i+1}$ 。那么只需要考虑特殊的 $a_i=a_{i+1}$ 执行一次操作 $2$ 即可。

而对于当前位的前一位而言，由于不存在任何能够使 $a_{i-1}$ 的值增加的方法，所以其一定会产生 $a_i-a_{i-1}+1$ 的贡献。

综合而言，对于奇数位的 $a_i$ ，产生的贡献是 $\max(0,a_i-\min(a_{i-1},a_{i+1})+1)$ 。

Code#

赛时代码，思路可能差异。

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define MULTI_CASES
4
#define ll long long
5
#define int ll
6
#define endl '\n'
7
#define vi vector<int>
8
#define PII pair<int, int>
9
const int MaxN = 2e5 + 100;
10
const int INF = 1e9;
11
const int mod = 1e9 + 7;
12
int T = 1, N, M;
13
int a[MaxN];
14
inline void Solve()
15
{
16
    cin >> N;
17
    for (int i = 1; i <= N; i++)
18
    {
19
        cin >> a[i];
20
    }
21
    int maxn = 0;
22
    int ans = 0;
23
    for (int i = 1; i <= N; i++)
24
    {
25
        // cerr << maxn << " ";
26
        maxn = max(maxn, a[i]);
27
        if (i % 2 == 0)
28
        {
29
            a[i] = maxn;
30
            if (!(a[i] > a[i - 1]))
31
            {
32
                // cerr << i << " ";
33
                ans++;
34
            }
35
        }
36
        else
37
        {
38
            if (a[i] >= a[i - 1] && i != 1)
39
            {
40
                // cerr<<i<<" "<<a[i]-a[i-1]+1<<"  ";
41
                ans += a[i] - a[i - 1] + 1;
42
                a[i] = a[i - 1] - 1;
43
            }
44
        }
45
    }
46
    // cerr << endl;
47
    cout << ans << endl;
48
}
49
signed main()
50
{
51
#ifdef NOI_IO
52
    freopen(".in", "r", stdin);
53
    freopen(".out", "w", stdout);
54
#endif
55
    ios::sync_with_stdio(0);
56
    cin.tie(nullptr), cout.tie(nullptr);
57
#ifdef MULTI_CASES
58
    cin >> T;
59
    while (T--)
60
#endif
61
        Solve();
62
    return 0;
63
}

C1+C2. No Cost Too Great#

给定长度为 $n$ 的两个数组 $a,b$ 。可以执行以下操作任意次：

选择一个 $a_i:=a_i+1$ ，操作代价为 $b_i$ 。

要求在最小的代价下实现存在一组 $(i,j)$ 满足 $\gcd(a_i,a_j)>1$ 。

C1要求 $b_i=1$ ，C2要求 $1\le b_i\le 10^9$

题目分析#

首先考虑在C1的条件限制下的做法。

由于 $b_i=1$ ，所以我们可以忽略代价，只需要考虑最小的操作次数。

不难发现，只要存在两个数 $a_i,a_j$ 都是偶数，直接就可以满足条件。那么显然，最坏的情况下也可以通过至多 $2$ 次操作实现满足要求。

那么我们只需要考虑答案为 $0,1$ 的两种情况即可。

首先考虑答案为 $0$ 的情况，我们只需要确定是否有两个数的质因数相同即可。

同理，对于答案为 $1$ 的情况，我们只需要确定是否存在 $a_i,a_j+1$ 的质因数相同即可。

那么就很简单了，我们只需要通过埃氏筛预处理出所有数的质因数并使用std::map<int,int> 统计答案即可。

考虑在C2的条件限制下的做法

类比C1的做法，可以得出几个性质。

首先，我们总能以不超过 $b_i+b_j$ 的代价，使得两个元素 $a_i,a_j$ 均变为 $2$ 的倍数。所以，根据这一性质，可以发现对于多个元素执行多次操作一定不会比修改两数变为 $2$ 的倍数更优。

那么，本题就只有两种情况需要考虑了。

第一种情况，对于某一对 $(i,j)$ ，分别对 $a_i,a_j$ 执行 $0$ 或 $1$ 次操作。这一部分很简单，类比C1的做法即可。对于每次符合条件的情况维护一个最小值即可。

第二种情况，对于某一个位置 $i$ ，只对其执行多次操作。这一部分比较难处理，按照暴力的想法来看，我们需要对于每个 $a_i$ 遍历执行一次。但实际上只需要处理 $b_{min}$ 所对应的数即可。

使用反证法可以证明，对于任意不为 $b_{min}$ 的 $b_i$ ，对其执行 $k$ 次操作。那么其产生的贡献就是 $k\cdot b_i$ 。但从刚才提到的性质可知，会有另外一种方案 $b_{min}+b_i$ ，且 $b_{min}+b_i<k\cdot b_i$ 。所以这些方案是没有必要的。

那么怎么快速处理对 $b_{min}$ 多次操作的情况呢？我们可以转化思路，遍历其他元素的质因数，并求解使得 $b_{min}$ 对应的 $a_i$ 可被整除的最小次数。

Code#

1
//C2
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define MULTI_CASES
5
#define ll long long
6
#define int ll
7
#define endl '\n'
8
#define vi vector<int>
9
#define PII pair<int, int>
10
const int MaxN = 5e5 + 100;
11
const int INF = 1e9;
12
const int mod = 1e9 + 7;
13
int T = 1, N, M;
14
// int a[MaxN], b[MaxN];
15
int pf[MaxN];
16
void init()
17
{
18
    for (int i = 2; i <= MaxN - 2; i++)
19
    {
20
        pf[i] = i;
21
    }
22
    for (int i = 2; i * i <= MaxN - 2; i++)
23
    {
24
        if (pf[i] == i)
25
        {
26
            for (int j = i * i; j <= MaxN - 2; j += i)
27
            {
28
                if (pf[j] == j)
29
                {
30
                    pf[j] = i;
31
                }
32
            }
33
        }
34
    }
35
}
36
// int c[MaxN];
37
struct node
38
{
39
    int a, b;
40
} a[MaxN];
41
bool cmp(node a, node b)
42
{
43
    return a.b < b.b;
44
}
45
inline void Solve()
46
{
47
    cin >> N;
48
    int maxn = 0;
49
    for (int i = 1; i <= N; i++)
50
    {
51
        cin >> a[i].a;
52
        maxn = max(a[i].a, maxn);
53
    }
54
    for (int i = 1; i <= N; i++)
55
    {
56
        cin >> a[i].b;
57
    }
58
    sort(a + 1, a + N + 1, cmp);
59
    map<int, int> mp, mp2;
60
    for (int i = 1; i <= N; i++)
61
    {
62
        int x = a[i].a;
63
        while (x != 1)
64
        {
65
            int t = pf[x];
66
            if (mp[t])
67
            {
68
                cout << 0 << endl;
69
                return;
70
            }
71
            mp[t]++;
72
            if (i != 1)
73
            {
74
                mp2[t]++;
75
            }
76
            while (x % t == 0)
77
            {
78
                x /= t;
79
            }
80
        }
81
    }
82
    int cnt = -1;
83
    int ans = a[1].b + a[2].b;
84
    for (auto y : mp2)
85
    {
86
        int r = a[1].a % y.first;
87
        if (r == 0)
88
            continue;
89
        int cnt = y.first - r;
90
        ans = min(ans, cnt * a[1].b);
91
    }
92
    for (int i = 1; i <= N; i++)
93
    {
94
        int x = a[i].a + 1;
95
        while (x != 1)
96
        {
97
            int t = pf[x];
98
            if (mp[t])
99
            {
100
                ans = min(ans, a[i].b);
101
                // cout << 1 << endl;
102
                // return;
103
            }
104
            while (x % t == 0)
105
            {
106
                x /= t;
107
            }
108
        }
109
    }
110

111
    cout << ans << endl;
112
}
113
signed main()
114
{
115
    init();
116
#ifdef NOI_IO
117
    freopen(".in", "r", stdin);
118
    freopen(".out", "w", stdout);
119
#endif
120
    ios::sync_with_stdio(0);
121
    cin.tie(nullptr), cout.tie(nullptr);
122
#ifdef MULTI_CASES
123
    cin >> T;
124
    while (T--)
125
#endif
126
        Solve();
127
    return 0;
128
}

Codeforces Round 1060 (Div. 2）题解

A. Notelock#

题目解析#

Code#

B. Make it Zigzag#

题目解析#

Code#

C1+C2. No Cost Too Great#

题目分析#

Code#