AtCoder Beginner Contest 174

发表于2020-08-04更新于2023-09-15字数统计1.3k阅读时长13分

比赛链接

C Repsept

Description

求 7，77，777，7777，7，77，777，7777， 中的第几个数是给定的 KK 的倍数 (K≤ 106K \le\ 10^6)，没有则输出 −1-1。

Solution

  • 设 f(n)f(n) 为数列中第 n 个数的值，则有 f(n)=10∗f(n−1)+7f(n) = 10 * f(n - 1) + 7，两边同除以 10n10^n，求通项可得:

    f(n)=7∗(10n−1)/9f(n) = 7 * (10^n - 1) / 9

  • 问题转化为求 f(n)% K=0f(n) \%\ K = 0 所对应的 nn
  • 可以发现，KK 是 2 或 5 的倍数时无解。有解时，一定有 n<Kn < K
  • 故可枚举 nn，使用 mod=Kmod = K 的快速幂判断即可

Code Repsept

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

int k;

int qpow(int a, int b, int modd) {
    int ans = 1, base = a;
    while (b) {
        if (b & 1) ans = ans * base % modd;
        b >>= 1, base = base * base % modd;
    }
    return ans;
}

inline void work() {
    cin >> k;
    for (int i = 1; i <= 2e6; i++) {
        if ((7 * (qpow(10, i, 9 * k) - 1) % (9 * k) + (9 * k)) % (9 * k) == 0) {
            cout << i;
            exit(0);
        }
    }
    cout << -1 << endl;
}

signed main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    work();
    return 0;
}

D Alter Altar

Description

题目链接

Solution

应该使所有的 WW 在 RR 右侧。那么从头开始扫，如果遇到 WW 就将其与最右端的 RR 交换即可(用双指针维护)。

Code

Alter Altar
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>

using namespace std;
const int maxn = 200005;
int n, ans;
char c[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    int i = 1, r = n;
    for (; i <= n; i++) {
        while (c[r] == 'W' && r > i) r--;
        if (c[i] == 'W' && i < r && c[r] == 'R') {
            swap(c[i], c[r]);
            ans++;
        }
    }
    cout << ans;
    return 0;
}

E Logs

Description

有 NN 个木头，现需要将这些木头砍 KK 次(设选取的木头长度为L，则砍了之后得到长度为 tt (0<t<L0 < t < L), L−tL - t 的木头，砍了之后的木头还能继续砍)，求 KK 次操作后这些木头中最大长度的最小值(向上取整)。

Solution

二分木头最大长度的最小值 midmid，并 checkcheck 把所有木头分为长度 l≤ midl \le\ mid 的木头所需要的次数，与 kk 比较即可。
注意木头的最小长度应取 1 而不是 0。

Code

Logs
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
#include <bits/stdc++.h>
#define int long long

using namespace std;

constexpr int MAXN = 3e5 + 5;

array<int, MAXN> a;

int n, k;

inline bool check(int mid) {
    int cnt(0);
    for (int i = 1; i <= n; i++) {
        if (a[i] % mid == 0) cnt += a[i] / mid - 1;
        else cnt += a[i] / mid;
    }
    return cnt <= k; //
}

signed main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = 2e9, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid, r = mid - 1;
        } else l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}

F Range Set Query

Description

给定一个序列，多次询问区间 [li,ri][l_i, r_i] 不同数字的个数。

Solution

  • 记录 aia_i 前一次出现的位置 pre[ai]pre[a_i](若 aia_i 第一次出现则为 0)
  • 对于区间 [l,r][l, r]，如果区间的一个数 per[ai]≤lper[a_i] \le l，则该数在区间内第一次出现，可计入答案
  • 于是以下标为值域，建立可持久化至于线段树。每个版本在 pre[ai]pre[a_i] 位置权值加 1，最后统计 [0,li−1][0, l_i - 1] 的权值总和即可

Code

Range Set Query
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
#include <bits/stdc++.h>

constexpr int MAXN = 5e5 + 5;
constexpr int MAXA = 5e5 + 6;
constexpr int LOG = 30;
using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - 48, ch = getchar();
    return x * f;
}

struct Node {
    Node *lson, *rson;
    int cnt;
} Tree[MAXN * LOG], *root[MAXN];
int tot, n, m, cnt, arr[MAXN], pre[MAXA], last[MAXN];

inline Node *newNode(Node *&root) { return root = &Tree[tot++]; }

inline void build(int L, int R, Node *root) {
    if (L == R) return;
    int mid = (L + R) >> 1;
    build(L, mid, newNode(root->lson)), build(mid + 1, R, newNode(root->rson));
}

inline void modify(Node *pre, Node *cur, int L, int R, int pos) {
    cur->cnt = pre->cnt;
    if (L == R) {
        cur->cnt++;
        return;
    }
    int mid = (L + R) >> 1;
    if (pos <= mid)
        cur->rson = pre->rson,
        modify(pre->lson, newNode(cur->lson), L, mid, pos);
    else
        cur->lson = pre->lson,
        modify(pre->rson, newNode(cur->rson), mid + 1, R, pos);
    cur->cnt = cur->lson->cnt + cur->rson->cnt;
}

inline int query2(Node *pre, Node *cur, int L, int R, int qL, int qR) {
    if (qL == L && R == qR) return cur->cnt - pre->cnt;
    int mid = (L + R) >> 1;
    if (qR <= mid)
        return query2(pre->lson, cur->lson, L, mid, qL, qR);
    else if (qL > mid)
        return query2(pre->rson, cur->rson, mid + 1, R, qL, qR);
    else
        return query2(pre->lson, cur->lson, L, mid, qL, mid) +
               query2(pre->rson, cur->rson, mid + 1, R, mid + 1, qR);
}

int main() {
    n = read(), m = read();
    build(0, n, newNode(root[0]));
    for (int i = 1; i <= n; i++) {
        arr[i] = read(), last[i] = pre[arr[i]], pre[arr[i]] = i;
        modify(root[i - 1], newNode(root[i]), 0, n, last[i]);
    }
    while (m--) {
        int l = read(), r = read();
        printf("%d\n", query2(root[l - 1], root[r], 0, n, 0, l - 1));
    }
    return 0;
}