大豆和包子等等一车人出的场，总之题目是有点阴间的，特别是D2B。
还是上了点分，这没的说。
B
题目大意：有 $n$ 个座位，学生不能相邻坐，现在给定一个字符串 $s$ ，$s[i]=1$ 表示已经被占用了，问这一排不可能再有其他座位时，最少的学生总数。
数据范围： $1 \leq n \leq 2 \cdot 10^5$
思路：首先考虑一条空白的，那么配置形式肯定是 $01001001 \ldots$ 这样的，现在只需要处理边界就可以了，一种简单的方式是在两侧加上 $01$ ，这样可以避免讨论。
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
|
void solve() {
int n;
cin >> n;
string s;
cin >> s;
int las = -1;
int tem = 0;
int ans = 0;
for (int i = 0; i <= n - 1; i++) {
if (s[i] == '1') {
if (i == 0) {
las = i;
ans++;
continue;
}
if (s[i - 1] == '0') {
if (las == -1) {
if (tem == 1)
ans += 0;
else if (tem <= 3)
ans++;
else if ((tem - 1) % 3 == 0)
ans += (tem - 1) / 3;
else
ans += (tem - 1) / 3 + 1;
} else {
if (tem <= 2)
ans += 0;
else if (tem <= 4)
ans++;
else if ((tem - 2) % 3 == 0)
ans += (tem - 2) / 3;
else
ans += (tem - 2) / 3 + 1;
}
}
las = i;
tem = 0;
ans++;
} else
tem++;
}
if (las == -1) {
if (tem <= 2)
ans++;
else if (tem % 3 == 0)
ans += tem / 3;
else
ans += tem / 3 + 1;
} else {
if (tem <= 1)
ans += 0;
else if (tem <= 3)
ans++;
else if ((tem - 1) % 3 == 0)
ans += (tem - 1) / 3;
else
ans += (tem - 1) / 3 + 1;
}
cout << ans << endl;
return;
}
|
C
题目大意：给定一个数组 $a$ ，对于整数 $k$ ，当且仅当执行以下任意次数的操作，可以将 $a$ 排序后，才称它为小猪数组，操作为交换 $a_i,a_j,|a_i-a_j| \geq k$ ，请确定最大的小猪整数，若不存在则输出-1。
数据范围： $1 \leq n \leq 2 \cdot 10^5,1 \leq a_i \leq 10^9$
思路：考虑冒泡排序中，所有没有被正确排序的整数，都构成一个置换环，这个环内要求都能相互交换。
同时，在这个环之外，还能引入其他的整数进来形成新环，因此考虑引进最大的整数和最小的整数作为媒介（或者它们本来就在里面），进行交换，而最大的整数和最小的整数保持不动，于是得到答案。
本题更显然的做法是手玩。
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
|
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i <= n - 1; i++) cin >> a[i];
auto b = a;
ranges::sort(b);
bool flag = true;
map<int, set<int>> ma;
for (int i = 0; i < n - 1; i++) {
if (a[i] <= a[i + 1]) continue;
flag = false;
break;
}
if (flag) {
cout << -1 << endl;
return;
}
int maxx = *max_element(a.begin(), a.end());
int mixx = *min_element(a.begin(), a.end());
int ans = INT_MAX;
for (int i = n - 1; i >= 0; i--) {
if (a[i] != b[i]) {
int tem2 = max(maxx - a[i], a[i] - mixx);
ans = min(ans, tem2);
}
}
cout << ans << endl;
return;
}
|
D
题目大意：给定整数 $x,y$ 要求求出 $p,q$ ，其中 $p&q=0,$ 且 $|x-p|+|y-q|$ 最小。
数据范围： $0 \leq x,y < 2^{30}$
思路：这道题的正解其实是贪心，也就是一个数跟原来的相等。
赛时的做法是，进行数位DP，既然 $p&q=0$ ，那么它们每个位的组成必然只有 $(0,0),(1,0),(0,1)$ 两种，同时可以观察到 $p$ 跟 $x$ ，$q$ 跟 $y$ 的关系只由高位决定，因此可以算出它们的差，并用记忆化搜索取最优，状态设计就设计为当前数大于/小于/等于 $x,y$ 。
至于还原路径，可以通过每次记录的最优状态，重新跑一遍DP，就这样。
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
void solve() {
int x, y;
cin >> x >> y;
if ((x & y) == 0) {
cout << x << ' ' << y << endl;
return;
}
if (x == 1) {
cout << 0 << ' ' << y << endl;
return;
}
if (y == 1) {
cout << x << ' ' << 0 << endl;
return;
}
vector<array<array<int, 3>, 3>> vis(31); // 0一样大，1比x大，2比x小
vector<array<array<int, 3>, 3>> ma(31);
vector<pair<int, int>> tem = {{0, 0}, {1, 0}, {0, 1}};
for (int i = 0; i <= 30; i++) {
for (int j = 0; j <= 2; j++) {
for (int v = 0; v <= 2; v++) {
vis[i][j][v] = false;
ma[i][j][v] = INT_MAX;
}
}
}
vector<array<array<pair<int, int>, 3>, 3>> pa(31);
auto dfs = [&](this auto&& dfs, int t, int tx, int ty) -> int {
if (t < 0) return 0;
if (vis[t][tx][ty]) return ma[t][tx][ty];
ll res = LLONG_MAX;
int mask = (1 << t);
for (auto& [a, b] : tem) {
int ttx = tx, tty = ty;
int xt = (x >> t) & 1, yt = (y >> t) & 1;
ll temp = 0;
if (tx == 0) {
if (xt < a) {
temp += 1LL * mask;
ttx = 2;
} else if (xt > a) {
temp += 1LL * mask;
ttx = 1;
} else
ttx = 0;
} else if (tx == 1)
temp += 1LL * (xt - a) * mask;
else if (tx == 2)
temp += 1LL * (a - xt) * mask;
if (ty == 0) {
if (yt < b) {
temp += 1LL * mask;
tty = 2;
} else if (yt > b) {
temp += 1LL * mask;
tty = 1;
} else
tty = 0;
} else if (ty == 1)
temp += 1LL * (yt - b) * mask;
else if (ty == 2)
temp += 1LL * (b - yt) * mask;
temp += dfs(t - 1, ttx, tty);
if (temp < res) {
res = temp;
pa[t][tx][ty] = {a, b};
}
}
vis[t][tx][ty] = true;
ma[t][tx][ty] = res;
return res;
};
dfs(30, 0, 0);
int fx = 0, fy = 0;
int tx = 0, ty = 0;
for (int i = 30; i >= 0; i--) {
auto& [a, b] = pa[i][tx][ty];
if (a) fx += (1 << i);
if (b) fy += (1 << i);
int xt = (x >> i) & 1, yt = (y >> i) & 1;
if (tx == 0) {
if (a > xt)
tx = 2;
else if (a < xt)
tx = 1;
}
if (ty == 0) {
if (b > yt)
ty = 2;
else if (b < yt)
ty = 1;
}
}
cout << fx << ' ' << fy << endl;
return;
}
|
