大半年没训练, 加上早起做数电实验赶场导致状态不好, 被 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;
}
|
