P11208 『STA - R8』轮回疯狂
只执行操作一就是逆序对的个数，统计对于每一个 \(a_i\) 的逆序对个数为 \(b_i\)，然后模拟执行删除操作，如果删除操作比换位操作更优就更新答案。
复杂度 \(O(n \log n)\)
record
将最小的删除可以等价成往里加最大的数，倒着模拟即可。至于操作一，每次往数组 \(b\) 里加完后排序。因为一定可以通过直接删除 \(n-1\) 次使其有序，所以只要操作次数达到 \(n-1\) 直接 break
复杂度 \(O(n)\)
record
P11212 『STA - R8』挑战 Goldbach 猜想
这里提供两种非官解做法。
对于正整数 \(n\)，不超过 \(n\) 的素数个数大约有 \(\frac{n}{\ln n}\) 个。预处理筛素数随便写个筛就行，对于复杂度影响不大。考虑对于小于 \(n\) 枚举每一个素数。那么复杂度就是 \(O(\frac{n^2}{\ln n})\)。我们可以很轻松的将暴力打出来。但是交上去显然过不了。
考虑复杂度瓶颈，我们先忽略代码正确性，将取模运算随便换成别的运算交上去（或者本地测），运行时间甚至没有超过 \(2s\)。所以瓶颈在于取模运算。
将 \(n\) 个答案预处理出来，我们可以预处理出所有的答案记为 \(f_i\)，每询问一次 \(n\) 输出 \(f_n\) 即可。至于预处理时的优化取模，我们可以定义一个变量代表余数，跟随你的枚举而改变，当大小等于模数时重新变为 \(0\) 即可。可以通过。
code
如果不预处理在线计算的做，记忆化一下。开个数组记录已经出现过的答案。然后如果询问的值之前出现过直接输出，否则现场计算。在进行取模的时候，使用巴雷特快速取模算法进行优化。取模慢是因为做除法慢，算法原理大概就是将除法变成其运算加速。具体地，将除以任意数转化成乘一个数、除以一个 \(2^k\)。可能是细节处理的不太好，这个做法最慢的点跑了 \(3s\)。但也足以通过。
code
当然，出题人还友善的提醒了我们代码长度限制。显然是怕我们打表。不难发现，对于大部分答案，大概都是个三位数。计算一下发现对于超出洛谷代码限制我们可以打大概 \(13000\) 个数字。打个表存起来，对于大于 \(13000\) 的再在线暴力计算。代码太长就不放了。
P11209 『STA - R8』小熊游景点 II
太久没写 01-Trie 了人家说这个题正解是 01-Trie 甚至一时没反应过来。
01-Trie 板子题，\(a[i]\) 和 \(b[i]\) 一起存储即可。实现方式很多，让你的 01-Trie 长得奇怪一点多维护一些信息或开个 pair 啥的都是 OK 的。然后每次 query(k) 就是答案。
#include <bits/stdc++.h>#define rint register int
#define int long long
#define endl '\n'using namespace std;const int N = 5e5 + 5;
const int M = 3e7 + 5;int T, n, m;
int a[N], b[N];
int ch[M][2], cnt[M], tot;void insert(int x, int k)
{int p = 0;for (rint i = 30; i >= 0; i--) {int t = x >> i & 1;if (k >> i & 1) {if (!ch[p][t]) ch[p][t] = ++tot;if (!ch[p][!t]) ch[p][!t] = ++tot;cnt[ch[p][t]]++;p = ch[p][!t];} else {if (!ch[p][t]) ch[p][t] = ++tot;p = ch[p][t];}}cnt[p]++;
}int query(int x)
{int p = 0, res = 0;for (rint i = 30; i >= 0; i--){int t = x >> i & 1;if (ch[p][t]) {p = ch[p][t];res += cnt[p];} else {return res;}}return res;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> T >> n >> m;for (rint i = 1; i <= n; i++) cin >> a[i];for (rint i = 1; i <= n; i++) cin >> b[i];for (rint i = 1; i <= n; i++) insert(a[i], b[i]);int last = 0;for (rint i = 1; i <= m; i++) {int k;cin >> k;k ^= T * last;int ans = query(k);cout << ans << endl;last = ans;}return 0;
}
P11187 配对序列
令 \(f_{i,0/1}\) 表示以 \(a_i\) 结尾的偶/奇项的最长配对子序列长，目标 \(f_{i,0}\) 最大值。
转移方程显然：
复杂度 \(O(n^2)\)
考虑优化，这是一个非常典的线段树优化 dp 的转移方程。优化后复杂度 \(O(n \log n)\)
#include <bits/stdc++.h>#define rint register int
#define int long long
#define endl '\n'using namespace std;const int N = 5e5 + 5;
const int inf = 5e5 + 5;int n;
int a[N], f[N][2];
int g[N], ans;struct Node
{int v;
} t[N * 4];#define ls p << 1
#define rs p << 1 | 1void push_up(int p)
{t[p].v = max(t[ls].v, t[rs].v);
}void change(int p, int l, int r, int x, int d)
{if (l == r) {t[p].v = d;return ;} int mid = (l + r) >> 1;if (x <= mid) change(ls, l, mid, x, d);else change(rs, mid + 1, r, x, d);push_up(p);
}int query(int p, int l, int r, int x, int y)
{if (x <= l && r <= y) return t[p].v;int mid = (l + r) >> 1;int res = -inf;if (x <= mid) res = max(res, query(ls, l, mid, x, y));if (y > mid) res = max(res, query(rs, mid + 1, r, x, y));return res;
}signed main()
{cin >> n;memset(g, -1, sizeof g);for (rint i = 1; i <= n; i++) {cin >> a[i];f[i][1] = 1;if (a[i] != 1) f[i][1] = max(f[i][1], query(1, 1, inf, 1, a[i] - 1) + 1);if (a[i] != inf) f[i][1] = max(f[i][1], query(1, 1, inf, a[i] + 1, inf) + 1);f[i][0] = g[a[i]] + 1;g[a[i]] = max(g[a[i]], f[i][1]);if (query(1, 1, inf, a[i], a[i]) < f[i][0]) change(1, 1, inf, a[i], f[i][0]);ans = max(ans, f[i][0]);}cout << ans << endl; return 0;
}
