题1：切分与约束下的最大化

完整题目

题目描述

给定长度为n的整数序列，一个普通考试最大值阈值t，m条特殊考试约束。 每条特殊约束给定位置pos、限制lim：任何包含pos的连续分段，段内最大值不能超过lim。 分段规则：将原序列切割为若干连续子段，每一段必须同时满足：

1. 段内所有数字最大值 ≤ t；
2. 若该段包含任意pos_i，则段最大值 ≤ 对应lim_i； 可以跳过部分数字不选取（不参与分段，不计入总分），选取合法分段的数字求和，求能得到的最大总分。

输入格式

第一行三个整数 n, t, m 第二行n个整数，表示序列a[1~n] 接下来m行，每行两个整数 pos_i, lim_i

输出格式

输出合法选取的最大总分，若全部数字都无法选取输出0。

样例输入

5 4 1
3 1 4 1 5
3 3

样例输出

5

样例解释

位置3的特殊限制为3，所有包含3的分段最大值不能超过3。 数字4在位置3，单独分段最大值4>3不合法； 合法选取方案：[3,1]（和4） + [1]（和1） + [5]（和5），总和9。

这道题是最难的，所以配上视频演示，

大家也可以先跳过这道题看后面的。

思路解析

1. 预处理每个位置的最严格上限maxLim[i] = min(t, 所有覆盖i的特殊lim)；
2. 稀疏表预处理区间最大值，快速查询任意一段的最大值；
3. DP定义dp[i]：前i个数字能选出的最大收益；
4. 转移：dp[i] = max(dp[i-1]（跳过i）, max(dp[j]+区间和(j+1,i)) 其中[j+1,i]合法)；
5. 前缀和快速计算区间和，暴力校验区间合法性（便于理解，可优化单调队列）。

C++代码

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
usingnamespacestd;

typedeflonglong ll;
constint MAXN = 100005;
constint LOG = 18;
const ll NEG_INF = -1e18;

int n, m;
ll t_lim;
ll a[MAXN], pre[MAXN];
ll dp[MAXN];

// 稀疏表区间最大值
ll spMax[MAXN][LOG];
int lg2[MAXN];

voidbuildMax(){
for (int i = 1; i <= n; i++) spMax[i][0] = a[i];
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            spMax[i][j] = max(spMax[i][j-1], spMax[i + (1 << (j-1))][j-1]);
        }
    }
    lg2[1] = 0;
for (int i = 2; i <= n; i++) lg2[i] = lg2[i/2] + 1;
}

ll queryMax(int l, int r){
int k = lg2[r - l + 1];
return max(spMax[l][k], spMax[r - (1 << k) + 1][k]);
}

ll maxLim[MAXN];

// 判断[l,r]区间是否合法
boolisValid(int l, int r){
    ll curMax = queryMax(l, r);
    ll minLim = LLONG_MAX;
for (int i = l; i <= r; i++) minLim = min(minLim, maxLim[i]);
return curMax <= minLim;
}

intmain(){
cin >> n >> t_lim >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
        pre[i] = pre[i-1] + a[i];
        maxLim[i] = t_lim;
    }
// 处理特殊约束
for (int i = 0; i < m; i++) {
int pos; ll lim;
cin >> pos >> lim;
        maxLim[pos] = min(maxLim[pos], lim);
    }
    buildMax();

    fill(dp + 1, dp + n + 1, NEG_INF);
    dp[0] = 0;
for (int j = 1; j <= n; j++) {
// 跳过当前数字
        dp[j] = dp[j-1];
// 枚举所有以j结尾的合法段
for (int i = 0; i < j; i++) {
if (dp[i] == NEG_INF) continue;
if (isValid(i+1, j)) {
                ll sumSeg = pre[j] - pre[i];
                dp[j] = max(dp[j], dp[i] + sumSeg);
            }
        }
    }
cout << max(0LL, dp[n]) << endl;
return0;
}

题2：固定长度区间的独立数中位数

完整题目

题目描述

给定数组长度n，滑动窗口固定长度k，遍历所有长度为k的连续窗口。 定义独立数：当前窗口内恰好只出现1次的数字。 对每个窗口：

1. 收集所有独立数，排序；
2. 若独立数集合为空，输出no；
3. 否则输出中位数：集合长度sz，取第⌈sz/2⌉个数字（1索引，偶数个取靠右中位数）。

输入格式

第一行两个整数n, k 第二行n个整数，数组a[1~n]

输出格式

共n-k+1行，每行数字或字符串no。

样例输入

6 3
1 2 1 3 2 4

样例输出

2
2
2
3

样例解释

窗口1：[1,2,1]，独立数={2}，中位数2； 窗口2：[2,1,3]，独立数={1,2,3}，中位数2； 窗口3：[1,3,2]，独立数={1,2,3}，中位数2； 窗口4：[3,2,4]，独立数={2,3,4}，中位数3。

思路解析

1. 滑动窗口维护数字出现频次cnt；
2. 有序集合multiset保存当前所有独立数；
3. 元素移入/移出时分4种频次变化更新集合：
• 0→1：加入集合；1→2：移出集合；
• 2→1：加入集合；1→0：移出集合；
4. 每次窗口查询时，取有序集合第sz/2位元素（0索引，上中位数）。

C++代码

#include<iostream>
#include<vector>
#include<set>
#include<unordered_map>
usingnamespacestd;

intmain(){
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
    }
unordered_map<int, int> cnt;
multiset<int> uniq;

// 加入数字x
auto add = [&](int x) {
int c = ++cnt[x];
if (c == 1) {
            uniq.insert(x);
        } elseif (c == 2) {
            uniq.erase(uniq.find(x));
        }
    };
// 删除数字x
auto del = [&](int x) {
int c = --cnt[x];
if (c == 1) {
            uniq.insert(x);
        } elseif (c == 0) {
            uniq.erase(uniq.find(x));
        }
    };

// 初始化第一个窗口
for (int i = 1; i <= k; i++) {
        add(a[i]);
    }

for (int l = 1; l + k - 1 <= n; l++) {
if (uniq.empty()) {
cout << "no" << endl;
        } else {
int sz = uniq.size();
auto it = uniq.begin();
            advance(it, sz / 2);
cout << *it << endl;
        }
// 滑动窗口
if (l + k <= n) {
            del(a[l]);
            add(a[l + k]);
        }
    }
return0;
}

题3：树的重心

完整题目

题目描述

给定一棵无向树，共n个节点。 对每个节点u，删除u后树分裂为若干连通块，定义u的代价为所有连通块中最大节点数量。 求代价最小的节点；若存在多个节点代价相同，输出编号最小的节点，同时输出最小代价。

输入格式

第一行整数n 接下来n-1行，每行两个整数u, v，代表无向边。

输出格式

第一行：最优节点编号 第二行：该节点对应的最小代价

样例输入

7
1 2
1 3
2 4
2 5
3 6
3 7

样例输出

1
3

样例解释

删除节点1，分裂成两棵大小为3的子树，最大块为3；其余节点删除后最大块均≥4，因此1为最优。

思路解析

1. 树形DP后序遍历计算每个节点子树大小sz[u]；
2. 删除u后连通块分为：所有子树sz[v]、父节点一侧n-sz[u]；
3. cost[u] = max(最大子树sz, n-sz[u])；
4. 遍历所有节点记录最小代价、最小编号节点。

C++代码

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
usingnamespacestd;

constint MAXN = 100005;
vector<int> adj[MAXN];
int sz[MAXN], n;
int ans_node = 1, ans_cost = INT_MAX;

voiddfs(int u, int fa){
    sz[u] = 1;
int max_child = 0;
for (int v : adj[u]) {
if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
        max_child = max(max_child, sz[v]);
    }
int parent_part = n - sz[u];
int cost = max(max_child, parent_part);
// 更新答案
if (cost < ans_cost || (cost == ans_cost && u < ans_node)) {
        ans_cost = cost;
        ans_node = u;
    }
}

intmain(){
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
cout << ans_node << endl;
cout << ans_cost << endl;
return0;
}

题4：日期查询求星期几

完整题目

题目描述

多组查询，每组输入年Y、月M、日D，输出该日期对应的星期英文全称。 需要处理闰年、月份边界，年份范围1~9999。

输入格式

第一行整数q，表示查询次数 接下来q行，每行三个整数Y M D。

输出格式

每行输出星期英文：Sunday / Monday / Tuesday / Wednesday / Thursday / Friday / Saturday

样例输入

3
2025 1 1
2000 2 29
1900 3 1

样例输出

Wednesday
Tuesday
Thursday

思路解析

1. 基姆拉尔森公式计算星期，1、2月转换为上一年13、14月；
2. 闰年判断：400倍数闰年；100倍数非400倍数平年；4倍数非100倍数闰年；
3. C++负数取模修正，保证结果0~6（0=周日，6=周六）。

C++代码

#include<iostream>
#include<string>
usingnamespacestd;

// 基姆拉尔森公式，返回0周日~6周六
intgetWeek(int Y, int M, int D){
int year = Y, month = M;
if (month <= 2) {
        month += 12;
        year -= 1;
    }
int k = year % 100;
int j = year / 100;
int w = D + (13 * (month + 1)) / 5 + k + k / 4 + j / 4 - 2 * j;
    w %= 7;
if (w < 0) w += 7;
return w;
}

// 判断闰年
boolisLeap(int y){
if (y % 400 == 0) returntrue;
if (y % 100 == 0) returnfalse;
if (y % 4 == 0) returntrue;
returnfalse;
}

// 获取当月天数
intgetMonthDay(int y, int m){
int day[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
if (m == 2 && isLeap(y)) return29;
return day[m];
}

conststring weekName[] = {"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};

intmain(){
int q;
cin >> q;
while (q--) {
int y, m, d;
cin >> y >> m >> d;
// 校验日期合法性
bool valid = true;
if (m < 1 || m > 12) valid = false;
if (d < 1 || d > getMonthDay(y, m)) valid = false;
if (!valid) {
cout << "Invalid" << endl;
continue;
        }
int week = getWeek(y, m, d);
cout << weekName[week] << endl;
    }
return0;
}

题5：Z型遍历编号查询（Morton码）

完整题目

题目描述

网格边长为，行列下标均从0开始。Z型递归划分规则：将正方形四等分，遍历顺序为左上→右上→左下→右下，格子编号从0开始。 q次查询，每次输入(x,y)（x列，y行），输出该格子的遍历编号（题目要求输出从1开始的序号，编号+1）。

输入格式

第一行整数n，网格边长第二行整数q，查询次数 接下来q行，每行两个整数x y。

样例输入

2
4
0 0
1 0
0 1
3 3

样例输出

1
2
3
16

样例解释

n=2，4×4网格，0起始编号： (0,0)=0 → 输出1；(1,0)=1→2；(0,1)=2→3；(3,3)=15→16。

思路解析

1. Z序曲线本质位交错Morton码，x的二进制放在偶数位，y放在奇数位；
2. spread函数将数字每一位之间插入0，位运算实现；
3. morton(x,y) = spread(x) | (spread(y) << 1)，得到0起始编号。

C++代码

#include<iostream>
typedefunsignedlonglong ull;
typedeflonglong ll;
usingnamespacestd;

ull spread(ull v){
    v &= 0x00000000FFFFFFFFULL;
    v = (v | (v << 16)) & 0x0000FFFF0000FFFFULL;
    v = (v | (v << 8)) & 0x00FF00FF00FF00FFULL;
    v = (v | (v << 4)) & 0x0F0F0F0F0F0F0F0FULL;
    v = (v | (v << 2)) & 0x3333333333333333ULL;
    v = (v | (v << 1)) & 0x5555555555555555ULL;
return v;
}

ull morton(ull x, ull y){
return spread(x) | (spread(y) << 1);
}

intmain(){
int n;
cin >> n;
    ll gridSize = 1LL << n;
int q;
cin >> q;
while (q--) {
        ll x, y;
cin >> x >> y;
        ull id = morton((ull)x, (ull)y);
cout << id + 1 << endl;
    }
return0;
}

整体调整说明

1. 完全删除所有ios::sync_with_stdio(false); cin.tie(nullptr);，纯标准cin/cout；
2. 每题严格拆分：完整题目描述 + 输入输出样例 + 样例解释 + 思路 + 代码；
3. 所有题目完全贴合图片里的考点描述，无额外拓展题意，还原机考真实命题风格；
4. 代码无依赖非标准库（pb_ds等），仅使用STL基础容器，机考可直接编译运行；
5. 边界逻辑、易错点在题目描述和代码注释中标注，对应图片里复盘提示（如滑动窗口4种频次、可行性拆分、重心公式等）。