比赛链接
众所周知，E 题比 B 题简单。
D、F、G 待填坑。
【A】 LCM Problem
考虑固定 $x$，看 $\operatorname{lcm}(x,y)$ 的取值。设 $\operatorname{lcm}(x,y) = kx$，因为 $x < y$，故 $k \neq 1$，$k_{\min} = 2$。又因 $x_{\min} = l$，故当 $x = l$，$y = 2l$ 时，方案最优。若 $r < 2l$，则输出 -1 -1。
自行打一个 $\mathcal{O}(n^2)$ 暴力也不难得出这个规律。
【B】 Array Walk
由于 $z$ 很小，可以考虑暴力枚举向左走的次数。
$z=0$ 的时候，答案即为前 $k+1$ 个元素的前缀和。
$z \neq 0$ 的时候，很明显有如下三条性质：
证明：举个例子，若几次向左走时，起点不同，如下图：
那我们总是可以将左走的起点移到相同位置，使得答案更优：
- （二）最终的落点一定在 $k+1-2z$ 处。 证明是显然的。
- （三）按照（一）的策略，左走的起点不能超过 $k+2-2z$。 不然一定需要连续向左走多次。
综上，记 $M_{i}=\max_{j=1}^{i} a_j+a_{j+1}$，答案即为 $\max_{j=1}^{k+1-2z} (\sum_{i=1}^{k+1-2z} a_i+M_j)$。
$\mathcal{O}(n)$ 前缀预处理后就可以单次 $\mathcal{O}(1)$ 算答案。
代码：
【C】 Good String
不难发现，一个字符串是好的，当且仅当 $t_2 = t_4 = t_6 = \cdots$ 且 $t_1 = t_3 = t_5 = \cdots$。
于是符合条件的字符串只有两种：（1）由一种字符构成的字符串（2）由两种字符交替构成的字符串，且字符串长度为偶数。
对于第（1）种字符串，直接统计字符个数即可。
对于第（2）种字符串，由于字符集大小仅为 $10$，可以考虑暴力枚举这两个字符并计算答案。具体细节详见代码注释。
单次时间复杂度 $\mathcal{O}(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
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>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
x = 0; T f = (T) 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T>
inline void write(T x) {
if(x < 0) {x = -x; putchar('-');}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int inf = 1e9 + 10, maxN = 2e5 + 10;
int t, n, cnt[10], Cnt[maxN][10];
std::string s;
int main() {
read(t);
while(t--) {
memset(cnt, 0, sizeof(cnt));
memset(Cnt, 0, sizeof(Cnt));
getline(std::cin, s);
int len = s.size(), ans = inf;
_rep(i, 1, len) {
cnt[s[i - 1] - '0']++;
Cnt[i][0] = Cnt[i - 1][0] + (s[i - 1] == '0');
Cnt[i][1] = Cnt[i - 1][1] + (s[i - 1] == '1');
Cnt[i][2] = Cnt[i - 1][2] + (s[i - 1] == '2');
Cnt[i][3] = Cnt[i - 1][3] + (s[i - 1] == '3');
Cnt[i][4] = Cnt[i - 1][4] + (s[i - 1] == '4');
Cnt[i][5] = Cnt[i - 1][5] + (s[i - 1] == '5');
Cnt[i][6] = Cnt[i - 1][6] + (s[i - 1] == '6');
Cnt[i][7] = Cnt[i - 1][7] + (s[i - 1] == '7');
Cnt[i][8] = Cnt[i - 1][8] + (s[i - 1] == '8');
Cnt[i][9] = Cnt[i - 1][9] + (s[i - 1] == '9');
}
_rep(i, 0, 9) ans = std::min(ans, len - cnt[i]);
_rep(i, 0, 9) {
_rep(j, 0, 9) {
if(i == j) continue;
int qwq = 0, flg = 1;
_rep(k, 1, len) {
if(s[k - 1] == '0' + j) {
if(Cnt[k - 1][i] - Cnt[flg - 1][i]) {
qwq = qwq + 2;
flg = k;
}
}
}
ans = std::min(ans, len - qwq);
}
}
writesp(ans, '\n');
}
return 0;
}
|
【D】 Segment Intersection
首先，容易看出，两个闭区间 $[l_1, r_1]$，$[l_2, r_2]$ 的相交长度为 $\min(r_1, r_2) - \max(l_1, l_2)$。
【E】 Calendar Ambiguity
可以将问题抽象为如下形式：
给定 $m, d, w$，求得满足下列条件的 $(x,y)$ 数对个数：
- $1 \leq x \leq \min(m, d)$
- $1 \leq y \leq \min(m, d)$
- $x < y$
- $(x-1) \times d + y \equiv (y-1) \times d + x \pmod w$
化简条件四可得 $(x-y)(d-1) \equiv 0 \pmod w$，$(x-y)(d-1)+wk=0 ; (k \in \mathbb{Z})$；$(d-1)$、$w$ 均为定值，设 $g = \gcd(d-1, w)$，则可得一组解（由于 $x < y$ 所以 $x-y$ 取负值）：
$$\begin{cases} x-y = -\frac{w}{g} \\ k = \frac{d-1}{g}\end{cases}$$
并可得到通解（$k_1 \in \mathbb{N}^+$）：
$$\begin{cases} x-y = k_1 \times (-\frac{w}{g}) \\ k = k_1 \times \frac{d-1}{g}\end{cases}$$
由条件一、二、三得 $x-y$ 的取值范围：$1 - \min(m, d) \leq x-y < 0$，
考虑 $x-y = \Delta$ 时的解数：
$x - y = \Delta \rightarrow x = \Delta + y$
$\rightarrow \begin{cases} 1 \leq y + \Delta \leq \min(m, d) \ 1 \leq y \leq \min(m, d) \end{cases}$
$\rightarrow 1 - \Delta \leq y \leq \min(m, d)$
可以看出，$x-y = \Delta$ 时，相应解数就会减少 $|\Delta|$ 个。而 $\Delta = 0$ 时的解数我们可以轻易得到，$|\Delta|$ 的变化又是 等差 的，公差为 $\frac{w}{g}$，这部分的贡献可以使用等差数列求和解决。
项数 $x = \left\lfloor \frac{1 - \min(m, d)}{\frac{-w}{g}} \right\rfloor$，故答案即为：$x \times \min(m, d) - \frac{x \times (x + 1) \times |\Delta|}{2}$。
代码：
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
| #include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
x = 0; T f = (T) 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T>
inline void write(T x) {
if(x < 0) {x = -x; putchar('-');}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
int main() {
int t, m, d, w;
read(t);
while(t--) {
read(m, d, w);
if(d == 1) {
writesp(0, '\n');
continue;
}
int q = d - 1; int g = std::__gcd(q, w);
int f = -w / g, h = q / g;
int limit = 1 - std::min(m, d);
int k = limit / f;
writesp(1ll * k * std::min(m, d) - (1ll * (k + 1) * (-f) * k) / 2, '\n');
}
return 0;
}
|