分类 POJ 下的文章 - ZigZagK的博客

本文为透视入门，自己画的图可能存在错误，欢迎大家指出。视频链接：解决一切绘画透视问题1。解决一切绘画透视问题2。解决一切绘画透视问题3。消失点定律观察者的眼（观

[Meting][Music server="netease" id="1403087332" type="song"/][/Meting]本文已经对重要剧情进

前言前置知识：基础的图形学。参考链接：简单易懂的Unity5 Shader着色器入门教程Unity手册基础 Shader一个基础的 shader ，纯色。Sha

Ray Tracing in One Weekend译注：本文为 Ray Tracing in One Weekend 一书的中文翻译，某些地方与原文不同，因

前言本文章为自用笔记，部分图片和部分内容版权归原出处所有。原网课链接为：GAMES101-现代计算机图形学入门-闫令琪。笔记可能存在纰漏，欢迎在评论区指出。1.

从三维旋转的角度简单介绍一下四元数。定义$\hat{q}=xi+yj+zk+w=\hat{q}_v+q_w=(\hat{q}_v,q_w)$ 。$q_w$ 为实

[Meting][Music server="netease" id="39224658" type="song"/][/Meting]ACM，作为OI生涯的延

Day [-n,-1]这次是我和熊哥第一次EC（也是最后一次），柴老师是第二次。我们新组的杭电4队这赛季取得了不错的成绩，但是训练时还是偶尔会发现严重的短板，那

题目概述Luogu5055解题报告带tag的可持久化平衡树，Pushdown需要在新建的节点上进行，并且Pushdown需要新建两个儿子，以避免影响之前的信息。

题目概述Luogu3835解题报告由于非旋Treap的Split和Merge都是自上而下的操作，因此可以很方便的可持久化。未解之谜：Split肯定需要新建节点，

题目概述Jewel Grab解题报告因为 $k\le 10$ ，其实就是个暴力题。记录 $pre_x$ 表示 $x$ 前面第一个颜色相同的位置（没有就记成 $0

题目概述下克上の天邪鬼解题报告顺着 ${\lfloor{a_i\over 2}\rfloor}\le a_j<a_i$ 想，不难想到利用这个 $\lflo

题目概述CFGYM102566L解题报告如果没有询问路径就是很裸的平衡树维护DFS序，对于每个节点维护入栈节点 $x_{in}$ 和出栈节点 $x_{out}$

题目概述CF1037H解题报告算法不难得出：对于 $x$ 的每个前缀 $x[1,i]$ ，往后添加一个比 $x_{i+1}$ 大的字符 $ch$ ，$i$ 越大

题目概述Luogu4022解题报告不难想到二分答案 $mid$ ，然后求 $L\ge mid$ 是否可行。令 $K={\lfloor{len\over 10}\

题目概述CF316G3解题报告用广义后缀自动机做可以避免很多复杂的情况。把 $s$ 和所有 $p$ 都扔进广义SAM里，然后把 $s$ 扔进SAM匹配得出所有属

题目概述HydroH1079解题报告建出SAM，找到 $[A,B]$ 对应节点 $p$ ，然后在 $p$ 的 $Right$ 集合上考虑。$[C,D]$ 中出现

题目概述Luogu4747解题报告找性质题过于困难……首先很明显，如果两个合法区间有重叠部分，那重叠部分一定也是合法的。更进一步，根据这个性质可以得知答案一定是

题目概述Ayano and sequences解题报告其实并不是很难，但感觉考场上性价比不高 🤔 ，也可能只是我们队做的太慢了 😭 。这个问题如果在线做会发

题目概述LOJ2083解题报告想了很久匹配做法，不会做，实际上是性质题……如果能求出 $pre_i$ 表示以 $i$ 结尾的 $AA$ 个数和 $suf_i$

题目概述LOJ2720解题报告毒瘤字符串题……这题的关键在于，给出串 $T$ ，在 $S$ 的 $[L,R]$ 子串中查询每个后缀的最长匹配前缀。倒着考虑 $T

题目概述CF528D解题报告奇怪的字符串匹配，并且字符集很小，考虑卷积。对于字符 $ch$ ，如果 $S$ 的 $i$ 位置是 $ch$ ，说明 $[i-K,i

题目概述Hold the Line解题报告直接线段树套set是过不了的，我们需要一个小常数的做法。考虑离线，这样第 $i$ 次事件插入 $x$ 位置时，就可以认

题目概述LOJ2320解题报告学到了好多多项式套路。如果 $i$ 连通块度数是 $d_i$ ，则每条边都有 $a_i$ 个选择，把 $a_i$ 放进答案式子里，

题目概述LOJ575解题报告有个比较好想的想法是 $f_{i,j}$ 表示前 $i$ 末尾放第 $j$ 大的方案数，转移方程很显然是前缀和、后缀和的形式，但是前

题目概述Alice's Dolls解题报告定义 $f_{n,k}$ 表示要得到 $n$ 个物品，$x^k$ 的期望。$n>1$ 的情况十分复杂，但是根据期

题目概述给一个字符串 $S$ ，选一个子串 $T$ ，使 ${T\over T-Border(T)}$ 最大。解题报告每个串的Border并不好考虑，但是可以考

题目概述LOJ3058解题报告这个 $m\bmod k=t$ 以及 $k$ 是 $MOD-1$ 因子显然是单位根反演，所以考虑用生成函数表示答案。令转移矩阵为

非自身卷积$f_i=\sum_{k=0}^{i-1}f_kg_{i-k}$ ，$f_0$ 已知，给出 $g_{1..n}$ 。（ $k>i$ 同理）cdq

题目概述HDU5279解题报告首先每个连通块里必须是森林，然后连接每个连通块的 $n$ 条边只要删掉一条，就肯定不会存在全局环，这样每个连通块就独立了。定义 $

题目概述Hasse Diagram解题报告考虑 $f(n)$ 的递推式，但是如果只考虑单个素数，很明显会数重复，因此一次性考虑完一个素数，即 $p^k$ 。对于

题目概述Luogu4705解题报告二项式展开后：$$ {t!\over nm}\sum_{k=0}^{t}{1\over k!}(\sum_{i=1}^{n}a

题目概述Distance解题报告$i$ 走到 $j$ 不管怎么走，每个相差的素数都必须走一遍，所以：$$ dis(i,j)=\sum_{p}p|e_{p,i}-

题目概述AGC005F解题报告考虑每个点对 $k$ 的贡献：$$ \sum_{i=1}^{n}[{n\choose k}-\sum_{(i,j)\in E}{s

性质$S$ 是Lyndon串当且仅当 $S$ 本身是所有后缀中的最小串。$S$ 是Lyndon串可以推出 $S$ 是所有循环表示中字典序最小的。各种性质与推论：

题目概述HDU5322解题报告考虑连通块是什么样的，对于 $n$ 的排列，$n$ 所在位置之前的点肯定都是 $n$ 连通块中的，并且 $n$ 没有往后的边。然后

题目概述LOJ2541解题报告可以把题目转化为，有一个外人向 $n$ 个人开枪，打到第 $i$ 个人的概率是 $w_i\over \sum w$ ，并且可以对死

题目概述洛谷4292解题报告题解里很多点分治，但其实用长链剖分十分的直白。首先先用01分数规划，二分答案 $mid$ ，然后问题转化为边权为 $w-mid$ 的

题目概述给出一棵树，求多少个 $(a,b,c),a<b<c$ 满足三个点两两距离相同。解题报告考虑以这三个点的LCA $x$ 统计答案，则只有两种情

题目概述CF1009F解题报告定义 $f_{i,j}$ 表示 $i$ 子树内到 $i$ 距离为 $j$ 的个数，则显然 $f_{i,0}=1,f_{i,j}=\

题目概述给出一个排列 $\{a_n\}$ ，对于这个排列的所有循环同构，求出排列的排名，对所有排名求和。解题报告对于一个固定的 $\{a_n\}$ ，根据康托展

题目概述Lndjy and the mex解题报告首先不难发现长度为 $len$ 的区间的方案数是相同的，因此只需要考虑区间长度而不需要考虑区间位置（乘 $n-

题目概述HDU6320解题报告暴力想法：枚举 $L$ 开始的回文串 $A$ ，和 $R$ 结尾的回文串 $B$ ，如果 $|A|+|B|=R-L+1$ 则找到一

题目概述CF932G解题报告首先原题意有点恐怖，我们需要进行一定的转化。原题意需要分成偶数个串，然后前后对称相同，如果我们把串的后一半翻转，那么就会发现前后对应

题目概述LOJ6289解题报告这题显然是一个树形背包 $f_{x,j,0},f_{x,j,1}$ 表示 $x$ 没选 / 选了，子树里选了 $j$ 个的方案数。

题目概述Cmostp解题报告建出SAM，考虑离线，每次添加一个前缀节点 $p_i$ 的时候，就是把 $p_i$ 到 $fail$ 树根路径上的节点的最右终止端点

题目概述Equivalence in Connectivity解题报告好像确实有维护动态图的方法……但是可能是考场上写不出的那种……考虑离线，建出可持久化树，如

题目概述Suffix Sort解题报告一直在想Hash，然后寄了……实际上应该分析一下性质。首先有一个比较显然的想法是将 $S$ 变为另一个数组，$a_i$ 表

题目概述Striking String Problem解题报告神仙题，根本想不到。记 $n$ 为 $S$ 长度，$m$ 为 $T$ 长度，$U_i$ 表示 $S

题目概述HDU7217解题报告一个显然的想法：定义 $f_{i,j}$ 表示放了 $i$ 位，第 $i$ 位为 $j$ 的方案数，那么：$$ f_{i,j}=\

题目概述HDU7218解题报告这道题看起来和城市规划很像，但是由于要考虑概率，所以卷积式子和求方案数的式子不一致。定义 $f_i$ 表示 $i$ 个点成为一个连

题目概述HDU7232解题报告比赛的时候想的是正着做，写完DP式子发现是个看起来很可做的东西，结果实际上不能做，寄掉了。实际上应该倒着做，$f_{i}$ 表示

题目概述HDU7199解题报告多项式套路题，需要把题目中两种路径对应到比较容易处理的多项式形式。首先是 $i\to i+1$ ，有 $n+k-i$ 条路径，这个

题目概述HDU7185解题报告其实并不难。由于每次区间操作都是直接覆盖成一种颜色，所以我们可以考虑用set维护所有的颜色相同的线段，然后每次操作就是对set中的

题目概述Generating Strings解题报告裸的回文自动机回退。对于一个长度为 $len$ 的回文串，在 $s$ 中出现一次的权值为 $(N-len+1

题目概述Jobs (Hard Version)解题报告首先我们先考虑二维不重复数点问题：不难发现按照 $x$ 排序后，只有 $y$ 递降的那些点是有用的，其他点

题目概述CF GYM103687K解题报告科技题过于困难。考虑离线，如果我们把询问分成若干个长度为 $BLK$ 的块，那么块中最多涉及到 $BLK$ 条边，$2

题目概述HDU7171解题报告题目保证了DAG，所以是个DAG上的传递闭包问题，考虑用bitset做。定义 $f_{i,j}$ 表示是否能通过 $j$ 询问中的

题目概述HDU7167解题报告被队内计算几何选手演了😡，本来写个最小圆覆盖就过了。首先很显然 $n$ 个点的最小圆覆盖和这个 $n$ 个点求完凸包之后的最小圆

题目概述NIO with String Game解题报告感觉赛时榜都歪飞了……这题明明不难却只有20个队过。由于对 $t_i$ 只有单字符加的操作，因此最终所有

题目概述Directed解题报告这题竟是脑子题……显然这是个树上解方程的题目，设 $D_x$ 为 $x$ 的度数，$fa$ 为 $x$ 的父亲，$u$ 为 $x

题目概述HDU7147解题报告从来没做过这种容斥，长见识了😭。定义 $f_i$ 表示走了 $i$ 行都合法的权值和，以及 $g_i$ 表示走了 $i$ 行全非

题目概述Spirit Circle Observation解题报告找性质题最烦了.jpg。首先建SAM，考虑一个直观的做法。直接考虑枚举SAM里的节点，然后在节

题目概述Cut解题报告这题思路是不难的，但是如果没写过类似的就会巨难写（细节比较多）……把 $[l,r]$ 内的排序其实就是认为 $[l,r]$ 这一块按照权值

题目概述Fly解题报告首先想到DP：$f_{i,j,0/1/2}$ 表示前 $i$ 个二进制位（从低位到高位），到 $i$ 这位时背包大小为 $j$ ，并且状态

题目概述Luogu5309解题报告题目保证 $y\le x$ ，因此每次都是全局 $i\bmod x=y$ 的 $a_i$ 加上 $z$ 。不难想到 $x>

题目概述LOJ3049解题报告把串反过来，那么 $B$ 是 $A$ 前缀就变成 $B$ 是 $A$ 后缀，也就是 $B$ 是 $A$ 在SAM上的parent树

题目概述CF1701F解题报告对于 $x$ ，设 $[x-d,x-1]$ 上共有 $cnt$ 个点，那么以 $x$ 作为结尾的三元组个数为 ${cnt\choo

题目概述LCS Spanning Tree解题报告听说这题卡倍增SA，表示强烈谴责😡（不过我没想到SA怎么做）。由于需要求任意两个字符串之间的最长公共子串，因

题目概述String Problem解题报告首先很显然，对于前缀 $i$ ，答案一定是某一个位置到 $i$ 。用后缀数组可以做，但是思考起来比较麻烦。考虑后缀自

题目概述Karshilov's Matching Problem解题报告首先不难想到对 $n$ 个匹配串建AC自动机，在 $fail$ 树上求和就可以得知匹配到

题目概述Paimon Segment Tree解题报告首先肯定考虑离线，把询问 $[L,R],[x,y]$ 拆成 $([L,R],[0,y])-([L,R],[

题目概述Beautiful Words解题报告先把 $A$ 复制一份，令 $B_i=A[i-n+1,i]$ 。然后二分答案 $mid$ ，这样就只需要验证是否存

题目概述Suffix Automaton解题报告被时限骗了，以为做法是两个 $\log$（空间爆炸），其实只要离线就可以一个 $\log$ 。求出后缀数组后，第

题目概述Scholomance Academy解题报告伪装成数论题的多项式全家桶题。首先我们可以把 $\varphi(n)$ 拆成 $\prod\varphi(

题目概述给出递推 $f$ 的 $[0,K-1]$ 项，给出系数 $\{a_K\}$ ，$f_n=\sum_{i=1}^{K}a_if_{n-i}(n\ge K)

题目概述HDU7057解题报告首先这道题很显然可以用生成函数做，但是 $n$ 太大了，因此需要考虑类似矩阵快速幂或者分治的办法。定义 $F_i$ 表示花费

题目概述xay loves sequence解题报告先对数组差分，令 $c_i=a_i-a_{i-1}$ 。每次区间加或者区间减就是对 $c$ 的两个位置 $+

题目概述xay loves monotonicity解题报告首先我们很自然联想到楼房重建那道题，定义 $Find(p,l,r,i)$ 表示在 $[l,r]

题目概述Gambling Monster解题报告显然是个期望DP，倒着考虑正常一点（因为在 $n-1$ 处结束，步数为 $0$ ），所以我们倒着DP。定义 $f

题目概述Starch Cat解题报告正解是猫树，但是我不会，所以我选择黑科技。首先我们能想到一个比较暴力的做法，每次询问 $x,y$ 路径上的最大独立集，就是求

题目概述Kuriyama Mirai and Exclusive Or解题报告第一种操作没什么好讲的，我们关注第二种。这种加法和异或混合的一般都只能考虑按位统计

题目概述Prof. Pang's sequence解题报告首先根据经典套路，我们记录 $pre_i$ 表示 $i$ 上次的出现位置，这样的话对于一个左端点 $L

题目概述United in Stormwind解题报告太久没做过这种题了，其实非常套路。题目里给出了 $n$ 个 $01$ 串，把两个串异或就可以得到两个串不同

Day [-n,-2]考前天天gym VP，感觉状态神神鬼鬼的，我的发挥比较看题目。某天晚上梦见飞机坠机了，可能是某种预兆（迫真）。Day -1本来还想考前最后

题目概述图论小王子小C经常虐菜，特别是在图论方面，经常把小D虐得很惨很惨。这不，小C让小D去求一个无向图的最大独立集，通俗地讲就是：在无向图中选出若干个点，这些

题目概述给一个 $n$ 个点 $m$ 条边的连通无向图，满足每条边最多属于一个环，有 $Q$ 组询问，每次询问两点之间的最短路径。解题报告不难想到建出圆方树，然

题目概述CF GYM103145F解题报告其实两个反转操作是独立的，我们可以用两棵Splay来维护位置的序列（A树）以及数值的序列（B树）。每次询问位置 $i$

题目概述CF1527B解题报告我来翻译题解啦！由于不是回文串的时候才能进行操作2，所以我们可以认为操作2是执行一次“啥都不干”。如果 $s$ 是回文串（B1）：

题目概述CF GYM103049A解题报告物品体积小，背包容量大的题，我们可以采用大范围贪心，小范围DP的办法。当询问的背包容量超过 $V$ 时，我们选取性价比

题目概述CF1139D解题报告这是2021天梯赛L3-3的弱化版，吉老师加强版又要杜教筛又要快速乘，懒得写了XD。直接推式子（ $1\over n$ 是长度为

题目概述CF GYM 102978B解题报告不难发现 $0$ 和 $1$ 执行and和or操作时，相当于把其中一个元素删掉了。而 $00$ 之间或者 $11$

题目概述CF1499E解题报告这道题想法不难，但是实现的时候很注重细节。首先我们考虑DP $f_{i,j,0/1}$ 表示第一个字符串取到了 $i$ ，第二个字

题目概述CF1491H解题报告这么诡异的操作，考虑分块。每个元素记录 $last_i$ 表示 $i$ 往前跳，最后一个没有跳出 $i$ 所在块的位置。查询的时候

题目概述EOJ4120解题报告本题难点就在于快速选出海拔 $\le L$ 的连通块，可以利用Kruskal重构树：网格按照海拔从小到大考虑对于 $(x,y)$

题目概述CF1479B1 & CF1479B2解题报告在本算法下，B1和B2其实没有很大区别，所以下面仅讨论最小值。定义 $f_{i,0/1,x}$ 表示 $i

题目概述CF1479A解题报告如果 $a_i<a_{i+1}$ 则称 $i$ 为上点，否则称 $i$ 为下点。首先如果 $1$ 是上点，或者 $n-1$

题目概述CF1477C解题报告呜呜呜，几何学太差了，根本不会。三角形大边对大角，所以最小边一定是锐角。随便选一个点开始走，每次选距离最远的，那么夹角一定是锐角。

题目概述CF1476E解题报告如果用模式串来匹配给出的串，复杂度显然炸了。但是我们发现，字符串长度很短，所以如果用给出的串来匹配模式串（枚举哪些位置改成_），复

F. Strange Memory呜呜呜，想了半天怎么快速处理这个 $i\ \mathbb{xor}\ j$ ，之后发现其实根本没有好的处理方法，只能拆位计算贡

题目概述Kth Query解题报告这道题给了我01 Trie的新思路QAQ。首先我们考虑没有限制的情况，我们对于每个节点 $x$ 维护 $MIN_{x,k}$

比赛链接我是代码工具人，打的都是代码题2333。B. Labyrinth如果终点起点构成的矩阵中没有黑洞，那么答案显然就是曼哈顿距离。否则最优解一定会贴着至少一

题目概述CF1464B解题报告我太菜了，这种题的思路其实挺经典的。考虑相邻两个?之间的情况，假设他们之间有 $s_0$ 个 $0$ 和 $s_1$ 个 $1$

单位根性质单位根一个神奇的性质：$$ {1\over k}\sum_{i=0}^{k-1}\omega_{k}^{ni}=[k\mid n] $$证明：当 $k

题目概述UOJ79解题报告带花树板子题。由于一般图可以有奇环，所以不能直接匈牙利算法增广。但是一个奇环中我们是可以调配使得只有一个点连向外部，因此奇环是可以当成

题目概述CF1453F解题报告考虑路径计数 $cnt_i=\sum_{j=1}^{i-1}[j+a_j\ge i]cnt_j$ ，如果想要 $cnt_n=1$

入坑又是看到WYX在玩这个游戏然后入的坑。 :orz11:游戏体验画面 & 音乐简直就是视听盛宴，吹爆。经典的每张画面都可以当壁纸。加上本人比较喜欢发光的特效，

题目概述CF GYM 102861M解题报告首先要仔细读题，题目保证了覆盖的点的个数总和不超过 $10^6$ ，因此只需要想办法快速找到被覆盖的点就行了。如果按

题目概述CF1444D解题报告这题演我啊，我看三个 $1000$ 以为有什么高级的分半算法，结果写背包能过QAQ。首先显然 $h\not=v$ 时无解，然后我们

题目概述CF1446C解题报告画下Trie树，不难发现如果一个节点 $0$ 子树中只有一个元素，$1$ 子树中只有一个元素，那么这两个元素就会形成重边。由于题目

题目概述CF1444C解题报告首先我们对于每个相同颜色的块，求出是否存在奇环，如果存在那么这种颜色显然不能选。排除了不能选的颜色之后，我们发现只有有边相连的两种

题目概述CF1442B解题报告定义一个新数组 $A_i$ 表示 $b_i$ 在 $\{a_n\}$ 中的下标，然后将 $\{a_n\}$ 递增排序，问题转化为在

题目概述CF1442解题报告首先有个基础想法：$dis_{i,j}$ 表示走到 $i$ ，反转了 $j$ 次的最短路，那么答案就是 $\min\{dis_{n,

题目概述Equivalent Prefixes解题报告首先我们用单调栈维护出 $[LA_{i},RA_i]$ 表示 $a_i$ 的控制区间（ $a_i$ 最小的

题目概述有 $m$ 条边，每条双向边 $(x_i,y_i)$ 只有人数在 $[l_i,r_i]$ 时才能通过，如果人数 $x$ 能够从 $1$ 到 $n$ 则可

题目概述求数列 $\{a_n\}$ 所有子区间不同数个数的和。解题报告套路题，令 $nxt_i$ 表示 $a_i$ 下一个和 $a_i$ 相同的位置。对于一个

题目概述一个合法的整数数列 $\{a_n\}$ 需要满足：$1\le a_i\le n$ 。令 $p_i=\max\{a_k|1\le k\le i\}$ ，则

题目概述CF1436E解题报告呜呜呜，忘了区间mex可以用主席树做了QAQ。开 $n$ 个权值主席树，第 $i$ 棵树记录 $1\sim i$ 中 $x$ 最后

题目概述你有一种法术 $a,b,c,d$ ，在 $t$ 时刻使用时将对敌人造成 $a$ 伤害，但是在 $[t+1,t+c]$ 秒时敌人将每秒回复 $b$ 的血量

题目概述CF1435C解题报告将 $a$ 排序，令 $B_{i,j}=b_i-a_j$ 。我们可以枚举 $x$ ，然后对于每个 $i$ 我们采用第一个 $\ge

题目概述CF1428F解题报告不是很难，但是要考虑的周全一些。对于一块连续的 $1$（假设区间是 $[L,R]$ ），我们枚举 $[L,i](i>L)$

题目概述CF1428E解题报告这就是换了皮的贪心+堆套路题，但是我不会QAQ。设 $Count(x,k)$ 表示 $x$ 分成 $k$ 堆的最少时间，显然是分成

题目概述CF1408E解题报告呜呜呜，这就是个沙雕题，但是我不会。如果多个集合之间的边组成了环说明就有彩虹路，但是显然我们不可能把一个集合中的所有边建出来。考虑

题目概述CF1427E解题报告神仙构造题，我又来翻译题解啦QAQ！如果 $(x,y)=1$ ，根据裴蜀定理，一定能求出两个正整数 $a$ 和 $b$ 使得 $a

题目概述洛谷6786解题报告假设 $(b_i,b_j)=A,b_i=BA,b_j=CA(C>B)$ ，然后推式子：$$ BA+CA+A={BA\cdot

题目概述CF1417F解题报告超级套路题……任意无向图删边是很麻烦的，所以肯定考虑离线转换成加边然后回退。加边就可以利用并查集来进行合并，考虑用set维护一个块

题目概述AtCoder Regular Contest 104E解题报告这题还是挺可做的。我们发现 $n$ 小的一批，因此考虑离散。我们没必要对于每个 $i$

题目概述HHKB Programming Contest 2020 D解题报告其实不难，就是烦的一批，考试的时候写复杂了然后调不出来。首先补集转化，我们求相交的

题目概述CF1427D解题报告题目中疯狂暗示你做 $n$ 次，往这方面考虑就行了。假如我们现在已经有了连续的 $1,2,3,\cdots,k$ ，我们想要把 $

题目概述CF1427C解题报告我又被傻子题干翻了😭，首先 $O(n^2)$ DP非常好想，需要优化。由于保证了 $t_i<t_{i+1}$ ，所以当 $

题目概述CF1407E解题报告这题好妙啊……如果正着做，那么一个城市的颜色决定了好多边，但是倒着做的话，一条边决定了一座城市的颜色，明显好考虑了很多。从 $n$

题目概述AtCoder Regular Contest 104F解题报告我又来翻译题解了😭。我们在最前面加上一个 $+\infty$ ，然后把 $P$ 中的

题目概述AtCoder Regular Contest 104D解题报告对于每个 $x$ ，我们认为第 $i$ 个物品大小为 $x-i$ ，共有 $K$ 个，现

题目概述ACL Beginner Contest F解题报告直接求不太可做，我们考虑容斥，用总方案数减去至少一组相同的方案数加上至少两组相同的方案数……$2n$

题目概述AtCoder Regular Contest 104C解题报告我英语太渣题目读错了😭，以为只要存在某两个人满足 $C_i=C_j$ 就行了，实际上应

题目概述CF1408F解题报告我们可以把 $2$ 个不同的变成相同的，$4$ 个不同的先变成 $2$ 个不同的，再变成相同的。以此类推，$2^k$ 个不同的可以

题目概述CF1405E解题报告显然有贪心：当有多个可以删除的元素同时存在时，先删除后面的，因为删后面的不影响前面。既然如此，我们从左往右考虑一个位置能否被删除。

题目概述CF853C解题报告直接求很麻烦，我们求不满足的个数。对于询问的矩形 $A$ ，我们划分出八个区域： | 0 | 1 | 2 | ----------

题目概述ACL Contest 1E解题报告神仙转化题我根本做不来……我又来翻译题解了。按顺序random_shuffle可以转化为以下形式：有一个数组 $A$

题目概述CF1425D解题报告把和的平方拆开：$$ (\sum_{i=1}^{m}B_i)^2=\sum_{i=1}^{m}B_i^2+\sum_{i=1}^{

题目概述CF1417E解题报告比赛结束之后想出来了……我做D题的时候不SB可能能做出来？很显然我们需要考虑每个二进制位的贡献，第 $i$ 位取反之后只会影响到

题目概述CF1417D解题报告本来已经会做了，但是我把小根堆写成大根堆然后暴毙了QAQ……我们发现 $a_1$ 可以随意向其他位置分配，因此我们考虑将其他位置都

题目概述HDU3842解题报告先按 $D$ 排个序，然后不难想到DP（注意，根据题目要求 $f_j$ 必须 $\ge 0$ ）：$$ f_i=\max\{f_j

题目概述ACL Beginner Contest E解题报告不知道各位数学课上有没有求过这个数列的通项公式……$$ 9,99,999,9999,\cdots $

题目概述HDU5127解题报告我们分析在甜度热爱为 $x$ ，酸度热爱为 $y(y>0)$ 时，$A(p_1,q_1),B(p_2,q_2)(p_1<

题目概述动态加点维护凸包，每次询问 $(x,y)$ 是否在凸包中。解题报告终于写了下动态凸包……其实就是用set维护凸包中的点，动态做Andrew算法。我用的是

题目概述ACL Contest 1D解题报告根本不会做，我来翻译原题解了QAQ。如果要求的是 $[L,R]$ 中最长的good set，我们直接从 $L$ 开

题目概述ACL Contest 1C解题报告这题还是挺可做的，首先考虑棋子之间拦路的问题，在一颗棋子穿过了另一颗棋子时，我们可以认为两颗棋子互换位置，显然移动次

题目概述求最小 $k$ 使得 $k(k+1)\over 2$ 是 $n$ 的倍数。解题报告AC的题太难了，我全都不会做😭。移下项：$k(k+1)\equi

题目概述HDU2328解题报告首先将所有串中间隔开接起来（注意中间隔开的字符不能相同）。二分枚举答案 $len$ ，然后根据 $Height$ 数组分块，每个块

题目概述HDU3518解题报告枚举子串的长度 $len$ ，然后将后缀数组按照 $Height\ge len$ 分块，每个块中检查最左和最右的子串是否交叉就行了

树上差分忘完了……康复一下。记 $x$ 节点的父亲为 $fa(x)$ 。记 $x,y$ 节点的LCA为 $lca$ 。记权值数组为 $w_x$ ，差分数组为 $

题目概述求 $f(n,k)=\sum_{i=1}^{n}i^k$ 。解题报告我们知道 $f(n,k)$ 的公式可以由组合数推导，并且由推导方式可知 $f(n,k

题目概述有 $n$ 个建筑物，高度 $h_i$ 。要从 $1$ 跳到 $n$ ，求最少跳跃步数。$i\to j$ 的跳跃要求：$i+1=j$$\max(h_{i

题目概述交互题。有一个 $1\sim n$ 的排列 $\{p_n\}$ ，每次可以询问 $(x,y)$ ，得知 $p_x\bmod p_y$ 。在 $2n$ 次

求多项式我们知道 $n$ 个点可以确定 $n-1$ 次多项式（比如三点求抛物线）。假设 $f(x)=\sum_{i=0}^{n-1}a_ix^i$ ，如果我们要

太久没打比赛，手感极差，而且题意问题导致我T3 WA了 :tieba17: 。比赛链接1.树木规划二分+DP。#include<cstdio> #i

起因8月初，网上疯传了一篇浙江省满分作文《生活在树上》，我父母也是立刻给我分享了这篇文章。然而，和大部分人一样，我草草看了第一遍，就发现读不懂文字。对，不是文章

准备打ACM了，进行康复训练。洛谷P1045 麦森数快速幂+高精度，因为要的是最后500位，所以只存500位就行了。[panel title="示例程序"]#i

[Meting][Music title="君の銀の庭" author="Kalafina" url="/usr/uploads/2020/07/3811365

[Meting][Music server="netease" id="1440936344" type="song"/][/Meting]回校之后的两个月原本

问题Typecho自带了文章加密（给文章设置访问密码），但是存在奇怪的bug，以及不兼容PJAX。由于加密文章返回403状态码，所以无法PJAX跳转页面。存在多

[Meting][Music server="netease" id="25539263" type="song"/][/Meting]前言起源纵使遭受了家长老

下文均为作者个人观点，如果感到厌恶请不要继续阅读，请不要对我的观点进行恶意抨击。回望网课也算是告一段落了，我终于要回学校了。网课期间我并没有好好学习，颓得很愉快

负能量爆棚警告，请谨慎观看！！！这一切的一切都要从家中早读开始说起……现在上网课，年级组要求在家中早读也可以理解，虽然心里不是很情愿，但是督促下学习也不错，至少

MDUI2333这是一款基于MDUI的typecho主题。它并不是为了纯粹的美观而设计出来的产物，它甚至有些随意，您可以从它的起名和logo看出作者并没有花费较

[Meting][Music server="netease" id="39227637" type="song"/][/Meting]考前考前停课的时候回归课

[Meting][Music server="netease" id="365158027" type="playlist"/][/Meting]入坑大概在B站

[Meting][Music server="netease" id="39224651" type="song"/][/Meting]可能是没啥用的骚操作QA

一时兴起逛MonsterX博客的时候发现了友链随机输出的这个方式，我觉得的确挺不错的，于是开始折腾。研究了一下Links插件发现……并不能在不改动插件的情况下实

前言星之卡比补全计划，就从梦之泉DX开始啦。梦之泉DX应该是很多人的童年（包括我），但实际上这个GBA版本是FC版的重置版，至于FC版我还没有玩过，之后应该也会

2020.2.24UPD：之前这篇文章是一篇毫无意义的水文……现在重新写过了，记录了一点PHP编写API的入门知识。机房大佬语录：“” $.ajax({

吐槽由于网友的鞭策……我决定处理一下这个大坑……本来想做个插件，发现根本没有教程……所以就使用了常规的Json版配置。配置指南图示下面的某些参数所在位置可以在这

啊暑假第一天……修仙是必须要修仙的……说说退役后的半个学期内的划水状况。期末考试前语文课：一如既往地听不懂。数学课：起码还是能听懂的。英语课：一如既往地划水，被

终于把AJAX评论搞好了QwQ，效果可以在这篇文章下面评论试试（所以在本页可以随意划水2333333）。AJAX评论方法1：AJAX提交评论2020.2.16

入坑我吹爆空洞骑士！最开始是看到JZ和WYX在打这个游戏，我发现画面非常萌（并不）就草草入坑了。开始打的时候我才发现一点都不萌……这是个硬核动作游戏，地图十分复

[Meting][Music server="netease" id="139774" type="song"/][/Meting]二试翻盘失败啦，AFO。作为

[Meting][Music server="netease" id="1301395546" type="song"/][/Meting]Day [-n,-2

题目概述有 $n$ 个基地，每个基地可以发射和接收 $[x_i,y_i]$ 频率内的信号，坐标为 $l_i$ ，且 $i$ 号基地只能往前发射到距离不超过 $L

题目概述求 $\sum_{i=1}^{n}\sum_{j=1}^{m}gcd^K(i,j)$ 。解题报告水题吧……先用莫比乌斯函数处理一下：$$ \sum_{d

题目概述单点加，矩阵求和，强制在线。解题报告强制在线还卡空间，所以我们用KDT吧QAQ！每个节点记录一下控制区域和控制区域内的和，每次查询的时候不停找和询问区域

题目概述维护一个点集，有两种操作：1.加入一个点。2.询问 $(x,y)$ 到点集中曼哈顿距离最小值。解题报告KDT入门可以看这里。KDT玄学玩意……我没写重构

题目概述求不存在 $|a_i-a_{i+1}|=1,i<n$ 的 $n$ 的排列 $\{a_n\}$ 的个数。解题报告定义 $f_{i,j,0/1}$ 表

上次打完之后分数还是不够Div1……只能再打Div2。UPD：这次打完分数还是不够QAQ。Maximum Remaining去重后第二大。#include<

题目概述有 $n$ 条线段 $(a_i,b_i)$ ，定义 $C(i)$ 表示包含 $i+{1\over 2}$ 的有序线段列表，求字典序第 $K$ 小的 $C

题目概述有 $n$ 个箱子，每个箱子的长宽高为 $(a_i,b_i,c_i)$（可以任意旋转），把 $[l,r]$ 的箱子装入一个大箱子需要满足区间内任意的箱子

题目概述把 $[2,n]$ 分成两半（不需要全部选），求两边不存在不互质的数的方案数。解题报告如果素数个数少的话可以直接状压 $f_{s,t}$ 表示第一组的素

课件链接Problem A考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。由于答案在 $[1,n+K]$ 范围内，所以可以把值域也

题目概述解题报告考试的时候看到这种题只能想不到+打不出来……一道SB剪枝我没加然后就只有暴力分 $20$ 了……一副牌怎么样能胡？1.选出一种牌当对子，剩下的牌

题目概述有 $m$ 种牌共 $n$ 张，求最多组成多少面子（即顺子 $i,i+1,i+2$ 或者刻子 $i,i,i$ ）。解题报告题目名称是将麻可还行……CF泄

题目概述给出长度为 $m$ 的基因串 $S$ ，对于每个 $i$ 求有多少个长度为 $n$ 的基因串 $T$ 使得 $LCS(S,T)=i$ 。解题报告DP套D

解题报告ZJOI又双叒叕出线段树，我又双叒叕没做出来。Orz%%%zhouzhendong。定义 $f_{i,0}$ 表示线段树节点 $i$ 没有标记，但是

题目概述求 $\sum_{i=1}^{n}\sum_{j=1}^{n}f^K[gcd(i,j)]$ ，其中 $f(n)$ 表示 $n$ 的次大质因子（相同质因子

题目概述求 $\sum_{i=L}^{R}f(i)$ ，$f(n)$ 表示 $n$ 的次大质因子（相同质因子算多次），若次大质因子不存在则 $f(n)=0$ 。

题目概述求最小的 $n$ 使得 $fib_n\equiv C(mod\ P)$ 。解题报告模板题调这么久我是不是没救了……题目要求：$$ {1\over\sqr

题目概述定义积性函数 $f(n)$ 满足 $f(p^k)=p\ xor\ k$ ，求 $\sum_{i=1}^{n}f(i)$ 。解题报告不难发现除了 $f(2

一类问题已知积性函数 $f(n)$ ，其中 $f(p)$ 是简单多项式，且 $f(p^k)$ 可以快速计算（ $p$ 是素数），求其前缀和。上杜教筛？如果 $f

Day [-n,-2]天天考试，天天爆炸+被学弟吊打。Day -1在家休息（颓废）了一天，下午去找放学了的同学打了下乒乓球。内心虚的一批，和同学聊了下未来规划发

题目概述有一棵 $n$ 个节点的树，每个节点有一个字符。定义一条路径 $(x,y)$ 形成的字符串为从 $x$ 走到 $y$ 路径上所有字符按顺序接起来形成的字

题目概述有一个序列 $\{a_n\}$ ，定义一次操作 $[L,R]$ 表示将 $[L,R]$ 中的数改成 $[L,R]$ 中的最大数。现在要进行 $q$ 轮，

题目概述有 $n$ 棵树和 $m$ 个操作，操作有：1.在 $[L,R]$ 树当前根的后面加一个点。2.把 $[L,R]$ 树的根改为 $x$ 。3.询问第 $

题目概述JZ需要从 $n$ 个妹子中挑出 $3$ 个出去浪，但是三个妹子之间不能有冲突，一种方案 $(i,j,k),i<j<k$ 的贡献为：$Ai+

题目概述用 $K$ 种颜色对 $n\times m$ 的网格进行染色，需要保证无论怎么样纵切将棋盘分为左右两个部分，两个部分的颜色种类数都必须相等，求方案数。

题目概述定义两个 $n$ 的排列 $A,B$ 的相似度为通过交换两个元素使得两个排列相同的最小次数。现在给出两个 $n$ 的排列，有些位置还没有确定，求相似度为

题目概述给出一个数组，求这个数组的 $k$ 次前缀和（前缀和的前缀和的前缀和……）。解题报告就是这题套个NTT，水博客真开心。可能略有卡常……示例程序#incl

题目概述有 $n$ 个点的有根树，每个节点只能往上走，且每个节点有一个特产。现在有 $q$ 个询问，每次询问 $c$ 个点，求这些点走到他们的公共祖先，在满足：

题目概述给出一个操作串：如果是小写字母，表示在当前字符串后面添加这个小写字母。如果是 $−$ ，表示删除当前字符串最后的小写字母（保证合法）。求每次操作后当前字

题目概述给出一个数组，求这个数组的 $k$ 次前缀和（前缀和的前缀和的前缀和……）。解题报告可能大力找规律就可以很快做出来？不过我们可以考虑这个东西的组合意义，

题目概述有 $n$ 个点带点权的树和 $m$ 个物品，一个物品能放在树上一个节点的条件是树上这个节点到根路径上点权最小值大于等于这个物品的权值。现在能够把一个点

题目概述有 $n$ 个点的树，$1$ 为根，每个节点的深度定义为到根的点数。求深度为奇数的点恰好为 $K$ 的树的个数。解题报告emm……我们把树按照深度奇偶分

题目概述有 $n\times n$ 的矩阵 $a$ ，判断该矩阵是否满足：1. $a_{i,j}=a_{j,i}$ 。2. $a_{i,i}=0$ 。3. $\

题目概述求长度为 $n$ ，元素值域为 $[1,m]$ 的所有序列的本质不同子序列的个数的和。解题报告不难发现长度为 $i$ 的子序列的出现次数是相同的，所以

像我这种菜鸡只能打Div2QAQ……这里放一下除了Challenge之外的题解。Chef and Number Game最优解只能是正负分两半。#include

题目概述有 $n\times n$ 的网格，如果 $(i,j)$ 满足 $i+j$ 是奇数那么这个格子就有危险度，现在可以放 $m$ 个占地为 $3$ 的 $L

题目概述有 $n\times n$ 的网格，每次可以选择一个 $m\times m(m={n+1\over 2})$ 的子网格将数字进行取反，求最大数字和。解题

题目概述把 $n$ 个数分成 $m$ 份，求最小的均方差 $\sqrt{\sum_{i=1}^m(sum_i-ave)\over m}$ ，其中 $ave={\

题目概述有 $n$ 个砝码，第 $i$ 个砝码在 $x_i,y_i$ ，重量为 $w_i$ 。现在把所有砝码绑在一起，求绳结平衡在哪个位置。解题报告玄学大法模拟

题目概述有 $n-1$ 座城市，$n$ 个乡村，每个城市有一条公路和一条铁路连进来（乡村没有连进来的路），每个乡村有参数 $a_i,b_i,c_i$ ，如果乡村

题目概述有 $n$ 个数 $a_i$ ，求每个数的逆元。解题报告$O(n)$ 求 $n$ 个数逆元？？？Orz WA自动机，感觉这个技巧非常有用，帮助我解决了C

题目概述求多少序列 $\{A_n\},A_i\in[1,2^K)$ 满足 $B_1=A_1,B_i=B_{i-1}\ or\ A_i$ 的序列 $\{B_n\}

解题报告题目里已经告诉我们怎么判断宝藏和陷阱是否被圈起来了……由于只和奇偶性有关，所以可以状压：$f_{x,y,A,B}$ 表示目前在 $(x,y)$ ，宝藏的

解题报告我不会“简单题”.jpg。可以考虑从 $(a,b)$ 到 $(c,d)$ 的两种走法：先上再右 $A_a(c-a)+B_d(d-b)$ 以及先右再上 $

题目概述给出一棵 $n$ 个节点的树，求每个点成为与其他点距离和最小点最少需要删除并加上的边数 $k$（新加边之后依然是一棵树）。解题报告我根本发现不了性质.j

题目概述这题太水了，鸽了。解题报告这题太水了，鸽了。答案就是 $\sum_{i=1}^{n}{n\choose i}p^i(1-p)^{n-i}\sum_{j=

题目概述有 $n$ 种颜色的膜法卡，每种颜色有 $a_i$ 种，总共有 $m$ 张。现在要把所有卡片排成一排，如果相邻两个卡片颜色相同则产生一个膜法对，求

题目概述有 $n$ 个点的带边权树和 $m$ 次操作，每次操作：1.将一个点变成黑色。2.求 $x$ 到所有黑色点的距离。解题报告好像可以大力点分树……我没有想

题目概述给出一个 $n$ 的排列 $\{p_n\}$（满足 $i\not=p_i$ ），求一个括号序列满足：1.是合法的括号序列。2.对于所有左括号 $i$ ，

题目概述定义 $0$ 维基础图形为点，$1$ 维基础图形为边，$2$ 维基础图形是正方形，$3$ 维基础图形是正方体，以此类推。问 $n$ 维基础图形由多少个

题目概述原来有 $n$ 个点的一棵树，现在加进了 $K$ 条边。问多少种方案删边使得图依然连通。解题报告非正解警告……接下来要讲的是原题解中的算法七，不过这

题目概述给出一个 $n\times m$ 的巧克力，每个位置有形状和美味值，求一个个数最小的连通块满足形状数 $\ge K$ ，且在个数最小的前提下，美味值的中

题目概述$a_{t}[i]=\sum_{j}a_{t-1}[j]b[count(i\ xor\ j)]$ ，其中 $count(i)$ 表示 $i$ 二进制下

解题报告题目里要我们找出的实际上是一个满足条件的连通块，又因为数据范围这么小，所以想到斯坦纳树来做这种连通块最小值问题。令 $f_{i,j,s}$ 表示 $i,

题目概述在 $n\times m$ 的网格上有 $k$ 个景点，选取每个网格都有代价，求最小代价使得景点之间全部连通。解题报告感觉这个东西好mogical啊……

题目概述有 $n$ 个骰子，每个骰子投出剪刀、石头、布的概率已知。现在每次随机拿出剩余骰子中的一个进行投掷（并不知道这个骰子的概率分布），投完后扔掉。你要出 $

题目概述有长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个询问，每次询问 $[L,R]$ 表示 $s$ 的 $[L,R]$ 这些前缀之间的最大公共后缀。

解题报告题解里有个很厉害的 $O((n+s)log_2n)$ 做法，但是我不会……我只会这种比较好想的做法。首先这明显是一个二分图完全匹配问题，我们可以把每项

题目概述有 $n$ 个骨牌，每个骨牌有高度和推倒代价，骨牌可以往左往右推倒，如果两个骨牌的距离小于推倒骨牌高度那么就会向同一个方向倒下，求最小代价使得所有骨牌都

题目概述有两种操作：1.将 $a_i,i\in[L,R]$ 加上 $fib_{i-L+1}$ 。2.求 $\sum_{i=L}^{R}a_i$ 。解题报告水Bl

解题报告陈老师的题解和没讲一样……考虑每一个二进制位的贡献，发现只要存在 $a_i$ 有 $j$ 这个二进制位，这个二进制位就有 $2^{n-1}2^{j}$

题目概述定义字符串 $A$ 和 $B$ 的乘法 $A\times B$ 的结果为将 $B$ 插入 $A$ 的每个空隙中（包含两端），给出 $n$ 个串，求按顺序

解题报告很明显至多选 $3$ 个就能构成一种方案，所以我们只需要考虑选 $1,2,3$ 个的情况就行了。考虑不合法的情况，即物品之间有包含的情况，如：1 1 1

解题报告重新看一遍发现这题十分斯波……我们要求的是：$$ \sum_{\{a_k\}}e[(a_1,a_2,\cdots,a_k)]\\ \sum_{\{a_k

解题报告摆明了要你点分治……每次统计 $x$ 子树的时候记录两个值：到 $x$ 路径最大值和到 $x$ 路径点权和。按照最大值排序之后，枚举 $i$ ，只要看前

题目概述给出 $f(x),g(x),h(x)$ ，求 $f(g(x))\ mod\ h(x)$ ，系数在 $mod\ 2$ 意义下。解题报告直接就有一个 $O(

解题报告考虑决策树，每次枚举操作，根据返回的结果把符合当前状态的排列分成三份（当然如果符合当前状态的只有 $1$ 个排列就不需要继续分了），我们要做的是把决策树

解题报告题目中显然给出了一个卷积形式，所以我们移下项，凑凑常数，得到：$$ {A(x)-A_0\over x}-A_1=A(x)A(x)-A_0^2\\ A(x

题目概述一个 $n$ 个点的简单无向图的价值定义为每个点度数 $K$ 次方的和，求所有 $n$ 个点的简单无向图的价值的和。解题报告只需要知道这两个前置姿势，这

题目概述求有多少 $n$ 的排列满足从左边会更新 $A$ 次最大值，从右边会更新 $B$ 次最大值。解题报告第一类斯特林数：$s(n,k)$ 表示把 $n$ 个

题目概述给出一个多项式 $F(x)$ ，有 $m$ 个询问，每次求 $F(a_i)$ 。解题报告将 $F(x)$ 在 $x=a$ 处进行泰勒展开：$$ F(x)

题目概述求 $B(x)=e^{A(x)}\ mod\ x^n$ 。解题报告前置姿势：多项式求逆，多项式ln。第一种方法是两边求导：$$ B'(x)=e^{A(x

题目概述求用集合 $S$ 中的点权构造点权和为 $[1,m]$ 的二叉树的方案数。解题报告生成函数什么的好大啊，我好菜啊。令 $C(x)$ 表示所有点权的生成函

题目概述求 $n$ 个点简单无向连通图的个数。解题报告我感觉好像重新学了一遍指数型生成函数的样子……普通型生成函数解决的是组合问题，而指数型生成函数解决的是排列

题目概述求 $B(x)=lnA(x)(mod\ x^n)$ ，即满足 $A(x)=e^{B(x)}$ 。解题报告前置姿势：多项式求逆，多项式求导，多项式积分。多

题目概述给出多项式 $A(x),B(x)$ ，求 $C(x),D(x)$ 满足 $A(x)=C(x)B(x)+D(x)$ 。解题报告显然求出 $C(x)$ 或

题目概述给出一个多项式 $A(x)$ ，求 $B(x)$ 使得 $B^2(x)\equiv A(x)(mod\ x^n)$ ，保证 $A(x)_0=1$ 。解题

2023.4.22：ACM也退役力，不再更新。奎若小哥镇楼！ヾ(≧∇≦*)ゝ！！！因为首页摆着很多置顶文章感觉很奇怪而且看不到新文章了QAQ。于是就整理了一些

题目概述有 $n\times m$ 的客厅，要用 $L$ 型地板覆盖整个客厅，求方案数。解题报告棋盘覆盖问题，$min\{n,m\}\le 10$ ，想到插头D

题目概述给出 $n\times m$ 的网格图，其中有些格子是障碍，求有多少种方法用一条哈密顿回路覆盖没有障碍的格子。解题报告ps：大量图片来自于cdq的课件Q

题目概述给出 $n\times m$ 的网格图，其中有些格子是障碍，求有多少种方法用若干个哈密顿回路覆盖没有障碍的格子。解题报告万年神坑插头DP，插头DP可以解

这是我的Blog里第一篇技术向的文章，有点小激动QwQ（并不）。Hexo里那种可以根据文章数量改变字体大小和颜色的标签云我一直很喜欢：但是Typecho关于这方

解题报告可能是沙雕题，但是我又做不来又写不来QAQ。只要求出所有直线的凸包（分界点），就可以分类讨论树上倍增搞了。注意分界点相同标号的大小问题，处理不好就会GG

解题报告这题好像挺水的……手玩下会发现如果两个相邻元素没有正确排序，那么他们就会在最终序列里并起来。比如：4 1 3 2 -> (4 1) (3 2) -

解题报告其实不用管期望……只要算出总贡献然后最后除以 $(n^2)^k$ 就行了（Manchery：期望就是层壳），不过也可以利用期望的线性性把期望转成概率。

题目概述有 $n$ 种物品，每单位时间出现 $i$ 物品的概率为 $p_i$ ，求恰好出现 $K$ 个不同物品的期望时间。解题报告Min-Max容斥？但是出现

题目概述有 $n$ 个带权糖果和 $n$ 个带权药片，求一一配对后糖果权值大于药片权值比药片权值大于糖果权值对数多 $K$ 的方案数。解题报告emm……我刚开始

题目概述有一棵树，刚开始你在 $X$ ，每次随机走到相邻的点。有 $q$ 个询问，每次询问给出一些点，求把这些点至少经过一次的期望时间。解题报告不难想到Mi

题目概述有一个 $n$ 个元素的集合，求选出若干个子集（不可以不选）相交后元素个数刚好为 $K$ 的方案数。解题报告学Min-Max容斥的时候没有考虑过怎么构造

题目概述我写过了来着，鸽了。解题报告用Min-Max容斥再做一遍这题，学习自memset0。Min-Max容斥，对于一个集合 $S$ ，他的最大值 $max(S

Day [-n,-2]填了一堆算法坑（然后都没有用到）。Day -1从13:00跑图到22:00。Day 0下午报到，试机的时候发现是Win7，里面真的是应有尽

题目概述给出矩阵 $A,B$ ，求最小的 $x$ 满足 $A^x\equiv B(mod\ p)$ 。解题报告哇 $A^x\equiv B(mod\ p)$ ，

题目概述给出一张无向图，求 $4$ 个点构成两个有公共边的三元环的方案数。解题报告填坑填坑，如果我们知道每条边所在的三元环个数 $num_i$ ，那么 $\su

题目概述求 $\sum_{i=1}^{n}i^K,K\le 50000$ 。解题报告同51Nod1228，只不过 $K\le 50000$ 所以不能 $O(K^

题目概述求 $\sum_{i=1}^{n}i^K$ 。解题报告这个东西可以用二项式定理和组合数 $O(n^2)$ 递推来着，但是 $n$ 太tm大了，不过 $K

解题报告搜FMT搜到这道题，其实我都想到怎么做了……结果以为自己解法是错的就没写了……FMT除了集合并卷积之外还有一个经典应用就是子集卷积，他是这样的：$$ h

题目概述刚开始 $x$ 为 $0$ ，每秒会产生一个 $[0,2^n)$ 的随机整数使 $x$ 或上这个数，生成 $i$ 的概率为 $p_i$ ，问 $x$ 变

题目概述给出 $g$ 以及 $f(0)=1$ ，求：$f(i)=\sum_{j=1}^{i}f(i-j)g(j)$ 。解题报告其实我是想学分治+NTT来着的，结

解题报告树的情况直接贪心做，基环树枚举环上的边断开然后贪心做。乱优化代码害人不浅，少 $20$ 分送我爆炸。测评鸭上面有 $O(n)$ 加强版，大佬们可以去切啊

题目概述有 $n$ 个技能，每个技能有一些前置技能，现在 $1$ 技能已学习，求学完所有技能的方案数。解题报告矩阵树定理求有向图中外向树和内向树的个数：外向树：

题目概述令 $f(x)$ 表示 $x$ 质因数分解之后最大的次幂，$m$ 次询问，每次求 $\sum_{i=1}^{A}\sum_{j=1}^{B}f[(i,j

题目概述求二分图 $K_{n,m}$ 的生成树个数。解题报告我骗我自己：$A+B=d(dA+dB)$ ，导致我做不出来。二分图的基尔霍夫矩阵的一个主子式长这样（

题目概述有 $n\times m$ 的网格，每个网格是房间或者柱子，周围都有墙，问打破墙使得房间连成一棵树的方案数。解题报告矩阵树裸题，问题是行列式取模，因为不

题目概述给出一张无向图，求生成树个数。解题报告大佬传送门：*ZJ，Candy?。矩阵树定理裸题，先来讲（瞎扯）一波行列式：行列式定义式：$Det(A)=\sum

题目概述有 $S$ 个数，取 $n$ 次（可重复取），将得到的数乘起来模 $m$ 为 $x$ 的概率。解题报告做过这道题的弱化版……这道题只需要把循环矩乘换成N

题目概述有权值为 $0\sim n$ 的 $n+1$ 个点，如果 $u\ and\ v=v$ 那么 $u$ 有一条到 $v$ 的有向边，现在问点数为 $k$ ，

题目概述有一棵黑白两种颜色的树，两种操作：1.修改一个节点的颜色。2.询问最远的黑点之间的距离。解题报告如果没有修改的话就是裸的点分治，但是有修改的话就凉了……

题目概述求 $f(n)=\sum_{i=0}^{n}\sum_{j=0}^{i}S(i,j)\cdot2^j\cdot j!$ ，$S(i,j)$ 表示第二类斯

题目概述有 $n\times m$ 的网格，有两种方法占领一个格子：1.花费 $c_{i,j}$ 。2.该格子上下左右的格子已经被占领。占领一个格子之后有 $b

题目概述有一张 $n\times m$ 的数表，其第 $i$ 行第 $j$ 列的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$ , 计算数

题目概述一棵 $n$ 个节点的树，每个节点有颜色，求路径上没有相同颜色的路径个数，每种颜色出现次数不超过 $20$ 。解题报告填联赛前的坑，模拟考的时候我疯狂想

题目概述有 $n$ 个点，每个点是一个函数：$sin(ax+b),e^{ax+b},ax+b$ 。有 $4$ 种操作：1.连接 $x,y$ 。2.断开 $x,y

题目概述区间与，区间或，区间最小值。解题报告完了我连吉利线段树裸题都不会做。这种题一般都是考虑差分数组来分析复杂度，如果 $[L,R]$ 与(或)上 $x$ ，

题目概述给出一个序列 $\{a_n\}$ 和 $m$ 次询问，每次询问 $[L,R]$ 中是否有两个数相加为 $x$ 或两个数相减为 $x$ 或两个数相乘为 $

Day [-n,-2]最近法老的题都好难啊……Day -1本来早上考试，结果到了机房之后说不考了QAQ。那当然是tuituitui啦。Day 0新校区都这么豪华

题目概述判断一个序列是否满足所有子序列都有一个数只出现了一次。解题报告可以用矩形覆盖+扫描线的方法，不过可以像NWERC2017F一样启发式分裂。一个数左边第一

题目概述如果一棵二叉树儿子和祖先权值均互质则是一棵FFT（手动滑稽），现在给出一棵树权值的中序遍历，问是否有一种方案使得该树为FFT。解题报告首先有结论：如果

题目概述有一个二进制数序列 $\{A_n\}$ ，现在有 $Q$ 个询问，每次询问 $(L,R,X)$ 表示询问 $[L,R]$ 中与二进制数 $X$ 异或值最

题目概述有一棵既有点权又有边权的树，求 $max\{dist(u,v)\cdot min(u,v)\cdot gcd(u,v)\}$ ，其中 $dist(u,v

题目概述有两个串 $A,B$ ，有些位置是通配符，求 $A$ 可以在 $B$ 的哪些位置匹配。解题报告早就听说了这题，今天来填坑。判断两个字符串相等可以用式子：

题目概述字符串对 $(A,B)$ 是相似的需要满足两个串等长，且存在 $C$ 使得 $A+C=C+B$ 。求长度为 $n$ ，出现字母是小写字母前 $K$ 个的

解题报告抄题解时间到，令 $f(i)$ 表示长度为 $i$ 的答案，则可以得出这样的方程：$$ f(1)=0,f(i)=\sum_{j=2}^{i}[f(j)+

解题报告吃我一记万年神坑。考场上我想到了 $f_{i,j}$ 表示到 $i$ 点比最短路多 $j$ 的方案数，但是我不会转移，写了玄学转移骗了60。不会转移？记

解题报告吃我一记万年神坑。去年考场上做这题的时候一直在想二进制状压，现在回头看看那时候的自己真是蠢爆了。很明显可以三进制状压 $f_{i,s}$ 表示深度为 $

解题报告补集转化，则统计有数超过区间一半的区间的个数，由于是超过区间一半所以只会是 $012$ 中的一个。分开统计 $012$ ，考虑前缀和，其实就是个逆序对问

题目概述有 $n$ 个物品，可以用两种方式获得（可以一起用，一种获得了即可），两种方式成功的概率分别为 $a_i,b_i$ ，第一种方式可以用 $A$ 次，第二

题目概述有 $n$ 个单词，要给每个单词对应一个 $k$ 进制数，使得所有单词变为 $k$ 进制数之后接起来长度最小，并且满足在长度最小的前提下最长 $k$ 进

题目概述有一个长度为奇数的 $01$ 串（有些位待定），每次可以把相邻三个合并成 $01$ 中数量多的，求最终能够变成 $1$ 的方案数。解题报告题解好像是大力

题目概述令 $f(x)=\sum_{a=1}^{+\infty}\sum_{b=1}^{+\infty}[ab|x]$ ，求 $\sum_{i=1}^{n}f(

题目概述有一棵树，每个节点有一个权值 $t_i$ 。现在有 $m$ 次操作，每次操作表示一个节点被删除了或被重新添加了，每次操作后统计子树中被删除节点 $>

题目概述给定一个字符串 $S$ ，要求构造字符串序列 $s_1, s_2, \ldots, s_k$ ，满足任意 $s_i$ 都是 $S$ 的子串，且任意 $i

题目概述给出 $n$ 个数和 $m$ 个询问，每次询问给 $[L,R]$ 中的数进行哈夫曼编码得到的长度总和。解题报告挺强的题，给 $[L,R]$ 中的数进行哈

题目概述给出一张带边权无向图，现在要砍掉最多两条边，使得 $s$ 到 $t$ 不连通，求最小边权。解题报告其实就是考虑 $s$ 和 $t$ 所在的边双连通分量，

题目概述一棵 $n$ 个点的树，给出 $2k$ 个关键点，现在要把这 $2k$ 个点组成 $k$ 对，每对的贡献为点之间的距离，求最大贡献。解题报告完全想不到…

解题报告这题在现在看来好像不是很难啊……把每对蚊子分开考虑，那么就是考虑每个节点作为LCA时的贡献，而每个节点作为LCA时又可以拆成两半处理，这样问题就简化得比

题目概述给出一张有边权的无向图，求从 $1$ 到 $n$ 路径异或最大值，可以重复走点并且可以重复经过 $n$ 。解题报告好妙的题！无向图中的环是可以经过也可以

解题报告先来介绍一波原根：如果 $\forall i\not=j,g^i\not\equiv g^j\ (mod\ P)$ ，那么 $g$ 是 $P$ 的一个原

题目概述有 $R$ 张红牌，$B$ 张蓝牌，$G$ 张绿牌。现在给出 $m$ 种洗牌法（把 $i$ 位的放到 $x_i$ 上），如果两套牌可以通过 $m$ 种洗

题目概述有 $n$ 个人和 $m$ 条关系 $(x,y)$ 表示 $x$ 和 $y$ 有联系方式。如果两个人没有联系方式就需要在同一个连通块，求出连通块个数和每

题目概述交互题，有 $n$ 个点，你需要指定每个点的坐标 $(x,y)$ ，每次指定之后会告诉你这个点的颜色。你需要确定你的点的坐标使得你给出的点能被直线分成两

题目概述给出一张地图，有障碍和空地。问从 $(s,t)$ 出发最多往左走 $max_L$ 步，往右走 $max_R$ 步能到达多少点。解题报告翰爷秒了Orz。看

题目概述有 $n$ 个珠子，可以把不少于 $K$ 个同样颜色的连续珠子消去并把两端接起来。现在可以随意加珠子，问最少加多少珠子使得所有珠子都消去。解题报告挺妙的

题目概述一棵 $n$ 个节点带点权的树，有 $m$ 种取节点的方法，第 $i$ 种 $[L,R,D,T]$ 表示只能取点权在 $[L,R]$ ，$D$ 子树中的

题目概述有 $n\times n$ 的网格，每个格子有 $1$ 块金子，现在处在 $(i,j)$ 的会变到 $(f(i),f(j))$ ，其中 $f(i)$ 表

题目概述如果 $S$ 是 $T$ 重复无数次之后的前缀，那么 $T$ 就是 $S$ 的循环节，现在给出一个串每个前缀 $i$ 的最短循环节 $per_i$ 表示

题目概述给出 $n\times m$ 的 $01$ 棋盘，有 $q$ 个询问，每个询问 $k$ 表示能够修改最多 $k$ 个格子的颜色，问能选出的边长最长的 $

题目概述给出一棵树，求从 $x$ 到 $y$ ，经过的每个点都可以决定异或还是不异或，求能够得到的最大异或值。解题报告倍增+线性基就好啦，复杂度为 $O(60^

题目概述有一棵树，现在要把树分成若干个级别，每个级别是若干个权值加和相等的连通块。第一个级别是所有节点，之后的级别需要满足第 $i$ 个级别中的连通块均在 $i

题目概述把一棵有权值的树分成若干条儿子到祖先的路径，每条路径节点个数不能超过 $L$ ，节点权值和不能超过 $S$ ，问最少分成多少路径。解题报告一个不知道正确

题目概述有一个 $R\times C$ 的网格，其中 $n$ 个格子有资源点，问至少有一个资源点的子网格个数。解题报告万年神坑。先补集转化，那么就是用总方案数减

题目概述求一个半径最小的圆使得和 $x$ 轴相切，并且包含了所有给定的点。解题报告很明显可以二分 $r$ ，那么圆心就是 $(x,r)$ ，通过每个点就可以确定

题目概述给出一个序列，一个回文区间的权值是区间权值和，问 $[L,R]$ 中所有回文区间的权值和。解题报告刚开始想用回文自动机 $O(n\sqrt n)$ 暴搞

题目概述给一棵基环树，有两种操作：1.将到 $x$ 的距离 $\le K$ 的点权值均加上 $d$ 。2.询问到 $x$ 距离 $\le K$ 的点的权值和。解

题目概述有一个字符串，用若干个回文串覆盖该串，回文串可以重叠，问需要的最少的回文串数 $-1$ 。解题报告很容易想到DP $f_i=f_j+1$ 其中以 $i$

题目概述有一个字符串，现在问这个字符串的一个子串中有多少子串是给出的素数 $p$ 的倍数（ $0$ 也算）。解题报告$10^5$ ？莫队？先把满足条件的子串的式

题目概述刚开始有 $A$ 个一点血的奴隶主，$B$ 个两点血的奴隶主，$C$ 个三点血的奴隶主。有一个克苏恩要攻击 $K$ 次，每次攻击随机攻击奴隶主或者玩家。

题目概述有 $n$ 个村庄，现在要建 $m$ 个邮局，一种方案的代价是每个村庄到最近的邮局的距离之和。解题报告我再来水一遍这道题……之前已经用了wqs二分去掉了

题目概述有一棵带边权的树，现在要从根节点出发，至少经过所有边一次，可以传送 $K$ 次，代价为 $C$ 。问走回根节点经过的最小边权和。解题报告先考虑把传送换成

题目概述有 $n$ 个有权值的物品，现在给出若干个询问：$m$ 个颜色，每种颜色有 $c_i$ 个且和为 $n-1$ ，现在要在 $K$ 这个位置选择一个颜色，

题目概述有 $n$ 个点和 $m$ 个传送点 $(l,r)$ 表示可以从 $l$ 传送到 $r$ ，只能往下爬或者传送。问从 $x$ 出发在不超过 $y$ 且不

题目概述有一个AB字符串，问间距为 $k$ 的BA对有多少，其中 $k\in[1,n-1]$ 。解题报告emm……应该算是生成函数吧？令A的位置的权值为下标，B

题目概述求 $\sum_{i=0}^{+\infty}{nk\choose ik+r}$ 。解题报告我好斯波啊……这个式子很明显不可算，应该考虑实际意义，发现就

题目概述有一棵 $n$ 个节点的树，每个节点有个防御值。有 $m$ 个骑士在树的节点上，如果骑士攻击力大于等于防御值就可以攻占这个节点获得收益并向上攻占，否则凉

题目概述加边；单点加；连通块加；整体加；单点询问；连通块最大值；整体最大值。解题报告平衡树启合好像会TLE来着，加边只求最大值就是个可并堆嘛……连通块加打tag

题目概述有 $m$ 个操作：1.在末尾添加一个数 $a_{n+1}$ 。2.询问 $max\{a_p\ xor\ a_{p+1}\ xor\ \cdots\

题目概述有 $n$ 个数，求最长的子区间使得添加 $K$ 个数，排序之后得到一个公差为 $D$ 的等差数列。解题报告我太斯波了，式子都没仔细看就写了个二分，显然

题目概述有 $n$ 对CP，和 $m$ 对前男女友关系，一对CP（因抢着打隔膜导致电脑爆炸所以）解散之后可能会旧情复燃，导致很多CP都解散。问第 $i$ 对CP

题目概述有一个序列 $\{a_n\}$ ，现在有三种操作：1.令 $i\in[L,R],a_i=\varphi(a_i)$ 。2.令 $i\in[L,R],a_

题目概述有 $n$ 个物品，第 $i$ 个物品在 $a_i$ ，移动一格需要 $w_i$ 的代价。现在有两种操作：1.把 $w_x$ 变成 $y$ 。2.询问把

题目概述有一棵树，现在要给这棵树重编号，叶子节点的权值为到根路径的最小值，现在求叶子节点权值的积的最大值，保证叶子节点的个数不超过 $20$ 。解题报告可以想到

题目概述有 $n$ 个组 $V$ 张票，假设 $i$ 组有 $V_i$ 的票。总共有 $m$ 个钦点机会，令 $S_i$ 表示目前 $i$ 组被钦点了几次，每次

题目概述一个管道，从一端向另一端发射一条射线，问最多能够经过多少两端指定的点。解题报告可能很斯波……隐约会感觉到有用的发射间距 $d$ 很少……实际上真的很少…

题目概述有一棵树，切掉一条树边后会得到两棵树，求出两棵树中的最大编号，记为 $(x,y)$ 。现在给出 $(\{x_{n-1}\},\{y_{n-1}\})$

题目概述维护森林，每次询问一条路径 $(X,Y)$ 上任意选出两个点 $(x,y)$ 的路径权值和的期望。解题报告刚开始竟然极其斯波的想成了路径权值和的 $si

题目概述有 $m\times n$ 的矩阵，第 $i$ 行的 $[L_i,R_i]$ 是好的。现在要选出 $[A,B]$ 使得在所有行中要么没有好的元素要么有奇

题目概述有 $n$ 堆石子，每堆 $a_i$ 个，现在要取 $m$ 次，第 $i$ 次在 $[L_i,R_i]$ 中取 $K_i$ 个（不够 $K_i$ 就取完

题目概述有 $n$ 个点 $m$ 条边，每个点的点权是 $a_i(0\le a_i\le 2^{K}-1)$ ，现在要把一个点集 $A$ 的点权异或上 $x$

题目概述有 $n$ 个点 $m$ 条边，每条边有个出现时间 $s$ 和消失时间 $t$ ，问每个时刻是不是二分图。解题报告法老给我们上课用的PPT表示：把边加到

题目概述求 $\sum_{i=1}^{n}\sum_{j=1}^{n}\varphi(gcd(i,j))$ 。解题报告推式子：$\sum_{T=1}^{n}\l

题目概述一个字符串，令 $num_{i}$ 表示前缀 $i$ 的长度 $\le{i\over 2}$ 的 $border$ 数量，求 $\prod_{i=1}^

题目概述交互题，现在要猜一个数 $x$ ，可以询问 $x$ 是不是 $l\le x\le r$ ，但是每次询问完成后 $x$ 会移动一个到距离 $\le K$

题目概述CF19E数据加大版。解题报告不能分治+LCT啦。由于只删除一条边所以可以大力分类讨论。先用DFS树+差分求出树边被多少个奇环覆盖以及被多少个偶环覆盖，

题目概述有 $n$ 个点 $m$ 条边，问有多少边删除了之后让原图是二分图。解题报告远古CF题。删除一条边可以考虑分治，然后用LCT判断有没有奇环就行了。这是斯

题目概述交互题，现在有一个数 $x(1\le x\le 10004205361450474)$ ，每次可以询问 $k(k\le x\land k<1000

题目概述有一个序列 $\{a_n\}$ ，如果区间 $[L,R]$ 里存在 $i<j$ 使得 $a_ia_j$ 是完全平方数就称这个区间是好的。一次操作可

题目概述有 $q$ 次操作，每次操作：1.加入一个整点。2.删除一个整点。3.询问以一条 $y\over x$ 为斜率过原点的线为对称轴，需要添加多少个点使得所

题目概述有一个序列 $\{a_n\}$ ，令 $\{b_i=a_i\ mod\ a_{i\ mod\ n+1}\}$ ，现在给出 $\{b_n\}$ ，求出一组

题目概述有 $n$ 次操作，每次操作可以：1.加入一个A/B类型值为 $p$ 的元素（保证 $p$ 互不相同）。2.删去值为 $p$ 的元素，保证之前出现过。同

题目概述有 $n$ 个区间，求取 $m$ 个区间使得交不为空时的最小 $max\{len\}-min\{len\}$ 。解题报告我不会做题啦……很显然区间越多交

题目概述$x$ 轴上按顺序有 $n$ 座山，每座山有海拔 $h_i$ ，如果一座山比周围两个山高就可以建房子。可以花费 $1$ 的代价把山铲去 $1$ 的海拔，

题目概述如果存在 $(r_1,c_1),(r_2,c_2),(r_2,c_1),r_1\not=r_2,c_1\not=c_2$ 那么就可以不消耗费用添加 $(

场次编号完成状态题解Codeforces Round #721 (Div. 2)1527QwQBEducational Codeforces Round 106

题目概述从原点出发，每次往上下左右走都有一定的概率，问第一次走到离原点距离超过 $R$ 的点的期望步数。解题报告很显然可以期望DP，令距离超过 $R$ 但最接近

题目概述有 $n$ 种小矩形，第 $i$ 种小矩形长为 $w_i$ 宽为 $h_i$ ，有 $c_i$ 个，问有多少种 $(A,B)$ 使得存在一种切割方案将其

题目概述有一个文本串，现在有 $m$ 个模板串（互不相同），问文本串中长度最小的子串使得模板串出现了 $k_i$ 次。解题报告$m$ 个模板串互不相同奥妙重重，

题目概述有 $n$ 个点，选出 $6$ 个点使得能够组成两个不相交的三角形，求方案数。解题报告几何神题，可以证明两个不相交的三角形之间恰好有两条切线（画了几个好

题目概述有 $n$ 个点，$K$ 条特殊边，边权待定，保证无环，还有 $m$ 条普通带权边，现在确定特殊边的边权，使得最小生成树（边权相同选特殊边）包含所有特殊

题目概述给出 $X,Y$ 和 $\{a_n\}$ ，问有多少 $(i,j)$ 存在 $v$ 满足 $(a_i,v)=X,[a_j,v]=Y$ 。解题报告来分析一

题目概述有一棵带边权的树，询问 $m$ 次，每次新建一条边权为 $x$ 的边（不能建重边），问如何建使得 $1$ 到 $n$ 的最短路最大。解题报告可能不难吧，

题目概述有一个光源按照 $(a\to b,s_y)$ 移动，还有 $n$ 个板 $(l_i,r_i)$ 。有 $q$ 个询问，问一个点 $(x,y)$ 被板挡住

题目概述在 $n\times n$ 的棋盘上放 $n$ 个车(ju)，使得车之间不会吃到，且在不经过车的情况下能够从 $(1,1)$ 走到 $(n,n)$ ，求

题目概述有一棵树，如果 $w_i|w_j$ 且 $j$ 是 $i$ 的祖先那么 $j$ 可以直接到达 $i$ ，问从第一个点到所有点的方案数。解题报告$O(n^

题目概述你在play♂CSGO，被第 $i$ 种枪打跪体现你有 $S_i$ 的手残值，并且有 $K$ 个参数 $\{x_{i,K}\}$ ，被第 $j$ 种刀捅

题目概述给出一棵带点权的树，求每个节点 $i$ 的 $max\{(a_x,a_y)|LCA(x,y)=i,x\not=y\}$ 。解题报告因为 $10^5$ 内

题目概述$n\times n(n\le 50)$ 的网格上有 $m(m\le n)$ 个方块，现在要把 $m$ 个方块归位，移动过程中不能碰到其他方块。求一种方

题目概述有 $n$ 组数对 $(a_i,b_i)$ ，求一个数使得 $\forall i,d|a_i\lor d|b_i$ 。解题报告因为随便求所以找共有的素因

题目概述有 $n\times m$ 的网格，现在要不重复的填入 $1\sim nm$ ，如果一个格子比同行同列的数都大就称这个格子占领了这行这列。求只有一个格子

题目概述有 $n\times n$ 的矩阵，现在给矩阵黑白染色，需要满足相邻行和相邻列要么全相同要么全不同，还需要满足最大同色子矩阵的面积小于 $K$ ，求方案

题目概述有 $n$ 个点的树，每个点上有 $p_i$ 只咕咕咕。从任意点出发开始走，有 $k$ 次放面包的机会，放下面包后相邻点的咕咕咕就会凑到该点，问先走一遍

题目概述有 $n$ 场考试，第 $i$ 场考试可以在 $a_i,b_i$ 两天中的一天完成，问至少什么时候能考完所有试，无解输出 $-1$ 。解题报告我图样图森

题目概述按顺序将 $1\sim q$ 涂到长度为 $n$ 的板上（范围自定），问是否能够涂成目标状态（目标状态中有些通配符）。解题报告被翰爷秒掉了，目标状态中相

题目概述交互题。有一个 $n\times n$ 的网格图，每个格子是空地或者障碍。每次可以往右或者往下走，你可以询问 $(A,B)\to(C,D)$ 是否存在一

题目概述在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ，问第 $i$ 个线段必选时至少需要多少线段能够覆盖这个环。解题报告和BZOJ53

题目概述在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ，在线段不交的情况下最多选择多少个线段？解题报告思路还停留在以前的斯波解法上……然

题目概述交互题，让你猜两个 $[1,n]$ 的数 $a,b$ ，每次会回复四种情况之一，如果多条满足随机回复一条合法的：$x=a,y=b$ 。$x<a$

题目概述给出一个序列 $\{a_n\}$ ，重排列这个序列使得新序列 $\{b_n\}$ 中 $b_i>a_i$ 尽量多。解题报告这啥啊……田忌赛马？将

题目概述求有多少个小长方体 $(a,b,c),a\le b\le c$ 能够拼成大长方体 $(A,B,C)$ 。解题报告其实就是求有多少个 $(a,b,c)$

题目概述给出一张 $n$ 个点 $m$ 条有向边的图，可以有环但没有自环。现在要选出一个集合 $Q$ 使得 $Q$ 内的点不连通，但 $Q$ 到其他不在 $Q$

题目概述交互题，$n(n\le 10^5)$ 个人接成环，手上拿着一个数 $a_i$ 。$i$ 和 $i\ mod\ n+1$ 相邻，保证相邻人之间的数之差绝对

题目概述$$ f(x,y)=\begin{cases}A_y&x=1\\f(x-1,y)+A_y&y=1\land x\not=1\\min\{

题目概述咕咕咕。求 $f(a,b)={\varphi(ab)\over\varphi(a)\varphi(b)},\sum_{a=1}^{n}\sum_{b=1

题目概述$f_1=A,f_2=B,f_n=Cf_{n-2}+Df_{n-1}+\lfloor{P\over n}\rfloor$ ，求 $f_n$ 。解题报告这

题目概述给出 $n$ 个点 $m$ 条无向边的连通图，每条边有距离和高度，如果高度 $\le$ 水的高度这条边就会被淹没，令 $dis_i$ 表示到达 $1$

题目概述给出一张无向图，多次询问两个点之间最长边的最小值为多少。解题报告因为最小生成树神奇的性质，我们只需要建出最小生成树然后求最小生成树路经上的最长边就是答案

题目概述判断两个凸包是否同构，即是否能平移+旋转使得两个凸包重合。解题报告原题意是说两个点之间都会建新点，建完之后新点之间也会建新点，那么其实很明显所有点构成了

题目概述给出一个字符串 $S$ ，求 $max\{LCP(S_{[i,j]},S_{[c,d]})|a\le i\le j\le b\}$ 。解题报告先二分答案

题目概述给出 $f(x)=Ax^3+Bx^2+Cx+D$ ，令 $x=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},g(x)=a_1f(

题目概述有 $n$ 个物品，分配到 $m$ 个箱子里（可以为空），问 $(2^{fib_{a_1} }-1,2^{fib_{a_2} }-1,\cdots,2^

题目概述给出 $n$ 个点 $m$ 条无向边，有 $Q$ 个询问每次删除 $k_i$ 条边（之后还原），问图是否连通。解题报告先特判掉没删边就不连通，然后我们建

题目概述给出长度为 $n$ 的数字串，求最长非降子序列的长度，允许翻转一个区间 $[l,r]$ 。解题报告因为数字串，所以我们可以利用数值定义状态来快速转移，而

题目概述给出一个逻辑运算树，每个节点有一个逻辑运算或输入框（ $0$ 或 $1$ ）以及 $0/1/2$ 个儿子（根据符号定）。问每次只把所有输入框中的一个改成

题目概述给出 $\{a_n\}$ 和 $\{b_n\}$ 以及刚开始 $P_i=i$ 的排列 $\{P_n\}$ ，有 $m$ 个询问，每次询问先交换 $P_x

题目概述求 ${1\over a}+{1\over b}={1\over c}(a,b,c\in N^{*},a,b,c\le n)$ 解的个数。解题报告被学弟

题目概述给出 $n$ 个带权点和 $m$ 条无向边的图，给出 $q$ 个操作：1.修改某个节点的点权。2.询问 $x\to y$ 路径上所有简单路径的最小点权。

题目概述求 $\sum_{i=0}^{m}{n\choose m}$ ，多组询问 $(n,m)$ 。解题报告莫队大法好，由 $n\choose m$ 可以 $O

题目概述煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设

题目概述给出一个长度为 $n$ 的字符串和一个长度为 $n$ 的序列 $\{a_n\}$，问有多少个子串 $s_{[L,R]}$ 满足 $Rank(s_{[L,

题目概述给出一个长度为 $n$ 的序列，求每个长度为 $m$ 的序列中的最大值以及最大值被更新的次数。解题报告最大值单调队列，更新次数可以这么搞：先预处理 $n

题目概述给出一个长度为 $n$ 的字符串和 $q$ 个询问，每个询问形如 $(l_i,r_i)$ 表示求 $s_{[l_i,r_i]}$ 的最短循环节的长度（最

题目概述给出排列 $\{b_n\}$ 和刚开始都是 $0$ 的 $\{a_n\}$ ，有两种操作：1.把 $a_{[L,R]}$ 都 $+1$ 。2.询问 $\

题目概述有一个长度为 $n$ 的序列，给出 $m$ 个限制，每个限制形如 $(l_i,r_i)$ 表示 $l_i$ 到 $r_i$ 的数互不相同，求字典序最小的

题目概述在第 $i$ 个月月初需要提供 $w_i$ 的货物，购买货物的单位价格为 $p_i$ 。货物可以存在上限为 $S$ 的仓库，但每月月底需要支付的单位价格

题目概述求方程组 $atk_ix\equiv a_i\ (mod\ m_i)$ 最小的解。示例程序如果把系数去掉就是裸的非互质CRT，根据同余方程的同除性，我们

题目概述BZOJ4182弱化版，原版是要求选出来的点是连通的（我不会），弱化版只需要满足儿子选了父亲必选。解题报告其实之前做过带依赖的一道题，但是并没有体积，所

题目概述有 $n+1$ 个人，选第 $i$ 个人需要花费 $s_i$ ，得到 $p_i$ 的贡献，第一个人必选，没有花费和贡献。$2\sim n+1$ 都有一个

题目概述求 $[1,n]$ 中满足 $x\ xor\ 3x=2x$ 的 $x$ 的个数以及 $[1,2^n]$ 中 $x$ 的个数。解题报告我竟然分析成了 $x

题目概述有 $n$ 个物品，每个物品的体积满足 $a\cdot 2^b$ ，背包体积为 $W$ ，求最大价值。解题报告直接上背包！因为每个物品体积满足 $a\c

题目概述给出一棵 $n$ 个节点的二叉树，现在可以修改任意个节点的权值（只能改成整数），问至少多少次能把这棵二叉树改成BST。解题报告先中序遍历得到序列，然后就

题目概述如果选了 $x$ 就不能选 $2x$ 和 $3x$ ，求 $1..n$ 满足条件的子集个数。解题报告这种神题完全做不来，一波转化日神仙： x 3x

题目概述问 $[L,R]$ 多少个整数是每个位上的数的倍数（$0$ 不算）。解题报告这道题想法不是特别难，但是要考虑优化。首先可以发现只需要记录 $mod\ 5

题目概述问一张 $n$ 个点 $m$ 条有向边的图是否满足两两点 $x,y$ 之间均有 $x$ 与 $y$ 连通或 $y$ 与 $x$ 连通。解题报告FFF团还

题目概述构造一个 $n\times m$ 的矩阵，矩阵元素的值是 $[1,K]$ 中的整数。如果一个元素的值是同行同列中最大的，那么就是一个JZ数。令 $A_g

题目概述有 $n$ 个JZ在一个长度为 $m$ 的环上，第 $i$ 个JZ刚开始在 $c_i$ ，每天会顺时针走 $p_i$ 的路程到那里虐人，共虐 $l_i$

题目概述有 $n$ 个ZZK $m$ 个JZ，每个JZ可以虐两个指定的ZZK中的一个，一个ZZK被虐之后就心态爆炸不能再被虐，问从第一个JZ开始按顺序连续不断的

题目概述一个整点 $(x,y)$ 的代价 $w(x,y)$ 是与 $(0,0)$ 连线上的整点的个数的两倍减三，求 $\sum_{i=1}^{n}\sum_{j

题目概述有一棵 $n$ 个点的点权树，刚开始根是 $1$ ，现在有 $q$ 次操作：把根换成 $x$ 。把 $LCA(x,y)$ 子树中节点的权值均加上 $w$

题目概述有 $n$ 个任务，第 $i$ 个任务需要 $T_i$ 的时间完成，加分为 $L_i−s_i$ ，其中 $s_i$ 表示完成该任务的时间。有 $q$ 组

6.1 Day-1由于要给两位签PKU的大佬当陪衬，所以提前了一天去BJ。儿童节好评，暗示我只有小学生水平。6.2 Day0早上睡到9点，看了看Emacs配置。

题目概述两个数 $x,y$ 可以匹配定义为 $x+y\ge H$ 。现在给出 $\{a_n\}$ 和 $\{b_m\}$ ，问 $\{a_n\}$ 有

题目概述给出一个 $n$ 位随机 $01$ 串，定义 $data(L,R)=max\{LCP(Suf_i,Suf_j)|i\not=j,L\le i,j\le

题目概述有 $n$ 个矩阵，问多少三元组 $(i,j,k),i<j<k$ 满足三个矩阵至少有一个相交的格子。解题报告我怎么连计数题都不会……这种题目

题目概述给出一棵 $n$ 个节点的树，每个节点有权值，一条路径上的对称数定义为最小的出现次数为偶数（包括 $0$ ）的数，现在给出 $m$ 个询问 $(x

题目概述给你 $n$ 个点，每个点有一个 $[1,n]$ 的随机权值，问有多少回文路径。解题报告因为是随机的……所以你要有信仰，假装回文路径长度最多只有 $5$

题目概述给你 $\{a_n\}$ ，给出 $m$ 个询问 $l,r,d$ 表示询问 $a_l\times a_{l+1}\times\cdots\times a

快速数论变换(Fast Number-Theoretic Transform)，简称NTT(FNTT)。然而这货和FFT基本上一样，就是求 $A(x)B(x)$

题目概述现有一个 $n$ 行 $m$ 列的棋盘，一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列，且跳到本行或相邻行。跳越期间，马不能离开棋盘。试求跳法种

题目概述有 $n$ 个有颜色的点，颜色有 $K$ 种，现在选一条线段并获取上面或下面的所有点，规定获得的点不能包含所有颜色，问你能获得多少点。解题报告我怎么套路

题目概述给你 $n$ 种物品，每种物品有无数个，体积为 $V_i$ ，选出若干种物品使得这些物品存在一种方案使得体积加起来 $mod\ p=w$ ，问方案数。解

题目概述有一个长度为 $n$ 的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格

题目概述你有一个长度为 $n$ 的数字串。定义 $f(S)$ 为将 $S$ 拆分成若干个 $1\sim m$ 的数的和的方案数，你可以将这个数字串分割成若干个数

题目概述求 $A(x)B(x)$ ，系数对任意模数 $p$ 取模。解题报告任意模数NTT好像需要三模数NTT搞。然而我不会NTT……所以我来愉快的讲一波任意模数

题目概述有一个长度为 $n$ 的 $01$ 串，你可以每次将相邻的 $k$ 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 $k$

题目概述我们知道，求任意图的最大独立集是一类NP完全问题，目前还没有准确的多项式算法，但是有许多多项式复杂度的近似算法。例如，小C常用的一种算法是：对于一个 $

题目概述给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。解题报告先套路一波：把两个串

题目概述有 $n$ 张攻击牌（造成攻击牌数值的伤害）和 $n$ 张强化牌（攻击牌伤害均 $\times$ 强化牌数值），从中抽出 $m$ 张并选出最优秀的 $K

题目概述给出 $n$ 个生物 $m$ 条能量流动，求食物链个数。解题报告脑子不好用了，划波水。生物题了解一下。食物链的开始通常是绿色植物（生产者）,从绿色植物开

题目概述一条直线上有 $n$ 个点，只有相邻点之间有边。刚开始 $dis_i=10^{18}$ ，给出 $K$ 个关键点的 $dis$ ，用Bellman–Fo

神tm结论大赛日神仙。A求中位数。#include<cstdio> #include<algorithm> using namespac

题目概述一个节点 $i$ 的权值有 $p_i$ 的可能是儿子节点权值最大值，$1-p_i$ 的可能是儿子节点权值最小值（至多两个儿子），假设根节点(1)权值有

题目概述有 $n$ 个询问：$Insert\ s\ x$ ：增加 $x$ 个 $s$ 。$Delete\ s$ ：删除所有 $s$ 。$Query\ s$ ：查

题目概述有一棵点数为 $n$ 的树，树边有边权。给你一个正整数 $K$ ，你要在这棵树中选择 $K$ 个点，将其染成黑色，并将其他的 $n−K$ 个点染成白色。

看来我和去年相比完全没有什么长进Orz。Day1一试放在本校日神仙，Manchery学长演讲好评。听课的时候发现自己和去年比好像没有什么长进。Day1点开试卷发

题目概述你要跟一共 $m$ 个人玩剪刀石头布的游戏，其中 R(Rock) 胜 S(Scissors)、S(Scissors) 胜P(Paper)、P(Paper

题目概述有 $n$ 个点 $m$ 条单向边，每个点的不平衡度为出度减入度的差的绝对值，现在可以删除至多 $m-K$ 条边，求最大不平衡度的最小值。解题报告其实不

题目概述有 $n$ 个ZZK给JZ打工，他们的上下级关系是一棵树。现在JZ要给蒟蒻ZZK输送一定的神犇之力，每个ZZK可以得到 $r_i$ 点神犇之力或者 $p

题目概述有 $n$ 个由双向边连通的城市，$1$ 号城市里住着神犇JZ。$i$ 号城市想要离JZ所在城市距离为 $want_i$ ，如果实际的距离为 $real

题目概述给出一个递增的数组，求 $a_i=a_{i-1}+1$ 的段数。解题报告TC交题方法比较鬼畜，不是读入输出，而是让你实现一个指定名称的class，里面写

题目概述有一块 $X\times Y\times Z$ 的切糕，每个点 $(x,y,z)$ 都有不和谐值 $v(x,y,z)$ 。现在要切这块切糕，为每个直线

题目概述有一个串 $S$ ，现在要把 $S$ 分成不超过 $k$ 段，从每一个子串选出最大的子串，再从这些最大的子串中选出最大的串"JZ串"，求最小的"JZ串"

题目概述求不上升OrzJZ子序列的个数，OrzJZ子序列需要满足 $\prod_{i=2}^{k}{a_{i-1}\choose a_i}\ mod\ 2=1$

题目概述有 $n$ 个神犇JZ，某两个JZ配合有神犇值，共有 $m$ 组这样的JZ。现在要选出若干个JZ（假设选了 $k$ 个），贡献为存在于这些JZ中的所有配

题目概述有 $n$ 个区间 $A_i=[L_i,R_i]$ ，现在选 $m$ 个 $(m>1)$ 区间，贡献为 $|A_{k_1}\cap A_{k_2}

题目概述有两个管道，第一个有 $n$ 个黑白珠子，第二个有 $m$ 个黑白珠子，每次可以从一个管道取出最靠管道口的珠子。假设有 $k$ 中取珠子的方法，第 $i

题目概述有 $n$ 个村庄，现在要建 $m$ 个邮局，一种方案的代价是每个村庄到最近的邮局的距离之和。解题报告显然是 $O(n^2m)$ DP吧？数据小的可怜，

题目概述有 $n$ 个员工 $m$ 条矛盾，现在要炒若干个员工的鱿鱼，一组方案的权值是矛盾数与员工数的比值。求最大比值的方案。解题报告最大密度子图模板题。双倍经

题目概述给出一张 $n$ 个点 $m$ 条有向边的图，现在要求 $S,T$ 的最小割，问每一条边：有没有可能出现在最小割中。是否一定出现在最小割中。解题报告先跑

题目概述题目太复杂了QAQ，自己去看吧……吃我传送门。解题报告很显然最优解一定是选若干个不相交的区间。我们观察题目里的条件，发现带有很多“强制”操作，比如吃了

题目概述有 $n$ 个点 $m$ 条边，每个点需要花费 $p_i$ 购买，每条边可以得到 $c_i$ 的价值。现在要购买一些点，如果一条边两端的点都被购买了，就

对《最小割模型在信息学竞赛中的应用》的一些口胡QAQ。分数规划(01)分数规划为下面一些问题作准备……基本上都是二分答案的套路。分数规划+最小割：ZOJ2676

题目概述有 $n$ 种无数个的物品，每种物品带有ZZK的蒟蒻值 $weak_i$ 和JZ的神犇值 $strong_i$ ，你现在可以选任意个物品，将得到所有物品

题目概述有一个 $n$ 个点 $m$ 条双向边的图，每条边的边权是 $w_i$ 。JZ为了防止神犇之力外泄，想切断 $1$ 到 $n$ 的连接（切断一条边的代价

题目概述有 $n$ 个软件和 $m$ 的容量，每个软件需要 $w_i$ 的容量，有 $v_i$ 的价值，同时依赖 $d_i$ 软件( $d_i=0$ 则没有依赖

题目概述问能否用任意个向量 $(\pm a,\pm b)$ 和 $(\pm b,\pm a)$ 组合出向量 $(x,y)$ 。解题报告显然只有这么几种方法：$x

题目概述一共有两堆物品，分别有 $n$ 个和 $m$ 个。所有物品都是一样的，但是它们有不同的优先级。只能够移动某堆中位于顶端的物品，你可以把任意一堆中位于顶端

[Meting][Music server="netease" id="440241194" type="song"/][/Meting]欢迎来到ZigZagK

题号日期题解备注BZOJ11712019.4.17QwQ BZOJ44072019.4.16QwQ BZOJ40062019.4.16QwQ BZOJ26482