摘要: 模拟赛记录 前言 update 2025.10.16 因为上周黄队说要关注模拟赛的排名变化,然后想到我打模拟赛都不总结,没有一个具体的指标能看出我有没有进步。所以就开一篇写。把这周的补了,再早的不管了。目前的格式是使用流水账语言风格,需要改进的地方加粗。 update 2025.11.08 排名改为 阅读全文
posted @ 2025-11-30 13:45 wing_heart 阅读(9) 评论(0) 推荐(0)
摘要: 这个东西写完了吗? 阅读全文
posted @ 2025-11-30 13:43 wing_heart 阅读(36) 评论(0) 推荐(0)
摘要: NOIP 游记 2025.10.31 明天要考 CSP-S 了。 标题来源。 NGOI 晋级 NOI 属于 B 类名额,广义上来讲算省队吧。 我一直在划水,而不是在写题。既然如此,不如把 NOIP 游记开了,再划多一些水吧。 update 2025.11.02 这里似乎是有争议的内容,单开一个随笔写 阅读全文
posted @ 2025-11-30 13:33 wing_heart 阅读(22) 评论(1) 推荐(0)
摘要: NOIP2025 之组题人没有妈妈记 前言 《长文警告》《消极情感警告》 要是有人不希望透露名字等,请告诉我。 这个标题传洛谷不知道能不能过审。 了解我的人应该知道我平常不说这种骂人的话,因为我不习惯说。但是打完这场我怨气很重,所以我真的要骂人了。不知道我之后能不能完全释怀并撤回这句骂人的话。 组题 阅读全文
posted @ 2025-11-29 22:57 wing_heart 阅读(77) 评论(1) 推荐(1)
摘要: 开赛时要做什么? 前言 这篇随笔的性质是个人记录而非公共教学,请酌情参考。 虚拟机配置 项目 操作 备注 系统 开大内存 系统 多分几个 CPU 显示 开大显存 共享文件夹 检查是否开启共享文件夹/剪贴板/拖放 共享文件夹 把共享文件夹改成文件夹 GD-xxxx vscode 配置 项目 操作 备注 阅读全文
posted @ 2025-11-28 10:30 wing_heart 阅读(9) 评论(0) 推荐(0)
摘要: 题意:有$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”深度 。 阅读全文
posted @ 2025-11-24 21:17 wing_heart 阅读(3) 评论(0) 推荐(0)
该文被密码保护。 阅读全文
posted @ 2025-11-21 21:51 wing_heart 阅读(3) 评论(0) 推荐(0)
该文被密码保护。 阅读全文
posted @ 2025-11-18 20:33 wing_heart 阅读(7) 评论(0) 推荐(0)
摘要: 题意:给定一棵$n$个点的树,一条蛇在路径$(h,t)$ 上($h \neq t$),蛇类似火车移动,问蛇能否走到路径$(t,h)$ ,需线性或接近线性做法。思路:合法枢纽(关键点)指存在三条长度大于等于蛇长岔路的点。先证明若直径上无关键点则整棵树无关键点,若蛇能到达一个关键点就能到达任意关键点。先求树的直径,找到直径上关键点$u$ ,若蛇一端能在$u$ 上则有解。以$u$ 为根,若$h,t$ 是祖孙关系蛇可到根;否则求$h,t$ 的LCA ,在变成祖孙关系前LCA不变,蛇来回走向最远叶子,若走到同一位置则无解,直接模拟,总时间复杂度线性 。 阅读全文
posted @ 2025-11-14 22:04 wing_heart 阅读(18) 评论(0) 推荐(0)
摘要: 思路:考虑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)$ 。 阅读全文
posted @ 2025-11-13 22:10 wing_heart 阅读(12) 评论(0) 推荐(2)
摘要: 题意:A和B玩游戏,给定长度为$n$($n \leq 10^5$)的序列,A先手。每轮先手选一切割点将序列分成两份,后手选留其中一份,然后交换先后手,游戏至剩一个数字结束,A希望数字尽可能大,B希望尽可能小,求最终剩下的数字。思路:除A先手外条件公平,猜测留下数字为中位数(偶数长序列认为有两个中位数)。通过给比中位数大的数字赋权值`+1`,其他`-1`,证明无论谁先手都取不到比中位数大的数字。对于偶数长且两中位数不等的情况,给$\geq$较大中位数的数字赋权值`1`,其他`-1`,分析原序列能分成极小权值和为`0`的序列个数$cnt$,$cnt$为奇数时先手输,偶数时先手赢,用`nth_element()`函数平均$O(n)$求解 。 阅读全文
posted @ 2025-11-13 10:39 wing_heart 阅读(6) 评论(0) 推荐(0)
摘要: 题意:每个商品有利润$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)$ 。 阅读全文
posted @ 2025-11-10 16:47 wing_heart 阅读(5) 评论(0) 推荐(0)
摘要: 2025 校运会小记 前言 update 2025.11.09 本来拖到这么久还没有开始写,大概是要咕咕掉了的。但是想到这个运动会还是太有意思了,所以写吧。这篇应该没有照片,因为懒得放,因为放照片是不是得把其他人(以及我自己?)码掉? 前置准备 开幕式 要结合竞赛元素。 那信息可以演啥啊??想出了很 阅读全文
posted @ 2025-11-09 20:20 wing_heart 阅读(40) 评论(3) 推荐(0)
摘要: 无。 阅读全文
posted @ 2025-11-03 19:53 wing_heart 阅读(41) 评论(0) 推荐(0)
摘要: 思路:一条路径能被某最小生成树覆盖,意味着路径边必选,在此情况下求最小生成树花费应等于无限制时的花费。先有$O(n^3 \alpha)$暴力,即枚举点对做最小生成树;$O(n^2 \log)$暴力则预处理各边权$w$下仅考虑$ 阅读全文
posted @ 2025-10-30 09:13 wing_heart 阅读(10) 评论(0) 推荐(1)