2026 寒假大学习
Day 1
P11086 [ROI 2019] 机器人高尔夫 (Day 2)
首先考虑朴素 \(\Omicron(nm)\)，
若 \((i,j),(i+1,j),(i+2,j),(i,j+1),(i,j+2),(i+1,j+1)\) 都为空
则 \(g_{i,j} = \min(\max(g_{i+2,j},g_{i+1,j+1}),\max(g_{i,j+2},g_{i+1,j+1}))\)
等价于 \(g_{i,j} = \max(\min(g_{i+2,j},g_{i,j+2}),g_{i+1,j+1})\)
发现仍然不好做，令 \(f_{i,j}\) 为后手先的答案，进一步展开寻找性质
\(g_{i+2,j} = \min(f_{i+3,j},f_{i+2,j+1})\)
\(g_{i,j+2} = \min(f_{i,j+3},f_{i+1,j+2})\)
\(g_{i+1,j} = \min(f_{i+2,j+1},f_{i+1,j+2})\)
则 \(\min(g_{i+2,j},g_{i,j+2}) = \min(f_{i+3,j},f_{i,j+3},g_{i+1,j+1})\)
所以 \(\min(g_{i+2,j},g_{i,j+2}) \le g_{i+1,j+1}\)
即 \(g_{i,j} = g_{i+1,j+1}\)
那么关键点 \(\Omicron(k)\) 个，把这些点的 \(g\) 求出来后，再计数一下非关键点的贡献即可
#include <bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a; i<=b; ++i)
#define pii pair<int,int>
#define fr first
#define sc second
#define pb push_back
typedef long long ll;
const int N = 2e5+10; const ll Mod = 998244353;
int n,m,k;
struct ROLE{
int x,y,v;
} rl[N];
map<pii,ll> dp[2],vis;
map<int,ll> lst,nxt[2];
vector<pii> keyp;
ll ans;
bool inmap(int x,int y){
return x>=1&&x<=n&&y>=1&&y<=m;
}
int main(){
cin >> n >> m >> k;
F(i,1,k) cin>>rl[i].x>>rl[i].y>>rl[i].v;
F(i,1,k){
int x=rl[i].x, y=rl[i].y, v=rl[i].v;
dp[0][{x,y}] = dp[1][{x,y}] = v;
keyp.pb({x,y}), keyp.pb({x-1,y}), keyp.pb({x,y-1}), keyp.pb({x-2,y}), keyp.pb({x,y-2}), keyp.pb({x-1,y-1});
}
sort(keyp.begin(),keyp.end(),greater<pii>());
for (auto elm:keyp){
int x = elm.fr, y = elm.sc;
if (!inmap(x,y) || vis.count({x,y})) continue;
if (!dp[0].count({x,y})){
F(o,0,1){
int a = nxt[o^1][(x+1)-y], b = nxt[o^1][x-(y+1)];
dp[o][{x,y}] = (o?max(a,b):min(a,b));
}
}
F(o,0,1) nxt[o][x-y] = dp[o][{x,y}];
vis[{x,y}] = 1;
}
sort(keyp.begin(),keyp.end());
for (auto elm:keyp){
int x = elm.fr, y = elm.sc;
if (!inmap(x,y)) continue;
ans = (ans + dp[0][{x,y}]*(min(x,y)-lst[x-y])%Mod + Mod)%Mod;
lst[x-y] = min(x,y);
}
cout << ans;
return 0;
}
P3647 [APIO2014] 连珠线
由题目中构造方式，我们可以把两条相邻蓝线分为一组，那么所有的蓝线组都包括三个点，且中间的点都不相同
于是可以树形 DP，设 \(dp_{u,0/1}\) 表示以 \(u\) 为根的子树内，是否存在单条未成组的蓝线的答案，考虑转移
首先考虑没有横跨 \(u\) 的蓝线组，则
若存在横跨 \(u\) 的蓝线组，直接 dp 会 WA，给出 hack: 深度为 3 的满二叉树
这是构造过程中可能使得我们有一个森林，这个森林的所有根不能用蓝线连接，也就是上面所说的“横跨 \(u\) 的蓝线组”，所以在构造过程中一定有一个所有蓝线所连的点的“总根”，dp，时间复杂度 \(\Omicron (n^2)\)
容易发现这个可以换根 dp 优化到 \(\Omicron(n)\)
Day 2
CF1667C Half Queen Cover
答案上界可以定为 \(n-1\)，现在重点考虑答案下界
设当前放了 \(k\) 个不同行列的半皇后，那么会还剩下 \((n-k)^2\) 个格子，把这些格子拼起来可以得到一个 \((n-k) \times (n-k)\) 的正方形，显然需要斜线覆盖这些格子，那么仅当这些格子形成一个 \((n-k) \time (n-k)\) 的正方形时，斜线数最少
则 \(k \ge 2 \times (n-k)-1\)，即 \(k \ge \lceil \frac{2n-1}{3}\rceil\)
若 \(n = 3m+2\)，则 \(k = 2m+1\)，我们把斜线画过去，那么怎么构造都可以满足，其中其中方式是两条 \(k = -\frac{1}{2}\)
若 \(n = 3m\)，则 \(k = 2m\)，按照上面的方法，只用 \(2m-1\) 个半皇后，然后发现有一个角上的格子覆盖不到，直接放一个半皇后即可
若 \(n = 3m+1\)，则 \(k = 2m+1\)，直接用 \(n+1\) 的构造
AT_arc172_d [ARC172D] Distance Ranking
观察到 \(n\) 极小，而点的坐标可以到很大，难以直接做
考虑等于时怎么做，那么显然令 \(p_{i,j} = [i = j]\)
然后我们微调一下，使得满足小于关系，设 \(p_{i,j}\) 的微扰为 \(c_{i,j}\)，远小于 \(1\)
则 \(dis(P_{a_i},P_{b_i})\) 变成一个很长的式子。但是观察到二次项过小，可以忽略，于是式子变成
\(p_{a_i,a_i}\) 和 \(p_{a_j,b_j}\) 可以不用微扰，直接设成 \(10^8\)，而 \(p_{a_i,b_i}\) 和 \(p_{b_i,a_i}\) 其中一个设为 \(0\)，另一个可以按 \(i\) 正序或倒序来排名
Day 3
折半警报器
我们希望在线解决如下形式的问题：
给定长度为 \(n\) 的数组和 \(q\) 次操作，每次操作如下：
- 给数组一个位置加 \(v\)。
- 给定不超过 \(k\) 个位置，要求在数组这些位置的总和超过 \(v\) 的时候输出该操作的编号。
一般 \(k\) 非常小
利用鸽巢原理，我们如果一个报警器可能到达 \(v\)，那么其监视的屋子至少有一个到达 \(\large\frac{v}{k}\)，于是我们利用优先队列等数据结构在每个点上存储一些监视器信息，到达阈值时检查一下
但是这样复杂度仍然不对，我们到达阈值检查完后，可以更新阈值，让 \(v\) 减去现在的总和 \(s\)，那么这样阈值至少变成 \(\large\frac{k-1}{k}\)，时间复杂度就是 \(O(n\log n \log V)\)
Day 4
LCT 相关题目
1
Task
维护一个 \(n\) 个节点的无向图
1.加边
2.删边
3.查询x和y是否连通
允许离线
Sol
1.线段树分治
2.LCT 维护边的删除时间的最大生成树
2
Task
有 \(n\) 个点，任意两点 \((u,v)\) 有条边，边权为 \(gcd(u,v)\)，求最大生成树的边权和。
Sol
发现可以转化为全部是 \(u,v\) 为倍数关系的边，于是枚举每个数的约数，LCT 维护最大生成树
3
Task
\(n\) 个点 \(m\) 条边的无向图，询问保留图中编号在 \([l,r]\) 的边的时候图中的联通块个数，强制在线
Sol
先用 LCT 预处理一下，依次加入每一条边
当前加入第 \(i\) 条边，如果这个边加入之后成环了，就弹出这个环上面编号最小的边 \(x\)，并且记录下 \(b_i = x\)，默认 \(b_i = 0\)
之后就是查询区间中 \(b\) 值小于 \(l\) 的数个数
因为如果 \(b\) 值小于 \(l\)，那这个边与 \([l,r]\) 内边不成环，所以连通块数量 \(-1\)。否则没有贡献
浙公网安备 33010602011771号