P11208 『STA - R8』轮回疯狂
只执行操作一就是逆序对的个数，统计对于每一个 \(a_i\) 的逆序对个数为 \(b_i\)，然后模拟执行删除操作，如果删除操作比换位操作更优就更新答案。
复杂度 \(O(n \log n)\)
将最小的删除可以等价成往里加最大的数，倒着模拟即可。至于操作一，每次往数组 \(b\) 里加完后排序。因为一定可以通过直接删除 \(n-1\) 次使其有序，所以只要操作次数达到 \(n-1\) 直接 break
复杂度 \(O(n)\)
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\) 即可。可以通过。
如果不预处理在线计算的做，记忆化一下。开个数组记录已经出现过的答案。然后如果询问的值之前出现过直接输出，否则现场计算。在进行取模的时候，使用巴雷特快速取模算法进行优化。取模慢是因为做除法慢，算法原理大概就是将除法变成其运算加速。具体地，将除以任意数转化成乘一个数、除以一个 \(2^k\)。可能是细节处理的不太好，这个做法最慢的点跑了 \(3s\)。但也足以通过。
当然，出题人还友善的提醒了我们代码长度限制。显然是怕我们打表。不难发现，对于大部分答案，大概都是个三位数。计算一下发现对于超出洛谷代码限制我们可以打大概 \(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}\) 最大值。
转移方程显然：
\[f_{i,1}=\max_{a_j=a_i}f_{j,0}+1\\ f_{i,0}=\max_{a_j\neq a_i}f_{i,1}+1\]复杂度 \(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 | 1
void 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;
}