wing_heart(:

摘要： 模拟赛记录 前言 update 2025.10.16 因为上周黄队说要关注模拟赛的排名变化，然后想到我打模拟赛都不总结，没有一个具体的指标能看出我有没有进步。所以就开一篇写。把这周的补了，再早的不管了。目前的格式是使用流水账语言风格，需要改进的地方加粗。 update 2025.11.08 排名改为 阅读全文

摘要： 这个东西写完了吗？ 阅读全文

摘要： NOIP 游记 2025.10.31 明天要考 CSP-S 了。 标题来源。 NGOI 晋级 NOI 属于 B 类名额，广义上来讲算省队吧。 我一直在划水，而不是在写题。既然如此，不如把 NOIP 游记开了，再划多一些水吧。 update 2025.11.02 这里似乎是有争议的内容，单开一个随笔写 阅读全文

摘要： NOIP2025 之组题人没有妈妈记 前言 《长文警告》《消极情感警告》 要是有人不希望透露名字等，请告诉我。 这个标题传洛谷不知道能不能过审。 了解我的人应该知道我平常不说这种骂人的话，因为我不习惯说。但是打完这场我怨气很重，所以我真的要骂人了。不知道我之后能不能完全释怀并撤回这句骂人的话。 组题 阅读全文

摘要： 开赛时要做什么？ 前言 这篇随笔的性质是个人记录而非公共教学，请酌情参考。 虚拟机配置 项目 操作 备注 系统 开大内存 系统 多分几个 CPU 显示 开大显存 共享文件夹 检查是否开启共享文件夹/剪贴板/拖放 共享文件夹 把共享文件夹改成文件夹 GD-xxxx vscode 配置 项目 操作 备注 阅读全文

摘要： 题意：有$n$个点（$n \leq 3×10^5$），点颜色$a_i \in \{0,1\}$ ，每个点$u$可通过操作`L`跳到$l_u$ 、操作`R`跳到$r_u$ 。$q$次询问（$q \leq 3×10^5$），每次给出两人初始点$x,y$ ，求两人选同类型操作，至少跳几次所在点颜色不同，无解输出`-1`。思路：$n^2$做法是对无序数对$(x,y)$状态建图跑最短路。正解是将每个点走不同次数形成类似完美二叉树结构，通过找最小$k$使$x,y$二叉树第$k$层有不同点求解。无法显式建二叉树，就按二叉树分层分裂集合，用启发式枚举除最大集合外的其他集合维护集合分裂，时间复杂度$O(n \log n)$，查询时求$x,y$类似“lca”深度 。 阅读全文

该文被密码保护。 阅读全文

该文被密码保护。 阅读全文

摘要： 题意：给定一棵$n$个点的树，一条蛇在路径$(h,t)$ 上（$h \neq t$），蛇类似火车移动，问蛇能否走到路径$(t,h)$ ，需线性或接近线性做法。思路：合法枢纽（关键点）指存在三条长度大于等于蛇长岔路的点。先证明若直径上无关键点则整棵树无关键点，若蛇能到达一个关键点就能到达任意关键点。先求树的直径，找到直径上关键点$u$ ，若蛇一端能在$u$ 上则有解。以$u$ 为根，若$h,t$ 是祖孙关系蛇可到根；否则求$h,t$ 的LCA ，在变成祖孙关系前LCA不变，蛇来回走向最远叶子，若走到同一位置则无解，直接模拟，总时间复杂度线性 。 阅读全文

摘要： 思路：考虑DP，对于每一位存在关键操作，操作后该位不再变化，之前该位状态无关紧要。设$f_S$表示集合$S$的位未固定，不在$S$的位已固定且与$y$相同的最小花费。预处理$g_S$，即集合$S$上与$y$相同的AND操作的最小费用，通过高位前缀和求解（因取$\min$无需容斥），OR操作同理。转移时枚举$S$补集的子集$T$，对AND操作，要求$y$在$T$位置均为$0$，可选AND操作在$T$位置为$0$且在$S$中为$1$的位置为$1$；OR操作类似。时间复杂度$O(2^k k + 3^k)$ 。 阅读全文

摘要： 题意：A和B玩游戏，给定长度为$n$（$n \leq 10^5$）的序列，A先手。每轮先手选一切割点将序列分成两份，后手选留其中一份，然后交换先后手，游戏至剩一个数字结束，A希望数字尽可能大，B希望尽可能小，求最终剩下的数字。思路：除A先手外条件公平，猜测留下数字为中位数（偶数长序列认为有两个中位数）。通过给比中位数大的数字赋权值`+1`，其他`-1`，证明无论谁先手都取不到比中位数大的数字。对于偶数长且两中位数不等的情况，给$\geq$较大中位数的数字赋权值`1`，其他`-1`，分析原序列能分成极小权值和为`0`的序列个数$cnt$，$cnt$为奇数时先手输，偶数时先手赢，用`nth_element()`函数平均$O(n)$求解 。 阅读全文

摘要： 题意：每个商品有利润$w$和数量$c$，有三种操作：1. 对$[l,r]$商品的$w$加上$x$；2. 将商品$x$的$c$改成$c'$；3.查询$w×c$的最大值，$n,m \leq 10^5$，$|w|,|x|\leq 10^6$，$c,c'\leq 10^6$。思路：若无操作2，商品权值可表示为$wc + k×c$，需找到过点$(c,wc)$斜率为$k$直线的最大截距，对所有点维护上凸壳，通过二分找到与凸壳相切点得最大截距。因操作一是区间加，采用分块，对整块打标记，不满一块重构。操作2在凸壳上删点加点，操作三在每个块二分取最大值，可使用set或暴力维护凸壳，总时间复杂度约$O(n\sqrt n)$ 。 阅读全文

摘要： 2025 校运会小记 前言 update 2025.11.09 本来拖到这么久还没有开始写，大概是要咕咕掉了的。但是想到这个运动会还是太有意思了，所以写吧。这篇应该没有照片，因为懒得放，因为放照片是不是得把其他人（以及我自己？）码掉？ 前置准备 开幕式 要结合竞赛元素。 那信息可以演啥啊？？想出了很 阅读全文

摘要： 无。 阅读全文

摘要： 思路：一条路径能被某最小生成树覆盖，意味着路径边必选，在此情况下求最小生成树花费应等于无限制时的花费。先有$O(n^3 \alpha)$暴力，即枚举点对做最小生成树；$O(n^2 \log)$暴力则预处理各边权$w$下仅考虑$ 阅读全文