病毒可能具有膜结构，但不存在生物膜系统。核糖体是唯一所有细胞均含有的细胞器，但病毒中无核糖体。
病毒的主要组成是 \(10\%\sim 20\%\) 的核酸，\(60\%\sim 70\%\) 的蛋白质外壳，\(<10\%\) 的结合水，可能具有逆转录酶、RNA 聚合酶。病毒的含水量（\(<10\%\)）远远小于细胞（\(70\%\)）。
Type I：调整法 - 1
虽然话是这么说，感觉这就是平常正常的做题路径，『想做法』——『发现有锅』——『打补丁』。
只是可能这是在提醒你在构造题中发现有锅不要急着换做法（？）
例题：C - Stations
一个简单的想法是，当可用的编号范围很大时，可以记下每个点 \(u\) 的 \(DFN_u\) 和出栈序（记为 \(RFN_u\)），这样就能解决查询；但标号是 \(N^2\) 级别的。
现在思考，我们为什么需要记录 \(RFN_u\) 呢？因为在询问时，需要判断 \(t\) 的位置：如果在 \(x\) 某一儿子的子树内，答案为该儿子；否则，答案为 \(fa\)。当 \(DFN_t\) 比 \(u\) 最靠后的儿子 \(v\) 的 \(DFN\) 还要大时，无法判断 \(t\) 在 \(v\) 内还是在 \(u\) 外。
此处有一个解决方案（原谅我实在无法猜出是怎么想到的），将树按奇数层、偶数层分层，计数层记录 \(DFN\)，偶数层记录 \(RFN\)（具体地，奇数层在入栈时编号，偶数层在出栈时编号）；接下来进行判断（注意我们并不知道 \(u\) 所在层数的奇偶性）：
- 若不存在 \(id_i>id_u\)，说明 \(id_u\) 为 \(RFN_u\)；此时 可以判断 \(t\) 是否位于 \(u\) 内。
- 否则，\(id_u\) 为 \(DFN_u\)。由于知道 \(RFN_v\)，可以判断 \(t\) 是否位于 \(v\) 内。
容易证明其他一般情况也可以判断 \(t\) 的位置。复杂度 \(O(n^2)\)。
#include "stations.h"
#include <bits/stdc++.h>
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<std::vector<int> > g(n);
for (int i = 0; i < n - 1; ++i)
g[u[i]].push_back(v[i]), g[v[i]].push_back(u[i]);
std::vector<int> id(n, -1);
int now = 0;
std::function<void(int, int, int)> DFS = [&](int x, int fa, int tag) {
if (tag)
id[x] = now++;
for (auto i : g[x])
if (i != fa)
DFS(i, x, tag ^ 1);
if (!tag)
id[x] = now++;
return;
};
DFS(0, -1, 1);
return id;
}
int find_next_station(int s, int t, std::vector<int> c) {
if (c.back() < s) {
int fa = c.front();
if (t > s)
return fa;
for (int i = (int)c.size() - 1; ~i; --i)
if (t >= c[i])
return c[i];
return fa;
}
else {
int fa = c.back();
if (t < s)
return fa;
for (int i = 0; i < (int)c.size() - 1; ++i)
if (t <= c[i])
return c[i];
return fa;
}
// assert(0);
return 114514;
}Type II：调整法 - 2
题目要求构造『恰好为 \(k\)』，可以先不看这个限制，对于局面求出上界和下界，然后再看是不是上下界中全部（或大多数）都能取到，此时有两个路径：
- 直接在某个上界 / 下界局面中通过若干步极小改动调整到恰好为 \(k\)；
- 通过这一点优化 DP 状态（这样就可以大量压缩『可到达局面』这一信息）。见 此。
例题：D - Construct the Binary Tree
https://codeforces.com/problemset/problem/1311/E
首先从找上下界的角度出发，发现链为上界，完全二叉树为下界。
那么只需先 check \(d\) 是否在该范围内；固定树最左侧的一条链，每次拿走右下角的一个叶子（这样就能维持完全二叉树性质），如果可以插入到链底就 do so；否则由于这是个左边挂着单链的完全二叉树，可以证明你想取的任意深度都可以取到，暴力跳即可，且跳完后就构造完了。
复杂度 \(O(n)\)。
\(O(nd)\) 是每次取点时扫一遍完全二叉树找一个能让当前点深度 \(+1\) 的父节点。\(O(d)\) 的做法是慢慢把树变窄变高，一次还是只 \(+1\)，二者的弊端都在于没利用『上界为链』即链和完全二叉树的优美性质。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int T;
for (std::cin >> T; T--; ) {
int n, d;
std::cin >> n >> d;
std::vector<int> tag(n + 1), dep(n + 1), cnt(n + 1), fa(n + 1);
int L = 0, R = n * (n - 1) / 2;
for (int i = 1; i <= n; ++i) {
L += std::__lg(i), dep[i] = std::__lg(i);
if (i * 2 <= n)
++cnt[i], fa[i * 2] = i;
if (i * 2 + 1 <= n)
++cnt[i], fa[i * 2 + 1] = i;
}
if (L <= d && d <= R) {
std::cout << "YES\n";
int t = 1;
for (int i = 1; i <= n; i *= 2)
tag[i] = 1, t = i;
for (int i = n; i && L != d; --i)
if (!tag[i]) {
// printf("i = %d\n", i);
if (L + (dep[t] + 1) - dep[i] <= d) {
// printf("L += %d - %d\n", dep[t] + 1, dep[i]);
L += (dep[t] + 1) - dep[i];
--cnt[fa[i]], cnt[i] = 0, ++cnt[t];
dep[i] = dep[t] + 1, fa[i] = t;
t = i, tag[i] = 1;
}
else {
for (int j = 1; j <= n; ++j)
if (cnt[j] != 2 && L + (dep[j] + 1) - dep[i] == d) {
fa[i] = j, L = d;
break;
}
}
}
for (int i = 2; i <= n; ++i)
std::cout << fa[i] << ' ';
std::cout << '\n';
}
else {
// printf("[%d, %d]\n", L, R);
std::cout << "NO\n";
}
}
return 0;
}Type III：增量法 / 规约法
增量法：类似数归，发现可以方便地从 \(n-k\) 扩展到 \(n\)，考虑 \(n-k\) 给 \(k\) 带来的限制 / 性质，就可以类递推地做了。
规约法：发现抠掉一个好处理的 \(k\) 之后可以转化为规模为 \(n-k\) 的子问题，考虑 \(k\) 给 \(n - k\) 带来的限制，也可以类递推地做。
其实真差不多哈，并不能说是一正一反之类的，因为思维路径真没太差。
例题：经典题
给定大小为 \(n\) 的竞赛图，\(O(n^2)\) 内求出一条哈密顿路径。
- 竞赛图：给完全图的每条边定向。
- 哈密顿路径：经过每个点恰好一次，对边无要求。
假设已经知道规模为 \(n-1\) 的子问题的解法，塞一个新点进去，考察 \(P(n-1)\) 中的 \(\forall\, u\to v\)：
- 若只存在 \(n\to u,n\to v\)：对于路径起点 \(s\) 也有 \(n\to s\)，把 \(n\) 添加到开头即可。
- 若只存在 \(u\to n,v\to n\)：对于路径终点 \(t\) 也有 \(t\to n\)，把 \(n\) 添加到末尾即可。
- 若只存在 \(n\to u,v\to n\)：对于路径起点 \(s\) 也有 \(n\to s\)，对于路径终点 \(t\) 也有 \(t\to n\)，爱加哪儿就加哪儿。
- 否则：存在 \(u\to n,n\to v\)，皆大欢喜，将 \(u\to v\) 改为 \(u\to n\to v\) 即可。
由此就可以解决问题。
例题：E - Travelling Salesperson
https://www.luogu.com.cn/problem/P6644
注意本题为无向边！
相似地，对于 \(P(n-1)\)，假如存在 \(u\to v\)，欲加入 \(u\to n\to v\) 讨论以下几种情况：
- 若 \(P(n - 1)\) 中只含有一种颜色的边：直接加入首 / 尾即可。
- 若存在 \(\color{red}{\to} u\color{red}{\to}v\color{red}{\to}\)、\(u\color{red}{\to} n\) 和 \(n\color{red}{\to} v\)（蓝色同理）：直接加入，皆大欢喜。
其余情况，就是 \(\color{red}{\to} u\color{blue}{\to} v\color{blue}{\to}\) 的情况了。容易发现除了 \(u\color{blue}{\to} n\land n\color{red}{\to} v\) 之外的情况都可以直接将边加入。故接下来讨论该特例。
此时在 \((u,v)\) 处无法加入；尝试考虑相邻的点。由于在 \(u\color{blue}{\to} v\) 处切换颜色，易知 \(u\ne s\)，即 \(u\) 存在前驱（记为 \(p\)）。
- 若存在 \(p\color{blue}{\to} i\)：连接 \(p,i,u\)，最终局面为 \(\color{red}{\to} p\color{blue}{\to} i\color{blue}{\to} u\color{blue}{\to} v\color{blue}{\to}\)，即将变换处提前两位。
- 否则：存在 \(p\color{red}{\to} i\)，仍然连接 \(p,i,u\)，最终局面为 \(\color{red}{\to} p\color{red}{\to} i\color{blue}{\to} u\color{blue}{\to} v\color{blue}{\to}\)，即将变换处提前一位。
由此可解决问题。可以发现并不存在所谓无解的情况 
—— 倒不如说可以对所有点套用最后一种情况（和第一种）——就能够 \(O(n^2)\) 解决原问题了。
loj 上过了但洛谷过不了 
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
if (n == 1) {
std::cout << "1\n1" << '\n';
return 0;
}
std::vector<std::vector<char> > g(n + 1, std::vector<char> (n + 1));
for (int i = 2; i <= n; ++i)
for (int j = 1; j < i; ++j)
std::cin >> g[i][j], g[j][i] = g[i][j];
for (int i = 1; i <= n; ++i) {
std::vector<int> tag(n + 1);
std::list<int> p({ i, i == 1 ? 2 : 1 });
tag[p.front()] = tag[p.back()] = 1;
bool flag = 1;
char R = g[p.front()][p.back()], B = ((R == 'R') ? 'B' : 'R');
auto pos = --p.end();
for (int j = 1; j <= n; ++j)
if (!tag[j]) {
if (flag && g[j][p.back()] == R)
// printf("%d: 30 ", j),
p.push_back(j), ++pos;
else if (g[j][p.back()] == B)
// printf("%d: 33 ", j),
p.push_back(j), flag = 0;
else {
auto u = pos, v = std::next(pos);
if (g[*u][j] == R && g[j][*v] == R) {
// printf("%d: 38 ", j),
p.insert(v, j), ++++pos;
if (v == --p.end())
flag = 1;
}
else if (g[*u][j] == R && g[j][*v] == B)
// printf("%d: 41 ", j),
p.insert(v, j), ++pos;
else if (g[*u][j] == B && g[j][*v] == B)
// printf("%d: 44 ", j),
p.insert(v, j);
else {
auto pr(std::prev(u));
if (g[*pr][j] == B)
// printf("%d: 49 ", j),
p.insert(u, j), ----pos;
else
// printf("%d: 52 ", j),
p.insert(u, j), --pos;
}
}
// for (auto j : p)
// std::cout << j << ' ';
// printf(" flag = %d\n", flag);
}
std::cout << n << '\n';
for (auto j : p)
std::cout << j << ' ';
std::cout << '\n';
}
return 0;
}