A. 树结构计数问题

给定数组 a = [1, 2, ..., n]，我们需要统计满足特定条件的子树结构数量。

关键观察：对于区间 [l, r]，当 max(b[l, r]) = b_l + r - l 时，该区间构成合法子树。

使用动态规划 f[l][r] 表示区间 [l, r] 构成森林的方案数。通过递归划分和卡特兰数优化，可将时间复杂度降至 O(n²)。

#include<bits/stdc++.h>
using namespace std;
const int N=5005, M=998244353;
int n, pos[N], val[N], dp[N][N], tmp[N];
vector<int> seg[N];

int calc(int l, int r) {
    if(l >= r) return 1;
    if(dp[l][r] != -1) return dp[l][r];
    
    int p = upper_bound(seg[l].begin(), seg[l].end(), r) - seg[l].begin() - 1;
    if(seg[l][p] < r) 
        return dp[l][r] = 1LL * calc(l, seg[l][p]) * calc(seg[l][p]+1, r) % M;
    
    int res = 1;
    for(int i = 1; i <= p; ++i) 
        res = 1LL * res * calc(seg[l][i-1]+1, seg[l][i]) % M;
    
    // 动态规划处理合并顺序
    tmp[1] = 1;
    for(int i = 1; i <= p; ++i) {
        if(seg[l][i-1] < seg[l][i] - 1) {
            for(int j = i; j >= 0; --j) 
                tmp[j] = (tmp[j] + tmp[j+1]) % M;
        } else {
            for(int j = i+1; j >= 1; --j) 
                tmp[j] = (tmp[j+1] + tmp[j-1]) % M;
            tmp[0] = 0;
        }
    }
    
    for(int i = 1; i <= p+1; ++i) 
        tmp[0] = (tmp[0] + tmp[i]) % M, tmp[i] = 0;
    
    return dp[l][r] = 1LL * res * tmp[0] % M;
}

void solve() {
    cin >> n;
    memset(dp, -1, sizeof dp);
    
    for(int i = 1, x; i <= n; ++i) 
        cin >> x, pos[x] = i;
    for(int i = 1, x; i <= n; ++i) 
        cin >> x, val[i] = pos[x];
    
    for(int i = 1; i <= n; ++i) {
        seg[i].clear();
        for(int j = i, mx = 0; j <= n && val[j] >= val[i]; ++j) {
            mx = max(mx, val[j]);
            if(mx - val[i] == j - i) seg[i].push_back(j);
        }
    }
    
    cout << calc(1, n) << "\n";
}

B. 矩阵优化动态规划

这是一个典型的矩阵快速幂优化DP问题。状态包括当前列球的位置、边界阻挡情况等。

通过构建转移矩阵，时间复杂度为 O(n³ log m)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;

struct Matrix {
    int f[205][205];
    Matrix() { memset(f, 0, sizeof f); }
    
    Matrix operator*(const Matrix& b) const {
        Matrix c;
        for(int i = 0; i <= 4*n; ++i)
            for(int k = 0; k <= 4*n; ++k) if(f[i][k])
                for(int j = 0; j <= 4*n; ++j)
                    c.f[i][j] = (c.f[i][j] + 1LL * f[i][k] * b.f[k][j]) % MOD;
        return c;
    }
};

int pow_mod(int a, int b) {
    int res = 1;
    for(; b; b >>= 1, a = 1LL * a * a % MOD)
        if(b & 1) res = 1LL * res * a % MOD;
    return res;
}

void solve() {
    int n, m; cin >> n >> m;
    Matrix I, Z;
    // 初始化矩阵...
    for(; m; m >>= 1, I = I * I) 
        if(m & 1) Z = Z * I;
    cout << Z.f[0][0] << "\n";
}

C. WQS二分优化

通过WQS二分将决策单调性问题转化为凸优化问题。

对数组排序后，利用四边形不等式性质进行动态规划优化，时间复杂度 O(n log n log V)。

#include<bits/stdc++.h>
#define LL __int128
using namespace std;

struct Info { LL cost; int cnt; };
bool operator<(const Info& a, const Info& b) {
    return a.cost != b.cost ? a.cost < b.cost : a.cnt < b.cnt;
}

Info check(LL lambda) {
    // 实现检查函数逻辑
    return {0, 0};
}

void solve() {
    int n, K; cin >> n >> K;
    vector<int> a(n+1);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    
    LL left = -4e19, right = 4e19, ans = right;
    while(left <= right) {
        LL mid = (left + right) >> 1;
        if(check(mid).cnt <= K) ans = mid, right = mid - 1;
        else left = mid + 1;
    }
    
    auto result = check(ans);
    // 输出结果...
}

D. 中位数排列构造

给定部分元素位置，构造满足中位数条件的排列。

通过分析 a_x = 1, a_y = n 的约束，将问题分解为两个递增序列的组合计数。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+5, MOD = 998244353;

ll fpow(ll a, ll b = MOD-2) {
    ll res = 1;
    for(; b; b >>= 1, a = a * a % MOD)
        if(b & 1) res = res * a % MOD;
    return res;
}

ll fact[N], ifact[N];
ll comb(int n, int k) {
    return k < 0 || k > n ? 0 : fact[n] * ifact[k] % MOD * ifact[n-k] % MOD;
}

void solve() {
    int n; cin >> n;
    vector<int> a(n+1);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    
    int x = find(a.begin()+1, a.end(), 1) - a.begin();
    int y = find(a.begin()+1, a.end(), n) - a.begin();
    
    // 根据x,y位置分割并计算方案数...
    ll result = 1;
    // 组合计算...
    cout << result << "\n";
}

E. 区间约束满足

处理区间包含关系和数值约束的动态规划问题。

去除被包含区间后，通过状态压缩DP记录约束满足情况。

#include<bits/stdc++.h>
using namespace std;
const int N = 2005, INF = 1e9;

void solve() {
    int n, m; cin >> n >> m;
    vector<int> count(n+1, 0);
    for(int i = 1, x; i <= n; ++i) 
        cin >> x, ++count[x];
    
    vector<array<int,2>> intervals(m);
    for(int i = 0; i < m; ++i) 
        cin >> intervals[i][0] >> intervals[i][1];
    
    sort(intervals.begin(), intervals.end());
    
    // DP处理区间约束...
    vector<vector<int>> dp(2, vector<int>(N, INF));
    // 状态转移...
    
    for(int i = 1; i <= n; ++i) {
        bool valid = false;
        // 检查位置i是否可行...
        cout << valid;
    }
    cout << "\n";
}

F. 图论2-SAT建模

将网格图问题转化为2-SAT可满足性问题。

通过对角线异或和作为布尔变量，建立约束关系后使用Tarjan算法求解。

#include<bits/stdc++.h>
using namespace std;
const int N = 4.2e6+5;

vector<int> graph[N];
int vid, eid, dfn[N], low[N], stack[N], top, belong[N], scc_cnt, time_stamp;
bool in_stack[N];

void add_edge(int u, int v) {
    graph[u].push_back(v);
}

void tarjan(int u) {
    dfn[u] = low[u] = ++time_stamp;
    stack[++top] = u; in_stack[u] = true;
    
    for(int v : graph[u]) {
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if(in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    
    if(dfn[u] == low[u]) {
        ++scc_cnt;
        int v;
        do {
            v = stack[top--];
            in_stack[v] = false;
            belong[v] = scc_cnt;
        } while(v != u);
    }
}

void solve() {
    int n, m; cin >> n >> m;
    vector<vector<char>> grid(n+2, vector<char>(m+2));
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> grid[i][j];
    
    // 构建2-SAT模型...
    for(int i = 1; i <= vid; ++i)
        if(!dfn[i]) tarjan(i);
    
    // 检查解的存在性...
    if(/* 无解条件 */) {
        cout << "NO\n";
        return;
    }
    
    cout << "YES\n";
    // 输出构造方案...
}

G. 最短路径Dijkstra

通过修改操作顺序和Dijkstra算法求解状态转移最短路径。

将三种操作类型统一处理，时间复杂度 O(m log m)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5+5;

bool visited[8][N];
ll dist[8][N];
priority_queue<array<ll,2>, vector<array<ll,2>>, greater<>> pq;

void add_state(int mask, int pos, ll cost) {
    if(cost < dist[mask][pos]) {
        pq.push({dist[mask][pos] = cost, 1LL * mask * N + pos});
    }
}

void solve() {
    int a[3], n, k;
    cin >> a[0] >> a[1] >> a[2] >> n >> k;
    
    for(int mask = 1; mask < 8; ++mask) {
        fill(dist[mask], dist[mask] + n, 1LL << 60);
        fill(visited[mask], visited[mask] + n, false);
    }
    
    for(int i = 0; i < 3; ++i)
        add_state(1<<i, a[i], a[i]);
    
    while(!pq.empty()) {
        auto [cost, state] = pq.top(); pq.pop();
        int mask = state / N, pos = state % N;
        
        if(visited[mask][pos]) continue;
        visited[mask][pos] = true;
        
        add_state(mask, pos*2 % n, cost + k * __builtin_popcount(mask));
        for(int i = 0; i < 3; ++i)
            add_state(mask | (1<<i), (pos + a[i]) % n, cost + a[i]);
    }
    
    cout << dist[7][0] - a[0] - a[1] - a[2] << "\n";
}

H. 排列构造与回文

基于特定约束构造排列，利用回文性质简化计算。

通过递归和特殊排列构造，时间复杂度 O(2^b)。

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> results;

void generate(int n, int k) {
    for(int mask = 0; mask < (1 << (n-1)) && results.size() < 2000; ++mask) {
        vector<int> perm(n);
        int idx = 0;
        
        // 构造排列...
        for(int i = 0; i < n; ++i)
            if(mask >> i & 1) perm[idx++] = i;
        for(int i = n-1; i >= 0; --i)
            if(!(mask >> i & 1)) perm[idx++] = i;
        
        // 验证循环节数量...
        vector<bool> visited(n, false);
        int cycles = 0;
        for(int i = 0; i < n; ++i) {
            if(!visited[i]) {
                ++cycles;
                for(int u = i; !visited[u]; u = perm[u])
                    visited[u] = true;
            }
        }
        
        if(cycles == k) results.push_back(perm);
    }
}

int main() {
    ios::sync_with_stdio(false);
    int n, k; cin >> n >> k;
    
    if(n <= 19) generate(n, k);
    else {
        // 处理大n情况...
        int base = min(n, 19);
        generate(base, k - n + base);
        
        for(auto& perm : results) {
            vector<int> extended(n);
            // 扩展排列...
            swap(perm, extended);
        }
    }
    
    cout << results.size() << "\n";
    for(const auto& perm : results) {
        for(int i = 0; i < n; ++i)
            cout << perm[i] + 1 << " \n"[i == n-1];
    }
    
    return 0;
}