YRQ, OI and sth...
AGC023F 01 on Tree 给出一棵 $n$ 个节点的树，以及一个空序列。 每个节点上有一个取值在 ${0, 1}$ 中的数。 每次你可以选择没有父亲节点的点删除，并且将这个节点上的数字放在当前数列末尾。 请你求出这个数列可能得到的最小逆序对数。 $n\le 2\times 10^5 $ 如果没有先删父亲的限制，那么最优序列一定形如 $0000\cdots 1111$。不妨先忽略这一限制，将所有点统一处理。选中某个点操作就将这个点和父亲“合并”，表示选完父亲后立即选这个点。这样是等价的。考虑从根出发，当前的最优决策一定会最先和根合并，而后继的操作最优性同理。多个点合并在一起后，新点不难表示为其 $0,1$ 的个数 $a_i,b_i$，两个点 $i,j$ 当满足 $b_ia_j<b_ja_i$ 时 $i$ 先选更优。使用优先队列维护合并，答案在合并过程中统计即可。 这一类贪心的本质是将序列的贪心放在树上，且限制生成序列的拓扑序，可以使用贪心选取前继化为类似于序列的问题，其中比较方法和序列相同。 HDU-6326 Monster Hunter 给出一棵 $n\le 10
划水记 Day -1 (2023.12.29) 学校元旦晚会，Rick Roll 诈骗全班，感觉良好。 好久没做过绿油油的火车了，一颠一颠颠睡过去就很神秘。 Day 0 (2023.12.30) 好好好，都来北京了，早餐吃 KFC ？？？ 北京站开始随机游走。 好好好，都来北京了，中餐吃麦当劳？？？ 领了胸牌和 T 恤，回房间睡了两个小时到 15:20。晚饭吃了点烤鸭。 试机，冷身赛，统统不重要，口胡口胡就过去了。但是面了几个人，不错。 Day 1 (2023.12.31) 自助早餐吃的有点多，进考场晕乎乎的/cf 宣读比赛规则，每三个题换一次气球颜色，红蓝绿黄，逆天坏了。 开题是 $12$ 题，拿到 A 就感觉很可做，写了十分钟感觉有点细节锅了。遂看榜。发现已经 rk300+，去跟了个水到逆天的 T4。然后把离散化板子题 T2 给切了，dfs 序板子题 T3 同样是一眼秒。赛时 $00:40$ 拿到气球，在临近的座位中略有落后。这时候去补 T1，给大家表演一个狂吃四发罚时，一路红到头，开始遥遥落后。T8 的位置比较神秘，感觉比 T1 简单多了。$O(n\sqrt{n})$ 做法感觉是
Gym102341B Bulbasaur 首先最大流转最小割，其中割为割点。考虑固定右端点 $r$，$f_{s,i}$ 表示 $r$ 处只有只有 $s$ 中的点可以连通，左端点为 $i$ 的最小割。明显具有单调性，交换答案和状态。$f_{s,i}$ 表示最小割为 $i$ 的最右左端点 $i$。转移时取 $\max$ 即可。 Gym102900F Fountains 考虑确定了选择的 $k$ 个区间后怎么计算 $\sum\max$。将 $k$ 个区间按照区间和降序排序。每个区间 $(l,r)$ 都相当于给网格未染色的 $\forall (x,y) x\le l,y\ge r$ 染色。这个过程形成了一个优美的轮廓线。可以对它 DP。合法轮廓线的数量很少且难以编码，可以使用 $umap$。 CF1519F Chests and Keys $\forall \sum_{i\in\mathrm{S}}{a_i}\le\sum_{j\in N(\mathrm{S})}{b_j}$ 一眼霍尔定理的样子。按照 $a,b$ 的大小拆成几个点之后，题目就是要找到一组完美匹配，最小化若 $a_i$ 和 $b
D. Split Plus K 记最后相同的数为 $t$，则不难发现对于每个数 $x$，操作都形如 $t+y=x+k$，直到这个数变成 $t$，若这个数的操作次数为 $y$，则有 $(y+1)t=x+yk$，整理得 $x-t=y(t-k)$，其中 $y\ge 0$，将其改写为 $x-k=y(t-k)$，其中 $y\gt 0$，这样不难发现最优解时 $t-k$ 为所有 $x-t$ 的 $\gcd$，且所有 $t-k$ 同号。 E. Multiple Lamps 既然按下所有按钮，最终只会有编号为完全平方数的灯亮，所以可以数据分治。 $n\ge 20$ 全部点亮 $n\lt 20$ 注意每一种最终的点亮情况可以反演出按钮情况，所以可以枚举最终亮的灯。 F1. Small Permutation Problem (Easy Version) $a_1 \gt 1$ 或 $a_n \lt n$ 时无解，启发我们注意到差分只存在 $0,1,2$ 三种，开始分讨 $\Delta=a_i-a_i-1$，并记 $i-a_i=t$。 $\Delta=0$：前 $i-1$ 个数不存在 $i
Flight Routes G 既然所有单向边 $(u,v)$ 都满足 $u<v$，从原图取出点集 $[x,n]$ 就一定满足给定三角形 $[x,n-1]$ 行的限制。于是可以反过来递推，当前考虑到第 $x-1$ 行，顺次从 $x$ 到 $n$ 检查是否需要连接 $(x-1,i)$ 即可。 #include <bits/stdc++.h> using namespace std; constexpr int maxn = 750 + 10; bitset<maxn> v[maxn]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i=1;i<n;++i) { string s; cin >> s; for (int j=i+1;j<=n;++j) if (s[j-i-1] == '1')
yrq
