警告
本文最后更新于 2022-06-29，文中内容可能已过时。
大半年没训练, 加上早起做数电实验赶场导致状态不好, 被 pllj 的键盘薄鲨心态爆炸, 成绩惨淡…
找出一个严格大于 $n$ 的最小的整数 $m$, 使得 $m$ 中任意相邻两个数位的差的绝对值不等于 $k$.
$1 \le n \le 10^{10^6}, 0 \le k \le 9$
看到就跳过了, 这种题需要分析的题一直是我的弱项.
很显然应该是 $O(n)$ 扫一遍, 于是一个简单的想法是, 从高位开始, 找到第一个不符合的数位 $p$, 即 $|a_p - a_{p+1}| = k$, 然后这一位加 $1$, 更低位就尽量填最小(如 $0$, 可能会因为限制填不同的, 先放一边, 之后分析). 如果都符合, 那么由于需要 $m > n$, 所以可以认为 $p = 0$. 第 $p$ 位加 $1$ 就可能有一些情况:
- 没有进位
- 有进位
没有进位, 那么就做完了; 有进位的话, 可以等效成 $p+1$ 位需要改变. 需要注意, 原本 $|a_{p+1} - a_{p+2}| \ne k$, 有可能因为 $a_{p+1} + 1$ 而导致非法. 这样就需要继续调整, 根据贪心, 尝试加 $2$.
还需要注意的是, 这一位也可能导致进位, 可能是直接 $9+1$, 也可能是 $8+1$ 非法, 从而 $8+2$. 然后就需要继续往高位走. (这里可以简单证明一下只可能是加 $1$ 或者 $2$)
这样走到最后可能导致最高位进位, 这里需要判断一下边界条件. 最高位进位, 新的最高位就始终是 $1$, 因为没有更高位, 不需要比较.
那么问题就可以分成两步, 首先找到最高的不满足条件的位置 $p$, 然后尝试给 $a_p$ 加 $1$, 若不满足条件则加 $2$(第一次一定是加 $1$, 加 $2$ 是由于进位可能导致的, 这里可以综合在一起). 若导致进位则改变 $p$, 重新判断是否满足条件. 直到找到一个满足条件的 $p$.
将找到的 $a_p$ 按照需求加 $1$ 或者 $2$ (显然不会导致进位), 然后依次考虑更低位. 显然填满足条件的最小的最好. 这里可以简单写成 a[i] = a[i+1] == k, 也就是填 $0$ 如果不满足, 那就填 $1$. 否则填 $0$.
复杂度 $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
|
int T = 1, k, a[MAXN], n;
char str[MAXN];
int delta(int p) {
if (p+1 >= n)
return 1;
for (int i = 1; i <= 2 && i + a[p] <= 9; i++)
if (abs(i + a[p] - a[p+1]) != k)
return i;
return 0;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%s%d", str, &k);
n = strlen(str);
for (int i = 0; str[i]; i++)
a[n-i-1] = str[i] - '0';
a[n] = a[n+1] = a[n+2] = 0;
int p = 0;
for (p = max(0, n-2); p; p--)
if (abs(a[p] - a[p+1]) == k)
break;
for (; p <= n; p++)
if (delta(p) && a[p] + delta(p) <= 9)
break;
a[p] += delta(p);
n += p == n;
for (int i = p - 1; ~i; i--)
a[i] = a[i+1] == k;
for (int i = 0; i < n; i++)
str[n-i-1] = a[i] + '0';
puts(str);
}
return 0;
}
|
$n$ 个物品, 每个物品有两个值 $a_i, b_i$, 且满足不存在某一个物品的两个值都分别大于另一个物品的. 从中选 $x$ 个物品放入集合 $A$, $y$ 个物品放入集合 $B$, 显然 $x + y = n$. 若某物品 $i$ 是放入集合 $A$ 的第 $k$ 个物品, 那么它带来的贡献是 $ka_i$. 同理若某物品 $i$ 是放入集合 $B$ 的第 $k$ 个物品, 那么它带来的贡献是 $kb_i$. 最后, 将贡献累加, 再减去 $(x - y)^2$, 得到最后的值. 问这个最大值是多少. (物品的选择顺序自行确定)
$1 \le n \le 2 \times 10^6, 0 \le a_i, b_i \le 10^6$
我是 sb. 简单的排序不等式. 排一下, 求前后缀, 枚举分界点, 没了. 考场丢 pair 里排导致排错了.
需要注意的是, 答案可能是负数, 所以最后开始枚举分界点前, ans 要设为 $-INF$ 而不是 $0$.
复杂度 $O(nlogn)$
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
|
int T = 1, n;
struct Node {
int a, b;
bool operator < (const Node &N) const {
return a == N.a ? b > N.b : a < N.a;
}
};
vector<Node> v;
LL pre_b[MAXN], suf_a[MAXN];
LL pre_bb[MAXN], suf_aa[MAXN];
int main() {
while (T--) {
scanf("%d", &n);
v.push_back({0, 0});
for (int i = 1; i <= n; i++) {
int a, b;
scanf("%d%d", &a, &b);
v.push_back({a, b});
}
sort(v.begin()+1, v.end());
for (int i = 1; i <= n; i++) {
pre_b[i] = pre_b[i-1] + v[i].b;
pre_bb[i] = pre_bb[i-1] + pre_b[i];
}
for (int i = n; i; i--) {
suf_a[i] = suf_a[i+1] + v[i].a;
suf_aa[i] = suf_aa[i+1] + suf_a[i];
}
LL ans = -INF;
for (int i = 0; i <= n + 1; i++)
ans = max(ans, pre_bb[i] + suf_aa[i+1] - LL(n-i-i)*(n-i-i));
printf("%lld\n", ans);
}
return 0;
}
|
$n \times m$ 的四连通网格, 每个格子有一个值 $a_{ij}$. 其中有 $s$ 个起点和 $e$ 个终点. 选择一个起点到终点的路径, 使得格子的值按位与最大. 求最大值.
$1 \le n, m \le 10^3, 1 \le a_{ij} \le 10^9$
题不难, 考场搞 E 心态爆炸, G 压根没怎么想.
位运算, 拆位考虑. 贪心, 从大到小考虑每一位. 考虑某一位的时候, 简单看成 01 矩阵即可. 这样, 如果有某个起点和某个终点是连通的, 那么答案这一位是 1. 如果起点终点集合被分开, 则答案这一位是 0. 如果确定了某一位是 1, 那么接下来再看连通性的时候, 就不能看全部格子了. 假如考虑最高位时, 为 1 的格子集合为 $S$, 那么接下来就只能在 $S$ 中考虑, 而不是全部的 $nm$ 个格子. 可以发现, 这个可用点集合是越来越小的. 如果这一位为 0, 那么可用点集合不变. (自然语言说不明白, 看代码中的 mask 数组吧).
复杂度 $O(nmloga)$
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
|
const int MAXN = 1e3 + 10;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int T = 1, n, m, s, e, layout[MAXN][MAXN];
vector<PII> ss, ee;
int vis[MAXN][MAXN], mask[MAXN][MAXN];
bool check(int x, int y) {
if (x <= 0 || x > n || y <= 0 || y > m)
return false;
return true;
}
void dfs(int x, int y, int k) {
vis[x][y] = 1;
for (int t = 0; t < 4; t++) {
int nx = x + dx[t], ny = y + dy[t];
if (check(nx, ny) && mask[nx][ny] && (layout[nx][ny] & (1 << k)) && !vis[nx][ny])
dfs(nx, ny, k);
}
}
int main() {
scanf("%d", &T);
while (T--) {
ss.clear(); ee.clear();
scanf("%d%d", &n, &m);
scanf("%d", &s);
for (int i = 0; i < s; i++) {
int x, y;
scanf("%d%d", &x, &y);
ss.emplace_back(x, y);
}
scanf("%d", &e);
for (int i = 0; i < e; i++) {
int x, y;
scanf("%d%d", &x, &y);
ee.emplace_back(x, y);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &layout[i][j]);
mask[i][j] = 1;
}
int ans = 0;
for (int k = 29; ~k; k--) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
vis[i][j] = 0;
for (auto[x, y] : ss)
if (mask[x][y] && (layout[x][y] & (1 << k)))
dfs(x, y, k);
for (auto[x, y] : ee)
if (mask[x][y] && (layout[x][y] & (1 << k)))
ans |= vis[x][y] << k;
if (ans & (1 << k))
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
mask[i][j] = vis[i][j] & mask[i][j];
}
printf("%d\n", ans);
}
return 0;
}
|
在 $a_1 \sim a_n$ 中填入范围在 $[1, c]$ 中的数, 使得 $\forall i \in [2, n], a_{i-1} \mid a_i$. 问一共有多少种填法.
$1 \le n, c \le 10^5$
第一眼动态规划, 但是得二维, 显然复杂度不对. 然后就看题解去了
这种关于约数倍数的题, 思考的方向是质因数分解, 对每个质因数考虑, 就像位运算的题把每一位拉出来考虑一样.
可以发现, 每个质因数对答案产生的贡献是相互独立的. 那么接下来考虑枚举第 $n$ 个数, 假设是 $x = \Pi p_i^{e_i}$. 对每个质因数 $p_i$ 考虑, $p_i^{e_i} \mid a_n$ ($a_n = x$), 然后看 $a_1 \sim a_{n-1}$, 填入 $p_i^{k_i}$, 只要幂次形成不递减的序列, 那么这个质因数就满足条件了. 这样的填法有多少? 隔板法可以轻松算出来.
将每个位置看成球, 假设现在枚举的最后一位有一个因数 $p_i^{e_i}$, 那么需要把前 $n - 1$ 个球, 分成 $e_i + 1$ 份 (指数从 $0$ 到 $e_i$), 可以空. 所以这个因数对答案的贡献是 $\binom{n+e_i-1}{e_i}$. (隔板法, 共 $e_i$ 个板, $n - 1$ 个球, 可以空). 然后所有的 $p_i^{e_i}$ 贡献乘起来, 得到当前枚举的 $a_n$ 的贡献. 枚举 $a_n = x$ 对答案的贡献相加.
注意一下, 组合数在求的时候, 数组开 $2 \times 10^5$ (表达式中有 $n+e_i-1$).
复杂度 $O(n \pi(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
71
72
|
int pls(LL a, LL b) {
a += a < 0 ? P : 0, b += b < 0 ? P : 0;
return a + b >= P ? a + b - P : a + b;
}
int mult(LL a, LL b) {
a += a < 0 ? P : 0, b += b < 0 ? P : 0;
return a * b >= P ? a * b % P : a * b;
}
int power(int a, int b = P-2) {
int res = 1;
while (b) {
if (b&1) res = mult(res, a);
a = mult(a, a);
b >>= 1;
}
return res;
}
int frac[MAXN], inv[MAXN];
void init_comb(int _n) {
frac[0] = inv[0] = 1;
for (int i = 1; i <= _n; i++) frac[i] = mult(frac[i - 1], i);
inv[_n] = power(frac[_n]);
for (int i = _n-1; i; i--) inv[i] = mult(inv[i + 1], i + 1);
}
int comb(int n, int m) {
return mult(mult(frac[n], inv[m]), inv[n - m]);
}
int prime[MAXN], isnotprime[MAXN], p_cnt;
void init_prime(int _n) {
isnotprime[0] = isnotprime[1] = 1; p_cnt = 0;
for (int i = 2; i <= _n; i++) {
if (!isnotprime[i]) prime[p_cnt++] = i;
for (int j = 0; j < p_cnt && i * prime[j] <= _n; j++) {
isnotprime[i * prime[j]] = 1;
if (!(i % prime[j])) break;
}
}
}
int T = 1, n, c;
int ans = 0;
vector<PII> prime_dec(int x) {
vector<PII> v;
for (int i = 0; i < p_cnt && x > 1; i++) {
int p = prime[i], e = 0;
while (x % p == 0) { e++, x /= p; }
if (e) v.emplace_back(p, e);
}
return v;
}
int main() {
scanf("%d%d", &n, &c);
init_prime(c);
init_comb(n+c);
ans = 1;
for (int m = 2; m <= c; m++) {
int res = 1;
vector<PII> v = prime_dec(m);
for (auto pa : v) {
int e = pa.second;
res = mult(res, comb(n+e-1, e));
}
ans = pls(ans, res);
}
printf("%d\n", ans);
return 0;
}
|
