长期计划

SAM专题

date:2020.05.21-2020.06.01

基础类:

Problem	Finished
P3804 【模板】后缀自动机 (SAM)	$\surd$
SP1811 LCS - Longest Common Substring	$\surd$
SP1812 LCS2 - Longest Common Substring II	$\surd$
CF235C Cyclical Quest	$\surd$
CF802I Fake News (hard)	$\surd$
CF271D Good Substrings	$\surd$

中等类:

Problem	Finished
CF547E Mike and Friends	$\surd$
CF1073G Yet Another LCP Problem	$\surd$
CF666E Forensic Examination	-
CF700E Cool Slogans	-

毒瘤类:

Problem	Finished
CF1098F Ж-functions	-

PAM专题

date:2020.05.31-2020.06.01

Problem	Finished
P5496 【模板】回文自动机（PAM）	$\surd$
P1659 [国家集训队]拉拉队排练	$\surd$
P4287 [SHOI2011]双倍回文	$\surd$
P3649 [APIO2014]回文串	$\surd$
P4555 [国家集训队]最长双回文串	$\surd$
P4987 回文项链	$\surd$
P4324 [JSOI2016]扭动的回文串	-

SA 专题

date:2020.06.02-2020.06.04

Problem	Finished
P3809 【模板】后缀排序	$\surd$
P4051 [JSOI2007]字符加密	$\surd$
P2870 [USACO07DEC]Best Cow Line G	$\surd$
P2852 [USACO06DEC]Milk Patterns G	$\surd$
CodeChef TANDEM Tandem	$\surd$
SP694 DISUBSTR - Distinct Substrings	$\surd$
SP687 REPEATS - Repeatsm	$\surd$
SP220 PHRASES - Relevant Phrases of Annihilation	$\surd$

数数 专题

找了几场今年来广(chou)受(ming)好(zhao)评(zhu)的毒瘤数数比赛来刷数数题。

Problem	Finished
[CTS2019]氪金手游	$\surd$
[CTS2019]珍珠	$\surd$
[CTS2019]随机立方体	$\surd$
[雅礼集训 2018 Day4]Magic	$\surd$
[PKUWC2018]Slay the Spire	=
[PKUWC2018]狼人游戏	=

数据结构 专题

找了一些有代表性的数据结构题来复习。

Problem	Finished
「HNOI2016」序列	$\surd$
「CodePlus #7」教科书般的亵渎	-
「雅礼集训 2017 Day2」水箱	-
[九省联考2018]IIIDX	$\surd$
[十二省联考2019]异或粽子	$\surd$
[六省联考2017]相逢是问候	$\surd$

图论 专题

Problem	Finished
「SHOI2017」寿司餐厅	$\surd$
「九省联考 2018」劈配	=

动态规划 专题

Problem	Finished
[九省联考2018]秘密袭击coat	=
[六省联考2017]摧毁“树状图”	=
[NOI2019]回家路线	$\surd$

贪心 专题

其实今年出贪心的可能性比较大…
但肯定会是神仙贪心。
[六省联考2017]期末考试

Matrix-tree定理 专题

(按难度排序)

Problem	Finished
[HEOI2015]小 Z 的房间	$\surd$
[SDOI2014]重建	=
[SHOI2016]黑暗前的幻想乡	=
[Code+#2]白金元首与独舞	$\surd$
[JSOI2008]最小生成树计数	$\surd$
HDU5498 Tree	-
[省选联考 2020 A 卷] 作业题	-
[THUPC2019]找树	$\surd$

week -3

效率要高啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。

2020.06.01

tag:3.5 stars
中午又花了半天整理博客…后来想了半天某交互题无果…
晚上开始写之前口胡但没有做的题目。
写的越快越好吧。

[UER #1] DZY Loves Graph

坑点:按秩合并!!注意可回退化并查集的写法。

[UER #1] 跳蚤OS

其实就是一道模拟题。
但是注意目录的字符串不能用map存，因为在map里面找字符串需要暴力匹配。
于是我们可以将其换成hash来存，当然，最简单的方法就是将其放在tire树上，类似AC自动机来做。

[UR#1] 缩进优化

显然的调和级数复杂度题。

2020.06.02

tag:4 stars
中午再次熟悉了一下FST。

[WC2018]州区划分

感觉这道题放在WC确实是签到题:)
首先我们要知道无向图欧拉回路的充要条件是连通且每个点的度数均为偶数。
题外话:

欧拉回路&欧拉通路知识点

1. 欧拉回路：图G的一个回路，如果恰通过图G的每一条边，则该回路称为欧拉回路。
   欧拉通路：即可以不回到起点，但是必须经过每一条边，且只能一次。也叫"一笔画"问题。
2. 判定欧拉回路:图G连通，无向图每个点的度数均为偶数，有向图每个点入度=出度。
   判定欧拉通路:图G连通，无向度数为奇数的点0/2个，有向图可以存在两个点，其入度不等于出度，其中一个出度比入度大1，为路径的起点；另外一个入度比出度大1，为路径的终点。
3. 求欧拉回路——fleury算法（坑）

欧拉定理(顺便复习一下)
对于平面图有$|V|-|E|+|F|=2$
（$|V|$:顶点数，$|E|$:边数，$|F|$面数）
平面图:可以画在平面上并且使得不同的边可以互不交叠的图。
其实很显然的:)
皮克定理
格点图形，$S=n+\frac{s}{2}-1$（$n$:在内部的点，$s$:恰好在边上的点）。

根据结论我们可以枚举点集$S$然后判断判断该集合分配是否可行。
这样我们就有了$O(3^n)$的做法。
然后我们再套用FST即可。
复杂度:$O(2^n{n}^2)$。

下午复习SA。

P3809 【模板】后缀排序
P4051 [JSOI2007]字符加密
P2870 [USACO07DEC]Best Cow Line G
P2852 [USACO06DEC]Milk Patterns G
CodeChef TANDEM Tandem

[CodeChef]Tandem

如果你做过NOI2016 优秀的拆分那道题，这题就很好做了。
同样的思路，我们先枚举$A$的长度$L$，那么$AAA$一定恰好覆盖$1,1+L,1+2L,...$这些点中的三个点。然后我们找到这三个位置共同的lcp和lcs的长度，设其分别为$x,y$。
画图容易发现一个位置的移动空间是$min(x,L)+min(y,L)-L$，设其为$D$。
我们按照$D$分成三类:

1.$D\le 0$，这样的串显然不存在。
2.$D>0,x\ge L$，说明这样的串不仅存在，由于$x$已经超出$L$，循环节导致不管你怎么选，你的串始终在这个大循环节上，因此$ans2+=D$。
3.$D>0,x<L$，由于你选的串必须在循环节上，因此只有放在最后面的那个位置才有可能与循环节外的字母接触，因此$ans1++,ans2+=D-1$。

至于如何求lcp/lcs，你可以用hash+二分/SA+ST表/SAM。
这里使用的是一个$log$的SA+ST表解决。
复杂度:$O(n\log n)$(调和级数)。

「CodePlus #7」神秘序列

感觉我考试的时候活在梦里…
题解咕掉.

2020.06.03

tag:2.5 stars

中午整理了一下PKUWC2020的题目，准备开始做。
顺便先写了一道签到题。
晚上想做后面的两题结果T2 100pts自闭了…

[PKUWC2020]火山哥与打铁传说

考虑贪心，我们需要尽量让小鱼发挥攻击作用。
此时我们攻击的一定是圣盾鱼，那么我们会选择一个在小鱼后面的剧毒鱼一起将这条圣盾鱼消灭。
这样我们可以将攻击分为单独用剧毒鱼或是剧毒鱼和小鱼的组合，我们很容易求出这个最大数目。
然后我们会发现询问的答案是一个分段函数，直接回答即可。

2020.06.04

tag:2.0 stars
发现越接近周末我越颓废…

[PKUWC2020]最小割
…

2020.06.05

tag:3.5 stars

[CTS2019]氪金手游

感觉被降智了…
首先给出的图描述的这么复杂其实说的就是一颗树。
考虑容斥，发现对于某条边$w$，$[没有w之后的方案数]=[有w的方案数]+[将w反向的方案数]$。
所以我们一开始可以把所有边都当做某一个方向，反向的与没有w之后的方案数相减即可。

[CTS2019]珍珠

首先有标号计数我们需要EGF解决。
然后回顾一下，$[x^n]e^{ax}=\frac{a^n}{n!}$。
那么 E G F { 0 , 1 , 0 , 1 , . . . } = e x − e − x 2 EGF{0,1,0,1,...}=frac{e^{x}-e^{-x}}{2} EGF{0,1,0,1,...}=2ex−e−x​(解个方程)。
后面我不想写了，%Tiw_Air_OAO神仙博客。

2020.06.06

tag:2.5 stars
模拟联考
题目质量还是不错的:)就是我太蠢了…

[Cg 17]「JOISC 2015 Day 1」卡片占卜

之前好像做过类似的题目。
先把原数组异或差分一下，得到4个为1的点，一个操作相当于改变两点的0/1状态。
那么我们将这4个点看成两个起点两个终点跑最短路即可。
其实我一开始绕到欧拉回路上去了。

[Cg 17]「ROI 2019 Day2」机器人高尔夫球赛

打表结论题。
首先根据题意dp得到20分。
然后打表发现对角线上的数字如果没有球洞两步之后就会相同(从右下到左上)。
利用这个性质维护即可。

[Cg 17]「雅礼集训 2018 Day4」Magic

考试的时候口胡出了这题的做法…然而调不出来…自闭了…
后来发现我数数数错了…幼儿园水平，不会数数.jpg…

首先考虑容斥，这里用二项式反演。
定义$f_i$为恰好有$i$个魔术对方案数，$g_i$为至少有$i$个魔术对方案数。
首先同颜色物品我们先赋一个标号，最后再除以一个广义组合数即可。
我们考虑分颜色将物品依次加入，对于保证存在魔术对的，我们将其插入到当前颜色没有保证存在魔术对的物品后面，没有保证存在魔术对的物品在序列中可以乱序。
因此插入至少$j$对魔术对的方案数就是$(a_i-1)\times ...\times (a_i-j)$。
$g_{i+j}=g_i\times (a_i-1)\times ...\times (a_i-j)$
dp结束之后$g_i$乘一个$(n-i)!$。

现在考虑用多项式解决这个问题，显然我们可以将其看为$m$个多项式相乘。
类似树上启发式合并，我们可以启发式合并来连乘这$m$个多项式，用堆维护即可。
复杂度:$O(n{\log }^{2}n)$

2020.06.07

tag:1.5 stars
早上口胡大会上课，然后自己又口胡了几道容斥题和Atcoder题…感觉我菜爆了…
然而一道题都没写:)

week -2

即使未来遥远在光年之外。

2020.06.08

[CTS2019]随机立方体

比较Atcoder的容斥计数题目。

首先显然这$k$个点的坐标都不可能有一维相同。
考虑先分配好这$k$个点的坐标，再这样我们将所有的极大点都等价到一条直线上来，方便计数，分配的总方案数是$P_n^k\times P_m^k\times P_l^k$。
考虑我们只关注会对这$k$个点产生影响的位置，其他位置我们乱放，最后容斥一下。
结论是这部分的概率是${\prod }_{j=1}^i\frac{1}{nml-(n-i)(m-i)(l-i)}$。
具体可以看粉兔大佬的博客，很详细。
我们像阶乘一样预处理这东西就能做到$O(n)$了。

[HNOI/AHOI2018]道路

被这道阅读理解题+卡空间题坑了好多时间…
本身题目是一个普及T3难度的dp…然而题面又臭又长，输入格式恶心，还卡空间…
设$dp[x][a][b]$为$1-x$的路径上选了$a$条公路，$b$条铁路在$x$子树内的叶子节点最小不方便值之和。
从叶子到根dp即可。

「PKUWC2018」Slay the Spire

好久之前口胡过这水题，现在来写一写…

2020.06.09

RT 有时间再写…[逃]
CF1313E Concatenation with intersection
CF1270F Awesome Substrings
CF1310C Au Pont Rouge

2020.06.10

今天做的题好少啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊…

「PKUWC2018」Minimax

线段树合并好题，感觉PKUWC2018的题都挺好的.
D1T1 D2T3首尾呼应:)

首先考虑$O(n^2)$暴力。
显然我们可以把一个子树内左右两个儿子的权值的概率分布都求出来，然后$O(n)$暴力合并成当前点上的概率分布。
显然这个可以用线段树合并加速。
考虑我们在合并的时候维护两个值$s1,s2$表示u/v中的权值在合并之后会乘上的系数。
但我们无法直接修改线段树叶子节点的概率，这时候我们维护一个tag就可以了。
复杂度:$O(n\log n)$。

「NOI2015」寿司晚宴

一道好题，本质上是对线性dp和状压dp区别的深层理解。
首先$30\%$的部分分我们可以将每个质因子当做一个0/1位。
定义$dp[S][T]$表示现在两个集合的质因子分布情况，其中$S\cap T=\varnothing$。
有 d p [ S ∪ { x } ] [ T ] + = d p [ S ] [ T ] ( x ∉ T ) , d p [ S ] [ T ∪ { x } ] + = d p [ S ] [ T ] ( x ∉ S ) dp[S∪{x}][T]+=dp[S][T](x∉T),dp[S][T∪{x}]+=dp[S][T](x∉S) dp[S∪{x}][T]+=dp[S][T](x∈/​T),dp[S][T∪{x}]+=dp[S][T](x∈/​S)。
我们发现$30^2$与$500$在同一数量级，在结合$[2,n]$中的数大于$\sqrt{n}$的质因数最多只有一个，因此大胆猜测我们可以将这个大因子特殊处理。
我们还是将每个数转为0/1状态的形式。根据结论，对于大于$\sqrt{n}$的质因数的比特位每个数最多只有一个。
这个结论该怎么用呢?
如果你足够细心，你会发现我们在做一般线性dp的时候都会满足这个性质。
也就是说，对于这个部分，我们可以考虑非状压而是直接线性dp解决。
接下来就简单了，我们考虑对数按照大因子的不同分层dp，对于每一层我们显然只能将其加入一个集合里面。那么我们每层定义两个dp数组$f[S1][S2],g[S1][S2]$。每层开始时将答案dp数组copy给$f,g$，每层结束之后再和答案dp数组合并一下即可。
注意每次由于我们每层copy了两次，因此如果这层不选会多算一次，因此每层最后合并的时候要减去一次先前的答案dp数组。
复杂度:$O(n{4}^D)$，$D$为$\le \sqrt{n}$的质因子个数，题目中$D=8$。

2020.6.10

「THUSC 2016」补退选

做做水题愉悦身心:)
发现答案中修改次数不超过$6\times 10^6$，因此用vector直接做就行了。

P4781 【模板】拉格朗日插值

拉格朗日插值复习。
算是一种构造方法。
$$f(k)=\sum _{i=1}^n{y}_i\prod _{i\ne j}\frac{k-x_j}{x_i-x_j}$$
将每个$(x_i,y_i)$带入公式你就知道是怎么一回事了。

P4463 [集训队互测2012] calc

离散拉格朗日插值基础dp题。
定义dp_{i,j}表示$i$个数，每个数在$[1,j]$的范围内的方案数。
首先写出dp式，$f_{i,j}=f_{i-1,j-1}\times i\times j+f_{i,j-1}$。
然后我们证明$f(i)$是一个$2i$次的多项式。
设$f(i)$多项式次数为$g_i$。
移项$f_{i,j}-f_{i,j-1}=f_{i-1,j-1}\times i\times j$
左边是次数是$g_i-1$的[$x^d-(x-1{)}^d$没有$x^d$项]。
因此$g_i-1=g_{i-1}+1$.
$g_i=2i$
然后带入$2n+1$（包括i=0）个点插值即可。
复杂度:$O(n^2)$。

CF995F Cowmpany Cowmpensation

跟上一题没什么区别，同样插值即可。
复杂度:$O(n^2)$。

[PKUWC2020]最小割

上次只是口胡，这次来做一下。
被细节恶心到了。
这种题目一定要想好细节再做…

2020.06.12

tag:1 stars
今天状态极差

[六省联考2017]相逢是问候

题目不难，就是一堆套路综合起来而已。
先看数据范围$n\le 5\times 10^4,1\le p\le 10^8$。
显然应该是一个$O(n{\log }^{2}n)-O(n\sqrt{n}\log n)$复杂度的题目。

再看操作，明显不能直接维护，因此肯定是一个势能线段树的题目。
那么原问题若干次操作之后一定会恒为一个值。
根据欧拉定理:
$$c^{c^{a_i}}\mathrm{m}\mathrm{o}\mathrm{d}p=c^{c^{a_i}\mathrm{m}\mathrm{o}\mathrm{d}\varphi (p)+\varphi (p)}=c^{c^{a_i\mathrm{m}\mathrm{o}\mathrm{d}\varphi (\varphi (p))+\varphi (\varphi (p))}\mathrm{m}\mathrm{o}\mathrm{d}\varphi (p)+\varphi (p)}$$
那么如果是$c^{c^{..{.}^{c^{a_i}}}}$，$a_i$会先模上一个$\varphi (\varphi (...\varphi (p)))$。而根据我们的直觉，仅需经过几次迭代我们的值就变成。而此时就与$a_i$无关了。
也就是说，此时这个值就会恒定。

简单证明一下这个次数是$O(\log n)$级别的:
奇数的phi一定是偶数(观察一下式子$\varphi (x)=n\times (1-\frac{1}{p_1})\times (1-\frac{1}{p_2})\times ...\times (1-\frac{1}{p_n})$)，而偶数的phi至少减半。
因此，我们的$\varphi (x)$肯定能在$2\log x$次内变成$1$。

然后我们就每次暴力算$c^{c^{..{.}^{c^{a_i}}}}$直至$\varphi (\varphi (...\varphi (p)))=1$。
但是你会发现这样做复杂度上限是$O(n{\log }^{3}n)$的，因为我们每次暴力算也需要${\log }^2$的递归+快速幂时间。
这里我们可以用光速幂代替快速幂。
其实就是因为指数大小$\le 10^8$次方，我们就可以将幂$a\times 10^4+b$的形式分别预处理，最后合并起来即可。
复杂度:$O(n{\log }^{2}n)$。

[NOI2019] 机器人

这种题目口胡起来还是很愉快的…
首先我们很容易得到一个$50$分的dp。
定义$dp[l][r][v]$为$[l,r]$中最大值不差过$v$的方案数。
那么有$dp[l][r][v]={\sum }_{mid}{\sum }_{k}dp[l][mid-1][k]\times dp[mid+1][r][k-1]$。
然后有一个结论:将给出的区间一起离散化，每相邻两点的一个区间是一个$n$次的多项式。
有了这个结论了之后我们对每个段只取前$n$个值进行dp，接下来的我们可以直接通过插值插出来。
这样可以得到95分的好成绩。
如果要得到满分的话我们需要将每层一定用不到的dp值域舍去(因为对于区间比较短的dp数组，$k$比较大的状态其实是和$dp[1][n][p-p+n-1]$无关的)。

2020.06.13

tag:0 stars
没有状态。

[六省联考2017]摧毁“树状图”

题面贼长…

[六省联考2017]寿司餐厅

首先你需要知道最大权闭合子图是什么。
然后你会发现题目显然是一个最大权闭合子图问题。

对于这道题目，我们定义两类点:区间点$A(l,r)$,每个食物种类点$B$。

写的时候代码开O2出现了一个奇怪的问题，记录一下:

定义的返回值的函数不返回值开O2会RE

[六省联考2017]分手是祝愿

之前做过，复习一下。
现在觉得是个大水题…不想说了。

2020.06.14

主要在讨论拉格朗日插值的题目。

[六省联考2017]期末考试

三分模板题…当然可以枚举。

重心拉格朗日插值

简单来说就是我们把式子变一下形，令$$w_i=\frac{1}{{\prod }_{i\ne j}^n(x_i-x_j)}$$
因此:
$$F(x)=\prod _{i=0}^n(x-x_i)\times \sum _{j=0}^n{y}_j\frac{w_i}{x-x_j}$$
每次增加一个数时，我们每次将每个$w_i$多除以一个$(x_i-x_{n+1})$即可。
这样动态增加数就是单次$O(n)$的了。

week -1

撑住，撑住，最多不过抽搐。

2020.06.15

[十二省联考2019]异或粽子

想起去年不知道0/1tire树可以持久化做这道题目自闭的样子…
其实用可持久化很简单，我们用优先对列维护前$k$大的套路维护即可。
复杂度:$O(k\log k\log a)$
其实有点卡常…

[HNOI2016]序列

莫队复习。
首先这题可以离线，考虑莫队。
然而我们需要考虑每次从$(l,r)$到相邻四个状态如何$O(1)$计算。
考虑$(i,r),(l,i)$的最小值和我们经常用单调栈解决，因此我们先做一次单调栈。
这样我们可以求出每个位置小于它的最靠近的左边/右边的位置$l{p}_i,n{p}_i$。
接下来讨论$(i,r)$的情况。
在$r,lp[r],lp[lp[r]],...$这条链上的$i$我们已经可以$O(1)$处理了。我们只需要加上剩下的没有算到的一小段。我们可以直接通过ST表查询区间$(l,r)$最小的位置$p$，那么这一小段就可以认为是$[l,p)$，最小值是$a[p]$。
复杂度:$O(n\sqrt{n})$。
当然这题显然也是一个二维数点维护的模板题…

2020.6.16

tag:2 stars

今天也要继续颓废哦:）
首先复习一下联考题的思路

[十二省联考2019]春节十二响

其实是一道简单的启发式合并的题目。
然而我太蠢，当时考试的时候口胡了一个$O(n^2)$的做法…
不想多说了。

[十二省联考2019]字符串问题

无脑重工业码农题。
首先一看这题就知道是一道后缀树优化建图的题目。
我们主要需要优化题目中“$A_{i{d}_i}$ 支配的 $B$ 类串，使得该 $B$ 类串为 $t_{i+1}$ 的前缀。”这样的连边。
首先我们建出串 $S$，然后我们发现为$B_j$为$A_i$的前缀的连边为fail树的一个子树。
因此我们把A串挂在fail树上，然后我们B串在fail树上向下走就可以走到所有满足条件的$A$串。
然而总所周知，SAM的fail树上代表了多个字符串，因此我们需要对在一个节点上的字符串按长度排序然后顺次连边。
实际上将$A,B$串一起放在树上跑会简单很多。
最后我们跑一边topsort即可。
树上定位需要用到倍增。

[九省联考2018]IIIDX
[NOI2019]回家路线

写完这两题之后深深的感受到自己的菜。

2020.06.17

tag:2 stars
我只希望这会是省选前最黑暗的一天。

[ZJOI2007]最大半连通子图

tarjan 缩点后dp模板题。

模板复习#1:

忘了复习了些什么了…

2020.06.18

今天居然是6.18…为什么CCF比赛总是和购物节联系在一起:)

下午考前打击信心考试，全是Codeforces的题(确实没有什么NOI风格)，心态崩了(不过我一直都不是很会做CF题目)…

CF712E Memory and Casinos

降智推式子题。

CF623E Transforming Sequence

降智MTT倍增题。

晚上找模板背诵，明天默写:)

[JSOI2016]灯塔(决策单调)
[清华集训2012]模积和(整除分块)
P5656 exgcd
P3386 二分图最大匹配
P3381 最小费用最大流
P3388 割点
P5854 笛卡尔树
P3384 轻重链剖分
P6192 最小斯坦纳树
P4717 快速沃尔什变换 (FWT)
P3803 多项式乘法（FFT）
P3389 高斯消元

week 1

2020.06.26

收拾心情重新出发。
但是今天可能也是我最困最困的一天。
今天学Matrix_tree定理(就是那个D2T3送我命的那个)。

P6178 Matrix-Tree 定理模板

同样是一道模板题:[CQOI2018]社交网络
既然是定理其实只需要了解结论就可以了。
结论是带权无向/有向图的拉普拉斯矩阵的行列式即为其生成树的方案数。
证明：大佬证明
对于有向图的情况需要注意一点:

有向图生成树分为内向树和外向树，在普拉斯矩阵矩阵中，我们始终只记录这个图的入度。同时我们也需要指定一个点$x$为生成树的根，容易我们只需要在一开始删去第$x$行和第$x$列即可。

week 2

2020.06.27

中午口胡完了矩阵树定理题单上的大多数题目…接下来就开始写了qwq…

[SHOI2016]黑暗前的幻想乡

容斥一下，变成矩阵树板题。

[Code+#2]白金元首与独舞

挺不错的一道题，也比较简单。
显然我们可以建一个$O(n\times m)$个点的图，那么现在我们只需要求这个图的生成树个数。
直接矩阵树定理是$O(n^6)$的，相当吓人。
注意到我们只需要填约$k(k\le 300)$个格子，考虑只用这$k$个格子建出一个等价的图。
首先我们需要判断无解的情况，我们需要寻找路径中的环，可以用记忆化搜索$O(nm)$实现。
然后我们容易发现$k$个格子上下左右可以直接连上走了这一步后会走到的下一个没有填充的格子。当然，如果走出去了，我们需要将这个点连向根。
找满足要求的格子同样可以用记忆化搜索实现。
复杂度:$O(T(nm+k^3))$
注意搜索一定要记忆化…否则会退化成$O(n^4)$。

2020.06.28

[HEOI2015]小 Z 的房间

模板题。
但是模数不是质数，需要用类欧几里得的黑科技。

2020.06.30

[THUPC2019]找树

思路挺简单的…就是这做法太神奇了…
做法是这样的:

• 先分别对不同权值都建一个拉普拉斯矩阵:

++f[u][u][w], ++f[v][v][w];
--f[u][v][w], --f[v][u][w];

• 然后对每个$f[u][v]$数组进行广义FWT(这里的广义是指每一位的运算不同)。
• 对于每个权值$w$单独求行列式，记答案为$an{s}_w$
• 将$ans$数组$IFWT$回来，答案显然是最大的方案数不为0的权值。

复杂度:$O(2^W{n}^3)$。
正确性…感性理解一下…

最后

以上就是知性芝麻为你收集整理的2020.6月做题记录长期计划week -3week -2week -1week 1week 2的全部内容，希望文章能够帮你解决2020.6月做题记录长期计划week -3week -2week -1week 1week 2所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。