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;
}