(赛中+补题记录)

不是题解,更多是做题心得与评价。

  • 时间卡的也太紧了,STD 两倍时限,STD 用数组我用 std::map 就 T 了。。

  • PI 节没出个关于 PI 的题

1001 学位运算导致的

和同学聊天时口胡的思路,可能有点混乱

所求的yy,直接看是若干个数 or and and or 这样从左至右算出来的,当然这些数可能重复。or and 运算满足分配律,所以表达式总是可以化简为若干个东西 or 起来再 and,或者若干个东西 and 起来再 or。选后者,比较符合直觉。

可以先从极端想,若干个东西 and 出来只有一位。枚举每一位,把 and 起来还有这一位的东西都 and 起来,尽量让其它位都变 0。当然如果没办法都变成 0,就形成了要有这一位,另一位就必须存在这种关系(注意这关系没有传递性)。比如原来是 10 和 11(二进制),包含最低位的那只能是 11。这些数有个特点,要么独立要么包含,两两 and 不可能更小,不会有 110 和 011 同时出现。这样处理将得到 64 个大数。

现在的问题就是,64 个数,选择一些数做 or,运算结果比xx 大且最小。

大概要枚举前缀,每次给xx 加个 lowbit,能不能用这些数或出一个这样的前缀。而后几位不用考虑,不加那肯定最小。比如当前前缀是 V,or 和是 sum,必须始终 sum&V=sum,逐个遍历那 64 个数加入 sum,看最终 sum 是不是等于 V,等于那就说明这个前缀可以构造出来。所有可能的结果取最小值就是答案。

但是复杂度是 log 方的,枚举前缀一个log,再枚举又一个log,过不去。

道理是对的,但是方案有问题,可能哪里浪费了。

确实浪费了。每次给xx 加个 lowbit 可以假加,因为这个步骤的本质是把某个 0 变成 1,后面忽略。sum&V=sum 也可以假判断,或者说这个判断完全没必要。xx 有 1 就必须把这个数加上,没得选,就算加上去更大了也没办法,得加,不加上就没法满足那个条件。所以其实是唯一的,没必要判断。这样省了个 log。

现在的方案是,从高位到地位枚举xx 的二进制位。如果是 1 就加到 sum 里,否则是 0,可能产生答案,把这一位 0 虚拟地变成 1 并把对应的数虚拟地加到 sum 计算结果。所有可能的结果取最小值就是答案。

时间复杂度O[(n+q)logV]\operatorname{O}[(n+q)\log V]

注意:mod 不要写 1e16 + 1029,这是个 double,精度丢完了。

Bonus: 出题人说优雅集对应拓扑,sol 相当于找一组拓扑基。

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
int n, q;
cin >> n >> q;
vector<ull> dp(64, -1); // -1 相当于 1111...1111
while (n--) {
ull x;
cin >> x;
for (int bit = 63; bit >= 0; bit--) {
if (x >> bit & 1) {
dp[bit] &= x;
}
}
}
ull ans = 0;
while (q--) {
ull x;
cin >> x;
ull sum = 0, res = -1; // -1 相当于最大值
for (int bit = 63; bit >= 0; bit--) {
if (x >> bit & 1) {
sum |= dp[bit];
} else {
res = min(res, sum | dp[bit]);
}
}
res = min(res, sum);
ans ^= res % mod;
}
cout << ans << endl;

1002 学历史导致的

我真的是读入一个字符串后,先分离出天干、地支,然后再用 exCRT 算出年份的。

应该先预处理。

1003 学数数导致的

比较考验基本功。

对于每个正整数,贪心找第一次出现的位置,下一个 0,下一个出现的位置,再加上后缀本质不同的数的数量。

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 n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
auto all = a;
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
for (int i = 0; i < n; i++) {
a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin();
}
vector<vector<int>> mp(all.size());
for (int i = 0; i < n; i++) {
mp[a[i]].push_back(i);
}
vector<int> suf(n + 1); // 后缀本质不同的个数
vector<int> cnt(all.size());
for (int i = n - 1; i >= 0; i--) {
suf[i] = suf[i + 1];
if (a[i] && !cnt[a[i]]) {
cnt[a[i]]++;
suf[i]++;
}
}
ll res = 0;
auto& vec0 = mp[0];
for (int i = 1; i < mp.size(); i++) {
auto& vec = mp[i];
auto it = vec.begin();
it = lower_bound(vec0.begin(), vec0.end(), *it);
if (it == vec0.end()) continue;
it = lower_bound(vec.begin(), vec.end(), *it);
if (it == vec.end()) continue;
res += suf[*it + 1];
}
cout << res << endl;

可以优化为线性:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> fst(all.size());
vector<int> suf(n + 1);
for (int i = n - 1; i >= 0; i--) {
suf[i] = suf[i + 1];
if (a[i]) {
suf[i] += (fst[a[i]] == 0);
fst[a[i]] = i;
}
}
ll res = 0;
int last0 = 0;
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
last0 = i;
continue;
}
if (fst[a[i]] < last0) {
res += suf[i + 1];
fst[a[i]] = inf;
}
}
cout << res << endl;

不离散化打 map 会多个 log,TLE。

1004 学 DP 导致的

小 DP,按值按下标皆可。k>26k>26 时相当于 26,但需注意数据范围,kk 不能用 int 或 ll 存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
string s, t;
cin >> s >> t;
int k = (t.size() > 2) ? 26 : stoi(t);
array<int, 26> dp{};
while (k--) {
for (auto c : s) {
c -= 'a';
dp[c] = max(dp[c], 1);
for (int j = 0; j < c; j++) {
dp[c] = max(dp[c], dp[j] + 1);
}
}
}
cout << *max_element(dp.begin(), dp.end()) << endl;

1005 学几何导致的

不喜欢计算,小计算也不喜欢。

1006 学博弈论导致的

操作规则很复杂,而且是可打表(不可能无法结束,按照红蓝盒子的顺序能打表)的博弈题,无脑打表观察。

个人认为题解那种转化可操作性不强。除非一眼,有这时间表已经打出来了。

打表程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int dp[500][500][500];
dp[0][0][0] = 0;
for (int k = 0; k < 150; k++) { // 盒子
for (int i = 0; i < 150; i++) { // 蓝
for (int j = 0; j < 150; j++) { // 红
int ans = 1;
if (j >= 1) chmin(ans, dp[i][j - 1][k]);
if (j >= 2) chmin(ans, dp[i][j - 2][k]);
if (j >= 3) chmin(ans, dp[i][j - 3][k]);
if (i >= 1) chmin(ans, dp[i - 1][j][k]);
if (i >= 1 && j >= 1) chmin(ans, dp[i - 1][j - 1][k]);
if (i >= 1) chmin(ans, dp[i - 1][j + 1][k]);
if (i >= 2) chmin(ans, dp[i - 2][j + 1][k]);
if (k >= 1) chmin(ans, dp[i][j + 1][k - 1]);
if (k >= 1) chmin(ans, dp[i + 1][j][k - 1]);
if (k >= 1) chmin(ans, dp[i + 1][j + 1][k - 1]);
dp[i][j][k] = 1 - ans;
}
}
}

打出来长这样:

1
2
3
4
5
6
7
8
0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1
0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1
0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1
0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1

0 的位置也比较显然了。

1
2
3
4
5
6
7
8
9
10
11
int j, i, k;
cin >> j >> i >> k;
j %= 4;
i %= 2;
if (j % 2 == 1) {
cout << "Alice" << endl;
} else if (i == j / 2) {
cout << "Bob" << endl;
} else {
cout << "Alice" << endl;
}

1007 学计算导致的(待补)

1008 学画画导致的

这题大概是区域赛铜,思路好想但不好写的那种。

拓扑排序删掉完美的某行,能全删掉就 ok。

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
int n, q;
cin >> n >> q;
vector<vector<int>> adj(3 * n);
bool ok = true;
while (q--) {
int x, y, c;
cin >> x >> y >> c;
x--, y--, c--;
int u[3] = {
y / 2, // 竖着的
2 * n - 1 - x, // 横着的
x - (y + 1) / 2 + 2 * n // 斜着的
};
bool found = false;
for (int o = 0; o < 3; o++) {
if (c == u[o]) {
found = true;
adj[u[o]].push_back(u[(o + 1) % 3]);
adj[u[o]].push_back(u[(o + 2) % 3]);
}
}
if (!found) ok = false; // 特判
}
// 下面是拓扑排序模板
vector<int> deg(3 * n);
for (int u = 0; u < (3 * n); u++) {
for (auto v : adj[u]) deg[v]++;
}
vector<int> Q;
for (int u = 0; u < (3 * n); u++) {
if (deg[u] == 0) Q.push_back(u);
}
for (int i = 0; i < Q.size(); i++) {
auto u = Q[i];
for (auto v : adj[u]) {
if (--deg[v] == 0) Q.push_back(v);
}
}
if (Q.size() != (3 * n)) ok = false;
cout << (ok ? "Yes" : "No") << endl;

1009 学高考第19题导致的

非常好的图论建模题,只是题面有点绕,真是学高考第 19 题导致的。

题目的意思是将aa 重排,新数组与原数组的那个关系\prec(Latex: \prec)相对不变,原来满足那新数组也要满足,反之亦然。

我的想法是,注意i,ji,j 满足那个关系,那么iii+1,,j1i+1,\dots, j-1 都满足,可以找对于每个ii,第一个不满足那个关系的jj,给iji\to j 连边后会形成一棵树。但这样丢信息了,只给iji\to j 连边不行,没有保证中间的都串在一起。

题解说找ii 左边最大的jj,使得j,ij,i 满足关系,这就对了。现在也构成一棵树,所有有关系的,在树上都有一条链,所有没关系的,在树上都是兄弟。因此,只能修改子树之间的顺序。

从叶子到根依次排序。排序方案是,如果根不同,小的在前(思考为什么字典序最大还要小的在前),如果根不同,按字典序排序。字典序缺位补++\infty

std::list 实现,代码极短。

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
vector<int> a(n + 1);
vector<vector<int>> adj(n + 1);
a[0] = inf;
stack<int> stk;
stk.push(0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
// 找左边最近的比自己大的数
while (a[stk.top()] <= a[i]) {
stk.pop();
}
adj[stk.top()].push_back(i);
stk.push(i);
}
vector<list<int>> list(n + 1);
for (int i = 0; i <= n; i++) {
list[i].push_back(a[i]);
list[i].push_back(inf); // 缺位补inf
}
for (int i = n; i >= 0; i--) {
sort(adj[i].begin(), adj[i].end(), [&](int x, int y) {
return a[x] == a[y] ? list[x] > list[y] : a[x] < a[y];
});
for (auto x : adj[i]) {
list[i].pop_back(); // 把补的inf删了
list[i].splice(list[i].end(), list[x]);
}
}
list[0].pop_front();
list[0].pop_back();
for (auto x : list[0]) {
cout << x << " ";
}
cout << endl;

1010 学排列导致的(待补)