正式训练
K. Maximum GCD
注意到两个结论：首先，对 $n$ 任意取模的结果只可能是小于 $\dfrac{n}{2}$ 的正整数。其次，一个序列的最大公约数不会超过这个序列的最小值。
不妨设给出的序列的最小值为 $a$。如果序列没有 $[a + 1, 2a]$ 中的数，那么根据结论一，其他所有数均可以变成 $a$，而结论二表明这一结果是最大的。
序列中有 $2a$ 并不会影响上述结论，因为显然 $a$ 能整除 $2a$，不影响最大公约数。
如果序列中有 $[a + 1, 2a)$ 中的数，那么显然 $a$ 已经取不到了。如果 $a$ 是偶数，我们可以将所有 $[a + 1, 2a)$ 中的数变成 $\dfrac{a}{2}$ 来构造出一组解。如果 $a$ 是奇数，我们可以将所有 $[a, 2a)$ 中的数变成 $\dfrac{a - 1}{2}$ 来构造出一组解。
A. TreeScript
显然把一个子树建完再开新坑是最优的。然后不难发现对于每个节点 $u$，最后一个被建的子树可以复用 $u$ 的寄存器。直接 DP 即可。
L. Permutation Compression
由于每次删除的是一个区间的最大值，考虑从大到小进行贪心。每次删的时候查一下最长能用多长的区间进行删除。需要用一些数据结构维护由于删除造成的下标偏移。
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
| #include <bits/stdc++.h>
using namespace std;
bool solve() {
int n, m, k;
cin >> n >> m >> k;
vector<int> pos(n + 1);
for(int i = 1; i <= n; i++) {
int val;
cin >> val;
pos[val] = i;
}
bool invalid = false;
vector<bool> used(n + 1);
for(int i = 1, lst = 0; i <= m; i++) {
int val;
cin >> val;
if(pos[val] < lst) {
invalid = true;
}
lst = pos[val];
used[val] = true;
}
map<int, int> tool;
for(int i = 1; i <= k; i++) {
int val;
cin >> val;
tool[val]++;
}
if(invalid) {
return false;
}
set<int> used_position {0, n + 1};
vector<int> bit(n + 1);
auto query = [&] (int u) {
int ans = 0;
while(u > 0) {
ans += bit[u];
u -= u & -u;
}
return ans;
};
for(int i = n; i >= 1; i--) {
if(used[i]) {
used_position.insert(pos[i]);
continue;
}
int cur_pos = pos[i];
auto nxt = used_position.lower_bound(pos[i]);
auto pre = prev(nxt);
int mxlen = *nxt - *pre - 1 - (query(*nxt - 1) - query(*pre));
auto it = tool.upper_bound(mxlen);
if(it == tool.begin()) {
return false;
}
it--;
if(--(it->second) == 0) {
tool.erase(it);
}
while(cur_pos <= n) {
bit[cur_pos]++;
cur_pos += cur_pos & -cur_pos;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
if(solve()) {
puts("YES");
} else {
puts("NO");
}
}
return 0;
}
|
F. Sum of Numbers
可以发现切出来相邻的两端长度之差不能超过 $1$。暴力枚举即可。
赛时这题的代码是队友写的，赛后感觉实现的不是很精细就自己重写了一个版本。
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
| #include <bits/stdc++.h>
using namespace std;
struct BigInt {
static const int MOD = 1000000000;
static const int N_BIT = 9;
vector<int> nums;
BigInt(const char *s, int n) {
int val = 0, base = 1;
for(int i = n - 1; i >= 0; i--) {
val += (s[i] - '0') * base;
base *= 10;
if(base == MOD) {
nums.push_back(val);
val = 0;
base = 1;
}
}
if(nums.empty() || val != 0) {
nums.push_back(val);
}
}
BigInt &operator= (const BigInt &&u) {
nums = move(u.nums);
return *this;
}
BigInt &operator+= (const BigInt &u) {
nums.resize(max(nums.size(), u.nums.size()));
int carry = 0;
for(size_t i = 0; i < nums.size(); i++) {
nums[i] += carry + (i < u.nums.size() ? u.nums[i] : 0);
if(nums[i] >= MOD) {
nums[i] -= MOD;
carry = 1;
} else {
carry = 0;
}
}
if(carry) {
nums.push_back(carry);
}
return *this;
}
bool operator< (const BigInt &u) {
if(nums.size() != u.nums.size()) {
return nums.size() < u.nums.size();
}
for(size_t i = nums.size() - 1; i < nums.size(); i--) {
if(nums[i] != u.nums[i]) {
return nums[i] < u.nums[i];
}
}
return false;
}
};
ostream& operator<< (ostream &os, const BigInt &u) {
ios states(nullptr);
states.copyfmt(os);
os << u.nums.back();
for(int i = (int)u.nums.size() - 2; i >= 0; i--) {
os << setw(BigInt::N_BIT) << setfill('0') << u.nums[i];
}
os.copyfmt(states);
return os;
}
void solve() {
int n, k;
string str;
cin >> n >> k >> str;
vector<int> lths(k + 1);
BigInt ans(str.c_str(), n);
function<void(int)> dfs = [&] (int idx) {
if(idx > k) {
partial_sum(lths.begin(), lths.end(), lths.begin());
int base = accumulate(lths.begin(), lths.end(), 0);
if((n - base) % (k + 1) == 0) {
base = (n - base) / (k + 1);
if(base + *min_element(lths.begin(), lths.end()) > 0) {
BigInt res(nullptr, 0);
int l = 0;
for(int cur : lths) {
res += BigInt(str.c_str() + l, base + cur);
l += base + cur;
}
if(res < ans) {
ans = move(res);
}
}
}
adjacent_difference(lths.begin(), lths.end(), lths.begin());
return;
}
for(int i = -1; i <= 1; i++) {
lths[idx] = i;
dfs(idx + 1);
}
};
dfs(1);
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
solve();
}
return 0;
}
|
补题记录
EH 题队友在训练的时候解决了。剩下的题暂咕。
