AtCoder Regular Contest 060

C - Tak and Cards

给定 \(n\) 个有序数字，求有多少个下标集，对应的数字平均数是 \(A\)

数据范围很小，用背包计数就好了，注意枚举的上下界。 

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 57
#define M 5007
#define B 2500

ll f[N][M];

int main() {
    int n = rd(), A = rd();
    f[0][B] = 1;
    for (int i = 1; i <= n; ++i) {
        int w = rd() - A;
        for (int v = max(-B, -B + w); v <= min(B, B + w); ++v)
            f[i][v + B] = f[i - 1][v + B] + f[i - 1][v - w + B];
    }
    printf("%lld\n", f[n][B] - 1);
    return 0;
}

D - Digit Sum

给定两个数字 \(n\ (n\le 10^{11})\) 和 \(s\) ，求最小的进制 \(b\) ，使得 \(n\) 在 \(b\) 进制下的数位和等于 \(s\) 。

一道典型的根号讨论题目。

  • 当 \(b\le \sqrt{n}\) 时，直接暴力验证。
  • 当 \(b\ge \sqrt{n}\) 时，数字最多是两位数，可以写成 \(n=pb+q,s=p+q\) ，联立得 \(n-s=p(b-1)\)

注意后一种情况判断要求：\(b\ge \sqrt{n},\ 0\le q< b\)

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
#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
  
inline ll calc(ll n, ll b) {  
    ll ans = 0;  
    for (; n; ans += n % b, n /= b);  
    return ans;  
}  
  
int main() {  
    ll n, s;  
    cin >> n >> s;  
    if (n < s) {puts("-1"); return 0;}  
    if (n == s) {printf("%lld\n", n + 1); return 0;}  
    ll lim = sqrt(n);  
    for (ll i = 2; i <= lim; ++i)  
        if (calc(n, i) == s) {printf("%lld\n", i); return 0;}  
    n -= s;  
    ll ans = 1e18;  
    for (ll i = sqrt(n); i >= 1; --i)  
        if (n % i == 0) {  
            if (i >= lim && s - n / i < i + 1 && s >= n / i) ans = min(ans, i + 1);  
            if (n / i >= lim && s - i < n / i + 1 && s >= i) ans = min(ans, n / i + 1);  
        }  
    printf("%lld\n", ans == 1e18 ? -1 : ans);  
    return 0;  
}

E - Tak and Hotels

给定数轴上的 \(n\) 个点，每次查询两个点 \(a,b\) ：

问从 \(a\) 到 \(b\) ，在给定的点之间跳跃，每次距离不超过 \(L\) ，最少多少次。

考虑倍增，设 \(mx_{i,j}\) 表示从 \(i\) 向右跳 \(2^j\) 步，最多能跳到哪里，组合的时候记得判一下最后一步即可。

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
#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
  
inline int rd() {  
    int x = 0;  
    bool f = 0;  
    char c = getchar();  
    for (; !isdigit(c); c = getchar()) f |= (c == '-');  
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);  
    return f ? -x : x;  
}  
  
#define N 100007   
  
int r[N][18], x[N];  
  
int main() {  
    int n = rd();  
    int t = log2(n) + 1;  
    for (int i = 1; i <= n; ++i) x[i] = rd();  
    int l = rd(), q = rd();  
    for (int i = 1, rpos = 1; i <= n; ++i) {  
        while (rpos < n && x[rpos + 1] - x[i] <= l) ++rpos;  
        r[i][0] = rpos;  
    }  
    for (int i = 1; i <= t; ++i)  
        for (int l = 1; l <= n; ++l) r[l][i] = r[r[l][i - 1]][i - 1];  
  
    for (; q; --q) {  
        int a = rd(), b = rd();  
        if (a > b) swap(a, b);  
        int ans = 0;  
        for (int i = t; ~i; --i)  
            if (r[a][i] < b) {  
                ans += (1 << i);  
                a = r[a][i];  
            }  
        printf("%d\n", ans + 1);  
    }  
    return 0;  
}

F - Best Representation

定义无循环节（完整补齐）的字符串是好的。

定义将一个串划分为若干好的字符串，这个划分是好的。

定义一个划分是最优的，当且仅当划分是好的并且划分的子串数最少。

给定串 \(S\ (|S|\le 5\times 10^5)\) 求最优划分所需的子串数和最优划分个数。

  • 如果 \(S\) 自己本身无循环节，两个答案都是 \(1\)
  • 如果 \(S\) 所有字母都相同，第一个答案是 \(n\) ，第二个是 \(1\)
  • 如果 \(S\) 有循环节且所有字母都不同，第一个答案是 \(2\) （在任意循环节中间切开）

对于第三种情况枚举分割点计数，需要快速判断一个前缀/后缀有无循环节。

对正反两个串都做一下 kmp 就可以了，若 \((n-nxt[n])\ |\ n\) 则有循环节。

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
#include <bits/stdc++.h>
using namespace std;

#define N 500007

char s[N];

int nxt[N], nxtr[N];

inline bool pre(int x) {
    return (nxt[x] == 0) || (x % (x - nxt[x]) > 0);
}

inline bool suf(int x) {
    return (nxtr[x] == 0) || (x % (x - nxtr[x]) > 0);
}

int main() {
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    bool fl = 0;
    for (int i = 2, pos; i <= len; ++i) {
        if (s[i] != s[i - 1]) fl = 1;
        pos = nxt[i - 1];
        while (pos && s[pos + 1] != s[i]) pos = nxt[pos];
        if (pos != 0) nxt[i] = pos + 1;
        else nxt[i] = (s[1] == s[i]);
    }
    if (!fl) {printf("%d\n1\n", len); return 0;}
    if (pre(len)) {puts("1\n1"); return 0;}
    puts("2");
    reverse(s + 1, s + 1 + len);
    for (int i = 2, pos; i <= len; ++i) {
        pos = nxtr[i - 1];
        while (pos && s[pos + 1] != s[i]) pos = nxtr[pos];
        if (pos != 0) nxtr[i] = pos + 1;
        else nxtr[i] = (s[1] == s[i]);
    }
    int ans = 0;
    for (int i = 1; i < len; ++i)
        if (pre(i) && suf(len - i)) ++ans;
    printf("%d\n", ans);
    return 0;
}