T1
沙漠点列
直接考虑贪心。容易发现首先一定是先割不在环上的边，这种边每割一条连通块数量增加 \(1\)。然后考虑对环下手。要对一个环进行有用的操作，首先需要先割掉其上的一条边，这次操作不产生贡献。我们希望这样的无用操作尽可能少，于是按照从大往小的顺序割环即可。
代码
#include <iostream>
#include <algorithm>
using namespace std;
static char buf[1000005], *p1 = buf, *p2 = buf;
inline char nnc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000005, stdin), p1 == p2) ? EOF : *p1++; }
// #define nnc getchar
inline int read() {
int ret = 0, neg = 0;
char c = 0;
while (c < '0' || c > '9') c = nnc(), c == '-' ? (neg = 1) : 0;
while ('0' <= c && c <= '9') ret = ret * 10 + c - 48, c = nnc();
return ret * (neg ? -1 : 1);
}
int n, m, k;
int head[1000005], nxt[4000005], to[4000005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int dfn[1000005], low[1000005], ncnt;
int stk[1000005], sz;
int a[1000005], acnt, cnt2;
void tarjan(int x) {
dfn[x] = low[x] = ++ncnt;
stk[++sz] = x;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (!dfn[v]) {
tarjan(v);
low[x] = min(low[x], low[v]);
if (low[v] == dfn[x]) {
int t, c = 1;
do {
t = stk[sz--];
++c;
} while (t != v);
(c == 2) ? (++cnt2) : (a[++acnt] = c);
}
} else
low[x] = min(low[x], dfn[v]);
}
}
int main() {
freopen("desert.in", "r", stdin);
freopen("desert.out", "w", stdout);
n = read(), m = read(), k = read();
for (int i = 1; i <= m; i++) {
int u, v;
u = read(), v = read();
add(u, v);
add(v, u);
}
int ccnt = 0;
for (int i = 1; i <= n; i++) !dfn[i] ? (++ccnt, tarjan(i)) : void();
if (k <= cnt2)
cout << ccnt + k << "\n";
else {
ccnt += cnt2;
k -= cnt2;
sort(a + 1, a + acnt + 1, greater<int>());
for (int i = 1; i <= acnt; i++) {
if (k <= 1)
break;
--k;
ccnt += min(k, a[i] - 1);
k -= min(k, a[i] - 1);
}
cout << ccnt << "\n";
}
return 0;
}
T2
集合划分
考虑到全集只有一个，那不持有全集的那个人必然有至少一位是全 \(0\) 的。也就是说必然存在一个位使得包含这个位的所有集合都被划分给某个人。容易发现这个事情是递归的。然后考虑在第 \(i\) 次划分时我们会将大小为 \(2^{n - i}\) 的集合划分给一个人。那么在给定 A 拿到的集合个数的情况下，容易知道有哪些次划分是给 A 的。那么每次划分给 B 的时候就需要保证这一次划分出的集合不能有 A 所要的。这个事情可以高位前缀和维护。然后可以考虑 dp，\(dp[S]\) 表示是否存在合法方案将 \(S\) 集合中的位划分完毕，转移枚举上一次划分的位即可。为了实现方便可以先枚举 popcount 以确定这次划分是给谁，然后再枚举状态转移，虽然看起来可能比较蠢。
代码
#include <iostream>
#include <algorithm>
#include <cassert>
#include <vector>
using namespace std;
int n, m, K;
int a[300005];
int f[300005], g[300005], S;
int main() {
freopen("set.in", "r", stdin);
freopen("set.out", "w", stdout);
cin >> n >> m >> K;
S = (1 << n) - 1;
for (int i = 1, x; i <= m; i++) cin >> x, ++a[x];
for (int i = 0; i < n; i++) {
for (int j = 0; j < (1 << n); j++) {
if (j & (1 << i))
a[j] += a[j ^ (1 << i)];
}
}
f[0] = 1;
for (int i = n - 1; ~i; i--) {
for (int j = 0; j < (1 << n); j++) {
if (__builtin_popcount(j) != n - i)
continue;
if (K & (1 << i)) {
for (int k = 0; k < n; k++)
(j & (1 << k)) ? (f[j ^ (1 << k)] ? (g[j] = k, f[j] = 1) : 0) : 0;
} else {
for (int k = 0; k < n; k++)
(j & (1 << k)) ? (f[j ^ (1 << k)] && a[S ^ j] == a[S ^ j ^ (1 << k)] ? (g[j] = k, f[j] = 1) : 0) : 0;
}
}
}
if (!f[S])
return 0 * puts("-1");
string str;
for (int i = 0; i <= S; i++) str += '0';
for (int i = 0, x = S, t; i < n; i++) {
x ^= (1 << (t = g[x]));
if (K & (1 << i)) {
for (int j = 0; j <= S; j++) {
if ((j & (1 << t)) && (j & x) == 0)
str[j] = '1';
}
}
}
cout << str.substr(1) << "\n";
return 0;
}
T3
染色
首先观察到答案具有上界 \(2(n - 1)\)，即为先把脚下的染成下一格，然后走。然后考虑计算最多能省掉多少染色。发现在一个位置时可以选择直接找到下一个和当前颜色一样的位置，然后把这一段全染成一个颜色再走。会发现这实际上相当于要选出若干区间 \([l_i, r_i]\)，满足任意两个区间不交于端点外的任何地方，要求最多选出多少区间。这个就随便预处理然后倍增了。
代码
#include <iostream>
#include <string.h>
using namespace std;
static char buf[1000005], *p1 = buf, *p2 = buf;
inline char nnc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000005, stdin), p1 == p2) ? EOF : *p1++; }
// #define nnc getchar
inline int read() {
int ret = 0, neg = 0;
char c = 0;
while (c < '0' || c > '9') c = nnc(), c == '-' ? (neg = 1) : 0;
while ('0' <= c && c <= '9') ret = ret * 10 + c - 48, c = nnc();
return ret * (neg ? -1 : 1);
}
int n, q;
int a[1000005];
int lst[1000005];
int tor[20][1000005];
int l[1000005], r[1000005], ans[1000005];
int main() {
freopen("color.in", "r", stdin);
freopen("color.out", "w", stdout);
n = read(), q = read();
for (int i = 1; i <= n; i++) a[i] = read(), lst[i] = n + 1;
for (int i = n; i; i--) tor[0][i] = lst[a[i]], lst[a[i]] = i;
tor[0][n + 1] = tor[0][n] = n + 1;
for (int i = n; i; i--) tor[0][i] = min(tor[0][i], tor[0][i + 1]);
for (int i = 1; i <= 19; i++) {
for (int j = 1; j <= n + 1; j++)
tor[i][j] = tor[i - 1][tor[i - 1][j]];
}
for (int i = 1; i <= q; i++) l[i] = read(), r[i] = read(), (l[i] > r[i] ? swap(l[i], r[i]) : void()), ans[i] = 2 * (r[i] - l[i]);
for (int i = 19; ~i; i--) {
for (int _ = 1; _ <= q; _++) {
if (tor[i][l[_]] <= r[_])
ans[_] -= (1 << i), l[_] = tor[i][l[_]];
}
}
for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
return 0;
}
T4
不跳棋
考虑不强制在线，可以直接时光倒流变加点，然后点分树每个点上维护最小距离和次小距离和分别的个数即可。然后考虑强制在线的情况，相当于要在删点的过程中维护最小和次小距离。在点分树的每个点上维护一个子树内点到它距离的桶，要删点就考虑在每个点上维护两个指针分别表示最小距离和次小距离，每次删的时候移动两个指针即可。不难注意到这俩玩意的移动都是单调的。在这里两个距离来自同一棵子树并不会影响答案，因为全局的答案一定会严格小于这两个距离的贡献。然后考虑对所有分治中心的答案开一个桶，在这个桶上也维护一个指针代表当前答案。由于每个分治中心的贡献单调，则答案单调，因此这个指针的移动也是单调的。然后就做完了。
代码
#include <iostream>
#include <string.h>
#include <cassert>
#include <vector>
using namespace std;
static char buf[1000005], *p1 = buf, *p2 = buf;
inline char nnc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000005, stdin), p1 == p2) ? EOF : *p1++; }
// #define nnc getchar
inline int read() {
int ret = 0, neg = 0;
char c = 0;
while (c < '0' || c > '9') c = nnc(), c == '-' ? (neg = 1) : 0;
while ('0' <= c && c <= '9') ret = ret * 10 + c - 48, c = nnc();
return ret * (neg ? -1 : 1);
}
int n, tp;
int head[500005], nxt[1000005], to[1000005], ecnt;
inline void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int all, rt, rsz, Rt, asdf;
int sz[500005], msz[500005];
bool vis[500005];
int dist[19][500005], ddep[500005];
int df[500005];
long long cnt[500005], lans;
int ans = 1;
struct node {
vector<int> vec;
int ans, p, q, mxd;
long long cnt;
void init() {
p = 0, q = 1;
if (q <= mxd)
ans = 1, cnt = 1ll * vec[p] * vec[q];
else
ans = n + 1, cnt = 0;
::cnt[ans] += cnt;
}
void upd(int x) {
::cnt[ans] -= cnt;
--vec[x];
while (p <= mxd && !vec[p]) ++p;
while (q <= mxd && !(vec[q] - (p == q))) ++q;
if (q <= mxd)
ans = p + q, cnt = (p == q ? 1ll * vec[p] * (vec[p] - 1) / 2 : 1ll * vec[p] * vec[q]);
else
ans = n + 1, cnt = 0;
::cnt[ans] += cnt;
}
} a[500005];
vector<int> G[500005];
void getroot(int x, int fa, int d = 0, int X = 0) {
msz[x] = sz[x] = 1;
asdf = max(asdf, d);
X ? ++a[X].vec[d] : 0;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa && !vis[v]) {
getroot(v, x, d + 1, X);
sz[x] += sz[v];
msz[x] = max(msz[x], sz[v]);
}
}
msz[x] = max(msz[x], all - sz[x]);
if (msz[x] < rsz)
rsz = msz[x], rt = x;
}
void dfs1(int x) {
vis[x] = 1, asdf = 0;
getroot(x, 0);
a[x].vec.resize((a[x].mxd = asdf) + 1);
a[x].vec[0] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (!vis[v]) {
all = sz[v], rsz = n + 1;
getroot(v, x, 1, x);
ddep[rt] = ddep[df[rt] = x] + 1;
G[x].emplace_back(rt);
dfs1(rt);
}
}
}
void dfs3(int x, int fa, int X, int d = 0) {
dist[ddep[x] - ddep[X]][x] = d;
for (int i = head[x]; i; i = nxt[i]) (to[i] != fa && !vis[to[i]]) ? dfs3(to[i], x, X, d + 1) : void();
}
void dfs2(int x) { vis[x] = 1; dfs3(x, 0, x); for (auto v : G[x]) dfs2(v); }
void Del(int x) {
int u = x, c = 0;
while (u) {
a[u].upd(dist[c][x]);
u = df[u], ++c;
}
while (!cnt[ans]) ++ans;
}
signed main() {
n = read(), tp = read();
for (int i = 1; i < n; i++) {
int u, v;
u = read(), v = read();
add(u, v);
add(v, u);
}
all = n, rt = 0, rsz = n + 1;
getroot(1, 0);
dfs1(Rt = rt);
memset(vis, 0, sizeof vis);
dfs2(Rt);
for (int i = 1; i <= n; i++) a[i].init();
for (int i = 1; i <= n - 2; i++) {
Del(read() ^ (tp * lans));
cout << ans << " " << (lans = cnt[ans]) << "\n";
}
return 0;
}
构造：注意到某个构成单位的特殊性，考虑干掉具有特殊性的构成单位，然后递归构造。
标签：p2,p1,int,20241105,++,include,buf From： https://www.cnblogs.com/forgotmyhandle/p/18529039