Day 1
分数：100+0+0+5
T2：社交距离S
错误原因：
十年OI一场空，不开longlong见祖宗（自测时开longlong了，但提交时交错代码了。。。）
思路：
因为 N,M \le 1e5，所以时间复杂度最高可以为 O(n log n)，又因为没有两个区间有重合部分或在端点处相交，所以可以将所有区间先排序，该题具有单调性，所以可以 D 的值（我的二分 mid 没开 long long ！）
T3：拖延症小信
错误原因：考试时没时间做啦！！！
思路：
1. 状态定义：
dp[i][j][0]：考虑前i个任务、当前时间为j时，能获得的最大总收益。dp[i][j][1]：对应最大收益下，被选择的任务个数
2.初始化：
- 默认
0
3.边界：
- 遍历每个任务
i（从1到n），并逆序遍历时间j
4.状态转移：
- 情况 1：选择第
i个任务
需要满足时间约束：当前时间j足够容纳任务耗时（j >= node[i].t），且任务结束时刻< 截止时间（j < node[i].d，因为任务从j - node[i].t开始，到j结束）
dp[i][j][0] = dp[i-1][j][0];
dp[i][j][1] = dp[i-1][j][1];
- 情况 2：不选择第 i 个任务
此时，“考虑前i个任务、时间j” 的状态，等同于 “考虑前i-1个任务、时间j” 的状态：
dp[i][j][0] = dp[i-1][j][0];
dp[i][j][1] = dp[i-1][j][1];
5.答案：
- 遍历所有
i（任务数）和j（时间），找到dp[i][j][0]的最大值（即最大总收益ans），以及对应dp[i][j][1]（即选择的任务个数res)
T4：世界树上世界果
错误原因：考试时BFS没写出来，只能骗分了。。。
思路：
- 读入
n-1条边u, v，双向添加到邻接表中，并更新两点的度数（l[u]++, l[v]++） - 初始化队列：遍历所有点，将度数为 1 的特异点标记为已访问（
vis[i]=1），并加入队列q（这些是 BFS 的起点）。 - BFS 扩展：从队列中的特异点出发，逐层扩展邻居。对于每个邻居
now_v，若未被访问过，则标记为已访问（vis[now_v]=1），并记录其到最近特异点的距离（p[now_v] = p[now_u] + 1），然后将now_v入队。 - 遍历所有点，维护两个变量：
k（记录最大距离）、cnt（记录最大距离的点的数量）。 - 若当前点的距离
p[i] == k，则cnt++； - 若
p[i] > k，则更新k = p[i]，并重置cnt = 1（找到更大的距离，重新计数）。 - 最后输出最大距离的点的数量
cnt，以及所有满足p[i] == k的点（按编号从小到大输出）
Day 2
分数：10+25+0+20
T1：子序列
错误原因：怕不加剪枝会TLE，所以加了几个剪枝WA了，结果不加剪枝就AC了
思路：
- 通过排序 查找 “最小值、最大值、中位数” ，再枚举可能的最小 / 最大值对 ，结合二分查找 定位中位数，最终统计最长符合条件的子序列长度。
T2：LDS
错误原因：考试时结论没推出来，写了个dp骗分
思路：
-
题目中排列满足 max(p_i, p_{i+1}) > p_{i+2} ，这保证了不存在长度 \ge 3 的严格下降子序列 。原因如下：假设存在长度为 3 的下降子序列 a > b > c （ a, b, c 位置递增），则中间位置
b需满足 max(a_{b-1}, a_b) > a_{b+1} 。若 a_{b-1}=a`、a_b=b 、a_{b+1}=c ，则 max(a, b)=a > c 成立，但此时会推导出更长的下降序列，与题目条件的约束矛盾。因此，所有子区间的 LDS 长度最多为 2 。 -
所有子区间的 “基础长度”（ LDS 至少为 $1$）
所有子区间的数量为1到n的。每个子区间的 LDS 至少为1，因此这部分是 “基础总和” -
LDS 长度为
2的子区间的 “额外贡献”
对于每一对相邻元素(i, i+1)，若a[i] > a[i+1]（即存在相邻下降对），则所有包含这对元素的子区间的 LDS 长度会从 1 提升到 2，因此每个这样的子区间需额外贡献 1。 -
含这对元素的子区间数量为
i * (n - i)： -
l的取值范围是[1, i]（共i种可能），保证左端点不超过i； -
r的取值范围是[i+1, n]（共n - i种可能），保证右端点不小于i+1 -
总和 = 所有子区间数量 + 相邻下降对的额外贡献总和
T3：涂鸭
错误原因：赛中没做！！！暴力好像可以骗好多分
思路：
- 反向处理的核心逻辑
因为后面的涂色操作会覆盖前面的操作，所以从最后一次操作倒序处理，能优先保留 “最新（后面）的操作” 对格子的影响，跳过 “已被后续操作覆盖” 的行 /或列。 - 若操作是 “涂行”：检查该行 y_i 是否未被后续操作覆盖 （!visy_{y_i}） 。若未被覆盖，则该行的所有 w 个格子会被当前颜色覆盖（因为后续没有更晚的操作覆盖它了）。标记该行为 “已覆盖” （visy_{y_i} = 1），并更新已覆盖行的数量 cnt_y++。
- 涂列同理
- 统计最终颜色（包括初始颜色
0）
所有操作处理完后：
非零颜色：收集所有 ans[color] > 0 的颜色，按升序排序后输出。
初始颜色0：若所有被覆盖的格子数之和 sum 小于总格子数 h \times w，则剩余格子为初始颜色0，数量为 h \times w - sum
T4：小信的奇异背包
错误原因：DP 没想到最优方法，TLE
思路：
1. 状态定义：
dpp[i][j]：考虑前i个物品（物品编号从1到i），总价钱不超过j时，能获得的最大价值。dps[i][j]：考虑后i个物品（物品编号从i到n），总价钱不超过j时，能获得的最大价值
2.初始化：
- 默认
0
3.边界：
- 当总价钱上限
j = 0时，无法选任何物品，价值为0（dpp[i][0] = 0，dps[i][0] = 0）。 - 当物品数量为
0时（前0个或后n+1个），价值为0
4.状态转移：
- 前向
DP（dpp数组）
对第i个物品（价钱x，价值y，限购z），枚举购买次数k（ 0 ≤ k ≤ z，且 k \times x ≤ j ）
dpp[i][j] = max(dpp[i][j], dpp[i - 1][j - k * x] + k * y);
含义：前i 个物品的最优解，是 “不选第i 个物品（继承前i-1 个的解dpp[i-1][j] ）” 与 “选k 个第i 个物品（前i-1 个用j-kx 价钱，加上k 个的价值ky ）” 的最大值
- 后向
DP（dps数组）
对第i个物品（价钱x，价值y，限购z），枚举购买次数k（ 0 ≤ k ≤ z ，且 k\times x ≤ j ）
dps[i][j] = max(dps[i][j], dps[i + 1][j - k * x] + k * y);
含义：后i 个物品的最优解，是 “不选第i 个物品（继承后i+1 个的解dps[i+1][j] ）” 与 “选k 个第i 个物品（后i+1 个用j-kx 价钱，加上k 个的价值ky ）” 的最大值
5.答案：
- 对于每个询问（去掉第
d个物品，总价钱上限e）：整体物品被拆分为 “前 d 个物品”和“后 d+2 个物品”（跳过第d+1个物品，即被去掉的物品）。枚举前半部分用的价钱j（0 ≤ j ≤ e），则后半部分可用价钱为e - j。总价值为 “前d个用j的最大价值（dpp[d][j]）” 加 “后d+2个用e-j的最大价值（dps[d+2][e-j]）”。最终答案为：\max\left \{ dpp_{d,j} + dps_{e +2,d-j} \Big | 0 \le e \le j\right \}
Day 3
分数：100+60+100+8
从Day3开始，DP没错过！
T2：LR String
思路：
- 预处理：记录每个位置的 “最近 L/R 位置”
定义数组 nextl_i 和 nextr_i：
nextl_i：字符串s中位置i及其左侧最近的L的位置。
nextr_i：字符串s中位置i及其左侧最近的R的位置。
预处理逻辑（从右往左遍历s）：
维护变量L和R，记录当前遍历到的最近L和R的位置。
遍历到 s_i 时，若s[i] == 'L'，则更新L = i；若s[i] == 'R'，则更新R = i。
最终nextl[i] = L，nextr[i] = R.
预处理后，可快速查询 “某个位置附近的 L/R 位置”，为后续删除操作的模拟提供支持 - 快速排除 不可能 的情况
对每个查询字符串t，先通过首尾特性快速排除无效情况：
如果s和t长度相同但内容不同 → 直接输出NO。
如果s开头是L，但t开头是R→ 无法生成（s开头的L只能删左侧，无法得到开头为R的 t）。
如果t结尾是L，但s结尾是R→ 无法生成（s结尾的R只能删右侧，无法得到结尾为L的t） - 通过函数
check(s, t)详细检查t是否可由s生成：
指针i遍历t的每个字符，指针j遍历s的位置（模拟删除后剩余的位置）。
对t[i]的每个字符：
若t[i] == 'L'：需在s中从j位置找最近的'L'（通过nextl[j]）。若找不到（nextl[j] == -1），说明无法生成，返回false；否则j跳到nextl[j] + 1（模拟删除该'L'左侧字符后的位置）。
若t[i] == 'R'：需在s中从j位置找最近的'R'（通过nextr[j]）。若找不到（nextr[j] == -1），说明无法生成，返回false；否则j跳到nextr[j] + 1（模拟删除该'R'右侧字符后的位置）。
若 t 的所有字符都能通过上述步骤匹配，则返回true，否则返回false。
T4：回文串
思路：
- 统计与寻找 第
k小的数
用数组b统计每个数的出现次数。
对 b 做前缀和，找到第一个满足b[i] > k-1的数mid， 即序列中第k小的数（因为前缀和表示 “小于等于 i 的数的总个数”，第k小的数会让前缀和首次超过k-1） - 将原序列中小于等于
mid的数存入数组c（这些数是后续构造回文的核心候选，因为mid可通过操作删除，再将c排序 - 双指针匹配回文串
用左右指针l（左端点）和r（右端点）遍历c，模拟回文构造：
情况 1：c[l] == c[r]：
这两个数可作为回文的 “两端”，匹配成功。若l != r，则计数cnt += 2（两个数匹配）；否则cnt += 1（中间数自身匹配）。然后l++,r--，继续匹配内部区间。
情况 2：c[l] != c[r]：
尝试利用 “mid可被删除” 的特性调整：
若c[l] == mid：左指针右移（模拟 “删除左数mid”，通过操作选包含该mid的长区间，删去区间的第k小数mid）。
若c[r] == mid：右指针左移（同理，删除右数mid）。
否则：无法通过操作调整使这两个数匹配，直接输出NO - 若匹配的总数 ·cnt >= k-1·，说明能通过操作（删除多余元素）留下足够的匹配数，从而构造回文，输出
YES；否则输出NO
Day 4
分数：100+90+60+100
T2：序列扩展
错误原因：0是肯定会被凑出来的，所以最后要加入0
思路：
- 枚举所有可能的位运算结果，利用set去重后统计数量
T3：最小分组
错误原因：没有考虑 a[i] > mid 的情况
思路：
- 二分答案：猜测一个 “最大和”
mid，判断是否能将数组划分为 ≤k 个子数组，且每个子数组的和都不超过mid。
贪心验证：模拟 “划分过程”，计算需要多少个子数组才能让所有子数组的和 ≤x，若所需子数组数量 ≤k，则 x 可行
bool check(LL x) {
LL sum = 0, cnt = 1; // sum：当前子数组的和；cnt：已用子数组数量（初始为1，至少有一个子数组）
for (int i = 1; i <= n; ++i) {
if (a[i] > x) return false; // 单个元素就超过x，不可能划分
if (sum + a[i] <= x) {
sum += a[i]; // 能加入当前子数组，累加和
} else {
sum = a[i]; // 不能加入，新起一个子数组
cnt++; // 子数组数量+1
}
}
return cnt <= k; // 所需子数组数量≤k时，x可行
}
Day 5
分数：0+100+100+50
T1：最小值之和
错误原因：十年OI一场空，不开longlong见祖宗
思路：纯暴力！
for (int i = 1; i <= n; i++) {
cin >> b[i];
cnt += min (a[i], b[i]);
}
while (m--) {
char ch;
int x, v;
cin >> ch >> x >> v;
if (ch == 'A') {
cnt -= min (a[x], b[x]);
cnt += min (v, b[x]);
a[x] = v;
} else {
cnt -= min (a[x], b[x]);
cnt += min (v, a[x]);
b[x] = v;
}
cout << cnt << '\n';
}
}
T4：越野大王
错误原因：BFS学得不太好，以为搜索过不了，写了个dp…
思路：
- 正常 BFS 即可，多加一层循环遍历步数，如果走不了了就
break
while (!q.empty()) {
Node now = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int now_cnt = now.cnt;
for (int l = 1; l <= k; l++) {
int now_x = now.x + dx[i] * l;
int now_y = now.y + dy[i] * l;
if (now_x < 1 || now_y < 1 || now_x > n || now_y > m || c[now_x][now_y] == '#') {
break;
}
if (vis[now_x][now_y] == 1) {
continue;
}
if (now_x == ex && now_y == ey) {
cout << now_cnt + 1;
return ;
}
vis[now_x][now_y] = 1;
q.push({now_x, now_y, now_cnt + 1});
}
}
}
}
Day 6
分数：100+100+30+40
T3：疯狂的异或大王
错误原因：题目的锅，样例解释去重了，测试点没去重，都是题目的错！
思路：
- 前缀异或
- 当
c % 2 == 1时，ans ^= sum[r] ^ sum[l - 1] - 当
c % 2 == 0时，ans ^= 0
T4：小信的迷宫
错误原因：想太复杂了，我甚至去记录离该点最近的开关格子去走回头路。。。还有就是考试时小写的o和x写成大写的了
思路：
- 正常BFS即可，记录一下走过开关格子的奇偶性，判断是否能走
o和x
Day 7
分数：0+100+100+20
T1：骑行旅游
错误原因：一开始忘开long long了，提交时把long long补上了，但min函数中的一个常数没开long long，CE了
T4：清羽的小熊猫
错误原因：二阶差分谁想得到啊！
思路：
- “最小天数” 具有单调性，所以考虑 二分
- 每天的投喂区间 [l_i, r_i] 内，投喂量是线性递增的（位置 pos 的投喂量为 pos - l_i + 1 ）。这种 “线性递增的区间和” 可通过两次差分数组 + 两次前缀和快速计算
- 差分数组的构造逻辑（以第 i 天的区间 [l, r] 为例）：
第一次差分标记：
d[l] += 1：区间起点的 “增量标记”。
d[r + 1] -= (r - l + 1 + 1)：区间终点后一位的 “减量标记”。
d[r + 2] += (r - l + 1)：区间终点后两位的 “补偿标记”。
两次前缀和：
第一次前缀和：d[i] += d[i-1]（初步累加差分标记）。
第二次前缀和：d[i] += d[i-1]（最终得到每个位置的累计投喂量）。 check函数
bool check(int x) {
memset(d, 0, sizeof d); // 每次验证前清空差分数组
for (int i = 1; i <= x; ++i) { // 处理前x天的投喂
int l = L[i], r = R[i];
++d[l]; // 区间起点标记
d[r+1] -= r - l + 1 + 1; // 区间终点后一位标记
d[r+2] += r - l + 1; // 区间终点后两位补偿
}
// 第一次前缀和
for (int i = 1; i <= L; ++i) {
d[i] += d[i-1];
}
// 第二次前缀和（得到每个位置的累计投喂量）
for (int i = 1; i <= L; ++i) {
d[i] += d[i-1];
}
int cnt = 0; // 统计≥K的位置数
for (int i = 1; i <= L; ++i) {
cnt += (d[i] >= K);
}
return cnt >= Q; // 判断是否满足目标
}
- 二分
void solve() {
cin >> L >> n >> K >> Q;
for (int i = 1; i <= n; ++i) {
cin >> L[i] >> R[i]; // 读取每天的投喂区间
}
int Left = 0, Right = n + 1; // 二分边界：最少0天，最多n+1天（超过则无解）
while (Left <= Right) {
int mid = (Left + Right) >> 1; // 取中间天数验证
if (check(mid)) { // 前mid天满足条件，尝试更小的天数
Right = mid - 1;
} else { // 不满足，尝试更大的天数
Left = mid + 1;
}
}
// 最终Left是“最小满足条件的天数”，若超过n则无解
if (Left <= n) cout << Left << '\n';
else cout << "-1\n";
}
