主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
CQYC 排位赛
最后更新于 2025-06-15 15:23:26
作者
Laisira
分类
个人记录
复制 Markdown
查看原文
更新内容
## 置顶内容 这个人很菜，快嘲讽他。  ### 我不曾忘记 ***【迪娜泽黛】*** 我的破木箱 装满枯萎的花 放不下 光与壤 和新鲜的愿望 如果能飞翔 去高高的地方 撒一张 梦的网 收集爱的回响 ***【纳西妲】*** 你也在听吗 落单的孩子啊 别害怕 别害怕 黑夜不会太长 悬崖上的花 让我为你摘下 数一瓣 落一瓣 就少一朵忧伤 ***【迪娜泽黛】*** 绿草和砂砾没有嘴巴 一定不会说谎话 他们让风提醒我有道光 落在我的肩膀 ***【兰那罗们】*** 是你吗 在回家的路上 洒满月光点亮花蕊 是你吧 弹奏古老和弦 赶走梦魇 伴我入睡 是你吗 把头顶的雨水 编织成蓝色的屋檐 约好啦 等我们都长大 再次遇见 要比现在更美 ***【纳西妲】*** 一千个噩梦 换一千个小偷 够不够 够不够 偷走你的难过 遇见那一刻 就倒置了沙漏 不必说 要铭刻 天长还是地久 ***【迪娜泽黛】*** 都说长大后会忘记童话 清醒后会忘记梦 可尤其是下过雨的午后 会想和你重逢 ***【兰那罗们】*** 是你吗 在回家的路上 洒满月光点亮花蕊 是你吧 弹奏古老和弦 赶走梦魇 伴我入睡 是你吗 把头顶的雨水 编织成蓝色的屋檐 约好啦 等我们都长大 再次冒险 追寻梦的蔓延 ***【大慈树王/兰那罗们和声】*** 谁越过一片花海 谁切切朝我走来 谁依然记得我未完成的心愿 ***【大慈树王】*** 是你吗 头戴着花环 衔着最纯净的枝丫 ***【兰那罗们/大慈树王和声】*** 是你吧 撕下一缕霓裳 借我照亮 盒中之花 是你吗 在某一天默默消失在春天的遥望 可我呀 记得你的所有 我不会忘 我不会忘 是你吗 在回家的路上 洒满月光点亮花蕊 是你吧 弹奏古老和弦 赶走梦魇 伴我入睡 ## [算法大纲](https://www.noi.cn/upload/resources/file/2023/03/15/1fa58eac9c412e01ce3c89c761058a43.pdf) - 二分图的判定 √ - 线段树： P4315√ - 平衡树： P1110 P3224 - 字典树（Trie 树） P4098 - 强连通分量 - 割点、割边 - 笛卡尔树 P9607 - 最（次）小生成树 - 单源最（次）短路 - 有向无环图的拓扑排序 - 状态压缩动态规划 - 动态规划的常用优化：P10894 ## Others ### 失配树 #### 一个经典的问题 给定字符串 $s$ 求前缀 $p,q$ 的最大公共 $boder$。 定义对于 $t$ 的 $boder$ 集合为所有 $i,pre_i = suf_i$。 #### 思路 考虑求一个串 $s$ 的所有 $boder$，就是 $s_{1,nxt{|s|}}$ 和 $s_{|s|-nxt_{|s|}+1,|s|}$。由于他们相等，就又可以继续只用前面的那个知道后面的，一直递推就可以找出所有 $boder$ 了。由于前缀长度有单调性，所以两个串找最大公共 $boder$ 就相当于在数上求 $LCA$，$x$ 的父亲就是 $nxt_x$。 **这玩意就是失配树** ### BSGS $$ a^{i} = K \mod p $$ 我们设常量 $m$，有： $$ a^{s\times m-t} = K \mod p\ (0<t<m) $$ 而 $s\times m-t$ 属于所有非负整数，等价于 $i$。 则：$a^{s\times m} = K\times a^t\mod p$ 枚举 $t$，用 map / hash 存右侧可能值，再枚举左侧比较。 时间复杂度 $O(\max(m,\frac{p}{m})\times l)$，$l$ 取决于存储算法，当 $m = \sqrt p$ 时最小。 ---- ### 根号分治 暴力有两种，时间和空间分别超的 / 循环节长度和次数，然后我们把他们糅杂在一起加入 `人类智慧催化剂` 生成踩爆正解的传奇根号分治！ ### Hall 定理 **定理** 在二分图中，若集合 $A$ 的任意子集元素个数总是大于所对应的集合 $B$ 中的子集元素个数，则该集合 $A$ 一定可以被完全匹配。 **用法** 对于一种特殊的二分图，有 $A$ 中元素对应 $B$ 中一个区间的元素，可以利用 Hall 定理判断完全匹配。 具体的，枚举 $B$ 中连续被覆盖的区间，看有多少 $A$ 中的元素对应这个区间。再具体的，对 $A$ 中元素在左端的小于等于 $L$ 的元素，树状数组维护右端点大于等于 $R$ 的元素，时间复杂度 $O(n\log n)$。 对上面选连续覆盖区间证明： 对于区间 $[l_i,r_i],[l_j,r_j]\ (r_i<l_j)$ 当 $i,j$ 都合法时合并区间一定合法，当合并区间不合法时，总存在一个区间不合法。 ---- ### 最短路树 这玩意应该是太简单了，都没找到哪有。。。 **定义** 使得以 $i$ 为根到 $j$ 原图的最短路与所生成树的链相等。 **实现** 挺简单的应该，在队列中记录他时被谁更新的，对于 Dijstra 队列松弛元素时，就可以记录下他父亲，然后最后建树。 **证明** 显然。 ---- ### 平衡树 Ps：看到大佬的函数就想写一下（以前我的太劣质了）。 **第 $k$ 小** ```cpp int find(int x,int k) { if(!x)return inf; if(k <= sz[lson[x]])return find(lson[x],k); if(k <= sz[lson[x]]+cnt[x])return val[x]; return find(rson[x],k-sz[lson[x]]-cnt[x]); } ``` **$k$ 的排名** ```cpp int find_rank(int x,int k) { if(!x)return -1; if(val[x] == k)return sz[lson[x]]+1; if(k <= val[lson[x]])return find_rank(lson[x],k); return find_rank(rson[x],k)+sz[lson[x]]+cnt[x]; } ``` **前驱（严格小于）** ```cpp int pre(int s,int x) { int cur = rt[s],lst; while(cur) { if(val[cur] < x)lst = cur,cur = rson[cur]; else cur = lson[cur]; } return lst; } ``` **后继（严格大于）** ```cpp int suf(int s,int x) { int cur = rt[s],lst; while(cur) { if(val[cur] > x)lst = cur,cur = lson[cur]; else cur = rson[cur]; } return lst; } ``` ### 矩阵 $f_{i,j} = \sum_{k=1}^{n} a_{i,k}\times b_{k,j}$ 新矩阵行数是 $a$ 的行数，列数是 $b$ 的列数，$a$ 的列数要等于 $b$ 的行数。 矩阵主要靠他的意义来设计。 ### ! 考试注意事项 ! 1. 有些东西不是你会做你就会做的，签题时间不得超过 $1.5\ h$，其他时间不得超过 $0.7\ h$，暴力至上！ 2. $long\ long$ 不管咋的就都开上，模数用 $const$，空间开 $2$ 倍！ 3. 你以为的时间复杂度和真时间复杂度永远不相等！你以为的歪解也有可能是正解！ 4. 看到向下取整想到模数。 5. $dp$ 重要的是正确不是去掉错误。 6. 位运算考虑二进制。 7. 字符串想到每种字符处理。 8. 因数问题考虑质因数分解，你线性筛只用筛根号个数。 9. 图上问题尽量转换到树上，否则大概率是网络流。 10. 博弈论的 SG 相当于单人赢单局的方案，不必考虑全局。 11. 重复覆盖问题考虑维护前一个覆盖的。 12. 正难则反。 13. 环的处理建议分段或双指针。 14. **开题顺序** 小中型数据结构板题 < T1 < 暴力好写思路难 < 思路简单难写。 ## 赛事 ### 24/09/06 怎么说呢，挺??的一次。 #### T1 >多重背包，容量数量巨大的 van 意。 前半贪心维护，后半 dp，马蜂很Ⅹ。 #### T2 >$n$ 个点的树，把边定向，定义权值为图上点对 $(x,y)$ 满足存在从 $x$ 到 $y$ 的路径。 > >给出 $n$ 问所有方案总权值，取模 $p$。 在 prufer 中考虑缩点数量为 $x$、度数 $d$。 $$ \sum_{x = 1}^{n} 2^{n-x} A_{n}^{x} \sum_{d=1}^{n-x} \begin{pmatrix} n-x-1\\ d-1\\ \end{pmatrix} x^{d}(n-x)^{n-x-d} $$ 然后似乎第二个 $\sum$ 提一个 $n-x$ 出来，就是二项式定理化简一下等于 $x\times n^{n-x-1}$。 记得卡常。 #### T3 >给定数组 ${a}$ 和 ${b}$，求三个不同的数 $x,y,z\ (0<x,y,z\leq n)$，使得 $a_x+a_y+a_z+\max(b_x,b_y)+\max(b_y,b_z)$ 最小。 签题 ~~（场上打挂了）~~。 要求的就是 $a_x+a_y+a_z+b_x+b_y+b_z-\min(b_x,b_y,b_z)$，于是将 $b$ 从大到小排序，维护前缀最小 $a_i+b_i$ 和后缀最小 $a_i$，枚举一遍即可。 #### T4 >一棵树，在每个点按给定顺序到下一个点。 > >问走 $k$ 步后到达的位置。 [??黑题](https://www.luogu.com.cn/problem/P7830) 考虑当所有节点上步走的是父亲时，所遍历的顺序就是欧拉序。 对于节点 $x$ 和他的父亲 $y$，从 $y$ 开始向 $x$ 的路径，要么是走第 $[1,k_{x}]$，要么是走 $(k_{x},sz]\cup[k_{x},k_{x}]$，$k_{x}$ 是 $x$ 对于 $y$ 的优先级。 然后就不会了。 update 24/09/11：悟了，一个指向父亲的点永远指向父亲，一个不指向父亲的点遍历至多一次后一定指向父亲。 先搜一遍全部指向父亲，然后剩下的就是欧拉序了。 ### 24/09/12 鹅妈妈。。。csp-s 跟 noip 考一样的是吧。。。 #### T1 唐题，简单小 dp，不说了。 #### T2 >$n$ 个人分队，当 $i$ 所在的组人数大于等于 $a_i$ 时，产生 $1$ 的贡献。 > >每次询问求分 $k$ 组时最大贡献。 怎么说呢，策略考场上倒是想出来了。 显然的排序后将 $[l,r]$ 的数分在一组一定不劣，那么每一组可以产生的贡献是 $[l,r]$ 的区间。 然后直接 dp。 设 $f_i$ 为产生贡献的是 $[1,i]$ 的最多分组。 转移： $$ f_i = f_{j}+1-\max(i-j,a_i) $$ 即把后缀 $[j,i]$ 全部放进去，再拉一堆凑数的。 然后发现有时候不合法，但是不合法的情况显然不优，然后有跟没有一样。 #### T3 #### T4 >每次操作区间加高 $i$ 颜色为 $j$ 的柱子，或问 $(x,y)$ 的颜色。 ~~数据太水了以至于整体二分过了。~~ ### 24/09/15 #### T1 #### T2 >给定一棵 $n$ 个点的树，点 $i$ 的权值为 $w_i$，对于树上两点 $i,j$，定义 $f(i,j),g(i,j)$ 分别为 $i$ 到 $j$ 简单路径上的按位与和按位或。 > >求 > $$ \sum _{i=1}^{n}\sum_{j=1}^{n}f(i,j)^{g(i,j)}\mod 111121 $$ > >特殊的： >- 在本题中，我们规定 $0^0=0$。 >- 树叶子不超过 100。 树形 dp ~~（虽然跟普通 dfs 没区别）~~。 记集合 $S_i$ 表示经过 $i$ 三元组 $(f,g,c)$ 的集合，定义三元组 $(f,g,c)$ 表示存在 $c$ 个子树内 $x$ 使得 $f(i,x) = f,g(i,x) = g$。 然后暴力转移就行了。 时间复杂度 $O(n\ k\ \log^2n)$（其中一个 $\log n$ 是快速幂，可以卡掉，$k$ 为叶节点数）。 #### T3 >给定序列 $T$ 和 $H$ 以及 $K,D$，到景点 $i$ 高兴值增加 $H_i$，从 $i$ 出发，可以达到 $[i+1,i+T_i]$，从 $i$ 到 $j$ 高兴值减少 $\lfloor \frac{j-i}{K} \rfloor \times D$ 显然的 $n^2$ dp，尝试优化。 Ps：考场上想到的是用线段树维护最值，枚举 $\lfloor i-j/k\rfloor$，复杂度 $\frac{n^2}{k}\times \log n$，结果过了 $5\times 10^4$。 可以发现： $$ \lfloor \frac{j-i}{K} \rfloor = \frac{j-i-((j-i)\mod K)}{K} \\ \\ = \begin{cases} \frac{(j-j\mod K)-(i-i\mod K)}{K}\ (j\mod K\ge i\mod K) \\ \frac{(j-j\mod K)-(i-i\mod K)}{K}-1\ (j\mod K< i\mod K) \end{cases} $$ 然后贡献拆开，两个线段树随便搞。 #### T4 >一个序列 $a$，进行若干次操作，每次操作： >- 选择一个数 $i$ 将 $a_i$ 赋值为 $\sum_{i=1}^na_i$。 > >最小化 $a$ 的字典序。 简单题。 操作一次后 $sum = -a_i$，即下一次赋的值就是 $a_i$，即相当于在 $a$ 和 $-sum$ 中选 $n$ 个数使得字典序最小，排个序就行了。 ### 24/09/16 $Rank\ 1$ 祭 ~~（一定是考试时想 `时光女孩` 的缘故）~~。 #### T1 >你有一个长度为 $n$ 的链，编号为 $i(1\le i<n)$ 的边连接着节点 $i$ 与 $i+1$。每个节点上有一个整数 $a_i$。你需要做以下操作 $n-1$ 次： > >- 选择一条还未被断开的边，设其连接了点 $i$ 与 $i+1$，将其断开。 >- 断边后，对于所有与 $i$ 联通的点 $j$，找到 $a_j$ 的最大值，设其为 $x$。对于所有与 $i+1$ 联通的点 $k$，找到 $a_k$ 的最大值，设其为 $y$。 >- 此次操作的代价为 $\lvert x-y\rvert$。 > >求做完 $n-1$ 次操作的代价之和的最小值。 显然的贪心典题。 我们用一边大的减另一边大的，也就是说如果我们不尽快将最大的断掉，他会一直算贡献，且贡献大于断掉 Ta 的。 直接单调栈维护每个位置左右小等于于他的最大值就行了。 #### T2 >我们定义两个字符串是同构的，当且仅当一个字符串可以通过重排变成另一个字符串。 > >现在，你会获得一个大小为 $n$ 的字符串集合，你的任务是求出有多少个子集内，恰有 $k$ 对同构字符串。 简单背包，没技术含量，没做起的该滚了。 #### T3 >给一个串 $S$，取一个子串 $T$，然后给 26 个字符排列得一个 $P$ 数组。令 $K_i = P_{T_i-97}$。 > >最大化 $K$。 考试时的思路： ``` t3 甚么史题 他妈的直接贪心啊 对于后面的 p 取值在 T 固定时固定 重点是求 T 甚么他妈的史题 首先 T1 和第一个相同数 Tl 最近 这样 [1,l] 数不同且唯一 试确定 Tl+1 - 若 Tl+1 != Tp p=[1,l] 则有 Tl+1 < Tp - 若 Tl+1 = Tp 综上，我们可以将一个串变成 01 序 与前面相同的记作 1 否则为零 因为答案一定是一个后缀 于是支持修改 不对不对的 形象点说 对从起点开始降序标号 允许继承前面相同的数的编号 问最大后缀 n^2 的挺简单吧 枚举起点往后搜 维护最大值 优化一下 发现他值域只有 [1,26] 会不会有用 好像不是那么有用 那考虑 O(1) 转移 我们是可以 O(1) 知道后一个的状态 但怎么维护最大状态 反向枚举 维护哈希值 二分相同位置 但我们如何快速知道我们现在的之前哈希值 将 i 放入时 same[i] = newmax 不对，如果有相同的那我们值域不会变 第次一次调用时后的数全部加一 第次一次调用时前的数全部减一 欸，这好像就会影响我们的字典序啊 当前面 i - ci 的数都不相同时 我们这样做显然不劣 那相同时一定劣 但好像也没有太大的关系 艹，你特么数值范围大一点还可以试一下在 i - ci = j - cj 时更新答案 不做了，摆烂 部分分怎么拿啊 只有 a 的显然输出全部 a b 的显然要么 a 开头 要么 b 开头 值分别不变 对于每一个求解 哈希判大小 ``` ~~嘴里飘香~~ 对于字符构造 26 个 01 串 $S_i$，并记录原串中 $i$ 位后第 $j$ 种元素为 $f_{i,j}$。 对于 26 个 01 串我们可以将内部的最优后缀搞出来，在外部比较。 具体的，对于分别以 $a,b$ 开头的，组内优胜分别是 $o,p$ 位，枚举 $k$，比较 $S_{f_{o,k}}$ 和 $S_{f_{p,k}}$，用哈希二分。 时间复杂度 $O(n\ \log n)$。 #### T4 >你有一个长度为 $n$，由 $AB*$ 组成的字符串。 > >对于由 $AB$ 组成的字符串，有一种操作，每次将相邻两个相同字符替换为另一种字符。 > >记 $f(s)$ 为由 $AB$ 组成的字符串 $s$ 在所有操作方案中，如果最后只剩下一个字符，将这个字符加入集合 $V$，这个集合即为 $f(s)$。而这个集合有 $\varnothing，\{a\}，\{b\}，\{a,b\}$ 四种可能。 > >每个字符有激活与未激活两种状态，初始时所有字符均为激活。你需要处理以下三类操作： > >- $1\ l \ r$：将区间 $[l,r]$ 中所有激活的字符顺次拼接为字符串 $S$，你需要求出所有 $S$ 的非空子串将其中的通配符 $*$ 替换为 $A$ 或 $B$ 得到的所有$P$，$f(P)$ 中每类值的出现次数，即依次输出 $f(P)=\varnothing，f(P)=\{a\}，f(P)=\{b\}，f(P) =\{a,b\}$ 的数量，**答案对 $2^{32}$ 取模**。 形式化的说，你需要对于每个 $V ∈\{\varnothing ,\{a\},\{b\},\{a,b\}\}$ 求出： > $$ \sum_{1\le L\le R\le \lvert S\rvert}\sum_{P\in G(S[L:R])}[f(P)=V] $$ >其中 $S[L:R]$ 是 $S$ 在第 $L$ 个字符到第 $R$ 个字符之间的子串。 $G(T)$ 是将 $T$ 中每一个 $*$ 任意替换为 $A$ 或 $B$ 得到的字符串的集合。 > >- $2\ x\ c$：将第 $x$ 个字符改为 $c$。 > >- $3 \ l \ r$：将区间 $[l,r]$ 内的所有字符的状态反转，即激活改为未激活，未激活改为激活。 知名 noi 大佬 lcrh 睿评：这种史题没有什么营养啊，很典，来恶心人的。 ### 24/09/25 有史以来最惨的一次。 #### t1 >给出 $n,m$ 以及一个长为 $n$ 的字符串 $S$，要求构造一个长为 $m$ 的字符串 $T$，使得 $\sum_{i=1}^mLCP(S,T[i...m])$ 最大，求出这个最大值。 > >其中 $LCP(S,T[i...,m])$ 指 $T$ 从第 $i$ 个位置开始的后缀和 $S$ 串的最长公共前缀的长度。 史题，史题，一坨屎题。 式子改成： $$ \sum_{i=1}^{m} \sum_{j=i}^{m} [\ T[i\ ...\ j]=S[1\ ...\ j-i+1]\ ] $$ 问题成了我们要构造一个 $T$ 使得对于 $S$ 每一个前缀等于 $T$ 子串的数量和最多。 考虑从前往后确认 $T$，记 $dp_{i,j}$ 为 $T_i = j$ 的最大贡献。然后他新增的贡献就是 $S$ 的 fail 树上 #### t2 >无向图删边，询问 $u,v$ 是否边双联通。 边按删除时间排序，最大生成树，然后其他的边加进来时 $[u,\operatorname{LCA(u,v)}]$ 和 $[\operatorname{LCA(u,v)},v]$ 一定变成联通。 用并查集维护一下连通块暴力合并。 #### t3 >有一个逃犯来到了你所在的王国。首领下令抓捕他。 > >王国有 $n$ 个城市，对于任意 $i∈[1,n]$，第 $i$ 个城市和第 $i \mod n+1$ 个城市之间有一条无向道路，重要度均为 $C$。由于这是王国的边境，所以保证 $C≥10^9$。此外，王国内部还有 $m$ 条无向道路，第 $i$ 条连接 $u_i$ 和 $v_i$，重要度为 $w_i$。 > >摧毁一条道路的花费就是这条道路的重要值。定义 $f(s,t)$ 表示最少花费多少去摧毁道路才能使得逃犯无法从 $s$ 走到 $t$。如果无论如何逃犯都能从 $s$ 走到 $t$，则 $f(s,t)=0$。 > >由于首领不知道逃犯在哪，也不知道他要逃向哪里，所以他希望你求出所有可能的情况的花费和，即 $\sum_{s=1}^n\sum_{t=1}^nf(s,t)$。答案对 $10^9+7$ 取模。 知名 noi 大佬 lcrh 睿评：这道题你们根本不可做，讲评了能做个 60 分就不错了。 ~~所以说都知道我们不可以做你还放在模拟赛上？~~ #### t4 >两个傻逼在树上追逐，一些边只有某个人可以过，另一些边两个都可以过，无法走下一步的输，问局面。 傻逼签到题。 在所有边双方都可以过下，如果双方距离为偶数，先手胜，否则后手胜。 特别的，如果一个人在输状态下，如果可以在对面之前走到一个点 $u$，且 $u$ 存在一条对面无法通过的边且可以在边另一头无限走，就平局了。 细节贼多，改了半天还没 A。 ### 24/10/06 ### 24/10/07 #### t1 >YYX 是个无忧无虑的女孩子。 > >这天，YYX 在空地上发现了一本魔法书，书上记载了 $n$ 条魔咒，其中第 $i$ 条魔咒需要花费 $a_i$ 点蓝。作为一名见习魔法师，YYX 初始拥有 $m$ 点蓝以及 $k$ 块魔法饼干。 > >YYX 充满好奇心，她在得到魔法书的那一刻就想要把魔法书里的每一条魔咒都至少使用一次。但是她自己的蓝太少了，而补蓝需要花钱。具体的，YYX 可以做下列三种操作： > >- 选择一条未使用过的魔咒，假设选择的魔咒是第 $i$ 条。如果 YYX 持有的蓝大于等于 $a_i$ 点，那么她持有的蓝减去 $a_i$ 点，并记录第 $i$ 条魔咒为使用过。 >- 如果还有魔法饼干，YYX 可以吃掉一个魔法饼干并选择一条魔咒，假设选择的魔咒是第 $i$ 条。如果此时 $a_i\ge 1$，那么令 $a_i$ 减一。 >- 加入现在 YYX 持有 $a$ 点蓝，且 $a<m$，那么 YYX 可以花费 $m-a$ 块钱来使自己持有的蓝加一。也就是说，假如 $m=4,a=1$，那么 YYX 把蓝补满的花费为 $3+2+1=6$。 > >聪明的你一定知道 YYX 把每条魔咒都使用过一边所需最少的钱了，请把这个数目告诉她吧。注意，你不需要最小化饼干的使用数，也不需要关心最后 YYX 持有多少蓝。 签题，场上打挂了。 先补再加一定不劣于先加再补。把贡献拆开记录每种加法的数量 $cnt_j$，则 $$\sum_{j=1}^{a_i}cnt_j=cnt_j+1$$。 每次吃饼干相当于把最高的 $j$ 使得 $cnt_j = cnt_j-1$，暴力枚举即可。 #### t2 >对于每个 $i$ 可以覆盖 $l_i$ 到 $r_i$，问所有连续的一段覆盖数的期望。 记录 $pre_{i,j}$ 是第 $i$ 个人 之前最后一个做出 $j$ 的，那他没有重复的贡献是 $$\sum_{j=l_i}^{r_i} (i-pre_{i,j})\times (n-i+1)$$ 也就等于 $$(n-i+1)\times(i\times(r_i-l_i+1)-\sum_{j=l_i}^{r_i}pre_{i,j})$$ 扫描线维护一下就行了。 #### t3 #### t4 ### 24/10/10 #### t1 >YYX 是个无忧无虑的女孩子。 > >这天，YYX 在空地上发现了一个长度为 $n$ 的正整数数组，她觉得这个数组很有意思！所以她找到了 $\text{Dr. Wu}$，希望和他在这个数组上做游戏。 > >具体的，YYX 和 $\text{Dr. Wu}$ 事先指定了一个正整数 $x$，并在数组上轮流操作，YYX先手：当一个玩家操作时，她将选择数组中一个大于 $0$ 的元素 $a_i$ 并选择一个 $[1,\min(a_i,x)]∩\mathbb{Z}$ 中的数 $j$，令 $a_i$ 减去 $j$，不能操作者负。 > >现在，YYX 找到了你，希望你对于每个 $1\le x\le n$，求出若两个人都使用最优策略，是先手必胜还是后手必胜。 博弈论题，SG 函数还是比较好想的： 把最后 $x$ 个单独分一组，剩下的一定可以构造 $x+1$ 一段的情况，把对方从一组的最后一个开始是最优的。 即 $a_i-x \mod (x+1) = 1$ 时先手必败，否则必胜。 即 $a_i\mod (x+1) = 0$ 时同理。 然后就是求： $$\sum_{x=1}^{n}ans_x=[\oplus_{i=1}^{n}a_i\mod x+1 >0]$$ 然后不会优化了。 #### t2 签题没含金量。 #### t3 >眼镜店里共有 $n$ 种不同度数的眼镜，分别被标号为 $1,2,...,n$，每种眼镜都恰好有 $k$ 副。因为配与自己近视度数相差太大的眼镜会对眼睛造成伤害，所以规定若一个人的近视度数为 $x$，只能配标号在 $[x,x+d]$ 区间内的眼镜。 > >因为眼镜店生意非常火热，所以每个时刻都有人进出，你需要在每个时刻结束时判断眼镜店的眼镜是否足够。 Hall 定理模板题，但我当时还不到 Hall 定理。 枚举左侧连续相间小于 $d$ 的 $[l,r]$，答案为： $$ \max(-k\times(\min(r+d,n)-l+1)+\sum_{i=l}^{r}a_i)\leq 0 $$ 分讨： - $r+d\leq n$： $$\max(-k\times d+\sum_{i=l}^{r}a_i-k)\leq 0$$ - $r+d>n$： $$\max(\sum_{i=1}^{r}a_i-k)\leq 0$$ #### t4 智障题，做不来的可以滚了。 ### 24/10/14 #### t1 >你知道字典树吗？一个字典树是一棵有根树，树上的每条边有一个字符，一个节点所表示的字符串就是根到这个节点路径上边的字符依次拼起来得到的字符串。 > >我们认为一棵字典树是合法的，当且仅当所有节点表示的字符串互不相同。 > >小 X 有一棵每条边都有一个小写英文字母的 n 个节点的无根树，小 X 想要知道 $[1,n]$ 中哪些点作为根时这棵树是一棵合法的字典树。 简单题，换根秒了，没 A 的和打歪解的都该滚了。 #### t2 #### t3 >$X$ 国有 $n$ 座城市，这些城市通过 $n - 1$ 条道路连接，形成一棵树形网络。每条道路 都有一个长度。编号为 $1$ 的城市为 $X$ 国的首都。 $X$ 国的交通规划部门计划在城市 $x$ 和城市 $y$ 之间新建一 条长度为 $z$ 的道路。 >然而，由于预算限制，必须拆除一条现有的道路以筹措资金。规划部门希望在拆除一条道路后，新的道路网络仍然保持连通，并且使所有城市到首都的距离之和达到最小。 > >此外，规划过程中可能会对有些道路进行整修，即道路长度发生变化。总共有 $q$ 个 操作，分为两种操作类型： > >- $1\ x\ y\ z$：新建道路，表示在城市 $x$ 和城市 $y$ 之间新建一条长度为 $z$ 的道路 >- $2\ x\ y\ z$：整修道路，表示一条连接城市 $x$ 和城市 $y$ 的现有道路被整修，其长度变 为 $z$。 > >对于每一种新建道路的方案（即每个 $op = 1$ 的操作），需计算实施该方案后所有城市到首都的距离之和的最小值。需要注意的是，新建道路的操作是独立的，仅用于查询，不会实际修改道路网络。 先考虑只有操作 $1$,可以被断开的边一定在 $x,y$ 路径上，并且 $\Delta$ 式等于 $x$ 联通块到 $x$ 的距离之和 ＋（$z$ ＋ $y$ 到 $lca$ 的路径和 - 从断边边到 $lca$ 下的边权和）× 断掉的子树大小。 $x$ 的子树大小、子树到 $x$ 的距离和、$y$ 到 $lca$ 的路径和可以预处理，连通块其他到 $x$ 的和可以递推： $sum += son$（$sum$ 此时是之前的不算 $j$ 的和） $son +=Edge_j$ $sum +=(sz_j-sz_{last})\times Edge_j$ 时间复杂度 $n^2$。 优化 #### t4 ### 24/10/21 #### t1 >给一个由 $0,1,2,3$ 组成序列，要求将 $0$ 变成其他后，其中 $[l,r]$ 所有非空真子集中存在绝对众数的变化方案。 > 挺简单的，但场上看错题面了。 对所有长度大于 $5$ 的序列 $1,2,3$ 不能同时出现，原来出现了几种分讨一下就行了。 小于 $5$ 的暴力求解。 #### t2 #### t3 >一个傻逼在网格图上，开始在原点面朝 $x$ 轴正方向，给一个 $W,A,S,D$ 串 $a$： >- $a_i = W$ 向前走一格。 >- $a_i = S$ 向后走一格。 >- $a_i = A$ 右转。 >- $a_i = D$ 左转。 > >问从 $a_l$ 到 $a_r$ 他最终位置，带修。 记录他的坐标和方向的四元组 $x,y,X,Y$，四个操作变成： - $a_i = W \ $ $y\to y+Y,x\to x+X$。 - $a_i = S \ $ $y\to y-Y,x\to x-X$。 - $a_i = A \ $ $X\to -Y,Y\to X$。 - $a_i = D \ $ $X\to Y,Y\to -X$。 然后就上矩阵。 $$ \begin{pmatrix} x&X\\ y&Y\\ \end{pmatrix} \times \begin{pmatrix} 1&0\\ 1&1\\ \end{pmatrix} = \begin{pmatrix} x+X&X\\ y+Y&Y\\ \end{pmatrix} $$ $$ \begin{pmatrix} x&X\\ y&Y\\ \end{pmatrix} \times \begin{pmatrix} 1&0\\ -1&1\\ \end{pmatrix} = \begin{pmatrix} x-X&X\\ y-Y&Y\\ \end{pmatrix} $$ $$ \begin{pmatrix} x&X\\ y&Y\\ \end{pmatrix} \times \begin{pmatrix} 1&0\\ 0&-1\\ \end{pmatrix} = \begin{pmatrix} x&-X\\ y&Y\\ \end{pmatrix} $$ ### 24/11/20 好久没写了，今天继续。 #### t1 >龙猫决定在橡树下的小道上收集橡子。 > >小道可以视为一个数轴。有 $n$ 颗橡子，第 $i$ 颗橡子在数轴上 $a_i$ 的位置上（可能有多个橡子在同一个位置上）。 > >由于龙猫想要减少工作量，于是她想让你帮她解决如下的问题： > >定义一次操作为将其中一个橡子在数轴上向左或向右移动一个单位长度。求最少需要多少次操作，使得对于每个橡子，都至少有一个其他的橡子与它位于相同的位置。 >形式化地说，每次你可以选择一个 $a_i$，对其进行操作 $a_i\gets a_i+1$ 或 $a_i\gets a_i-1$，求最少的操作次数，使得对于所有 $i$ 存在一个 $j\ne i$ 满足 $a_i=a_j$。 简单题，不会的滚吧。 #### t2 >比赛场馆里设置了 $10^9$ 个位置用来放置气球。初始时，每个位置都是空的。 > >接下来有 $n$ 个气球批发商前来提供气球：第 $i$ 个批发商将会提供 $k_i$ 个气球，且主办方需要选择 $k_i$ 个在 $[l_i,r_i]$ 间的位置，接着将这 $k_i$ 个气球依次放在这些位置上。 > >每个位置只能放置最多一个气球；确定是否存在一种为每个批发商选择位置的方案，使得最终气球的放置满足上述条件。 简单 Hall 定理，枚举左端点线段树维护右端点为 $r$ 的最大 $val+len-r$ 值，场上没开 $8$ 倍挂了 $75$。 #### t3 #### t4 >$\mathrm{Jerry}$ 决定研究龙猫的基因；龙猫的基因序列可以表示为一个长度为 $10^9$ 的整数序列 $a$。 > >$\mathrm{Jerry}$ 购买了一台机器，用来检测龙猫的基因。具体地，机器可以给出若干条关于基因的信息，每条信息都是如下的形式： > >- $(l_1,r_1,l_2,r_2)$ 满足 $1\le l_1\le r_1\le 10^9$ 和 $1\le l_2\le r_2\le 10^9$：表示龙猫的基因满足 $a_{l_1}=a_{l_1+1}=\cdots=a_{r_1-1}=a_{r_1}=a_{l_2}=a_{l_2+1}=\cdots=a_{r_2-1}=a_{r_2}$，即 $a_{l_1\cdots r_1}$ 与 $a_{l_2\cdots r_2}$ 中的所有元素两两相等。 >- $\mathrm{Jerry}$ 想让你从已有的信息中推断出一些其他的信息。具体地，使用机器的过程中依次发生了 $n$ 次事件，每次事件可能是以下的两种之一： > >$\mathrm{Type\ 1}$：机器给出了一条形如 $(l_1,r_1,l_2,r_2)$ 的信息； >$\mathrm{Type\ 2}$：$\mathrm{Jerry}$ 提出一组询问 $(x,y)$，根据目前机器给出的所有信息，是否能确定 $a_x=a_y$。 >请你帮他处理这些事件。 相当于一段区间的合并以及两段区间的合并。 前面的直接在 set 上跑，记录一个点的起点，我们要将起点在 $[l,r]$ 区间内的全部合并起来。 要记什么东西，首先左右端点肯定要记，然后并查集合并时要记上编号，一个区间相交的所有在之后显然只有最大和最小的有用，将他们合并成一个区间即可，查询时也在 set 里边找编号，注意特判 $x=y$ 的情况。 ### 24/11/22 两道黑题压轴，懒得喷。 #### t1 简单小签题，懒得说。 #### t2 >给定一个长度为 $n$ 的链，点编号为 $1\sim n$，对于点 $1 \leq i \leq n-1$，$i$ 和 $i+1$ 间有一条双向边。每次你可以选择一个还未被删去的点 $i$，将它和以它为端点的边删去，要求把整条链所有点删去，且过程中任意时刻都满足连通块个数小于等于 $m$。求方案数模 $10^9+7$，$q$ 组询问，每次询问 $n$ 不同，$m$ 相同。 分段 dp 是合简单的： $$ f_{i,j} = (f_{i-1,j-1}+f_{i-1,j+1}+2f_{i-1,j})\times j $$ 然后发现可以矩阵乘法，~~可惜我矩阵从头烂到尾~~。 ### 24/11/25 #### t1 >对于一棵树，记 $f(i) = \sum_{1 \leq j \leq n} dis(i, j)$，其中 $dis(i, j)$ 表示在树上 $i, j$ 之间的距离。 > >给定一个数 $x$，你需要构造一棵树，满足存在两个点 $u, v$ 满足 $f(u) - f(v) = x$，同时树的节点数最少。 > >方便起见，你只需要输出这个最小值即可。 不难发现 $u,v$ 间隔在 $[\sqrt{x}-1,\sqrt{x}+1]$ 间，奇偶分讨一下就行了。 #### t2 >小 Q 很喜欢基因序列问题，按照剧本，你有两个长度分别为 $n$ 和 $m$ 的 0/1 串 $S$ 与 $T$。你需要在 $S$ 选择恰好 $m$ 个位置 $p_1, p_2, \cdots, p_m$，满足： > >$1 \leq p_1 < p_2 < \cdots < p_m \leq n$，即选择的 $m$ 个位置必须单调递增。 >$T = S_{p_1} S_{p_2} \cdots S_{p_m}$，即这 $m$ 个位置按顺序写下可得到串 $T$。 > >对任意 $0 \leq i \leq n$，记 $l = p_i + 1, r = p_{i+1} - 1$，则 $S[l \cdots r]$ 仅由一种字符组成。 > >额外规定 $p_0 = 0$ 且 $p_{n+1} = n + 1$。 > >注意当 $l > r$ 时，$S[l \cdots r]$ 为空串，仍然符合要求。 > >虽然这和基因序列问题没什么关系，但是小 Q 想要知道，是否存在任意一组合法方案，能够选出这 $m$ 个位置。如果存在，你需要给出任意一种合法的方案。如果不存在，你需要报告不存在任何合法的方案。 场上发现显然有一个 $nm$ 的记录结尾的分讨 dp $f_{i,j,0/1/2}$，但只配 72 分。 #### t3 >给定一个 $n$ 个点 $m$ 条边的有向图（可以有重边自环），你可以进行如下操作： > >选定两个不同的点 $x, y$； >将 $x$ 合并到 $y$ 上，即将所有边 $z \rightarrow x$ 改为 $z \rightarrow y$，所有 $z \leftarrow x$ 改为 $z \leftarrow y$。 >求至少进行多少次操作能使得图变为一个环。 > >定义一个 $n$ 个点有向图是环当且仅当，存在一种标号方式，使得，$E = \{i \rightarrow (i + 1) \mod n \mid 0 \leq i < n\}$。 史题一道。 显然对每条边都对应了环上的一条边，具体的，最每个连通块求 dfs 序后有相邻两数 $u,v\to dfn_u+1=dfn_v \mod t$，这里 dfs 序从零开始。 然后化简成 $u,v\to |dfn_v-dfn_u-1| = 0 \mod t$ 就是一个求最大公因数的问题，特别的答案最大值为 $\sum len_{max}-1$。 小 trick，记录反图，搜的时候回走深度减一，开始节点深度赋 $n$，然后 **C++ 的 __gcd 自动将 0 直接返回另一个数**。 #### t4 ### 24/11/27 #### t1 >给定两个整数 $a, b$（可能为负），你可以进行任意多次操作（也可以不操作），每次操作你需要在如下两种形式中进行选择: > >- 操作 1: 将 $a$ 赋值为 $a$ 与 $b$ 的差，即 $a\leftarrow a-b$。 >- 操作 2: 将 $b$ 赋值为 $b$ 与 $a$ 的差，即 $b\leftarrow b-a$。 > >你的目标是最小化 $a + b$ 的绝对值 $\lvert a + b\rvert$，请输出最小值。 简单性质题，观察到异号可以不断变接近即一定为 $0$，同号是 $\min(a,b,a+b)$，没了。 #### t2 #### t3 >由于你是新月的忠实粉丝，因此你要解决一道具有新月特色的题目。 > >现在你要玩一个名为《新月争霸 2》的游戏。游戏中有一位勇士，勇士初始有 $H_0 + 10^{-100}$ 的血量，共有 $n$ 个 Boss，每个 Boss 的血量是 $h_i$。 > >勇士初始有一把攻击力是 $a_0$ 的剑，每个 Boss 也有一把剑，攻击力为 $a_i$。 > >勇士可以以任意顺序挑战每个 Boss，挑战开始后，勇士和 Boss 会轮流发起攻击（勇士先进行攻击），每次向对方造成 $a_x$ 的伤害值（勇士每次攻击可以选择任意一把已经获得的剑，Boss 只有一把剑），当对方生命值 $\leq 0$ 则挑战结束。 > >当勇士击败一个 Boss 后，可以获得该 Boss 的剑。 > >由于这个游戏太垃圾了，因此你决定抛弃这个游戏，转而解决这么一个问题：如果要把 $n$ 个 Boss 全部击败，$H_0$ 的最小非负整数取值是多少。 观察出一个性质： - 答案分成两部分，一部分不断获取更强的🗡，一部分拿着最强的🗡乱杀。 然后就有了我的考场 dp，$a_i$ 升序排列，记 $f_i$ 为选到 $i$ 大的🗡的最小消耗血量，有： $$\min(f_{j}+\lfloor\frac{h_i-1}{a_j}\rfloor)\times a_i\to f_i\ \ ,\ \ f_{j}+\lfloor\frac{h_i-1}{\max}\rfloor\times a_i \to f_{j} \ (j<i)$$ **注意 $a_0$ 可能是最强的** 然后看到转移涉及到两个变量，考虑移到一边去。将 $\lfloor\frac{h_i-1}{\max}\rfloor $ 提出来，记 $sum = \sum_{i=1}^{n} \lfloor\frac{h_i-1}{\max}\rfloor\times a_i$，在转移 $f_{i}$ 时减去，于是只能从后往前转移： $$\min(f_{i}-\lfloor\frac{h_i-1}{\max}\rfloor\times a_i+\lfloor\frac{h_i-1}{a_j}\rfloor\times a_i) \to f_{j}\ (i>j)$$ 前面那一坨是一知的，接下来考虑形如 $K+\lfloor\frac{h_i-1}{a_j}\rfloor\times a_i \to f_{j}\ (i>j)$ 的转移。 直接枚举 $\lfloor\frac{h_i-1}{a_j}\rfloor$ 的值，总枚举量是调和级数 $O(n\ln n)$ 的，然后成了个区间一次函数维护问题，会不了一点。
正在渲染内容...
点赞
0
收藏
0
