NOIP 2024 四题详解
T1 字符串变换
时隔一年重新做这道题。由于之前做过，大约15分钟就用贪心思路解决了。核心策略：如果两个字符串当前位置都无需变换，或者已经相同，则直接跳过。否则检查 s₁ 和 s₂ 能否在当前位置完成交换，成功一次后立即跳过，避免重复操作。
交换过程采用从当前位置向后扫描的策略，遇到无法交换的字符即终止。若途中发现与原始位置字符不同的元素，即可将其与目标字符互换。由于字符间可以任意两两交换，内部顺序总能调整回原始状态，因此直接交换是安全的。
参考实现
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; i++)
int n, res, ptr1, ptr2, flag;
string str1, str2, pat1, pat2;
void process(string &pattern, string &text, int pos, int &cur) {
for (cur = max(cur, pos + 1); pattern[cur] == '1'; cur++) {
if (text[pos] == text[cur]) continue;
flag = 1; swap(text[pos], text[cur]);
res++; break;
}
}
void solve() {
cin >> n >> str1 >> str2 >> pat1 >> pat2;
res = ptr1 = ptr2 = 0;
rep(i, 0, n - 1) {
if (str1[i] == str2[i]) { res++; continue; }
if (pat1[i] == '0' && pat2[i] == '0') continue;
flag = 0;
if (pat1[i] == '1') process(pat1, str1, i, ptr1);
if (flag) continue;
if (pat2[i] == '1') process(pat2, str2, i, ptr2);
}
cout << res << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T--) solve();
return 0;
}T2 约束序列计数
一道典型的组合数学问题，耗时约30分钟。采用正难则反的思路，用总方案数减去不合法方案数。分析发现每个位置的约束仅与其前方最近的指定位置相关，更前面的位置无影响。
对于首个 x_c = d 之前的所有位置，a_i 和 b_i 均可自由选择，各有 v 种选法，共 v² 种方案。中间段的合法方案数同理，总方案数为 v^(2(r-l))。
不合法情形是指：从前一个指定位置 x 出发，通过递推关系 x_i = a_i → x_{i+1} = b_i 链式推导，最终得到的值与后一个指定位置的预期值冲突。此时中间段的 a_i 已被唯一确定，仅 b_i 有 v 种选择，但最后一个 b 需避开当前值，故贡献为 v-1。
参考实现
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
const int MAXN = 1e5 + 10;
const ll MOD = 1e9 + 7;
ll n, val;
int m;
struct Constraint {
ll pos, value;
} cons[MAXN];
ll qpow(ll base, ll exp) {
ll ret = 1;
while (exp) {
if (exp & 1) ret = ret * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return ret;
}
bool comp(Constraint x, Constraint y) {
return x.pos < y.pos;
}
void solve() {
bool invalid = 0;
cin >> n >> m >> val;
rep(i, 1, m) cin >> cons[i].pos >> cons[i].value;
sort(cons + 1, cons + m + 1, comp);
ll ans = qpow(val, 2 * (cons[1].pos - 1)) % MOD;
rep(i, 1, m - 1) {
ll left = cons[i].pos, right = cons[i + 1].pos;
if (left == right && cons[i].value != cons[i + 1].value) {
invalid = 1; break;
}
if (left == right) continue;
ans = ans * ((qpow(val, 2 * (right - left))
- (val - 1) * qpow(val, right - left - 1) % MOD + MOD) % MOD) % MOD;
}
ans = ans * qpow(val, 2 * (n - cons[m].pos)) % MOD;
cout << (invalid ? 0 : ans) << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T--) solve();
return 0;
}T3 树形结构计数
难度陡增，考场上先跳过了。不过 k = 1 的部分分非常友好，不到5分钟即可拿下28分，再次印证NOIP部分分策略的重要性。
k = 1 时，每个节点的贡献为其度数减一的阶乘，将所有节点乘积即为答案。
参考实现
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
const int MAXN = 1e5 + 10;
const ll MOD = 1e9 + 7;
int n, k;
ll fac[MAXN], ifac[MAXN];
vector<int> adj[MAXN];
int deg[MAXN], tmp[MAXN];
ll qpow(ll base, ll exp) {
ll ret = 1;
while (exp) {
if (exp & 1) ret = ret * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return ret;
}
void init() {
fac[0] = ifac[0] = 1;
rep(i, 1, n) fac[i] = fac[i - 1] * i % MOD;
ifac[n] = qpow(fac[n], MOD - 2);
for (int i = n - 1; i >= 1; i--)
ifac[i] = ifac[i + 1] * (i + 1) % MOD;
}
void solve() {
cin >> n >> k;
rep(i, 1, n) { adj[i].clear(); deg[i] = 0; }
init();
rep(i, 1, n - 1) {
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
deg[u]++; deg[v]++;
}
rep(i, 1, k) cin >> tmp[i];
ll ans = 1;
rep(i, 1, n) ans = ans * fac[deg[i] - 1] % MOD;
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int type, T; cin >> type >> T;
while (T--) solve();
return 0;
}T4 区间LCA查询
经典结论题：区间LCA可转化为相邻两点LCA深度的最小值。即对于区间 [l, r]，有：
dep(LCA(l, r)) = min{ dep(LCA(i, i+1)) | l ≤ i < r }
预处理出以 LCA(i, i+1) 为最近公共祖先的最大控制区间 [x_i, y_i, v_i]，其中 v_i 为对应深度。
查询转化为：找与 [l, r] 交集至少为 k 且 v_i 最大的区间。可行条件分为两类：
- 条件一：
y_i ≥ r且x_i ≤ r - k + 1 - 条件二：
l + k - 1 ≤ y_i ≤ r且y_i - x_i + 1 ≥ k
第一类对 r 扫描线，第二类对 k 扫描线，配合线段树维护，复杂度 O(n log n)。
参考实现
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; i++)
const int MAXN = 5e5 + 10;
int n, qnum;
vector<int> tree[MAXN];
int parentArr[MAXN], subtree[MAXN];
int depthArr[MAXN], heavy[MAXN], top[MAXN];
void dfs1(int u, int p) {
parentArr[u] = p;
depthArr[u] = depthArr[p] + 1;
subtree[u] = 1;
for (int v : tree[u]) {
if (v == p) continue;
dfs1(v, u);
subtree[u] += subtree[v];
if (subtree[v] > subtree[heavy[u]]) heavy[u] = v;
}
}
void dfs2(int u, int t) {
top[u] = t;
if (heavy[u]) dfs2(heavy[u], t);
for (int v : tree[u]) {
if (v == parentArr[u] || v == heavy[u]) continue;
dfs2(v, v);
}
}
int getLca(int a, int b) {
while (top[a] != top[b]) {
if (depthArr[top[a]] >= depthArr[top[b]]) a = parentArr[top[a]];
else b = parentArr[top[b]];
}
return depthArr[a] < depthArr[b] ? a : b;
}
struct EdgeInfo {
int left, right, val, idx;
} edges[MAXN];
struct QueryInfo {
int left, right, need, idx;
} queries[MAXN];
int answer[MAXN];
#define ls u << 1
#define rs u << 1 | 1
struct SegTree {
int mx[MAXN << 2];
void update(int u, int L, int R, int pos, int v) {
mx[u] = max(mx[u], v);
if (L == R) return;
int mid = (L + R) >> 1;
if (mid >= pos) update(ls, L, mid, pos, v);
else update(rs, mid + 1, R, pos, v);
}
int query(int u, int L, int R, int l, int r) {
if (l <= L && R <= r) return mx[u];
int mid = (L + R) >> 1;
if (mid >= r) return query(ls, L, mid, l, r);
if (mid < l) return query(rs, mid + 1, R, l, r);
return max(query(ls, L, mid, l, r), query(rs, mid + 1, R, l, r));
}
} seg[2];
bool cmpLen(EdgeInfo a, EdgeInfo b) {
return a.right - a.left > b.right - b.left;
}
bool cmpNeed(QueryInfo a, QueryInfo b) {
return a.need > b.need;
}
bool cmpR(EdgeInfo a, EdgeInfo b) {
return a.right > b.right;
}
bool cmpQR(QueryInfo a, QueryInfo b) {
return a.right > b.right;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
rep(i, 1, n - 1) {
int u, v; cin >> u >> v;
tree[u].push_back(v); tree[v].push_back(u);
}
dfs1(1, 0); dfs2(1, 1);
rep(i, 1, n - 1) {
edges[i].idx = i;
edges[i].val = depthArr[getLca(i, i + 1)];
}
rep(i, 1, n) seg[0].update(1, 1, n, i, depthArr[i]);
// 单调栈求控制区间
edges[0].val = edges[n].val = -1;
stack<int> stk;
stk.push(0);
rep(i, 1, n - 1) {
while (edges[stk.top()].val >= edges[i].val) stk.pop();
edges[i].left = stk.top() + 1;
stk.push(i);
}
while (!stk.empty()) stk.pop();
stk.push(n);
for (int i = n - 1; i >= 1; i--) {
while (edges[stk.top()].val >= edges[i].val) stk.pop();
edges[i].right = stk.top() - 1;
stk.push(i);
}
cin >> qnum;
rep(i, 1, qnum) {
cin >> queries[i].left >> queries[i].right >> queries[i].need;
queries[i].idx = i;
queries[i].right--;
queries[i].need--;
}
// 对k扫描线
sort(edges + 1, edges + n, cmpLen);
sort(queries + 1, queries + qnum + 1, cmpNeed);
int p = 1;
rep(i, 1, qnum) {
if (queries[i].need == 0) {
answer[queries[i].idx] = seg[0].query(1, 1, n, queries[i].left, queries[i].right + 1);
continue;
}
while (p < n && edges[p].right - edges[p].left + 1 >= queries[i].need) {
seg[1].update(1, 1, n, edges[p].right, edges[p].val);
p++;
}
answer[queries[i].idx] = seg[1].query(1, 1, n,
queries[i].left + queries[i].need - 1, queries[i].right);
}
// 对r扫描线
sort(edges + 1, edges + n, cmpR);
sort(queries + 1, queries + qnum + 1, cmpQR);
memset(seg[1].mx, 0, sizeof(seg[1].mx));
p = 1;
rep(i, 1, qnum) {
while (p < n && edges[p].right > queries[i].right) {
seg[1].update(1, 1, n, edges[p].left, edges[p].val);
p++;
}
answer[queries[i].idx] = max(answer[queries[i].idx],
seg[1].query(1, 1, n, 1, queries[i].right - queries[i].need + 1));
}
rep(i, 1, qnum) cout << answer[i] << '\n';
return 0;
}