yaoxi-std / yaoxi-std.github.io Goto Github PK

https://yaoxi-std.github.io/2021/12/17/sol-p4248/

[AHOI2013] 差异 题解

https://yaoxi-std.github.io/2022/01/09/sol-cf553e/#more

CF553E Kyoya and Train

https://yaoxi-std.github.io/2021/11/27/sol-p3233/

P3233 世界树 题解题面题目链接 解法以下所有的“关键点”都表示题目中的议事处 看完这题题解后去学习了虚树（然后day2上午模拟赛考了道类似虚树但不用建$lca$的题目） 于是看到$\sum m \le 3 \times 10^5$ 直接建立虚树（然而如果没学过虚树就看不出来了）。 用pair<int, int>储存树上节点到达最近关键点的距离和关键点编号以便于比较。先对虚树上的节

https://yaoxi-std.github.io/2022/01/23/sol-p3690/

P3690 【模版】动态树（Link Cut Tree）

https://yaoxi-std.github.io/2021/12/30/sol-p4015/

P4015 运输问题题面题目链接 解法怎么会有这么sb的题目啊。 AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586

https://yaoxi-std.github.io/2021/12/05/sol-p4245/

P4245 【模版】任意模数多项式乘法题面题目链接 解法对于任意模数的多项式乘法显然无法直接套用$NTT$。而由于数量级过大，采用std::complex的$FFT$也会产生比较多的精度丢失。 方法1: $NTT$合并由于$a_i,b_i \le 10^9$且$n \le 10^5$，所以答案的数量级不超过$10^9 \times 10^9 \times 10

https://yaoxi-std.github.io/2021/12/17/top-poly/

【专题】多项式主要为$FFT$，$NTT$，多项式求逆等变换，可以和生成函数结合起来考计数题。这篇题解中有对多项式乘法的较详细证明过程。 对于使用生成函数判断方案是否合法（而不是统计方案的数量），使用单模数容易被卡，建议在$998244353$，$1004535809$和$469762049$中选取两个，其原根都为$3$。 若题目中要求对奇怪的数取模，一定记得计算模数的原根，有可能不是$3$！ 题

https://yaoxi-std.github.io/2021/12/06/sol-at2064/

AT2064 Many Easy Problems 题解题面题目链接 解法对于每个节点$u$，考虑其对$f(i)$的贡献。 正面的贡献不好计算，考虑用总方案数减去不经过$u$的数量，则 \begin{aligned} f(i) &= \sum\limits_{u=1}^{n}{\left(\binom{n}{i} - \binom{n-siz_u}{i} - \sum\limits_{v \in

https://yaoxi-std.github.io/2021/11/25/sol-p7154/

P7154 Sleeping Cows P 题解题面题目链接 解法先分析性质。首先排序不影响答案所以将其排序。若$t_i$所能匹配到的最大$s$的下标为$x$，则如果放弃$t_i$就意味着$s_1$到$s_x$都要被匹配。所以在此思路上$dp$则需要维护两个指针分别指向最小的还没考虑的$s$和$t$，每次选择较小的一边进行更新。不妨将两个数组合并顺序去做。 考虑$dp$，设$dp_{i,j,0/1

https://yaoxi-std.github.io/2021/12/31/sol-p4009/

P4009 汽车加油行驶问题题目题目链接 解法分层图跑dijkstra。 AC代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384

https://yaoxi-std.github.io/2021/11/29/sol-p4606/

P4606 战略游戏 题解题面题目链接 解法 圆方树上圆方果 圆方树下你和我 圆方树前建虚树 欢乐多又多 /kk 看到$\sum|S|$于是开始套路地想到虚树。 但是给定的是一个无向图不是一棵树啊…… 所以要想办法把图转化成一棵树，这样的数据结构叫做圆方树。 这里假设你已经学会圆方树了 考虑圆方树的性质。显然对于一对节点$(u, v)$，它们在圆方树上的路径中的圆点（不包括自身）就是删掉后能使得

https://yaoxi-std.github.io/2021/11/22/sol-cf702f/

CF702F T-Shirts 题解题面题目链接 解法首先不难想到朴素的做法，对每个人枚举所有T恤。但是这样显然无法进一步优化。 但是发现可以按顺序枚举所有T恤$i$，对每个人$j$若$v_j \ge c_i$则将$v_j$减去$c_i$，同时将$cnt_j$加一。 下面考虑如何用数据结构优化。我们需要一个可以查找第一个$\ge c_i$并且能支持区间减去$c_i$的数据结构，这个可以用平衡树做到

https://yaoxi-std.github.io/2021/12/17/top-virtualtree/

【专题】虚树这种东西想到要用很容易，关键是建完虚树后怎么做。 虚树题的特征为多次询问且出现$\sum M \le 10^5$一类的数据范围。 如果题目给出的是一张图而不是一棵树，可以思考是否能够结合圆方树等算法转化为虚树。 对于每次询问，将询问的节点和其在原树上的$LCA$单独建出来$dp$即可。

https://yaoxi-std.github.io/2021/12/24/sol-p2766/

P2766 最长不下降子序列问题题面题目链接 解法第一问直接$O(n^2)$求。 第二问根据第一问$dp$的合法转移建立$DAG$图，拆点并求出最大流。即对于$\forall a_j \le a_i, dp_i = dp_j + 1$，连接$j_1 \to i_0$，流量为$1$，且连接每个$i_0 \to i_1$。如果$dp_i=1$则连接$S \to i_0$，$dp_i=ans_1$则连接

https://yaoxi-std.github.io/2022/01/17/sol-p4002/

P4002 生成树计数黑，真$^{\text{TM}}$的黑啊（指题目的颜色）

https://yaoxi-std.github.io/2021/11/22/sol-cf710f/

CF710F String Set Queries 题解又卷出来一道黑题哈哈哈题面题目链接 解法首先看到多模匹配想到AC自动机。 这个强制在线看起来很麻烦的样子，因为AC自动机必须要离线下来才能build。所以就引入一种新的算法叫做“二进制分组”。 二进制分组这个算法一看名字就很$\log$ 维护一个stack，里面的值都是2的次幂。每次操作在栈顶插入一个1，如果栈顶的两个数相同就将其合并，并改

https://yaoxi-std.github.io/2021/11/27/sol-p2495/

P2495 消耗战 题解题面题目链接 解法虚树模版题，不多说。 AC代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868

https://yaoxi-std.github.io/2021/11/23/sol-p6144/

P6144 Help Yourself 题解应该是第一次在学校午自习时卷OI（然后sxy走进来看了我一眼啥也没说） 题面题目链接 解法对于这种若干区间求值的题目，肯定先按照左端点或者右端点排个序。 不妨先来考虑对于$k=1$的情况dp状态怎么设。套路地设$dp_i$表示以$i$为当前覆盖的最右端点的联通块数目之和，下面要加入一条线段$[l,r]$，思考插入这条线段对$dp$值的影响。对于$i\lt

https://yaoxi-std.github.io/2022/01/23/sol-p1501/

P1501 [国家集训队] Tree II

https://yaoxi-std.github.io/2021/11/28/sol-p3803/

P3803 【模版】多项式乘法（FFT）题面题目链接 解法模版题了属于是（但我只会写递归的FFT） 为了防止自己忘记就写一下证明吧。 前置知识多项式表示方法系数表示法即 f(x) = \sum_{i=0}^{n-1}{a_ix^i}点值表示法不妨将多项式看成一个$n-1$次函数，从上面取$n$个点来唯一地表示这个函数。 设想一下高斯消元法，就能知道为什么$n$个不同的点就能唯一确定这个函数了。 f

https://yaoxi-std.github.io/2021/11/26/sol-p7155/

P7155 Spaceship P 题解题面题目链接 解法AC代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788

https://yaoxi-std.github.io/2021/12/17/top-suffixarray/

【专题】后缀数组 SA虽然有不少此类题目可以用字符串hash瞎搞 记住代码中每个数组的含义： 数组 含义 $sa_i$ 排名为$i$的后缀的起始位置 $rk_i$ 后缀$s_{i \cdots n}$的排名 $tp_i$ 临时数组，用来在基数排序中记录临时排名 $ht_i$ 第$rk_i$个后缀和第$rk_{i-1}$个后缀的$LCP$

https://yaoxi-std.github.io/2021/12/25/sol-p3254/

P3254 圆桌问题题面题目链接 解法较为显然的二分图网络流。 AC代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868

https://yaoxi-std.github.io/2021/12/21/sol-p4011/

P4011 孤岛营救问题题面题目链接 解法显然的状压分层$BFS$。 AC代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485

https://yaoxi-std.github.io/2021/11/24/sol-cf575a/

CF575A Fibonotci 题解题面题目链接 解法$K \le 10^{18}$ 显然矩阵快速幂优化。矩阵转移方程如下： \begin{bmatrix} f_i & f_{i-1} \end{bmatrix} = \begin{bmatrix} f_{i-1} & f_{i-2} \end{bmatrix} \

https://yaoxi-std.github.io/2021/12/27/sol-p3357/

P3357 最长k可重线段集问题题面题目链接 解法在P3358的基础上，多出来了线段与$x$轴垂直的问题，如果和刚刚一样连边就会导致$i \to i$自环的问题。所以进行拆点，如果$l=r$则连接$in(l)$和$out(r)$，否则连接$out(l)$和$in(r)$。 AC代码12345678910111213141516171819202122232425262728293031323334

https://yaoxi-std.github.io/2022/01/15/extra-blog-live2d/#more

Live2D 搭建一日闲来无事，忽觉Live2D。网上找教程，却嫌不够详细。奈何？奈何？只得自己摸索。

https://yaoxi-std.github.io/2022/01/27/trip-wc2022/

WC2022游寄冻零冬眠营几日游，学习了LCT等算法

https://yaoxi-std.github.io/2021/11/26/sol-bzoj2720/

BZOJ2720 列队春游 题解题面题目链接 解法对于这种全排列的题目发现不太好用$dp$。仔细观察发现对于每个人的期望视野都是独立的，可以直接相加，所以直接算$E(c)$表示有$c$个人的高度小于该同学时该同学的期望视野。答案显然$\sum\limits_{i=1}^{n}{E(c_i)}$。 考虑如何求$E(c)$。根据期望公式易得$E(c) = \sum\limits_{i=1}^{c}{i

https://yaoxi-std.github.io/2021/12/17/top-networkflow/

【专题】网络流网络流的话，先口糊好怎么建图，然后复制默写一下板子就好了。 难点其实有两个，一个是如何建图，另一个是输出路径。 如果一道题有许多奇怪的限制，并且$n$和$m$很小，导致$O(n^2m)$可以通过，就可以往网络流方面去想。 其实网络流24题的全称叫网络流和线性规划24题？ 费用流需要注意的地方 费用流建反边的$cost$是原来的$cost$的相反数，即需要add(u, v, c, f)

https://yaoxi-std.github.io/2022/01/18/sol-p4726/

P4726 【模版】多项式指数函数（多项式exp）

https://yaoxi-std.github.io/2022/01/07/sol-cf773f/

CF773F Test Data Generation

https://yaoxi-std.github.io/2021/12/30/sol-p4014/

P4014 分配问题题面题目链接 解法不就是个二分图最小/最大权匹配吗，就这也能紫题？ AC代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808

https://yaoxi-std.github.io/2021/12/30/sol-p4012/

P4012 深海机器人问题题面题目链接 解法图蛮好建的，跑MCMF。 AC代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485

https://yaoxi-std.github.io/2022/01/25/sol-p4491/

P4491 [HAOI] 染色

https://yaoxi-std.github.io/2022/01/18/sol-p4725/

P4725 【模版】多项式对数函数（多项式ln）

https://yaoxi-std.github.io/2022/01/27/trips/#more

游记（寄）

https://yaoxi-std.github.io/2021/12/22/sol-p1251/

P1251 餐巾计划问题题面题目链接 解法题目中已经暗示了要用费用流。 使用流模型，流表示餐巾的数量。但是不易处理餐巾干净与否，所以拆点，将一天拆成两个点，分别表示这天拥有的干净餐巾数量和脏的餐巾数量。为方便表述，分别设为$used_{i,0}$和$used_{i,1}$。 由于每天需要使用$r_i$块餐巾，所以让$used_{i,0}$连向汇点$T$，费用为$0$，流量为$r_i$，表示这天至少

https://yaoxi-std.github.io/2021/12/30/sol-p4013/

P4013 数字梯形问题题面题目链接 解法三次询问分别拆点构建网络流即可。 费用流不能在残余网络上加边重新跑，否则无法保证最大/最小费用。 数组应当开$20 \times 40$而不是$20 \times 20$。 AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484

https://yaoxi-std.github.io/2021/12/27/sol-p3356/

P3356 火星探险问题题面题目链接 解法问题很容易转化成最大费用最大流，拆点分别考虑即可。 如何输出路径呢？只需要跑一次$dfs$或$bfs$，从$S$到$T$走反边流量非零的边即可，记得每次走完将反边的流量$-1$。 AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647

https://yaoxi-std.github.io/2021/11/22/sol-p4632/

P4632 New Home 题解题面题目链接 解法把询问离线下来，考虑3种操作：新开一家商店，关掉一家商店，查询一个点的不方便指数。 先考虑查询。显然具有二分性，考虑判断一个区间 $[l,r]$ 是否包含了所有的颜色。这种区间统计颜色的题目有一个套路的解法，即对于一个点$i$，保存 $pre_i$ 表示 $i$ 的上一个相同颜色出现的位置，区间 $[l,r]$ 的答案即为 $\sum\limit

https://yaoxi-std.github.io/2021/12/05/sol-p4238/

P4238 【模版】多项式求逆 题解

https://yaoxi-std.github.io/2022/01/20/sol-p4223/

P4223 期望逆序对

https://yaoxi-std.github.io/2021/12/27/sol-p3358/

P3358 最长k可重区间集问题题面题目链接 解法先离散化，然后在坐标上连接$l_i \to r_i$，花费为$r_i-l_i$，其他边$i \to i+1$流量为$k$，显然这样得到的最大费用最大流就是答案。 AC代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495

https://yaoxi-std.github.io/2021/12/04/sol-cf526g/

CF526G Spiders Evil Plan 题解题面题目链接 解法有意思，很有意思。 首先我们暂时忽略路径必须经过$x$的限制进行思考。容易想到最长的一条路径是树的直径，且其他路径都是一个叶子到另一个叶子的类型，接着发现如果路径必须经过$x$也需要保证最长路径经过直径的其中一个端点（显然最优）。于是想到以直径两个端点为根分别建一棵树，分别求根经过$x$到一个叶子结点的最长路径后$\max$，

https://yaoxi-std.github.io/2021/12/20/sol-p2761/

P276 软件补丁问题题面题目链接 解法这题不是网络流！ 状压+最短路即可。 AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283

https://yaoxi-std.github.io/2021/11/25/sol-p3715/

P3715 魔法咒语 题解题面题目链接 解法睡觉去了有空再补 AC代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687

https://yaoxi-std.github.io/2021/12/16/sol-p3809/

P3809 【模版】后缀排序 题解题面题目链接 解法模版题不多说 123456789101112131415161718192021222324252627282930313233343536373839404142434445struct suffix_array { int n, sa[MAXN], rk[MAXN], tp[MAXN], ht[MAXN]; void r

https://yaoxi-std.github.io/2021/12/10/sol-p6329/

P6329 【模版】点分树｜震波题面题目链接 解法题目里都说了是点分树 发现自己学过的点分树现在已经不会写了，改天来补个点分树的题解吧。 AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768

https://yaoxi-std.github.io/2021/12/24/sol-p2770/

P2770 航空路线问题题面题目链接 解法$O(n^3)$的$dp$显然（bushi 考虑网络流的做法。首先每个点经过一次就想到拆点，然后按照原图连边，从$1$到$n$的最大流$\ge 2$就有解。 需要注意测试点$2$是$1$到$n$有连边且只有$1 \to n \to 1$这种走法的，但其实可以不用特判解决，输出路径时如果剩余流量$=+\infty-2$时多跑一次即可（具体见代码）。 AC代码