Codeforces Round 716 Div2

发表于2021-04-30更新于2023-09-15字数统计1.1k阅读时长11分

比赛链接

A - Perfectly Imperfect Array

Description

题目链接

Solution

只要一个数是非完全平方数答案就是 YES。

Code

Perfectly Imperfect Array
1
2
3
4
5
6
7
8
9
10
11
void solve(int caseNum) {
    cin >> n;
    bool tag = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        int tmp = sqrt(x);
        if (tmp * tmp != x) tag = 1;
    }
    cout << (tag ? "YES" : "NO") << endl;
}

B - AND 0, Sum Big

Description

题目链接

Solution

要使和最大，只需要满足对于任意 i∈[1,k]i∈[1,k]，有且仅有 11 个数第 ii 位为 00。对于每一位，我们选择一个数使它在这一位为0，其余数在这一位为 11，有 nn 种选法，一共 kk 位，故答案为 nkn^k。

Code

AND 0, Sum Big
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
#include <bits/stdc++.h>
 
#define debug(x) cerr << #x << " = " << x << endl
 
using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, k;
 
LL qpow(LL a, LL b, LL MOD) {
    LL ans = 1, base = a;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

void solve(int caseNum) {
    cin >> n >> k;
    cout << qpow(n, k,MOD) << endl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> testCase;
    for (int i = 1; i <= testCase; i++) solve(i);
    return 0;
}

C - Product 1 Modulo N

Description

题目链接

Solution

[1,n−1][1,n-1] 与 nn 互质的数的乘积模 nn 结果要么是 11 要么是 n−1n-1。如果结果是 n−1n-1，则只需要取 [1,n−2][1,n-2] 与 nn 互质的数。

Code

Product 1 Modulo N
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>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, T;

signed main() {
    cin >> n;
    vector<int> v;
    LL pro = 1;
    for (int i = 1; i <= n - 1; i++)
        if (__gcd(i, n) == 1) v.push_back(i), pro = pro * i % n;
    if (pro != 1) v.pop_back();
    cout << v.size() << endl;
    for (auto& val : v) cout << val << " ";
    return 0;
}

D - Cut and Stick

Description

题目链接

Solution

对于区间 [l,r][l,r]，设出现次数最多的数的出现次数为 xx。

  • 若 x≤⌈r−l+12⌉x \le \lceil \frac{r-l+1}{2} \rceil，则只需要分 1 组。

  • 若 x>⌈r−l+12⌉x > \lceil \frac{r-l+1}{2} \rceil，显然其余 (r−l+1)−x(r-l+1)-x 个数的出现次数均严格小于 ⌈r−l+12⌉\lceil \frac{r-l+1}{2} \rceil。我们只需要在出现次数最多的数中选出 (r−l+1)−x+1(r-l+1)-x+1 个分成一组，其余 2x−(r−l+1)−12x-(r-l+1) -1 个单独分组。这样一共分成 2x−(r−l+1)2x-(r-l+1) 组。

求区间出现次数最多的数的出现次数可以用莫队。参考这道题：大爷的字符串题

Code

Cut and Stick
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>

using namespace std;
const int MAXN = 3e5 + 5;
int n, m, sz, tot;
int color[MAXN], belong[MAXN], ans[MAXN], cnt[MAXN], num[MAXN];
vector<int> v;

template <class T>
void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct Query {
    int l, r, id;
    friend bool operator<(const Query& a, const Query& b) {
        if (belong[a.l] == belong[b.l]) {
            if (belong[a.l] & 1) return a.r < b.r;
            return a.r > b.r;
        }
        return a.l < b.l;
    }
} q[MAXN];

void Add(int x) {
    num[cnt[x]]--;
    cnt[x]++;
    num[cnt[x]]++;
    tot = max(tot, cnt[x]);
}

void Sub(int x) {
    num[cnt[x]]--;
    if (cnt[x] == tot && !num[cnt[x]]) tot--;
    cnt[x]--;
    num[cnt[x]]++;
}

int main() {
    read(n), read(m);
    sz = max(1, int(n / sqrt(m)));
    for (int i = 1; i <= n; i++) {
        read(color[i]);
        belong[i] = i / sz;
    }
    for (int i = 1; i <= m; i++) {
        read(q[i].l), read(q[i].r);
        q[i].id = i;
    }
    sort(q + 1, q + m + 1);
    int l = 0, r = 0;
    num[0] = n;
    for (int i = 1; i <= m; i++) {
        while (l > q[i].l) Add(color[--l]);
        while (r < q[i].r) Add(color[++r]);
        while (l < q[i].l) Sub(color[l++]);
        while (r > q[i].r) Sub(color[r--]);
        ans[q[i].id] = max(1, 2 * tot - (q[i].r - q[i].l + 1));
    }
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}