短暂的OI生涯，也许就只剩三个月了，如果NOIP2020挂了，我就真的要被强制退役了。为了不被强制退役，鸽子博主也爬了起来
8.12
loj2012「SCOI2016」背单词倒序放到trie树上，贪心选取（每次走最小的子树）
loj2013「SCOI2016」幸运数字树剖加线性基暴力合并
loj2014「SCOI2016」萌萌哒倍增优化并查集
loj2015「SCOI2016」妖怪推波柿子，发现是对勾函数取max，实数二分即可
loj2016「SCOI2016」美味把01trie的理解变成值域上的理解，区间加就是查询范围平移，主席树一波即可
loj2017「SCOI2016」围棋大力轮廓线dp,转移要用下kmp
zroi252亵渎考虑最后亵渎，状态一定是a1个1，a2个2，……，ai个i，设\(f_{i,j}\)表示前i个人，连续最大为j
zroi253绕口令如果有相同的，对于每个子串的每个border是不可达到的；如果没有相同的，对于每个可能的循环节长度x，x+1是不可达到的
zroi254最远点lct维护子树最远，每个点，给每个虚儿子到子树最远建个set，更新就比较实儿子和set中最大。定点最远，把定点转到跟，搜出最长路径，联通块直径，把刚才最长路径末端转到跟，再搜出最长路径
zroi255世界杯挺麻烦的，推推柿子，然后二分一下
zroi256数组不能有相同元素，维护pre和nxt，以i为结尾的子区间的个数为\(i-\max_{j=1}^ipre_j\)，吉司机线段树维护即可，单次修改只会改三个点的pre
zroi257淘汰赛大概只会20pts的生成函数部分分，后面的优化听得云里雾里
zroi258友谊巨轮对于每个人开个set或动态开点线段树，暴力即可
zroi259璀璨光滑随便构造一组解，发现珂以把所有的某位二进制交换，贪心即可
8.13
AGC047BFirstSecond倒序建trie即可
AGC047CProductModulog=2，模意义下乘变加，自己卷自己
AGC047DTwinBinaryTree枚举lca，暴力处理即可
AGC047EProductSimulation构造题（造计算机题）
AGC046BExtension简单容斥dp
loj2018「AHOI/HNOI2017」单旋考虑将min和max旋转到根的过程，答案就是深度，对树结构影响不大，区间深度的同加减1的，线段树或树状数组维护，插入用set找前驱后继
loj2019「AHOI/HNOI2017」影魔考虑对于每个点，用单调栈求出左右最近比它大的L[i],R[i]，贡献就能变成区间加的问题，配合上扫描线，就珂以把询问变成两个时刻的答案之差
loj2020「AHOI/HNOI2017」礼物经典题，把柿子写一下，除了定值之外，发现有项长得像卷积，配合上旋转，就变成求卷积系数max，fft即可
loj2021[AHOI2017/HNOI2017]大佬怼只有两次并且没有必然联系，预处理状态，双指针扫出最优解
loj2022「AHOI/HNOI2017」队长快跑发现射线方向不重要，只看上下，求最短距离，上下都维护单调队列
loj2023「AHOI/HNOI2017」抛硬币分析一波，得出一个组合式子，先利用网上博客说的范德蒙德卷积（实际是课内数学），把问题变成求组合数的和，这里用ex卢卡斯处理
8.14
loj2024「JLOI/SHOI2016」侦查守卫树形dp
loj2025「JLOI/SHOI2016」方容斥一下，随便数数数，记得正方形可以是斜的
loj2026「JLOI/SHOI2016」成绩比较人数分数分别容斥推柿子，用了一个\(\sum_{i=1}^ni^k=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\frac{(n+1)^{\underline{j+1}}}{j+1}\)，感觉这个我不看题解是真的不会
loj2027「SHOI2016」黑暗前的幻想乡大力容斥套矩阵树定理
loj2028「SHOI2016」随机序列仔细考虑性质，发现只用考虑前缀积，后面的都会因为+-而消失，单点修改变成区间（后缀）乘，线段树维护
loj2030「SDOI2016」储能表打表找规律后分治求解，或者按位dp
loj2031「SDOI2016」数字配对每个数分解质因数，对质因数次数求和，两个数能配对，当且仅当两数有倍数关系且次数和差一，按次数和奇偶分类，跑最小费用最大流，注意费用要不小于0
8.15
loj2033「SDOI2016」生成魔咒倒序建sa统计/sam统计新增节点带来贡献
loj2034「SDOI2016」排列计数就是求下错排，大概普及t2难度
loj2035「SDOI2016」征途王道征途，推个朴素dp，发现可以斜率优化
AGC044APaytoWin倒序记搜
AGC044BJoker暴力01bfs
AGC044CStrangeDancezroi出过这个套路，就是在trie上打标记
AGC044ERandomPawn画图找结论，发现结果在凸包上
8.16~8.22军训，看了看李煜东的书，发现很多细节我都没注意到过（比如树状数组上二分，今年联考就考了）
loj2036「SHOI2015」自动刷题机直接大力二分
loj2037「SHOI2015」脑洞治疗仪曾经写过珂朵莉树，大力线段树显然可以实现
loj2038「SHOI2015」超能粒子炮改首先考虑卢卡斯定理，因为卢卡斯定理有整除2333，那么考虑整除分块，那样递归下去求解
loj2039「SHOI2015」激光发生器计算几何模拟，口胡容易（）
loj2040「SHOI2015」零件组装机乱搞题，尝试将图分成俩子图求解
loj2041「SHOI2015」聚变反应炉树形dp，考虑父亲和儿子的先后顺序，转移过程还要套个背包
loj2042「CQOI2016」不同的最小割建最小割树，用set求不同边权数量
loj2043「CQOI2016」K远点对不会KDT，乱搞思路类似旋转卡壳（）
loj2044「CQOI2016」手机号码就是根据题目条件大力数位dp
zroi503终考虑贡献的式子，发现是个叉积形式，构造出有向三角形面积，要最大，发现凸包合法，就是求凸包面积
8.23
loj2045「CQOI2016」密钥破解先Pollard-Rho质因数分解算出p,q，算出r，用exgcd算出d即可求出答案
loj2047「CQOI2016」伪光滑数整个堆，如果最大质因数次数大于1，就将它换成比他小且最大的质因数加入堆里
zroi515图设一个点权为x，暴力解出范围即可
zroi516车站设f[i][j]表示看到i号车站，前面掉了j次头最小代价
2020多校10
CMineSweeper通过3*3的格子构造
DPermutationCounting大概就是SAO那题树退化成链
ETreecutting枚举中心，点分治统计
FDivideandConquer先随便找条水平线，二分第二条线的斜率
GCoinGame将硬币分成a和a+b/2，按性价比排序，贪心取
JIdonotknowGameTheory!将两个不同行不同列取完后，就变成了普通nim，行或列有取完的要记得-1
KTaskScheduler按照所需人数从大至小排序
loj2048「HNOI2016」最小公倍数对一维值域分块，另一维排序，分块维护
loj2049「HNOI2016」网络对重要值整体二分
loj2050「HNOI2016」树真·树套树，考虑把每部分缩成点，建个大树，答案分解成大树上贡献和模板的贡献
8.24
自闭了一天（主要是loj来了月经，开了套zroi的ZJOI膜你赛）
zroi512土地改革实数二分，贪心摆放check，最后暴力实数转分数
zroi513两弹一星考虑结果，将指数转化为第二类斯特林数和下降幂的形式，发现对答案有贡献联通块数小于等于k，考虑f[i][j]表示i个点，j个联通块是树的方案数，这个dp可以用NTT优化转移，对于有j个块情况，答案实际均摊到f[][0~j]上了，正常统计即可
loj2051「HNOI2016」序列考虑莫队，转移代价用单调栈预处理
loj2052「HNOI2016」矿区平面图转对偶图，取生成树，树上差分即可
loj2053「HNOI2016」大树分类讨论，2和5看末尾算，其他的使用莫队，需要两个后缀同余，问题转化成区间相等数对的对数
AGC041CDominoQuality构造
AGC041DProblemScores仔细思考题目限制，珂以将问题变为前一半大于后一半，列出dp，前缀和优化
AGC041EBalancingNetwork对于1，bitset暴力检查，对于2，大于等于3都行，构造下即可
AGC040CNeitherABnorBA发现要删AB的话，AB奇偶性一定不同，将偶数位置AB互换，不能出现AABB，总数减去A和B分别超过一半个数即可
loj2054「TJOI/HEOI2016」树显然可以树剖/LCT，但是太麻烦，考虑倒序并查集
loj2055「TJOI/HEOI2016」排序1.线段树合并分裂2.二分答案，将原序列转化为01序列，这样排序就很方便
loj2056「TJOI/HEOI2016」序列正常dp，有限制，cdq优化
8.25
毕竟是鸽子日记（）
loj2057「TJOI/HEOI2016」游戏套路的建图，套路的网络流
loj2059「TJOI/HEOI2016」字符串二分长度mid，求出rak的区间，主席树上判定是否有属于这个区间的rak
loj2060「HAOI2016」食物链裸的拓扑排序
loj2061「HAOI2016」放棋子障碍每行每列有1个，交换下顺序，能换成在i行i列，问题就变成了求错排数，高精即可
loj2062「HAOI2016」地图看到仙人掌，直接圆方树，剩下的可以线段树合并/dsu/莫队之类的算法求出
loj2063「HAOI2016」字符合并只有01，且合并区间长度很小，考虑区间dp和状压结合
loj2064「HAOI2016」找相同字符求lcp长度之和，可以用合起来的串的贡献减去两个串单独的贡献。height性质很优美，求贡献时运用单调栈
loj2065「SDOI2016」模式字符串可以拼接，所以点分治，判断相等哈希即可，卡常
loj2066「SDOI2016」墙上的句子最小割，建图不在此赘述
8.26
咕咕咕，SDOI不可做
loj2069「SDOI2016」齿轮带权并查集即可
loj2071「JSOI2016」最佳团体分数规划，然后树上背包判断
loj2072「JSOI2016」独特的树叶树上hash，无根树，换根转移
loj2073「JSOI2016」扭动的回文串在A串B串中枚举回文串，二分加哈希扩展
loj2074「JSOI2016」灯塔不用决策单调性，根号暴力即可2loj2075「JSOI2016」位运算考虑状压出单独一段状态，构建矩阵，矩阵快速幂
loj2076「JSOI2016」炸弹攻击模拟退火是屑，明天补计几做法
8.27
loj2076「JSOI2016」炸弹攻击考虑最优状况，一定有敌人在圆上。分两类处理，第一类圆的半径为R，选择一个敌人作为圆周上的点P，考虑对于每个建筑和敌人，求出圆心相对于P的角度范围，扫描一下即可得出答案；第二类圆的半径小于R，对于每个敌人，枚举两个建筑，二分出圆的最大半径，求出答案
loj2078「JSOI2016」无界单词先求出无界单词数量的递推式，求第k时按位考虑，假设是a，对比目标排名和钦定是a的方案数，大力计算
loj2079「JSOI2016」轻重路径不知道为啥现在网上主流做法变成了离线，写的又臭又长。考虑二叉树的性质，是重儿子的话，siz一定大于等于父亲siz的二分之一，二分去维护
loj2081「JSOI2016」反质数序列分奇偶建图，和为质数连边，求最大独立集（不知道为啥当时想起了零糖麦片）
loj2082「JSOI2016」炸弹攻击2每个S做极角排序，双指针扫一扫，前缀和查询贡献
AGC039BGraphPartition判定二分图，大力搜索
AGC039DIncenters取两点间弧的中点构成的三角型的垂心的期望，垂心期望由欧拉线得出
8.28
咕咕咕
loj2083「NOI2016」优秀的拆分算下以某点开头/结尾形式为AA的串的数量，枚举A的长度，设置关键点，sa求LCPLCS，区间加用差分实现
loj2084「NOI2016」网格就是随便讨论讨论
loj2086「NOI2016」区间按照区间长度排序，twopointers加线段树维护
loj2090「ZJOI2016」旅行者考虑分治，每次从长边中点断开
8.29
要开学了，真正的鸽子time开始了
太久没学oi了，失恋测失恋了
zroi1492stonehint说答案小于等于8，按mod6的余数分类，有两种选择的根号暴力扫一扫
zroi1533palindrome考虑把每个点扩展的最长回文串用马拉车求出（二分加hash也可），在树状数组上数一数即可
zroi1534random考虑树是随机的，树高是根号级别的，考虑每条链，预处理dp算出连前面每个点的期望贡献次数，大力数一数即可
8.30
zroi529圣诞树考虑叶子节点必须连边，最小边数为叶子节点数除二上取整。考虑构造，叶子权值为1，非叶子权值为0，求带权重心，不同子树间连边
zroi530染色一定有个点连向其他所有点边的颜色相同，删掉这个点和它连得边后，必然还能找到同样的，把一个点的颜色col定义为颜色相同时的颜色，那么S'的所有点的col一定相等，随便数一数即可
zroi531外壳特考虑把贡献的柿子写出来，发现除了对应的乘积，其他都是常数项，考虑带权最大匹配，KM或费用流解决
zroi543GoodBye2018发现贡献能够分成两段路径的算，考虑树形dp，在lca处合并答案
zroi544Hello2019可以变成mod2意义下的，考虑消去1的条件，跟括号序列，类似的在线段树上维护
晚上开了场cf，打的很自闭，c特判输出写挂，wa了7发，d博弈没来及写完，果然我不太适合cf（）
8.31
早上去学校报到，发现班上周围数竞物竟化竞生竞都有
CF1110DJongmah以前写过的麻将题，考虑同种顺子不超过三个
CF1110EMagicStones差分数组中的元素不会变，判一下即可
CF1110FNearestLeaf维护一个点到所有点的距离，建线段树，考虑这个点移动，相当于区间加减
CF1110GTree-Tac-Toe考虑对于每个白点，替换成无颜色的一个特殊结构，那么大力判一判即可
CF1401EDivideSquare用欧拉公式转化成求点数边数，扫描线即可
CF1401FReverseandSwap就是线段树上打打标记，出题人好像有bitmask做法
CF449AJzzhuandChocolate整除分块
CF449BJzzhuandCities最短路一下即可，记录一下最短路数量
CF449CJzzhuandApples枚举质数，把倍数两两配对，如果奇数个，剩下2*p，这样剩下的也能最大化配对
CF449DJzzhuandNumbersfwt+容斥的裸题
晚上复习下去年六校的题
nflsoj446【六校联合训练CSP#1】流量求出最大生成森林，这是可以不询问的，注意权值小于0的一定要询问
nflsoj448【六校联合训练CSP#1】假摔考虑(A,B)的取法，发现(A,B)之间元素一定小于等于A和B，否则显然不优。单调栈求出所有(A,B)，按A排序，离线下来，倒序操作，每个(A,B)相当于区间加，查询就是普通查询
nflsoj449【六校联合训练CSP#2】文体两开花维护所有节点子树里到该节点距离小于等于1/2的点的权值异或和，修改和查询都很大力
nflsoj450【六校联合训练CSP#2】国际影星设f[1/2][S]表示从1/2出发，只考虑S内连边，能到达所有点方案数，最后总方案数减去没有交集的方案数
nflsoj451【六校联合训练CSP#2】零糖麦片考虑差分序列，变成选两个差为奇质数的点，由哥德巴赫猜想，得出差为奇质数贡献为1，偶数贡献为2，奇合数贡献为3。先二分图最大匹配出奇质数，再分奇偶匹配。或者直接KM/费用流带权匹配，由于不是二分图，要写带花树，好像复杂度不星啊
nflsoj452【六校联合训练CSP#3】序列考虑每个位置数为[0,m-1]，那么在每个位置都有唯一的方案形成m的倍数，有m-1种方案不成为m的倍数，直接枚举m倍数数量计算
nflsoj453【六校联合训练CSP#3】图神题。给所有点随机染上k种颜色，选取所有颜色不相同的点构成答案，此答案可以状压求出，多随机几次，就能行
nflsoj454【六校联合训练CSP#3】商店设dp[i][j]表示看到第i个物品，积分大于等于j，金钱小于等于j的最小声望，考虑又f[i-1]中一段连续的区间转移，单调队列优化
9.1
开学了，开启大鸽子模式
CF833ATheMeaninglessGame乘起来，开三次根号，判是否整除
CF833BTheBakery考虑朴素dp，发现每次是前缀转移，考虑向后移带来的贡献，应该是前缀的一段后缀区间加1，线段树维护
CF833DRed-BlackCobweb拆成两个限制，就可以点分治大力合并
CF832CStrangeRadiation二分答案，向左向右算可行区间并，判断是否有交
CF832DMisha,GrishaandUnderground大力树剖，枚举三种情况，大力求交
CF832EVasyaandShifts考虑有四个，又是模五意义下的，相当于不用考虑数量，高斯消元，如果剩下i个方程没有用，那答案就是5^i，无解答案是0
CF830BCardsSorting操作形成环，断环为链，复制一倍，线段树维护最小值位置
CF830CBambooPartition把取模换成整除，移项，整除分块处理
CF830DSingerHouse任何时候都能连到根，所以子树内任意链都可以连到跟，考虑f[i][j]表示i子树内有j条链的方案数，满二叉树，这个i实际表示深度
9.2
白天在学校vpdiv1，我只做到d，pmt快速把ef口胡？
CF827AStringReconstruction每个点记录下从这开始最长的
CF827BHighLoad按%k余数讨论下，随便构造
CF827CDNAEvolution发现|e|很小，考虑对于每个长度，按取模后余数分类，建立树状数组
CF827DBestEdgeWeight先kruscal找出最小生成树，对其树剖，对于非树边，最大权值为生成树上两点之间最大权值减一，对于树边，最大权值为跨过这条边的非树边最小值减一。维护两个线段树，第一个区间最大值，第二个每个非树边区间取min，区间最小值
CF827ERustyString先当带有通配的做，NTT即可，发现是未知字符，对于每个长度，判断它的倍数是否都符合，这是调和级数，复杂度仍然单log
晚上回家随便口胡了些题
CF1156CMatchPoints好像去年写过（），结论是，从中间分开，twopointers扫描。不会的话，可以二分，取出前mid和后mid，判断可行性
CF1156D0-1-Tree实际记录f[i][0/1]表示i点子树来的链，最后一条边为黑/白，换根dp即可
CF1156ESpecialSegmentsofPermutation先用单调栈，求出每个数成为最大值的最左最右端点，在两边个数少的里枚举，判断是否可行，看起来是\(O(n^2)\)，但实际仔细分析，发现是单log
CF1156FCardBag考虑一种卡片只有一张的概率，这样可以很方便的算出获胜概率，设f[i][j]表示看了前i张牌，选了j个的概率，暴力是\(O(n^3)\)的，前缀和优化一波变成\(O(n^2)\)
CF1155EGuesstheRoot实际，询问11个点，拉格朗日插值一下（自己思考一下，都是模意义下的，所以不会出错），再枚举每个点带入求值即可，不知道为啥询问数多了那么多
CF1154FShovelsShop恶心人的题。先考虑显然的贪心，从小到大排序，取k个小的，每次优惠，肯定选连续的一段。考虑暴力dp，我原以为是\(O(n^2)\)的，再看下题，发现\(k\leq2000\)，复杂度实际是\(O(k^2)\)的
CF1154GMinimumPossibleLCM枚举gcd，暴力找倍数，复杂度是调和级数
CF1153FServalandBonusProblem考虑长度为1的，答案就是它乘l，考虑每个位置x的答案，最终结果就是0~1的积分。把每个位置的式子列出来，用NTT优化。注意，这里算出点值不要转回去，所有多项式点值累加起来最后再NTT回去，复杂度为\(O(n^2)\)
9.3
今天whk作业写的好累，在学校都没有vp
CF1153EServalandSnake对于一个矩形，如果查询结果是奇数，一定有头尾在里面，考虑对于每行每列查询并二分答案，这样会刚好超限，对于最后一行，实际不用判断它是否有头和尾，那就刚好满足限制
CF1152DNekoandAki'sPrank对于最大匹配，应该是每个奇数层都完全匹配，这样就直接设f[i][j]表示i个左括号，j个右括号的合法方案数
CF1152ENekoandFlashback考虑在min，max中，两个数各出现一次，给这两个值连边，对于度数不为偶数的，就是序列的开头或结尾，dfs即可，为了降低复杂度，用下当前弧优化
CF1152FNekoRulestheCatniverse设编号小的为前面，编号大的为后面。由于m很小，考虑记录一个点后连续的m个点是否被用过，这样就保证不重复了，且这个点可以出现在用过的点之间。考虑状压dp，设f[i][j][S]表示所有点都在i以及后方，选了j个，后m个点状态为S。普通状压dp可以过F1，考虑这个dp的转移系数和S无关，把后两维合并，矩阵快速幂优化即可通过F2
CF1151ENumberofComponents两种做法，sol1：对于每个数，当它为联通块中最大值时，让他产生贡献，单调栈求出控制区间即可。sol2：联通块数目等于点数-边数，分开来数，点数好算，考虑每条边被算几次
CF1151FSonyaandInformatics最后序列是0……01……1，设前面有连续c个0，设f[i][j]表示前i次操作，前c个位置有j个0的概率，每次从j-1，j，j+1转移过来。每次操作独立，所以转移的系数相等，矩阵快速幂优化
CF1149BThreeReligions记nxt[pos][ch]表示原串中pos后最近的ch的位置，设f[i][j][k]表示三个串分别匹配到了i，j，k位在原串中的最小位置，暴力dp。考虑加字符操作，实际有一维状态变化量为1，两维状态变化量为O(|S|)，所以单次添加复杂度是\(O(|S|^2)\)（这里S指s1s2s3的长度，不超过250）。删除啥都不用管
CF1149CTreeGenerator考虑在括号序列上表示两点间的距离，实际就是完成匹配后剩下来的括号数量（配对的就表示走入子树又走出子树），所以题目就是要求括号序列的子串配对后剩下的长度最大值。按照套路，左括号权值为1，右括号权值为-1，每个区间的答案，可以变成从中间任意一点断开后面的权值和-前面的权值和最大值（画个图，实际发现那点是树上的lca，那这样正确性显然），线段树维护一堆东西即可
CF1149DAbandoningRoads把a叫做轻边，b叫做重边。对于有轻边路径的两点，最小生成树上两点间不会有重边。只考虑轻边，原图变成若干个联通块，由前面得出，在符合题意的路径上，不会回到已经路过的联通块。把联通块是否访问压成状态，设f[S][u]表示状态为S，走到u点最短路，只有两种边权，相当于01bfs，但这样无法通过。考虑大小小于等于3的联通块，实际不需要判断，因为最短路的过程就能自动避开反复横跳，所以状态大小除了个4，复杂度为\(O(2^{n/4}m)\)
CF1149EElectionPromises对图拓扑排序，将点分组，每个点的组是后继组的mex，考虑val表示每个组内的异或和，当val初始状态不全为0时，必定能一步变为全0（找到最大第k组的非0，修改，这样[0,k-1]都能被任意修改），val全0时同nim一样，可以模仿（对方对全0操作一定会出现val非0，保证自己操作后val全0，而所有为税变成0时val也是全0），所以先手必胜
CF1148EEarthWindandFire对于优秀的答案，相对位置是不会变的，考虑t[i]-s[i]，若前缀和有负，就不能构造出合法答案，不难发现，这个类似于括号序列，那么处理就是跟括号序列一样做单调栈
CF1148FFooFighters每遇到一个一就取相反数，等价于奇数个1取相反数。考虑每个数最高位的位置，从低位到高位贪心，对于当前位置，记录sum在前面的操作下最高位为当前位置的val和（这里的val是被低位操作翻转过的），如果符号相反就不管，如果相同就再此取相反数，并对于每个本位是1的val都永久修改，这样，对于每一位，带来的贡献都和原来符号相反，最终肯定符号相反
9.4
白天想题
CF1147DPalindromeXOR异或后首位是1，枚举小的数的非零首位位置。考虑构建图论模型，必须相等连边权为0的边，边权不相等连边权为1的边，其他不管。把通过0连接的点缩点，判定森林是否是二分图，如果是，贡献就是2的联通块个数减一次方，注意，一开始已经有确定的一个联通块了
CF1146DFrogJumping找规律，发现n大于等于a+b时，答案是\(\frac{n}{gcd(a,b)}+1\)，整除分块，小于这个的，写个类似最短路的算法解决
CF1146EHotisCold考虑对值域维护线段树，一开始i位置值为i，每次修改，按到绝对值的关系，发现只有两种操作，区间取反和区间覆盖符号，线段树维护。值域有负的，那就全体加上1e5即可
晚上小号div3，第一次独自ak，1:29就AK了，全是1A，但是前几题手速不够，最后rak34，上了626ptsA模拟B使较小的尽可能小C枚举公差直接构造D按位贪心E二分出每个区间的范围随便数数F就大力dp
9.5
上午物竞，非常自闭
晚上失恋测
zroi1539小W与伙伴招募考虑对每一天贪心，尽量选最小的。维护两颗同构线段树，按价钱建，一颗是模板树，乘天数就是总量，另一颗是记录每种用了多少，这样就能线段树上二分，若左边个数不够，左边打上清空标记，递归右边，否则直接递归左边
zroi1540小W与制胡串谜题考虑自定义排序，按照a+b和b+a的大小排
9.6
上午七连测
zroi1535机器人指令就是个模拟
zroi1536逛餐馆考虑贪心，通过最远的位置cur，分两类考虑，前后分别线段树取min，当点权值变成inf，如果取后面要改cur和前后cur之间的贡献
zroi1547符文师实际就是背包，一定存在一种删除顺序，使得任意删掉张数小于等于总数的方案成立。我当时只会断环为链区间dp
下午ct的课
CF1101DGCDCounting每个数最多7种质因子，对于每个质因子，保留边权是它倍数的边，求森林每棵树的直径，边数不超过7n条
CF1101FTrucksandCities考虑dp，设f[i][j][k]表示i到j，分类k段最大一段的最小值。暴力dp会t，考虑从max(f[i][pos][k-1],dis(pos,k))转移时，前面是单增，后面是单减。跟冰火战士，pos显然在交点处最优，这个pos珂以twopointers更新
CF1100EAndrewandTaxi二分答案，保留边权大于当前mid的边，判断是否有环
CF1099FCookies对于以每个点为终点，都进行一次贪心取饼干，树状数组上二分实现。每个点的答案，应该是该点为终点的答案和儿子中非最优的最大值，答案就是根节点的答案
晚上cqh的课
晚上div2，过了4题，上了440pts，第二天一看，unr了（桌子发出响声）
CF1405APermutationForgery翻转序列即可
CF1405BArrayCancellation按顺序贪心，每个i是正的，就把\(a_i\)变成0，\(a_{i+1}\)加上\(a_i\)，最后统计下负数之和
CF1404ABalancedBitstring考虑k个一循环，判下循环节是否可能，0/1确定的个数是否超过k/2。我一开始想了个差分约束（人类迷惑），1是+1,0是-1，限制就相当于区间和为0，即前缀和差为0，拆成两个不等式（）
CF1404BTreeTag考虑树上一步最远距离是直径，把na，nb与直径比小，如果na*2>=nb或者dis(a,b)<=na，Alice必胜，自己可以在纸上画画图
9.7
白天文化，晚上打膜你赛，是我校以前选手出的（tjw鸽鸽出的，ytq，zyd，ct当时考的）
拼正体是Atcoder题，我不知道题号，大体就是给你n个正方形，四角有数，拼正方体，要求角上三个数相等，求方案数，n4e2，数1e3考虑枚举上下面，通过哈希查找可行数量，就是个纯码力题（虽说场上就我一个没想到思路，枯了）
K错排AGC005D考虑容斥。每一次，强制k个点不符合，考虑之和正负k有关，考虑按模k余数分别考虑，直接大力dp，设f[i][j][0/1][0/1]表示看到第i个数，选了j个不合法，第i个数和它加k是否使用过，大力转移
9.8
白天文化课，晚上cf，然而睡过头了
CF1404CFixedPointRemoval跟zroi前几天那个背包一样，一定存在一种合法操作使得都能删完。那我们发现递推式后，二分找到最多前x个不动，可以主席树上二分，少个log。当然想离线下来树状数组上二分也行
CF1404EBricks考虑一开始，每个点由单独一个砖块覆盖，每次能删两个砖块间的边界，但砖块不能拐弯。每个边界建一个点，一定不能共存的两个点间连边，求最大独立集，答案就是原来数量减去最大独立集大小。考虑这个图应该是个网格图的子图，所以是二分图，最大独立集转化为最小点覆盖即最大匹配
9.9
没写啥题（调题调不出来）
zroi1548魔法师一开始写了个set的大模拟，失败了，写了5k。后来，写了个权值线段树大模拟，写了3k
CF1407CChocolateBunny两个数之间询问(i,j),(j,i)两次，返回值中较大的就是这两个数中较小的，记录最大值位置，按顺序询问最大值和当前节点，更新答案。总次数为n*2-2
CF1407DDiscreteCentrifugalJumps单调栈预处理转移，暴力dp即可
9.10
白天文化，下午化（数）竞（数）测试，晚上校内oi课（）
ybtojAD1D种地收益考虑设f[i]表示考虑完i之前状况的最大收益，f[i]=max(f[i-1],max(f[j]-s[j]+cost(j+1,i))+s[i])，考虑线段树优化，有区间[l,r]，在dp到r时给[0,l]的加上贡献即可
ybtojBD1A简单游走直接最短路，转移时考虑下等待的情况
ybtojBD1B卡牌选取按位考虑，有贡献是选奇数个1，枚举该位1的个数，组合数随便算算就出来了
ybtojBD1C合影队形直接连边，有环一定不行，剩下是森林，直接树形dp即可
ybtojBD1D公交运输显然按照每种模数和余数考虑来转移dp，发现有斜率优化，但是这个横坐标不单调，所以要用数据结构转移，肯定会T。仔细思考下，发现最优情况下，v一定是单调增的，那么对于v单调栈的同时，进行斜率优化
zroi87树状数组发现对于pos位置修改，产生变化的位置个数是popcount(pos)，对于l-1,r的两次修改，被修改两次的个数是popcount(lcp(l-1,r))，考虑dp，f[i][0/1][0/1][j]表示只看二进制前i位，l是否等于r，r是否等于n，lcp中有j个1的方案数
zroi88雇佣妹抖套路题。联通块数等于点数减边数，查询大于等于v的点数和边数（此处边权的定义是两边点权的max），先离散化，再树状数组维护即可
zroi89建造对于距离之和为S的状况下，组合数很好求出答案，设f[i][j][k]表示考虑了前i个数，有k个空位填更大的数，当前S为j的方案数
zroi490StandardT1Problemf(x)值域很小，暴力枚举即可
zroi491TreeProblem考虑树形dp，设f[i][0/1/2]表示子树已经完全断绝/只剩X/只剩Y的最小代价。实际，直接建图跑最小割即可（）
zroi492PermutationProblem垃圾题（确信），发现k的值很小，考虑状压这连续的2k位。这样显然k较小时过不去，但是发现转移方程系数都一样，可以矩阵快速幂优化
9.11
昨天化竞全校rk21，没有丢oier的脸，白天想了套18年失恋测的题
zroi329巡逻从小到大贪心即可
zroi330矿石排序后扫描线，每次产生贡献就是没开采过的非空子集个数乘上开采过的子集个数，set实现即可（我一开始不知道为啥在想bitset，大概也能过（确信））（ps：我一开始没看见每种只有一个区间，所以自闭了很久（））
zroi331括号序列好熟悉的题啊，这不就是蔡老板与公司，哪个出题人这么能搬题啊（恼）在trie树走，如果下个字符是父亲到当前节点的字符，那就跳回父亲，贡献是父亲访问次数；否则就继续向下。
这场三题代码都小于十行，希望有生之年现场能遇到这种题（吉老师现场不可能这么良心的吧）（ps：我在学校想这些题，在草稿纸上比比划划，被老师当作不务正业，在纸上玩游戏（恼））
CF744AHongcowBuildsANation搜索求出每个所带联通块大小，把没有搜到的全部放到大小最大的，每个联通块连成完全图。正确性显然
CF744BHongcow'sGame交互题。考虑四个格子时，询问左上角，能得到左下角的最优解，询问右下角，能得到左上角最优解。那就2的高次幂向低次幂分治即可
CF744CHongcowBuysaDeckofCardsn很小，每次省掉的也很小（重点），考虑状压dp，设f[S][i]表示选了S集合，红色省了i个，蓝色最多省了多少，大力转移即可
CF744DHongcowDrawsaCircle好熟悉的题啊，这不是和「JSOI2016」炸弹攻击几乎一模一样吗（）枚举蓝点，极角排序，二分半径，求出每个对应的区间，twopointers即可
9.12
上午膜你赛，想了想就去vpcf了
ybtojBD2A互质数对我考场上的想法是，对序列中每个数，建出和别的数gcd是否为1的bitset，每个质数建bitset表示每个数是否含此因子，gcd是否为1的或起来取反即可。查询就是查and后的bitcount，也许能卡过去。正解是用莫比乌斯函数表示贡献，发现只需统计μ(x)不为0的x倍数的个数，单次复杂度是2^质因子种数（种数小于等于8）
ybtojBD2B树上取模仔细看一下，发现就是把CF438DThechildandsequence搬到树上，树剖后区间取模单点修改区间查询，每次取模数字必定减小一半，线段树上记录下子树是否全为1，暴力修改复杂度就对了
ybtojBD2C网格游走有环一定是全取到0最优，所以tarjan缩下点，算下等效点权，就变成了了dag，答案就是最长路。每次走到0的期望是2i，应该珂以数学归纳法证明，考场上没想到
后来vp了一场远古div1
CF763ATimofeyandatree一条边两端颜色不同，必选其中一个端点，判定交集是否为空
CF763BTimofeyandrectangles四色定理证明（），本来以为要建图，发现题目有优美性质，边长是奇数，就代表按某点奇偶分配即可
CF763DTimofeyandaflattree就是大力hash，换根转移，用set和multiset维护hash值
zroi1490cut一定是Yes（出题人的锅，我不背），考虑每条边由编号小的连向编号大的，这样就是dag，对于每个点，判断父亲中哪种少就选哪种，所以保证大于等于一半。由于从某点开始，所以能保证第一层全选，所以严格大于一半
9.13
上午普转提七连测，好自闭啊
zroi1549覆盖根据期望的线性性，考虑每个点选中的概率，相加就是答案
zroi1550糖果考虑按照奇数构造，偶数的话先随便选一个。按照a排序，选取最大的，剩下按顺序两两配对，取b大的，b显然满足，最劣情况下，即a每次选较小的，有(a2-a1)+(a4-a3)+…… zroi1551染色二分总数，把子树外也转化为子树内，剩下求出每个点的范围，判下根节点是否满足（场上一直在想差分约束，不会子树外的） 下午gutc膜你赛 T1棉花糖超好吃早年省队集训题，就是多随机化几次，再每次基础上微调，这样正确率就很高了。上一次见到这种操作是六校 T2xor先meetinmiddle，将前半部分插入trie树，并在节点上更新最大值标记。后半部分在上面查找，若m这一位是0，走向相同01的子树，否则走向不同01的子树，将相同01的子树更新答案 T3乌帕对于每种颜色，大力倍增即可 晚上还是gutc膜你赛（） T1小奇挖矿2考虑用4和7，能凑出所有大于17的数，那就暴力dp，设f[i]表示选取第i个矿最多矿石数，转移是个相距大于17前缀最大值与小于等于17的暴力枚举 T2小奇的矩阵推一下式子，发现答案是路径长度乘上平方的和减去和的平方，发现权值很小，考虑f[i][j][k]表示走到i行j列，和为k，平方的和的最小值，暴力转移 T3小奇的仓库发现要异或的很小只有15，那么就是分val%16和val/16分别考虑，大力换根dp，f[i][j]表示以i为根，长度模16为j的个数，g[i]表示所有路径长度除16的和 9.14 晚上gutc膜你赛，1.5h连想带写，不拍直接交，100+100+100->90+20+100 晚上cf，被AB把心态搞没了，就花了1h看了下题 CF1848ABuyingTorches模拟题，样例出错差评 CF1848BNegativePrefixes从小到大和从大到小比个最优 CF1848CMortalKombatTower直接线性dp,f[i][0/1]表示打到第i个怪物，0/1打的所需最小代价 CF1848DTrashProblem垃圾题（bushi）发现是最大值减最小值再减最大的相邻之差，写个能维护前驱后继的数据结构，splay/set即可 CF1848EExpectedDamage假设有k个大于等于b，如果k 大概后几天主要是补题，vp和六校 9.15 白天看了下ybtoj普及的后两题 ybtojAD2C最小差值求最小差值生成树，\(n\leq200,m\leq1000\)算法1，将边排序，枚举边权最小的边，向后做最小生成树的过程，求出差值，\(O(m^2\logn)\)算法2，将边排序，枚举边权最小的边，二分差值，暴力加边判断，在mid不成立时继续利用前面的边复杂度级别同算法1算法3，二分差值，twopointers扫描。想到这里，发现这个差值并没有意义，直接twopointers扫描，用LCT维护，每次加入权值大的(u,v)，如果联通，那么就删掉原u到v路径上权值最小的边\(m\log^2n\)（看见这题，仔细想想发现加两个0我也会，去问pmt，他直接告诉我这是板板题，我还是题做少了） ybtojAD2D三元组数对于\(i 晚上vp了一场早年div1，排名出奇的高？ CF741AArpa'sloudOwfandMehrdad'sevilplan如果有点不在环上就是-1。否则求出每个环长，再求lcm，如果是二的倍数，要除个2 CF741BArpa'sweakamphitheaterandMehrdad'svaluableHoses并查集后，大力背包，但由于有的不能同时选，不能一维数组，所以要用个滚动数组 CF741CArpa’sovernightpartyandMehrdad’ssilententering连边表示不同，夫妻连边，2i-1与2i连边，一定满足题目要求。发现这个图是二分图，所以一定有解，染色即可 CF741DArpa’sletter-markedtreeandMehrdad’sDokhtar-koshpaths路径上每个点是哪个字符，二进制权值上哪一位就异或1，算出从根出发到每个点的权值。如果两个点之间路径合法，那么两个异或起来只有0/1位是1。考虑答案是由子树合并来的，运用dsuontree就能很方便的解决 看了下前几天失恋测时鸽掉的cf CF1406CLinkCutCentroids一个重心删完再连同样的；两个重心的话，把一个siz最大的子树的叶子切掉一个，接到另一个重心上；重心在树上最多由一条边相连，所以最多两个重心 CF1406DThreeSequences考虑b单调不减，c单调不增，答案是\(max(c_1,b_n)\)。进行贪心，设\(c_1\)为x，发现\(b_n=a_1-x+\sum_{i=2}^nmax(0,a_i-a_{i-1})\)，显然\(c_1=b_n\)时最优，维护相邻差即可 9.16 白天想18失恋测 zroi352数组计数设f[i][j]表示选了i个数，和为j的方案数，转移用个前缀和优化 zroi353旅行答案是点集间边集大小乘二减去深度，每次暴力向上跳加边，每条边只被加一次，复杂度是正确的 晚上vp了两场cf CF735CTennisChampionshipf[i]表示i轮最小要多少人，f[i]=f[i-1]+f[i-2] CF735DTaxes哥德巴赫猜想，质数是1，偶数是2，能拆成2+质数的奇数为2，其他奇数为3 CF735EOstapandTree设f[i][j]表示i子树中离i最近黑点与i的距离 CF736DPermutations线代神题。发现i可以填j，相当于矩阵i行j列为1，方案数就是行列式。考虑求出包含所选限制的方案数，实际相当于去掉该行该列的行列式，由于是模2意义下，我们只需求出伴随矩阵就能得出答案，通过矩阵求逆即可 CF739AAlyonaandmexmex最大值一定是最短区间长度，然后每个位置填pos%mex，显然一定满足 CF739BAlyonaandatree每个点向上倍增，树上差分即可 CF739CAlyonaandtowers挺裸的线段树，但是写挂了（咕咕咕）考虑维护差分序列，区间修改变成了单点修改，题目询问的相当于求最长连续正再连续负的长度，线段树维护一坨东西即可 9.17 晚上校内训练 1.JSOI2008最小生成树计数所有最小生成树每种权值边的数量都是相同的，可以直接暴力。可以枚举边权，把不是该边权的缩成点，再连上该边权的，矩阵树定理求出该边权的选择方案数 2.BJWC2010严格次小生成树求出最小生成树，枚举非树变，求出非树边两端点间刚好小于它的点，LCT维护（） 3.Sightseeingtripfloyd求最小环 4.Telephonelines直接大力dp，或二分权值，大于的为1，小于的为0，跑01最短路 5.农场派对边正的反的分别跑一次最短路 6.最短路计数求最短路时，顺便转移次数 7.黑暗城堡求出最短路后，算出每个点转移方案数，乘起来即可 vpcf CF715APlusandSquareRoot推柿子 CF715BCompleteTheGraph每条未知边边权设为1，先最短路一次，若长度短了k，再最短路一次，每次对边权自定的边，改变其权值，使dis尽力加k 9.18 晚上自己vpdiv1，B题2500，自闭了啊（） CF704AThor不要看中文翻译，剩下就是队列模拟模拟了 CF704BAntMan考虑建图，把贡献摊到边权上，设f[i][j]表示考虑了前i个点，形成了j条链的方案数，大力分讨合并。这题实际有高深的贪心做法？ CF704DCaptainAmerica每一行每一列看做点，若有盾牌，行向列连边，流量为1，源向行连边，流量就是最少到最多，列向汇同理，剩下就是上下界网络流板子 CF704EIronMan显然可以树剖，使得问题变成线段上的问题，考虑只会相邻线段先产生交点，用set维护即可 9.19上午ybtoj膜你赛 ybtojAD3B剑的比试本质是辗转相减求gcd，用辗转相除gcd算次数 ybtojAD3CLCS问题考虑到每种数只有五个，所以我们只用记录合法转态及其转移。(x1,y1)转移到(x2,y2)的条件是x1 ybtojAD3D到达层数考虑xyz很小，考虑膜x意义下最短路，最后计算下能加上多少个x ybtojBD3A或位运算按位考虑，先对或为0的操作，显然全必须是0，再看或为1的，是否有位能填1 ybtojBD3B字串修改相邻的相同字符缩起来，判断是否相同，再判下能否个数的问题 ybtojBD3C波动序列设f[i][j][0~3]表示选i，目前第一行/第二行/第三行递增/第三行递减时最长长度，树状数组优化 晚上正睿失恋测，dmy的题果然效果拔群 zroi1564小好吃说鬼话设f[i][j]表示s看到i，t看到j的最小编辑距离。考虑大于50不需要计算，所以将状态简化为\(f[i][v\in[-50~50]]\)，表示s看到i，t看到i+v时最小编辑距离（有负的，全局加个50即可。实际场上想到了状态的简化，但还是没写出来，看来我还是菜） zroi1565小好吃很呆滞场上只会提答的30pts。考虑要求前100位，我们只需要考虑前200位，维护前缀最小和最大，设答案在[L,R]。如果每次乘上最小不超过R，直接乘，否则更新前缀最小和最大，直到乘上最小满足 zroi1566小好吃在摸鱼倒序贪心，染完一个可以染的节点后，没染过色中它前后两个位置不能染本种颜色 晚上有场cf，质量不太行，所以没打 CF1419BStairs合法的只有高为2^k-1的台阶 CF1419CKilljoy发现答案只有0/1/2，直接分讨 CF1419DSage'sBirthday二分答案k，取最小的k个，和最大的k+1个，看下能不能插在一起 CF1419EDecryption考虑每两个质因子之间填最小公倍数，剩下的插入其任意两质因子之间 CF1419FRainofFire二分答案，将能互相到达的点连起来，分讨下1/2/3个联通块的情况，大于等于4的一定不行 9.20 下午gutc膜你赛，信心场 T1电子邮件按题意模拟即可 T2游戏记f[i]表示看到第i个数并强制选时，最长的长度。记g[j]表示当前a[i]是j的倍数f[i]的最大值。每次f[i]暴力枚举约数从g转移，转移完再暴力枚举约数更新g T3删边最短路计数，求出单源最短路后数下前驱数量并乘起来即可 晚上gutc膜你赛（其实爆零，只因忘写文件，300->0） T1疯狂生长按题意模拟即可 T2两极反转丧心病狂的二合一（）正向边权为0，反向边权为1。对于图，直接01bfs/最短路。对于树，进行树上差分，拆成(s,lca)与(lca,t)两段去统计 T3地震数字最长四位，那么就一定有长小于等于12的循环节。线段树上预处理区间进行011次操作的结果，区间修改打标记，下放标记时相当于011次的这个结果进行转动，暴力维护 9.21 晚上gutc膜你赛 T1选数显然S为排序后相邻两数差的最小值。二分S，暴力线性贪心 T2化学反应按照B排序，B从小到大考虑，就相当于要找前面与现在a最近的点，维护个set查前驱后继 T3天际线将点排序，设f[i][j][k]表示i~j个点，高度大于等于第k大的都处理好的最小矩形数 9.22 补题订正 ybtojBD2D漫步校园考虑把p拆开，发现是选择两条路径，数列相同为某种的概率，设f[k][u][v]表示走了k步，第一条路径走到i，第二条路径走到j的概率，转移和k无关，矩阵快速幂优化即可（场上只知道是矩阵乘法题，但是并不知道如何去整） zroi1553aria的礼物当k小于等于n/2时，数一下有几个不相等。否则发现有长度为n-k的循环节，每个循环节每一位取出现次数最多的字母 zroi1554神奇位运算按位考虑，区分出三种操作，每一位一定要两个1，一个0 zroi1555终焉之数列考虑变成大于58的数不如变成1，把58以内的16个质因子是否用过进行状压，暴力转移即可，再记录下从哪转移来的 9.23 zroi1556终焉之排列考虑要寻找的是长度为3的等差数列，枚举中间的数，记录下哪些数出现在该数之前，在该权值打上1的标记，当该数左右开始的01序列有不同时，就找到了等差数列。判断区间01序列是否相等，我们用线段树在线维护 整了场提转普 zroi311阿设f[i][j]表示i,j排好序的方案数，从f[i][k]和f[k+1][j]转移来（两个合并排序后只有前面最大和后面最小交换时才能转移） zroi312姨分别算出选了i行，i列的方案数，选至少i个数的概率。最后统计选了i行j列方案数乘上选至少了(i+j)n-ij个数的概率之和。i行j列的概率会被2i*2j次统计到，所以正好就是权值期望 zroi314铁路考虑以每个点为最小的去暴力扩展。我们发现，某个点开始扩展的区间内，其他数作为扩展的起点肯定不会更优，连续相同数不会多次统计。容易证明，每个位置最多被更新log次（一个数列，前面要是后面所有数的倍数，不同种类数字个数是\(\loga\)），所以这样就保证了复杂度严格小于\(O(n\loga)\) nflsoj703【2020五校联考NOIP#5】I'm考虑鸡受到伤害小于等于猫的伤害的概率，我们枚举猫受到的伤害（这个远小于鸡受到的伤害上限），乘上鸡受到伤害的一个前缀和即可。最后答案就是用1减去前面结果 9.24 晚上校内oi训练，数竞教练来教数论（） 晚上cf，技不如人甘拜下风 CF1420ACubesSorting找一下有没有\(a_{i-1}\leqa_i\) CF1420BRockandLever每个数记录二进制下最高位，最高位相同的产生贡献 CF1420CPokémonArmy考虑直接ddp，用线段树维护区间开头为正负结尾为正负的最大价值，swap就是两次大力单点修改（正解好像是贪心） 9.25 晚上校内数竞课，所有题都只会构造，不会证明（除了一个用动态(数学)规划(归纳)证了一下） CF1420EBattleLemmings考虑最小化不产生贡献的0的对数。设f[i][s][t][c]表示看到第i个，用了s次交换，当前连续0的长度为t，用了c个1的最小不产生贡献0的对数。第一维可以滚掉，听说还有斜率优化 nflsoj706【2020五校联考NOIP#6】俄罗斯方块考虑两格为一单位，暴力矩阵乘法 9.26 写ybtoj的模拟赛 ybtojAD4A数列翻转暴力模拟 ybtojAD4B行走方案考虑每步可以向上或向左/右，由向上转向左/右时状态数乘二，矩阵乘法暴力转移 ybtojAD4C子串匹配考虑kmp，如果和上个同种字符距离相等，就可以扩展，或者第一次出现且border长度小于等于一半，可以扩展 ybtojAD4D树上距离考虑树上倍增，记录fa[x][i]表示2i次祖先，p[x][i]表示2i-1次祖先。设f[x][i]表示考虑向上到lca距离小于等于2^i的贡献之和，转移考虑分最高位和非最高位，f[x][i]=f[x][i-1]+f[fa[x][i-1]][i-1]+siz[p[x][i]]-siz[p[x][i-1]]，转移时记得判父亲存不存在之类的问题 ybtojBD4A古老谜题考虑拥有奇数个1的子区间，一定是合法的（只有一个1时不能在两边）。考虑记录奇偶性的后缀和，枚举起点，查出它后继的1位置为p，答案就是p+1位置的后缀和。每遇到一个1，奇偶性翻转一下 ybtojBD4B预算缩减考虑f[x][i]表示x所在联通块，当前大小为i。暴力转移即可，暴力合并即可，看起来是\(n^3\)的，但实际每个点对只会在lca处合并，所以复杂度是\(n^2\)的（我当时还在想fft优化） ybtojBD4C模拟比赛考虑算出每个人的最高最低分数，枚举每个人作为前s人最后一名，考虑最小大于等于其最大的一定在前s，枚举一定在前s的中间选了k个，暴力组合算下方案即可 ybtojBD4D筹备计划先不考虑34操作。根据小学数学，显然最优位置是带权中位数，那么我们需要一个线段树二分。如何计算贡献？考虑吧绝对值拆开，用树状数组维护在位置前后的人个数和与坐标和。考虑34操作，选择位置具有单调性，所以我们需要找到中位数左右两边最近可选位置，再比较哪个答案较小。考虑维护一棵线段树，支持区间赋值，线段树二分（思路很simple，下面开始码力表演，反正我写了6k） 9.27 P2885TelephoneWire考虑f[i][j]表示看到第i个，高度为j的最小代价，绝对值拆开前/后缀转移 P2886CowRelays离散化，直接矩乘即可 P2887Sunscreen考虑原点连向牛，流量为1，牛连向防晒霜流量为1，防晒霜连向汇点，流量为数量，跑最大流即可 晚上深夜cf，小号rating低，只能div2 CF1417ACopy-paste用最小的数给其他所有数加即可 CF1417BTwoArrays1与T-1,2与T-2，……这些不能放一起，当n为偶数时，n/2尽量均摊的放 CF1417Ck-AmazingNumbers对每种数字考虑最小的k值即可 CF1417DMakeThemEqual场上构造WA了，咕咕咕 CF1417EXORInverse考虑贡献只会由第一位不同的产生，建个trie，每次更新左右儿子异或/不异或构成的逆序对贡献，贪心的取即可 9.28 下午班会课请了个假，看了下div3题目 CF1426ERock,Paper,Scissors最小的话跑最小费用最大流，最大直接贪（最小我不会贪） CF1426FNumberofSubsequences枚举b/的位置，讨论前面选a/，后面选c/，暴力求和即可 晚上gutc膜你赛，是以前常高NOI膜你赛 T1朗诵每个数放入数值减去下标的桶中 T2保护数列考虑and的特殊性质，1的个数具有单调性，所以我们枚举右端点时，左端点分成log个区间，在可持久化01trie上查答案 CF1417FNumberofSubsequences考虑倒序并查集，定一个dfs序，一定能使每个查询是一个连续区间，因为倒序并查集合并时，不影响在原操作序列中后面查询联通块的标号连续性。那么就变成了线段树区间最大值的问题了（场上没来及看题） 9.29 Oier的国庆开始了（运动会就咕咕咕） 上午随便口胡口胡题 nflsoj473【六校联合训练CSP#10】数学题考虑裸的dp，按\(p^aq^b\)排序，设f[i][x][y]表示第i次考虑，乘积为\(p^xq^y\)。转移过程同背包一样，所以与顺序没有关系。预处理到k=23，每次暴力查询即可 nflsoj474【六校联合训练CSP#10】城市对每个二进制位单独连边，对于点x，连向\(a_i\)二进制为1的位的虚拟点，边权为指数。跑最短路，答案除二即可 nflsoj475【六校联合训练CSP#10】好♂朋♂友同昨晚保护数列，这题利用or的特殊性质，0的个数具有单调性。将询问离线，倒序扫描钦定左端点，暴力扫右端点值不同的log个区间。线段树/树状数组维护区间加，区间查询 这套题实际去年csp前几天写过，但是昨晚一开始根本没有想到and和or的单调性，我还是太菜了 后来随便开了场cf，又自闭了 CF700AAsFastAsPossible自己画画图，解解方程 CF700BConnectingUniversities贪心。考虑每条边贡献分开算，贡献为两端有标记点的较小值 CF700CBreakUp先tarjin一遍，判是否有割边。如果没有，暴力枚举一条边断掉，再跑tarjan找割边 感谢dyls提供的优致膜你题，又能让我写好几天了 下午开D1，自己会100+35+60 T1序列将奇/偶数填入奇/偶的位置，先分类讨论。考虑如何填最优，同JSOI2018列队，显然填完之后，相对顺序不变时，绝对值差最小。考虑如何最小化字典序，将原位置对应到新位置的关系抽象成有向线段到1~n的数轴上，两个对应的新位置能交换，当且仅当原来方向相同且有交集。线段按照方向分为三类，负，点，正。对于负，区间权值从大到小排序，尽量向后插入，用set维护。同理正，从小到大排序，尽量向前插入 T3比赛场上只想了个n^2的dp，f[i][j]表示前i个人，选了j个成为胜者的概率。剩下就是我想不到的离谱做法，考虑f[i][j]可以从头和尾添加，一共有两种正确的转移方式。联立后，发现形成了f[n][k-1]->f[n][k]的递推式，那么暴力推。当p=1/2时，是个特例，用人类智慧玩一下就能得出答案 T2内存我场上思考的是暴力枚举x，每次二分答案求解。考虑优化，随机化没用过的x，当前二分上限是之前的答案，若之前答案不满足，则不用二分。随机选x，更新答案概率为\(\frac{1}{i}\)，i表示是i次随机。那么期望二分答案次数是调和级数，即\(\lnm\)。总复杂度是\(O(nm+n\logn\lnm)\) T3子集部分分考虑f[i]表示lcm为i，gcd为1的方案数，\(f[i]=(\sum_{d=1}^i[d|i])^n-\sum_{d=1}^if[d][d|i]\)。好像和正解没啥关系？正解考虑，对于每个质因子，必须出现0次幂和最大次幂，这样分4种情况容斥。这样不能通过，考虑没有0次幂和没有最大次幂的方案数是一样的，只需分3种情况，即可通过。分解质因数用pollard'sRho或者奇技淫巧。 9.30 开了D4，自己会25+100+80~100 T1路径神仙构造，蒟蒻只会爆搜。“对于深度为奇数的节点，我们先输出它，再遍历它的整个子树；对于深度为偶数的节点，我们先遍历它的整个子树，再输出它。” T2魔法考虑先利用kmp/ac自动机求出t在s中出现的区间为[l,r]。设f[i]表示强制选i且r T3交集暴力思路是求出每个点x，在选取一个点作为父亲时，子树中选了k个点，且k个点两两lca都是x的方案数，显然每个儿子只能选1个，剩下的全是x上的。预处理每条边的状态，复杂度最多为\(O(nL^2)\)，我不太会算真正的复杂度。从生成函数的方面去考虑，选个点作为父亲，实际就是没有父亲时的生成函数除掉一个一次多项式，所以预处理所有点都作为儿子的\(O(nL)\)，查询时保留多项式除法\(O(qL)\)，即可通过此题 后来随便写了点CF题 CF1327FANDSegments按位考虑，对于and为0时，区间该位至少有一个0，and为1，区间全是1，运用上文魔法一样的思路，设计dp，f[i]表示强制选i位为0的方案数，前缀和优化即可 CF1327GLettersandQuestionMarks对于T建AC自动机。如果S没有？，就直接在自动机上跑即可。设f[i][j][msk]表示看到第i个字符，在自动机上j号节点，？处选用了字符的状态为msk。这个dp显然会超时，考虑？个数很小，中间很多转移都是重复工作。考虑预处理，记录从自动机上i号节点开始走S中一段极长的不包含？的序列的终点和贡献和。这样第一维简化成i个？后，直接写会MLE，把第一维滚动掉即可。这题写的时候要注意常数和剪枝 CF1158CPermutationrecovery考虑每个限制，可以拆成nxt大于i且i大于[i+1,nxt-1]中间的所有数，大的向小的连边，拓扑排序就能求出答案。直接连边边数太多，考虑是向区间连边，线段树优化建图即可 校内oi训练，看了套六校noi nflsoj654【六校联合训练NOI#5】划分和前几天那个cf思路一样，两个格子间的没染过色的边建点，相邻且夹角为π/2的之间连边，表示不能同时存在。显然是二分图，要求最小点覆盖=点数-最大匹配 nflsoj655【六校联合训练NOI#5】排列没n+1个人分成一段，维护每段最大值与次大值，找到次大值最大的点并选取，对于其他位置，若最大值大于选取点的次大值，就将最大值删去，重新选取该点最大值与次大值，每次操作每一段之多减少1个数，所以显然有解，用数据结构维护刚才所说的过程即可。 nflsoj656【六校联合训练NOI#5】超立方体分三类考虑1.p为0，q为1，记为x个\(O(2^x)\)暴力枚举2.p为1，q为1，记为y个\(f(x,y)\)表示\(p=x,q=y\)的答案，不妨设a为\(lowbit(p)\)，\(f(x,y)=f(x-a,y)-f(x-a,y-a)\)，预处理高维前缀和，复杂度为\(O(2^y)\)3.p为0，q为0，记为z个不妨设a为\(lowbit(q^((1<<31)-1))\)，\(f(x,y)=f(x,y+a)-f(x+a,y+a)\)，预处理高维后缀和，复杂度为\(O(2^z)\)每次三种选取最小的，单次复杂度最大为\(O(2^{\frac{n}{3}})\) 晚上CF，果然是智商场，靠py苟活（也许是降智严重） CF1408ACircleColoring直接模拟，显然有合法答案 CF1408BArraysSum考虑一个b，能带来k-1个变化。算下a中变化次数，除一下，上取整，k=1特判 CF1408DSearchlights计算出每个人向上跑x格时，至少向右跑距离的最大值，最后暴力扫描比最大 CF1408EAvoidRainbowCyclesm个集合建点，n个点也建出，集合向点连边，显然答案没有环，那就找个最大生成树即可 CF1408FTwoDifferent考虑2^k的做法，显然可以分治下去解决，最后只剩一个值。对于n，可以像st表一样，对\([1,2^k]\)和\([n-2^k+1,n]\)进行分治 10.1 上午正睿十一集训，讲了单调栈队列堆并查集之类的ds。发现假摔是JOIOPEN2019的原题。原来kruscal重构树也可以在并查集上用，或者说本来就是并查集的科技，只是在kruscal时也需要并查集（） CF1063BLabyrinth记向左次数为a，向右次数为B，考虑向左右为1，向上下为0的图，01bfs，可以算出到达每点a+b最小值，我们根据点的坐标知道a-b，算出ab并判断即可 下午讲了些线段树 P4198楼房重建考虑两区间如何合并，在线段树右子树中二分断点 例3：有一个序列列a[1…n]，每个a[i]是(c,x,y)，表示颜色和坐标。要求支持单点修改以及区间询问：颜色不同的曼哈顿距离最大的一对点的距离。考虑一个常规的想法，把绝对值拆开，分成四种求最大值。推下柿子发现要的是关于\(x_i,y_i\)的多项式的最大值最小值。由于要求颜色不同，维护颜色不同的次大值次小值 看了场六校NOI nflsoj642【六校联合训练NOI#1】fct考虑Lucas定理拆分组合数，每次拆成6个长度除3的子问题处理 nflsoj644【六校联合训练NOI#1】nim要求两两不同异或不为0的方案数，考虑总方案数减去不合法方案数。f[i]表示i个数异或为0方案数，\(f[m+1]=\prod_{i=1}^{m+1}{2^n-i}-f[m]-f[m-1]*(2^n-m)*m\)，总方案数减去前m个为0的再减去有相等的数（m-1个异或为0）的方案数 看dyls博客学了下sam，补了下nfls十一集训的题 nflsoj716【2020南外国庆集训#1】神秘代码考虑一个容斥，所有两两不同lcp的贡献-正串反串同时出现的贡献+同一个串同一位置的贡献，第一个是所有正反串一起建sam，后面是每个串单独建sam，很耗空间，记得重复利用 10.2 上午去nfls校内训练，被van泽远鸽鸽的提高组模拟赛打爆了 T1礼物从前到后枚举题目，用并查集维护所有t的答案。假设当前值域为[0,k]，如果\(w_i>=\frac{k}{2}\)，后面加1并合并并查集；如果\(w_i<\frac{k}{2}\)，前面减一，全局加1。总复杂度为\(O(t\alpha(t))\) T2简单题对于n=200，可以矩阵快速幂。对于n=2000，推出GF为\(\frac{1}{\prod_{i=1}^n(1-w_i)}\)，然后后面就是我不会的多项式做法了（悲） 下午听正睿时看了下gutc那边的题目 T1卵石奇数堆必胜，偶数堆除了两两相等的配对必败，其他必胜 T2村庄原题黑暗前的幻想乡。暴力枚举每个公司是否参与来容斥，矩阵树定理计算当前选择生成树方案数 T3翻转妙题。以四个小正方形为单位，计算黑色个数，若是奇数，这四个点中间那个就不可能在答案矩形里，称之为坏点。剩下就是找最大矩形，不包含坏点，枚举下边界单调栈即可 10.3 上午五校联考，样例出锅差评（我不会告诉你我一直不知道某个样例是错的，调了4h（确信）） nflsoj720【2020五校联考NOIP#9】樱初音的考试考虑限制的点集是有包含关系的，建出重构树，在上面dp，设f[i][0/1/2]表示i子树全为0/1/有0有1的最大价值 nflsoj721【2020五校联考NOIP#9】勇士考虑最小割。每个点拆点，一个用于连行（连源点），一个用于连列（连汇点），相交行列之间连上正无穷。每个勇士，取出他的路径上最且不于他本战的点，并设这个点的币数为mx。从起点按照格点依次连边，边权是mx-当前点的值。mx之和减去最小割即可 nflsoj722【2020五校联考NOIP#9】棋局对于每个k，线段树上二分即可（实际我的想法是整体二分，显然也是单log） van泽远鸽鸽在zroi的模拟赛 zroi1584[十一集训A班day1]奖杯和昨天nfls校内集训T1做法一样，启发式分裂。考虑一个贪心，删去出现次数小于\(f_n\)的数，剩下变成多段，递归求解。暴力是\(O(n^2)\)的，每次对分成两段中较短的直接处理参数，推出较长所要求的参数 zroi1585[十一集训A班day1]项链正解断环为链，对这些字符串排序，答案一定是第K小的前缀。随机前缀最后的位置，暴力dp即可。为啥写的这么简略，显然是我不太懂，我只会暴力sa，rak1~k选上就行（正确性好像也没有证明） 下午gutc模拟赛 P4081[USACO17DEC]StandingOutfromtheHerdP实际和sa求本质不同子串差不多，由于不能在其他串出现，所以有可能有些串被减了两次，记得加回来 P4082[USACO17DEC]PushaBoxP考虑转角，箱子不能动，人要动，相当于有两条路径，求变双即可，大力搜索 P4090[USACO17DEC]GreedyGiftTakersP考虑一定是一段后缀不能行，二分能行的个数，贪心check 10.4 zroi集训，今天讲的干货还是挺多的 1.1至少添加多少条边，可以使得图中不存在桥和zroi圣诞树那题一样，至少是叶子数除二上取整，这里不需要构造 1.2给定N个点的无向图，Q次询问，每次给出(a,b,c)，询问是否存在两条分别从a和b到c的边不相交的道路在同一个变双或者dis(a,c)+dis(b,c)=dis(a,b)。若询问的是点不相交，一定在同一点双或在圆方树上(a,c)和(b,c)没有交集 1.3给出一张无向图，求一个最大的子图，使得每个点的度数都不小于整个队列度数小于d的就删，直到对列为空 1.4loj3118「IOI2017」玩具火车1.搜出集合S，使得A能到电站集合P1'P满足2'A节点的后继有电站3'B节点后继全是电站2.搜出集合T，使得B能让火车到不了电站1'T为S的补集2'B节点的后继有属于T的3'A节点后继全属于T的3.将S中在T的元素删去，重复23操作 1.5给定N个01串，每个串中有1个星号问：是否存在一种把星号填写为0/1的方式，使得不存在一个串是另一个的前缀建出trie树，每个01串在trie上对应两个节点。两个节点二选一，建立2-sat。trie上不能产生祖先后代关系，建点\(P_x\)表示x子树都没选 1.6给定N个人，每个人可以在数轴上(a[i],b[i])两个位置中选一个站。安排所有人的站位，最大化距离最近的两人之间的距离二分答案，对于每个点，不能同时存在点的是一个区间，线段树优化建2-sat判断 1.7UOJ210【UER#6】寻找罪犯考虑把每个人口供排成一列，犯人的是一个全真的前缀，一个全真的后缀和一个单独的假话，2-sat解决。好像有老哥有更简单的写法（待填坑） 2.1bzoj4398福慧双修考虑1相邻的每个点，二进制分组，分别求最短路再对应点加和取min 2.2给定N个点的有权无向图，每个点另外有一个点权。定义一条路径的代价是路径总长+max(经过的点的点权)。求每对点之间的最短路，N<=500考虑floyd的过程，当k枚举到标号为k的点时，dis(i,j)表示只经过标号小于等于k的最短路。那么我们按照点权从小到大排序来标号，每个标号最短路更新完了，更新下答案 2.351nod1430地铁环线假设环长为k，我们可以直接断环，通过差分约束判断是否可行。我们二分出k的上下界，那么就能得出答案 3.1PA2014Kuglarz最小生成树裸题，这种通过推理发现答案和最小/大生成树有关的题还不少，六校和正睿都考过 3.2CF888GXor-MST这里and和or也能做，但是较为恶心，在此不提这题利用的是Boruvka算法，这个算法的思想，就是每次所有联通快找到到外面的最小边权来合并，期望次数是log次的。考虑每个联通快维护01trie，全局维护01trie。找到连通块外最小边权就是枚举联通块内元素，在全局-当前联通块的01trie上查答案。合并后同线段树合并一样合并01trie 3.3题目没看懂，老师也没讲，咕咕咕 3.4又是黑暗之前的幻想乡，大概是本随笔第三次出现 4.1loj523「LibreOJβRound#3」绯色IOI（悬念）神题。考虑点的度数不多于2，直接分类讨论1.度数为1，直接匹配2.度数为2，进行转化，它连接了两个右边的点，本身可以看做一个边。问题变成给右边的点构成的无向图定向，使得每个点入度小于等于1由于左半边满配，所以右边联通块点数>=边数，所以联通块只有两种情况1'联通块是树。考虑最终应该是选择一个根度数为0，其他都是外向。这个考虑换根dp，先钦定一个根，所有边方向都从上往下，每次换根，就相当于反转该点到根的链。求出初始dp值后，树剖建线段树。对于每次修改，就相当于对修改点到根区间操作，新答案单点查询即可2'联通块是基环树。环应该有正有反，挂的树必须全部向环外。所以记录下环正反的贡献，每次直接更改即可 4.201矩阵，要求用宽为1矩形覆盖所有1，矩形可以重叠，问至少要多少矩形长度极大行列建点，有个1的话，把该行该列连起来。答案就是最小点覆盖。由于是二分图，最小点覆盖=最大匹配 10.5 zroi集训 P3502[POI2010]CHO-Hamsters没有包含关系，只需考虑两串相交。建sa，枚举每个串开头，再枚举所有串每个位置求lcp，即可求出串之间的转移贡献，复杂度为O(nL)。然后矩阵快速幂一发就结束了（不太会ac自动机/kmp求转移贡献的做法，实际好像就是exkmp） Rank-KMP就是将字符相同的条件改变了，用主席树处理rak即可 P2375[NOI2014]动物园先kmp一次，并记录每个点border个数。第二次kmp时，当长度大于一般时，要跳nxt gutc膜你赛，这套题去年写过 T1剑与魔法当时被我暴力整过去了。应该是先找到单调递增的限制，然后按顺序用set之类的贪心 T2矩形将所有竖线按x排序，枚举一条竖线，x=a，在y上建线段树，将与之相交的横线的y插入，按x从小到大扫描x>a的竖线，每次线段树上查询再算个组合数，如果超过了某个横线的xmax，那就将其删除 T3gcd设f[i]是最大公约数为i的方案数，g[i]是公约数为i的方案数，如果能快速求得g，可以通过反演得到f。设l[i]表示a中i倍数的个数 10.6 P5021赛道修建二分答案。考虑每个子树最多向上走一条边，每个点维护个multiset，较小的去匹配，过大的直接更新答案，剩下的最大的传到父亲 AGC032EModuloPairing和小于M与大于等于M分开考虑，二分找断点，左右分别大小匹配 后来掉了很多线，待填坑 P4516[JSOI2018]潜入行动设f[i][j][0/1][0/1]表示i节点子树有j个，i有没有装，有没有覆盖到，这个是树上合并背包，复杂度分析不能只看循环 P3959宝藏f[i][S]表示选了i次，现在选过S里的元素。每次枚举msk加入即可，贡献按i算。这个看似是错误的做法，因为算了不合法的，但是肯定不优，不必担心。复杂度为\(O(3^nn)\) P2150[NOI2015]寿司晚宴分小于22和大于22的质数考虑，细节咕咕咕 P4547[THUWC2017]随机二分图把2n个点的状态压缩，对于类型为0的边组，直接建边。对于类型为1的边组(a,b)(c,d)，我们可以先建两条概率为50%的边，再建一个概率为25%的边组。对于类型为2的边组(a,b)(c,d)，我们可以先建两条概率为50%的边，再建一个概率为-25%的边组。记忆化搜索即可，由于是匹配，所以前后的bitcount数量相等，状态数并没有那么多 ARC096FSweetAlchemy考虑进行差分，问题就变成了背包，一个点最多选D次，选一次代价是子树花费之和，贡献是子树大小。按照性价比考虑，发现每种物品多余n的个数可以直接贪心，每个物品取n个，进行背包，设f[i][j]表示考虑前i种，贡献大小为j的最小体积，单调队列/二进制拆分优化即可 loj60692017山东一轮集训Day4」塔假设我们知道了一个排列，考虑有多少种方案，显然令\(S=\sum_{i=1}^{n-1}\max\left(p_{i},p_{i+1}\right)\)，记\(x_i\)为\(\max\left(p_{i},p_{i+1}\right)\)，\(min(x_0,x_n)\geq0\)，\(\sum_{i=0}^{n}x_{i}=L-1\)，答案为\(\binom{L-1-S+n}{n}\)（实际就是一个插板）考虑如何求和为S的排列数，设f[i][j][k]表示从小到大考虑到i，当前S是j，一共有k段连续的方案数，考虑可以插到每段两边或合并两段这里模数不是质数，考虑如何快速求组合数，发现n很小，且L-1-S+n的变化范围是n^2的，考虑矩阵快速幂求出\(\binom{L-1-\max(S)+n}{[0,n]}\)，递推求出其他要的 CF704BAntMan第二次做到，数轴上哈密顿回路 bzoj5232[Lydsy2017省队十连测]好题套路题。随机化每种颜色在1k的影射，状压dp，做个50100次取min 补一下前几天六校的题解，咕了好几天了 nflsoj724【2020五校联考NOIP#10】电车用stl维护极长区间[r1,r2]，使得区间中最多只有(r1,1)(r1,2)(r2,1)(r2,2)有人，最近距离是能O(1)计算的。至于代码啊，那就咕咕咕（主要是博主不一定写的出） nflsoj727【2020五校联考NOIP#10】猫和老鼠图论好题。看到这个题，感觉和点双有非常大的关系，所以立马建出广义圆方树。我们定义圆方树上好的路径：去除方点后，相邻圆点在原图有边，实际意义就是所有圆点对应在原图上的点删除之后都能使原图不连通。这样，每一步都能将原图缩小，实际就是将老鼠围剿。考虑猫有两种必胜态，1'存点点u，使得任意点v，存在u->v的好的路径。2'设C(a,b)表示删去a后b所在的联通块，即老鼠一开始能到达的点集，对于C(a,b)中任意一点v，存在a->v的好的路径。剩下考虑树形dp，不妨设a为根，\(f_x\)记录子树所有到跟是否都是好的节点，换根dp。对于1'，判下每个点的f值；对与2'，单独判一下b点所在的a点儿子的f值 10.7 总做周知，dls的课（配图开启自闭） nflsoj728【2020南外国庆集训10.6】小w与数字游戏考虑，出现0时，答案一定是0。若出现a+b=c，一定能得出0。打表发现，当数字种数多于7时，一定为0，小于等于七时大力搜索。 nflsoj729【2020南外国庆集训10.6】小w与密码考虑用总的个数减去数重复的个数。假设本质相同的串，我们记录在S串取的最少的。那么S=……A，T=A……，T中A……与……的lcp就是重复的。我们用exkmp求出T中每个点与T的lcp，在S串上建的sam上打标记。最后搜索一下parenttree，每个点需要减去的就是根节点到该节点路径上tag的最大值 gutc膜你赛 T1毒瘤题zroi失恋测d2t2，就是写个快排就行了，这里要id字典序也最小，stable_sort即可 T2简单题无修区间中位数，裸的主席树上二分，开题10min就过了吧（），出题人std写了主席树和莫队 晚上补六校 nflsoj709【2020五校联考NOIP#7】月饼考虑种颜色是断环为链，颜色从小到大考虑，正反都做一次（拆开绝对值） nflsoj710【2020五校联考NOIP#7】伟大的卫国战争题目就是问能不能把区间分成两棵树。考虑之间有些不能同时在一颗树里的限制，我的想法是主席树优化建图，跑2-sat。看我LJC00118大佬的代码后，我悟到了不少，实际可以直接每个点拆点并查集，不能同时存在，就是与对方的另一个点相连，线段树优化建并查集即可 10.8 主要是复习初赛内容，上午写洛谷的模拟赛90分，裂开 nflsoj711【2020五校联考NOIP#7】道路扩建这个题目，实际是cf的题，以前23forever讲过。考虑从1和n分别跑最短路，这样就可以得出强制选某条边的最短路。考虑想要使最短路最长，一定是在原来最短路的某条边上，尽可能的加大。考虑建出从1开始的最短路树，每条边断开都能把这个树分成两个子树。每次断一条1~n最短路的边，所求答案就是从1所在子树到n所在子树的最短路。记录强制选非原最短路边的最短路，当作一条边(u,v,dis[1->n])，对最短路树求dfs序，每次强制删边的答案实际就是个三维数点求边权最小值，第一维是起点的坐标，要在子树之外，是两个连续区间，第二三维是终点坐标的上下界，主席树维护前缀和后缀即可。 10.9 晚上回家打了下牛客的训练赛，降智debuff严重，希望能通过明天月考垫底，带来初赛的通过？ A回文数模拟 B烙印大力分类讨论，场上嫌烦就没写 C数学考试题解给的做法是组合做法，然而蒟蒻想不到，只好dp。f[i][j]表示前i个数max为j的方案数，用个前缀和优化转移，\(f[p_i][p_i]\)特判一下即可 E神奇的迷宫实际就是裸的暴力。统计长度为k的路径的出现概率，考虑点分治，合并时用NTT合并，复杂度为\(O(n\log^2n)\) 10.10 月考，头脑稀昏 晚上开始准备csp前每天看的模板 10.11 考试日 初赛感觉考的一般，错了至少四个 写板子 10.12 继续写板子，准备写重构树的板子时，想起来NOI2019归程连看都还没看，看了一下，发现挺简单，20min就1A了？ 大多数板子写好了，后面继续写题 10.13 周日晚上gutc膜你赛 T1：待填坑 T2：P6172[USACO16FEB]LoadBalancingP枚举一维，另一维二分答案取最优 T3：P3141[USACO16FEB]FencedInP考虑求的是mst，这里mst一定是一取整行整列都取 周一晚上gutc膜你赛 T1：P3101[USACO14JAN]SkiCourseRatingG按边权排序，并查集大小大于T时算下集合里为1点的贡献。显然也可以像我考场上想的大力重构树，倍增找到第一个子树siz>=T的节点 T2：P3121[USACO15FEB]CensoringG对T建ac自动机，S在自动机上跑，用栈维护答案，若到终止节点就弹栈 T3：P3097[USACO13DEC]OptimalMilkingG动态最大独立集，直接ddp。f[l][r][0/1][0/1]表示考虑了l~r，l/r是否选了的最大独立集，线段树维护 补下前几天没打的CF CF1430EStringReversal相同字符相对位置不变，算出后数下一共多少对前后顺序变了 CF1430FRealisticGameplayf[i]表示i开始用新的弹匣，枚举j>i，贪心更新f[j] CF1430GYetAnotherDAGProblem考虑入边减去贡献，出边加上贡献。设f[S]表示已经选了S的最小值，每次枚举权值相等的一层去更新 补前几天牛客的题 F红蓝图对于蓝色，建kruscal重构树，并求出dfs序，每次红色能满足的是一个区间。从大到小枚举蓝边加入，线段树维护能到达的点，两个联通块打通相当于线段树合并 看了下两年前的模拟赛 T1未来机器裸的bsgs T2MrBrown的卡车按两个相加贪心，遇到必须选的但是不能选，就不停反悔弹栈 T3机关的阴谋树链剖分，每种颜色建动态开点线段树 牛客IOI周赛19 T1基站考虑对于所有基站建新图，两基站且边权为原图上最短路，kruscal求最小生成树，找边权最大的那条。对于原图上最短路，我们用dijkstra跑多源最短路（一开始多个点dis为0且入队），做最短路同时记录最近的基站为u，对于边(x,y)，若u[x]!=u[y]，则新图上u[x]与u[y]之间连dis[x]+w+dis[y]的边 T2翻转考虑答案两段最大子段和。如果没有环，直接dp即可。对于有环的情况，那就要考虑首尾相接的情况，用总和减去不选的，不选的一定是没有环情况下，总数减去两段最小字段和即可 T3迷宫这题有算法1：\(O(nc^2)\)，算法2:\(O(nc)\)，算法3:\(nc\logc\)。实测好像是1<2<3，1比较显然的暴力，不再赘述。2是3的改进版，比较仙，不太会。对于树上一条路径的异或值，可以用根节点到两个节点的异或前缀和异或起来。枚举一条路径首尾的lca，钦定只会有一条路径在其子树，记录下子树内异或前缀和的情况，fwt一下，记录下子树外异或前缀和的情况，也fwt一下，最后一起fwt一下 NOI2020D1 loj3339「NOI2020」美食家看完题直接想到正解，但自己以为是假做法，实际max和+依然满足矩阵乘法的性质。考虑w*n很小，考虑维护连续5个时刻的每个点的最大值，矩阵快速幂转移，遇到活动单独处理。这样复杂度为\(O(k(nw)^3\logT)\)，会超时，预处理转移矩阵的2^k次，每次用dp数组乘矩阵，单次乘法复杂度变成\(O((nw)^2)\)，总复杂度为\((nw)^3\logT+k(nw)^2\logT\) loj3340「NOI2020」命运这个题一开始给我什么区间必须有1方案数的感觉，但仔细想想发现假了。设f[u][dep]表示考虑u点子树，上面一个1在dep的方案数，考虑dep一定不能太小，记录lim[u]表示dep最小是多少，若有关系(u,v)，则lim[v]=u+1，每个点lim跟父亲比max。 发现i会给i带来贡献，所以是对应位置贡献，不难想到线段树合并，这个线段树要实现区间加乘 牛客IOI周赛18 T1排列暴力求出一次所有翻转后的对应关系，找出环，剩下取模找下终点即可 T2拆分考虑总方案数减去不合法方案数。总方案数显然是\(2^{k-1}\)（k-1个位置随便插板）。对于不合法方案，发现数字都很小，考虑矩阵快速幂求出不合法方案数 10.15 校内膜你赛D1100+100+60=260 T1字符串第三次见到这个字符串排序题了。。。 T2膜拜考虑线段树维护区间o,r,z,or,rz,orz个数，ddp即可 T3游戏设f[i][j]表示考虑了前j个数，分成i段的最大贡献，直接dp是\(O(n^2k)\)的，考虑优化。此算法复杂度的瓶颈在于区间众数，但是我们发现，不是众数的数，也能用来更新dp（一定不会是最优）。记录g[i][j]表示a[j]出现次数是最后一段的众数出现次数，设a[pre]是上一个与a[j]相等的数，\(g[i][j]=max(f[i-1][j-1]+1,g[i][pre])\)，f的转移就变成了一个前缀max，复杂度为\(O(nk)\) 校内膜你赛D2，tjw鸽鸽的题好评，又能找到新的gal了？100+100+70=270 T1大图书馆的后导零考虑对k分解质因数，对于每个质因子c，通过枚举次数，算出在n!质因子c的次数，用这个次数整除在k中出现次数并取min即可 T2花与少女的比赛记录换根dp。记录siz[x]和sum[x]，sum[x]表示子树中每个点到根的距离，这样贡献就能表示为\(siz[u]*x[u]+sum[u]*a[u]\)，大力换根即可 T3夏空的赫斯提亚区间逆序对。现在只会莫队+bit的70pts，明天补正解。正解咕咕咕，实际就是维护块与块，点与块，块与点的贡献 校内膜你赛D3100+100+100=300 T1西天取经模拟一波，只要会点概率期望和逆元即可 T2食堂测试考虑合法的方案\((p,q)\)（假设\(p\leqq\)），1'\(p\)与\(q\)奇偶性不同2'\(p\)与\(q\)互质3'\(q\leq\frac{n}{2}\)。暴力判断即可，对于附加范围，咕咕咕 T3半夜回寝只考虑124，就是区间加乘线段树，操作3可以理解为x=255-x=-x-1，所以实际就是区间加乘线段树模板 10.16 什么叫做内卷啊（后仰） 校内膜你赛D4，双厨狂喜100+100+100=300 T1MisakaNetworkx轴y轴建虚拟点，把12操作变成34操作。现在只剩种类相同与不同两种情况了，不同连1，相同连0，判断是否有奇环（这个也可以2-sat，扩展域并查集做）。没有奇环就求最小生成树，否则不存在 T2KamijouTouma考虑字典序最小的问题，一般都是强制前面几位都相等，再钦定一位不等，后面随便填。需要维护每个点没被钦定的儿子数量乘积prod没被选过且权值小于某个数x的个数c（前面直接整，后面每个点整个set之类的维护），对答案的贡献是prod*c T3Accelerator对所有a建ac自动机，对于每个b找在a中出现的位置。对于\(a_{i1}=b_{j1},a_{i2}=b_{j2},(i1 校内膜你赛D5100+100+100=300 T1出题和前两天翻转是同一个题，求环上两段最大字段和 T2最短路每行每列建虚点，点连向本行列，变全为0；对于两个点，行与行之间连边，列与列之间连边，边权分别为\(|y_1-y_2|\)和\(|x_1-x_2|\)。这样边数还是很多，考虑只在相邻行列间建边，正确性显然，这样就变成了裸的最短路 T3道路升级把7个点01状态状压，构建转移矩阵。剩下就和今年NOID1T1一模一样了，向量乘矩阵复杂度是\(O(n^2)\) 校内膜你赛D6100+100+100=300 T1仰望飞机的八倍镜求出每个点的极角，加入到极角的桶中，找到所有桶中元素最多的桶并加和 T2天色McdoNauts考虑枚举最小值位置，通过单调栈求出极长区间左右端点。考虑在符合条件的区间中，最大值一定是这个极长区间的最大值。找到最小值位置前面前两近的和后面前两近的，分讨一波即可（代码细节似乎很多啊/qiao） 校内膜你赛D7100+100+40=240 T1桃李园统计每种映射的个数，最大权最大匹配，KM/费用流 T3数据生成器我只想到了一个状压的部分分，tooyoungtoosimple。对长度为奇数和偶数的分别dp，设f[i][j][k]表示考虑i个这种数，j个开头是奇，差模11位k的方案数。剩下就是偶数插到奇数中（分开头奇和偶插） 校内膜你赛D830+100+40=170 T1出题2考虑预处理n个数，k组相邻的方案数，设f[i][j]表示前i种数，共有j对相邻的方案数，就是结合插入位置大力讨论即可。 T2验题对于每个联通块，从小到大枚举两个值中间较大的数，然后扫描时统计小于当前数的数，二进制下每位有多少个1 校内膜你赛D9这场我也不确定自己场上能拿多少 T2小T与FIT楼考虑就是大力dp，但对于每个点的每个子树的点亮顺序，需要贪心决定。列出dp转移方程后，临项微扰，发现应该是按照f[v]-w[v]从大到小排序 T3小Q与离散数学考虑最暴力的dp，需要枚举划分数转移。考虑同时维护另一个dp，我们假设集合的长度表示集合的括号对数，设f[i][j]表示最长集合长度为i，出现次数为j。f与dp同时计算，还带一个调和级数，\(O(n^2\logn)\) 校内膜你赛D10100+100+40=240 T1香锅与选举与巧克力1'占用两条边，方案数为\(\binom{a_i}{2}\times\binom{a_j}{2}\)2'占用四条边，方案数为\(\sum_{i T2现在就想告诉神犇，我是蒟蒻！实际就是并查集求联通块大小，最多合并O(n)次。实现似乎有点烦，除了维护全局并查集，还需要维护个区间极长连续同集合的并查集 T3矢量推进的四重奏我就只想到了线段树维护矩阵乘法的那个分。考虑在i处加了x，对j的贡献就是\(fib_{j-i+1}\)。所以我们需要的是\(\Sigma_{i=0}^{k-1}fib_{pos+i\timesstep}\)。先求转移矩阵的step次方，考虑求\(\Sigma_{i=1}^{k}\left(fib^{step}\right)^{i}=FIB_{}\)，这个可以通过类似快速幂的科技求出(例如\(A+A^2+A^3+A^4+A^5+A^6=A+A^2+A^3+A^3*(A+A^2+A^3)\))，最后FIB再乘上转移矩阵的\(n-pos-(k-1)*step\)次方，就是对答案的贡献 再更新下前几天写的正睿2019CSP冲刺D5 T1染色能全部删完，但且仅当不存在环，并查集维护 T2乘方二分答案，变成判定性稳问题。对于lcm大于60的，我们只需要考虑到60即可。设f[i][j]表示前i个数，lcm为j的容斥系数 T3位运算都可以直接在值域上FWT。对于xor，可以用trie更优秀。对于and，维护可重集，从高位开始贪心，若有超过两个1，把所有是0的删除，如果没有，那就继续考虑低位，方案数也很好计算 10.17 斐波那契？数列！\(\sum_{i=1}^{n}fib_{i}^{2}=fib_{i}fib_{i+1}\)一个比较有用的公式（） 正睿2020联赛集训D1 zroi1593[20联赛集训day1]字符串做过小w与密码后，没转过脑筋，实际遇到相同字符就减去一个即可 zroi1594[20联赛集训day1]糖果若所有\(a_i\)相同，设\(g(i,j)\)表示前\(2^i\)种糖果，占了\(j\)个位置的方案数，转移显然。每种\(a_i\)分开算，最后合并下即可（大于m的\(a_i\)当作\(m\)算） zroi1595[20联赛集训day1]打字机设\(f(i,j,k)\)表示考虑了\(S\)前\(i\)位，\(T\)前\(j\)位，最大的后缀长度\(x\)，使得\(x-h(x)\)，即不需要变动的字符个数小于等于\(k\) zroi1596[20联赛集训day1]堆按照套路，枚举前为i位相同，再枚举第i+1位的值，计算方案数。方案数是个累乘，这个累乘可以动态更新 正睿2020联赛集训D2 zroi1597[20联赛集训day2]交通考虑转化，把边建成点，每个点的两个入边/出边所代表的点连起来。每个点度数为2且不存在奇环，我们只需要做并查集同时数一下环的个数c，答案就是\(2^c\) zroi1598[20联赛集训day2]冒泡排序两年前的普转提。只是数据范围多了两个0，理论上还珂以继续增多（bushi）。题目相当于给我们一些交换的先后关系，设f[i][j]表示前i个数，末尾是j的方案数，转移是前缀/后缀的和，暴力dp即可 zroi1600[20联赛集训day2]花瓶写出暴力的dp转移，斜率优化，维护上凸壳（斜率优化判断上下可以用过选取两个点，令某个大，求解关于斜率的方程即可） 正睿2020联赛集训D3 zroi1615[20联赛集训day3]树上排列树剖维护哈希即可 zroi1617[20联赛集训day3]埃及分数实际就是个背包。考虑895*7=2520的约数背包，剩下的暴力搜索 正睿失恋测D6 zroi1561[十连测修锅赛]string实际twopointers就好了。我场上降了智，觉得对于每个位置二分并判断，用st表写了本题 zroi1562[十连测修锅赛]subset全是正数是个很经典的题。这里把负的全取当成0点，权值变为正的，实际就和经典问题一模一样了 zroi1563[十连测修锅赛]rook现在只会cdq的做法，原题有两维，第三维就是该行列上一个点的坐标要在矩形外 10.18 正睿七连测D4 zroi1570[2020普转提七连测day4]最优排列正序考虑十分困难，考虑从后往前填。考虑建反图，拓扑排序，每次取权值最大的点出队（这里要用优先队列） zroi1571[2020普转提七连测day4]异或考虑a修改一位插入哈希表，b修改一位在上面查，最后减去30*AB相同对数（这个也是用哈希表计算） zroi1572[2020普转提七连测day4]日程表如果只有一种限制，实际是个经典题。设\(f_i,g_i,h_i\)表示从左到右填到第\(i\)段，且结尾是黑/白/有黑有白的合法方案数，那么\(i\)这个位置往前的最长黑色/白色连续段长度很容易求出，转移用前缀和优化一下就行了 zroi1573[2020普转提七连测day4]线性规划妙题。\(\suma\leqP\)且\(P\leq\sumb\)，实际相当于每个位置选\([a_i,b_i]\)的权值，使得权值和为P，设\(f_i\)表示当前权值和为\(i\)的最小代价，单调队列优化转移 T1排队发现\(a,b,c\)很小，而\(n\)很大，无脑写个矩阵快速幂，每个点拆成男女考虑，还要分方案数和贡献 T2选ID实际我一开始一直以为是什么高深的网络流做法。最后发现是在trie上直接贪心，能变长就变长 T3生日考虑当询问区间长度达到13以上时，一定符合题意。感性理解一下，就是大约\(2^13\)个数字都出现过了，不可能再找到1000以内没出现过的数字。维护用线段树维护幂次打tag，取模需要用扩展欧拉定理，查询小于14的暴力取出数列，meetinmiddle判断 晚上gutc膜你赛，T3前面出过，就不讲了 T1P3082[USACO13MAR]NecklaceG从kmp的角度考虑，就是每次添加字符，不能完全匹配。设f[i][j]表示添加了i个字符，匹配到第j位的最多保留个数，跳fail转移，这样会T。我们预处理每种字符在匹配到某位置跳fail最后到的位置，\(O(26m+nm)\) 正睿联赛集训D4题目和算法环移位了可海星 zroi1612[20联赛集训day4]计数题就是后缀树叶子节点个数。可以直接sam，或者从kmp和border角度考虑也行 zroi1613[20联赛集训day4]字符串题解不等式解出上限，然后构造，不太noip的题 正睿联赛集训D5 zroi1618[20联赛集训day5]打地鼠裸的二位前缀和 zroi1619[20联赛集训day5]竞赛图好题。若一个诱导子图是强连通的，诱导子图只向外连边形成的联通块一定是非强连通的。预处理原图每个子集S，找到所有不存在进入S的边的点，这样就可以像前面说的推出连通性了 10.19 初赛考了89.5，海星 正睿失恋测D5，至今才补 zroi1567[2020提高组十连测day5]藤原千花神仙图论题。\(k=0\)，所有度数为偶，\(k\geq1\)，所有度数为奇或偶，\(k\geq2\)，还可以是每条边两端度数奇偶性不同的。对于链要分类讨论（链每次变短1） zroi1568[2020提高组十连测day5]白银御行考虑整体二分。如何判断两个矩形是否相交，实际可以像二维前缀和一样，容斥数点 两套五校题 nflsoj735【2020五校联考NOIP#12】钢筋看到这个题，我说这不是个插值吗，再一看模数，我就啥都不会了。最后发现，是将phi和2phi次填相反数，其他填0（根据扩展欧拉定理，一定成立） nflsoj736【2020五校联考NOIP#12】仪式类似正睿失恋测D1T3，如果用的是上升子序列组合数那个做法，需要推柿子后NTT，或者进行dp求出期望贡献。最后答案的形式很卷积，NTT即可（还是逃不了NTT） nflsoj737【2020五校联考NOIP#12】线图草，这不是藤原千花吗，怎么题解都一模一样。一天见同一个题两次，绝活 nflsoj738【2020五校联考NOIP#12】塔防并集很不可做，考虑转化成交集。每一次学习相当于区间删除某个元素，若区间一个都没删，就相当于大家都没学。这样就变成了一个动态二维数点的问题 膜你赛标题FOC-PIOC模拟赛，是不是可以全排列了啊（后仰） nflsoj739【2020五校联考NOIP#13】路哥我感觉硬树上合并背包即可啊（仔细想想，发现这个树上合并背包不是取min(siz)，复杂度是假的）。这题正解用的是一个我没见过都优化技巧，向子树dfs时，直接把父亲当前的状态传到子树，但仔细想想确实很正确。NTT好像也能优化到\(n^2\) nflsoj740【2020五校联考NOIP#13】密电实际是个套路题。都从小到大排序，\(b_1\)是\(a_1+a_2\)，\(b_2\)是\(a_1+a_3\)枚举\(a_2+a3\)就可以推出后面所有的数 10.20 正睿联赛集训D6 zroi1629[20联赛集训day6]卷乘法加取模显然没有好的性质，我们取log，通过log之和最大来转移，顺便同时转移乘积 zroi1630[20联赛集训day6]简单题考虑一共有很多条链，链上在A在B的最多差1，我们求出最少是多少个（每条链取较少的），剩下的从长度为奇的链取，就是个组合数，卢卡斯即可 正睿联赛集训D7什么叫做真正的联赛难度啊（后仰） zroi1601[20联赛集训day7]稻草富翁随便判判即可 zroi1602[20联赛集训day7]序列倒序处理，用树状数组维护每个操作被执行了多少次，最后发现，倒序扫描，前缀和可以再r加，l-1减 zroi1603[20联赛集训day7]求和考虑大力分类，讨论选1条2条3条边不同点数的方案数。主要的是三元环计数，按度数排序，暴力去找，复杂度实际是\(O(m\sqrtm)\)的 10.22 zroi1632[20联赛集训day6]字符串考虑从首尾去掉相同的字符，题目变成将字符串划分成A+B+C+D，使得A+C或B+D是回文串且串长极大。考虑A+C，若回文中心在A中，回文串为[l,r]，那么要求[1,l-1]的反串在r后面出现过，z算法解决，对于回文中心出现在C，同理。B+D一样考虑 补去年失恋测D1 zroi954分组按从小到大排序，一定是先选组员，再选组长，设f[i][j]表示选了i组人，有j个组员还没配对的最小代价，由于2k>n直接无解，所以复杂度是就是根号的 zroi955折纸题目有很多很好的性质。考虑横着折和竖着折不会互相影响，分开计数。每次实际相当于裁剪，裁去较小部分。先考虑序列上如何计算，若[l,r]能折出来，相当于[l,n]和[1,r]都能折出。两种情况是对称的，只讨论如何求出前者，跑马拉车，求出每个点为回文中心的极长回文串，若本次求[i,n]是否可行，找到极大的j，若使得[j,n]可行且j在i的回文半径内，则[i,n]可行。考虑二维情况，把行列哈希，变成行列两个一维的问题 zroi956集合考虑每个数倒序插入trie，每次加一就相当于把全1的链每个点都交换左右儿子 正睿联赛集训D8 zroi1636[20联赛集训day8]蛋爆爆设f[x][0/1]表示从x出发，走完x子树，最后是否一定回到x的方案数，直接转移即可（一开始想的是和深度有关的贪心，好像也是对的） zroi1637[20联赛集训day8]高考考题目中每种结果的概率相同 设\(f(i,j)\)表示至少i个数大于等于j的方案数，则答案为 \(f\)本身不好求，考虑设\(g(i,j)\)表示恰好有i个数大于等于j的方案数 由于\(ij\leqm\)且\(jk\leqm\)，所以暴力求的复杂度是\(O(m^2)\)的 zroi1639[20联赛集训day8]田种种每个好的转化成二维平面上的点，求凸包，对于每个坏的点，有个斜率的区间不与凸包相交，我们要找的的是一个斜率，使得与凸包相交次数最少，刚才的区间差分一下即可。 2020牛客NOIP赛前集训营1 T1牛牛的方程式裴蜀定理的推广 T2牛牛的猜球游戏问就是线段树维护转移矩阵（好像这个东西实际具有可差分性，但我还是喜欢无脑点） T3牛牛的凑数游戏考虑一些数，将他们从小到大排序，记录前缀和数组，若\(sum_i T4牛牛的RPG游戏我自己想了个\(O(nm\sqrt{nm}\log(nm))\)的做法（sqrt是min(n,m)得来的），比较暴力。正解cdq+李超线段树维护这个斜率优化 P3593逛公园考虑K很小，所以每个点维护[dis,dis+k]的方案数。如何判无限解，保留边权为0的边tarjan缩点，若某个强连通分量到1加上到n距离在范围内，那么就无限解 P3960列队每行和最后一列维护动态开点线段树，每个位置记录个标记0/1表示这个人是否存在，这个人位置改变就将标记变为0，要第几个人就线段树上二分即可 正睿联赛集训D9 zroi1640[20联赛集训day9]送花枚举r维护每个l的答案，新加入一个r，相当于给上上个与上个之间区间减，上个到当前区间加，先付桉树维护即可 zroi1641[20联赛集训day9]星空坐标系旋转四十五度，相当于距离为\(min(|x_1-x_2|,|y_1-y_2|)\)，将距离为0的缩点，按x，y排序，暴力找最小值，并且记录最小值是哪两个联通块产生的，去重后统计答案 zroi1642[20联赛集训day9]零一串很妙的一道题。维护一个长度为T的01串，表示一开始在某个位置上的1在某个时刻是否能移动。如果我们知道第i个1的串，考虑第i+1个1的串，那么应该是i的右移一位并补上一个前导0，若中间隔着k个0，就将前k个0变成1。用队列维护0的位置，对于逆序对，就要求每个时刻有多少个1，差分去求 2020牛客NOIP赛前集训营 T1GCD魔改线筛，每个数被筛两次即可 T2包含记忆化搜索即可 T3前缀垃圾题。和乌帕一样，需要倍增，但这个题还要写高精除 T4移动这个题实际直接整个类似最短路的算法即可 CF1433FZeroRemainderSum设f[i][j][cnt][rem]表示看到i行j列，本行选了m个，余数为rem的最大值。听说有牛逼网络流做法 CF1433GReducingDeliveryCost先跑dij求出任意两点距离，枚举被删去的边，求\(\sum_{i=1}^k\min(dis(a_i,b_i),dis(a_i,x)+dis(b_i,y),dis(a_i,y)+dis(b_i,x))\)的最小即可 10.23 AGC020CMedianSum考虑\(n^3\)背包，肯定能找到中位数。用bitset优化，即可\(\frac{n^3}{w}\)，这个做法的正确性在于若a少数了，则sum-a也会被少数，不影响中位数 ARC101DRobotsandExits只考虑掉左洞还是右洞，每个机器人抽象成点，有条折线来区分掉左还是掉右，数点优化dp即可 CF360BLevkoandArray二分答案mid，用dp来check，f[i]表示前i个最多几个不修改，\(f_i=\max(f_j+1)*[(i-j)*mid\geq|a_i-a_j|]\) 正睿2019CSP冲刺D7 T1字符串记录下来ST每个位置下一个0/1的位置，设f[i][j]表示匹配到i，j位置最短多少。字典序最小就是优先短的，再要求尽量填0 T2序列相当于在一张对应二进制位的表格上选数，一定贪心选小的数。二分权值mid，判断可以通过数学手法 T3交换从小到大考虑每个数字，要么去前面，要么去后面，选较近的去，如何计算所谓距离，用线段树维护区间有多少个没有被操作过 正睿2019CSP冲刺D9 T1排列一位一位钦定，贪心判断。这里一共两种贪心，每个a找到刚好比他大的b，每个b找到刚好比它小的a。在每位判断的过程中，从前者慢慢转变成后者 T2分组按s从小到大排序，设f[i][j][S]表示考虑了前i个学生，还有j个组没结尾，极差之和为S的方案数，对于极差的贡献是个差分的形式 T3异或先需要奇妙的结论。设点权为与其相连的边权的异或和，边权全为0，是点权全为0的充要条件，我们考虑使点权全为0，每次操作相当于使相邻两点同时异或一个值。对于k个异或为0的数，我们花k-1次操作可以完成使所有全0，我们要尽可能的分成多个异或为0的组。每两个相同的数成一组，剩下数只有0/1个，状压dp即可 正睿2019CSP冲刺D10 T1旅行大力建图，跑最短路，这里对最短路的定义是路径上最小的边权 T2寻宝宝藏按方位可以分成四类，四类的贡献也都很好计算，用堆维护，每次取贡献最小的 T3鞋子dy好像在gutc膜你赛也出过。不考虑方向，二分图匹配，最后通过方向变成0123，加和后模4的余数判断是否能够达到 10.24 心血来潮，复习复习dp板子 P2340[USACO03FALL]CowExhibitionG裸的背包，只需要改下空间0点即可 P3647[APIO2014]连珠线一开始以为只需要是长度为2的链覆盖，仔细想想发现所有都必须是父亲-当前-儿子，那么dp记录下当前点是否是中间的点（记录中间的信息都很好访问）情况下最大（次大也需要记，方便换根），大力换根 CF939FCutlet先考虑暴力dp，发现每个区间最多翻2次且段数很少，dp一维变成段数，单调队列优化 P3628[APIO2010]特别行动队大概就是推下柿子，裸的斜率优化 晚上失恋测，T1cf都过了，竟然zroi爆了 zroi1633[2020提高组十连测day7]生成树原题CF1149DAbandoningRoads zroi1634CF1149DAbandoningRoads考虑贪心。对于每个限制，我们都能快速找到满足这个限制深度最小的点的深度，我们去这些点中深度最大的，判定是否可行，自己画个图大概就能理解了 zroi1635[2020提高组十连测day7]种树考虑必须满足限制最小的那个，我们从大到小排序。设f[i][j]表示前i人，还有j人没分好，\(f[i][j]=f[i-1][j-1]+\sum_{l=1}^{a_{i}}\binom{j+l-1}{l-1}f[i-1][j+l-1]\)，组合数拆开，FFT优化转移。好像还有个神奇的调和级数优化方法，待填坑 晚上cf，奇妙的降智之旅从此展开 CF1436AReorder判下元素之和即可 CF1436BPrimeSquare全1矩阵，对角线全填另一个数使得满足条件 CF1436CBinarySearch跟着题意二分，数有多少个点必须向左/右，排列组合统计即可 CF1436DBanditinaCity答案是子树权值和除叶子节点数的最大值 CF1436EComplicatedComputations对于每个权值为v的点，找到极长的不含v+1的区间，三维数点，看看mex是不是v+1 10.25 早上补了下昨晚的ARC ARC106A106暴力模拟 ARC106BValues暴力判下每个联通块两种权值和是否相等 ARC106CSolutions构造一个非常长的，是的第二个人答案为1，再构造第一个人的方案 ARC106DPowers推柿子，二项式定理展开，交换求和符号。我自己想的时候没想到交换求和符号，写了个\(O(nk\logk)\)的NTT做法，被卡常了 ARC106EMedals神题。答案下界为nk，上界为2nk，二分答案，判断是否可行。看到这种选择性的问题，应该考虑最小割模型。源点S向每天连边，流量为1，每个人向汇点连边，流量为k，天向人连边，流量为inf。考虑到这个图中很多表示天的点出边一样，我们只需保留\(2^n\)个本质不同的点。若本图最小割是nk，那么就合法，网络流判断此二分图最小割显然是复杂度爆炸的。我们考虑与汇点相连的边很少，对这些边是否割掉进行状压，对于每种转态，考虑与原点连出的哪些边要被割掉，应该是所有的去除掉连边是该状态子集的点，高维前缀和即可 下午gutc的课，大概讲了套奇奇怪怪的模拟赛，好像是fjwc的题 T1全连简单的树状数组优化dp T2直径大概就是个扫把，打个表，发现一定珂以拆成ab+ac+bc T3原样输出待填坑 T4不同的缩写二分答案，每个串随便选n个不同的且长度小于等于mid的子序列，建二分图匹配，看是否完美匹配 晚上打cf，状态爆炸 CF1434APerformEasily把每种的六个选择都算下，然后尺取法 CF1434BShurikens离线下来，从小到大贪心取填 CF1434DRoadsandRamen最优解一定包含直径的一端。每次操作时子树翻转，求dep最大的0 10.26 补了好几套鸽着的正睿题 正睿停课集训D10，这场难度挺大的，感觉我写不动 zroi1643【20联赛集训day10】玩游戏画出前缀和折线，每次更新某个序列，一定是贪心选择更新到某个比当前小的极小值，如果能移到这个极小值，就移动 zroi1644【20联赛集训day10】排列操作最多执行log次。在笛卡尔树上dp，又是我没见过的科技。设f[i][j][0/1]表示长度为i的区间，需要删j次的方案数，0/1表示在笛卡尔树上左右两边有1/2个极大值，有的转移要用前缀和优化 zroi1645【20联赛集训day10】最短路待填坑 zroi1646【20联赛集训day10】矩形线段树套set，直接硬维护即可 正睿停课集训D11 zroi1660[20联赛集训day11]第一题同D8T1蛋爆爆，什么叫做我抄我自己啊 zroi1661[20联赛集训day11]第二题二分答案后差分约束，这里最短路要利用蚯蚓一样的技巧去优化 zroi1662[20联赛集训day11]第三题感觉也许是个套路吧。根据前面多位相同的分类，枚举后面随便填的有几个1，查询就是整块直接算，其他零块递归下去做，单次\(O(w^2)\) zroi1663[20联赛集训day11]第四题平方就是有序选两个，如果我们现在考虑的是t这个数，设f[i][j][0/1/2]表示前i个数，最大值为j，选了0/1/2个t的方案数，暴力转移是\(O(n^3)\)的。下面是口胡time：考虑有很多转移一样，处理前缀转移和后缀转移，枚举中间的时候拼起来即可 普转提五连测D5 zroi1655【20秋季普转提day5】跳石头在纸上画一画，发现相离的相差不超过2，加二就是前后产生一对交换，记录下来，在减二时填 zroi1656【20秋季普转提day5】树考到这个题我就没了吧，我自己一开始写的是大力树形dp。考虑将相同的缩到一起，答案就是直径长度除二 zroi1657【20秋季普转提day5】背包按重量排序，相当于要求价值最长非降子序列。考虑背包大小的限制，一定是取最大的几个，从后往前dp，和正的一样，也是个数点，结果和装的下该物品的背包数取min。关于数点，树状数组优化转移即可 zroi1638【20秋季普转提day5】蚂蚁和树没有什么关系，抽象在以深度为轴的直线是哪个，自己在纸上画画，发现答案是\(\max{i+suf_i-1}\)（\(i\)处有蚂蚁，\(suf_i\)表示深度大于等于i的个数），线段树维护即可 zroi1639【20秋季普转提day5】划分分x祖先，和x子树外非祖先讨论，记录下是否有某个值出现，大概就是个类似换根dp的dfs 10.27 补一下前两天gutc的题 P3112[USACO14DEC]GuardMarkG大力状压dp即可 P3104[USACO14MAR]CountingFriendsG枚举，按度数从大到小贪心判断 P3119[USACO15JAN]GrassCownoisseurGtarjan缩点，建分层图，正向边同层，反向边跨层，显然还是个dag，拓扑dp即可 P3113[USACO14DEC]MarathonG线段树维护动态dp JOI2014final loj2756「JOI2014Final」JOI徽章模拟即可 loj2757「JOI2014Final」IOI馒头我考虑的是大力dp，盒子不好贪心，但是馒头很好贪心，记f[i][j]表示强制选了i盒子，当前装完价值第j大的馒头的最大贡献，前缀和优化一波即可 loj2758「JOI2014Final」年轮蛋糕二分答案，然后尺取两段即可， loj2759「JOI2014Final」飞天鼠考虑贪心，就是没有掉地就不向上走，没有飞得太高就不向下走，直接最短路，记录下高度，动态算边权 loj2760「JOI2014Final」裁剪线理性愉悦，本来以为只需要利用V+F-E=2，扫描线即可。写完后发现一直过不去样例二，纸上画图，发现若线段不连通，就不适用，发现要添加联通块数-1的边才满足，画个图应该还是很好理解的，那么就线段树套set硬维护 晚上打CF，原地裂开 CF1437AMarketingScheme判断一下2l和r的关系即可 CF1437CChefMonocarp，写个大力dp，前缀和优化，或者学dyls直接写个MCMF CF1437DMinimalHeightTree一开始写了个dfs的贪心做法/px CF1437EMakeItIncreasing就是最长不下降子序列，随便写了个过了pretest，有个细节忘判了，最后fston#105（一共105个点） CF1437GDeathDBMS建AC自动机，在fail树上树剖，但是jly好像利用了一些性质，使得暴力跳也能通过？ 10.28 由于身体原因，被迫停课？今天大概是口胡的最后一天了，之后就要多写题了 zroi1664[20联赛集训day12]第零题考虑从下向上的贪心，倍增优化，过lca的单独跳，另一边也从下向上并不会影响答案 zroi1665[20联赛集训day12]第负一题看着有点动态dp那味，然后考虑分治即可 zroi1666[20联赛集训day12]第负二题题目大概就是要找最大菱形，考虑每次答案最多增加1，单调队列维护答案 zroi1647[20联赛集训day13]异或考虑拆位直接计算贡献 zroi1648[20联赛集训day13]赌神待填坑 zroi1649[20联赛集训day13]路径大概自己只会点分+NTT的暴力做法。暴力dp考虑设\(f[i][j]\)表示子树所有点到\(fa[i]\)距离的j次方之和，暴力树上合并背包是\(O(nk^2)\)的。斯特林数展开正解考虑设\(f[i][j]\)表示\(\binom{i子树的所有点到fa[i]的距离}{j}\)，然后树上合并背包即可，甚至还能长剖优化 zroi1650[20联赛集训day13]树考虑模数来根号分治，比较毒瘤 loj2761「JOI2013Final」彩灯考虑答案应该是连续三段极长且不用修改的长度之和的最大值 loj2762「JOI2013Final」搭乘IOI火车朴素dp，考虑设f[i][j]表示A用到I，B用到J最多能多长 loj2763「JOI2013Final」现代豪宅每个点分行列拆点，若有开关则连边权为1的边，同行同列内的点按距离连。直接建点很多，只考虑起点终点和有开关的关键点即可 loj2764「JOI2013Final」JOIOI塔从后往前贪心即可，I->O->I/J这样匹配，贪心匹配，若J匹配不到且前面有IOI，则将IOI替换为JOI（这样I可以继续利用） loj535「LibreOJRound#6」花火/loj2765「JOI2013Final」冒泡排序好题，先简化一下题意，对于一个序列，自由进行一次任意两项交换，求交换后逆序对数最小是多少先考虑暴力，暴力枚举\(a_i,a_j,(a_i\geqa_j,i\leqj)\)的位置，将所有坐标和数字转化为二维平面上的点，求两点围成的矩形中点个数的最大值，二维数点二维差分解决，复杂度为\(O(n^2)\)考虑正解，考虑\((i,a_i),(j,a_j)\)何时有可能成为最大值，显然\((i,a_i)\)左上和\(j,a_j\)右下没有点，处理出合法的点集\(U\)和\(D\)，发现\(U\)和\(D\)中点的\(a\)随\(i\)增大而增大。我们建出一个以\(U,D\)为轴的坐标系，每个点的值的意义是\(U_i\)和\(D_j\)构成的矩形中点的个数。考虑\(i,a_i\)对新坐标系中值的贡献，由于\(U,D\)的单调性，所以对应的是\(U,D\)中的连续区间，即新坐标系中的一个矩形。求出所有矩形后扫描线即可，复杂度为\(O(n\logn)\) loj2724「JOI2015Final」铁路旅行本来以为是个树上差分，最后发现是序列上差分 loj2725「JOI2015Final」分蛋糕2断环为链，区间dp loj2726「JOI2015Final」JOI公园求完单源最短路后，将最短路从短到长的加入集合即可 loj2727「JOI2015Final」舞会很神奇的题。二分答案，发现相当于在树上填数，设f[i]表示至少两个儿子大于等于mid时，子树中有多少个大于mid loj2728「JOI2015Final」城墙按对角线考虑，每个点记录最多向后延伸多少和最多向前延伸多少，数点即可 10.29 zroi1667「20联赛集训day14」动物世界写个根号分治或调和级数都可通过 zroi1668「20联赛集训day14」走近科学去年dy给机房模拟赛出过，相对位置不变，二分位置，判断前面有几个（这个判断不关心编号，所以碰撞返回可以当做互相穿过） zroi1669「20联赛集训day14」自然传奇大力枚举镜面翻转旋转，暴力判同构 CF1400AStringSimilarity所有奇数位取下来即可 CF1400BRPGProtagonist贪心考虑价值小的一定尽量取，枚举一个人取了几个，算出其他取max CF1400CBinaryStringReconstruction一开始全1，把所有0的限制模拟下，看下是否满足 CF1400DZigzags偏序问题随便写个树状数组就过了吧 CF1400ECleartheMultiset设f(l,r)表示l~r为0最小次数，对于一个区间，贪心考虑，要么r-l+1次操作2，要么先用操作1使得最小数为0，递归成两个区间求解 CF1400Fx-primeSubstrings搜出所有不合法的序列，建ac自动机，在上面dp即可 CF1400GMercenaries设f[i][j]表示选择集合大小为i，强制选了j个后，剩下i-j个随意选的方案数，预处理出，大力容斥即可 P6858深海少女与胖头鱼随便推下递推式，然后就没了 P6859蝴蝶与花树状数组上二分。考虑本题的特性，权值只有1和2，所以从1开始的区间和没有达到val的也有达到val+1的，然后考虑应该是用1替换一个2，树状数组上二分出和为val+1的起点终点后第一个1的位置，判一判即可。吐槽一下数据，3*2e6次线段树二分都没卡掉，然而因为一个恶心的读题细节，把正解卡成0分 10.30 zroi1670[20联赛集训day15]游戏博弈题的常见套路，到达一定状态后模仿，本题也是同样思路，考虑从中间劈成两段相同的，剩下一直模仿即可 zroi1671[20联赛集训day15]连任线段树分治板板题 zroi1672[20联赛集训day15]排列大概是根据问号出现位置分类讨论，去数点。对于没有问号的数点，一般来说要写cdq解决。但是，这里三维值都互不相同，所以有单log的容斥做法。设三维为\(a,b,c\)，分别求出\(bc,ac,ab\)三个二维数点的答案\(A,B,C\)，三维数点的答案就为\(\frac{A+B+C+\frac{n(n-1)}{2}}{2}\) zroi1673[20联赛集训day15]追逐待填坑 CF1398DColoredRectangles大力三维dp CF1398ETwoTypesofSpells大概就是找到前k大，判下是否全是第一种，若是则踢掉最小的，换上第二种中最大的，随便数据结构维护维护 CF1398GRunningCompetition关于差一定的问题有两种常规解法，1'bitset，2'倒过来NTT P5459[BJOI2016]回转寿司写个线段树区间平移，单点修改就行了吧 10.31 CF1428ABoxisPull按题意输出即可 CF1428BBeltedRooms判下有没有环，无环数下-连接的点的个数 CF1428CABBB栈模拟下即可，只要栈里有元素，遇到B就弹栈 CF1428DBouncingBoomerangs从后往前构造，分123讨论，1新开一行，2利用之前的1，3找前面的1/2上面 CF1428ECarrotsforRabbits按照多切一次减少的价值贪心，用优先队列实现 P5298[PKUWC2018]Minimax考虑设f[i][j]表示i出现j的概率，发现转移和子树dp值前缀后缀和有关，线段树合并维护（好像挺烦的，过几天写一下） P4899[IOI2018]werewolf狼人和红蓝图一样，一种利用kruscal重构树，另一种线段树合并维护连通性 P3206[HNOI2010]城市建设只会想根本不会写。直接lct维护的话，不好维护删边操作，然而利用了线段树分治后，我们可以记录添加边对mst的改动，到时候恢复即可 loj6515[雅礼集训2018Day10]贪玩蓝月线段树分治然后暴力背包即可。在线做法好像挺神仙，⑧太懂 晚上打了下ARC，自闭了 ARC107ASimpleMath求和符号移下就没了，可是我取模取挂了了一次，全场就这一个罚时，裂开 ARC107BQuadruple随便枚举枚举算一算 ARC107CShufflePermutation发现行列交换不相干。我们现在只考虑行，到时候列同样算，乘起来即可。若两行能交换，就连一条边。最后每个联通块对答案的贡献是乘上其大小的阶乘（思考下就会发现联通块能实现里面的行全排列） ARC107DNumberofMultisets简单数数dp。考虑一开始有\(k\)个\(1\)，我们要将一些拆成\(\frac{1}{2}\)，再将\(\frac{1}{2}\)拆开。设\(f[i][j]\)表示还要拆\(i\)次，当前这层有\(j(j\mod2=0)\)个的方案数，显然有\(f[i][j]=\sum_{k=j>>1}^nf[i+(j>>1)][k]\)，前缀和优化一波 11.1 正睿普及七连测，数组开小，痛失rak1 zroi1677[2020普转提七连测day6]乒乓分奇偶讨论一下即可 zroi1678[2020普转提七连测day6]宝贝种类很少，就直接建多个主席树，同时在这些主席树上二分 zroi1679[2020普转提七连测day6]翻转仔细思考一波就会发现是个裸的最短路 zroi1680[2020普转提七连测day6]染色待填坑 gutc模拟赛，最近好像搬了些雅礼集训的题，T4不太可做 T1送你一堆区间朴素dp，线段树优化，单点修改，区间乘2 T2轰炸tarjan缩点后最长路 T3送你一个DAG这不和wzy前几天出的那个路径一模一样吗，topsort过程中转移朴素dp，然后斯特林数优化一波 11.2 zroi1581[20联赛集训day16]战术班dp一下发现max就是长度-2，min是长度除二。从构造角度想，max就是每次分出1，min就是每次分出2（2不能再分） zroi1583[20联赛集训day16]擒敌拳写个李超线段树就没了吧，昨天哪个老哥趁着我忘掉了李超树，跟我说只能全局加线段的/px，我差点写了个线段树分治套可持久化李超树 看了套六校，30+50+50+100，真就从后往前写（） nflsoj775公益按位置排序，设f[i]表示考虑前i个人的最小代价，先写出\(n^2\)暴力dp，然后发现可以斜率优化 nflsoj776时代的眼泪就是要找到i，满足\(a(i-j)+b%n=p\),\(j\)是在T中为0/1的位置，就转化成了求区间交。真的没想到，只会大力kmp nflsoj777摩的一开始以为是去对数的trick，仔细想想发现不可做。然后考虑位数作为边权，求最短路dag，在上面拓扑排序（我就这样错过了正解，正解是先把边拆成位数个相连的边，在这个dag上贪心搜索，每次选择数小的边走到未访问过的点即可） nflsoj778树上的数设f[i][j]表示i子树，当前联通块深度距离i最深为j的最大权值。转移类似树上合并背包。发现有个subtask是随机树，这样树高是log的，然后我就想到了长链剖分，然后就没了 T1送你一朵圣诞树还算是挺常见的一个套路？用堆和并查集维护贪心（考虑一个个合并，贡献是siz[a]*sum[b]，用堆维护这个最大值） T2xiz对着kmp改一改就过了 T3城堡发现一定是基环内向树，所以1不在环上，单独考虑1在的子树，方案数可以用状压dp解决（一层层添加） T4arg待填坑 11.3 P1993小K的农场裸的差分约束 P6190[NOIOnline#1入门组]魔法矩阵快速幂的max加法 P2149[SDOI2009]Elaxia的路线建出每个点起始的最短路dag，求dag上同向/异向相交的最长链 CF208EBloodCousins/P5384[Cnoi2019]雪松果树CF原题可以用线段树合并之类的。后面的只能长链剖分