[Acker]AFO前总结
20191020
昨天核了下分，如果没涂错卡之类的话应该是91.5，并查集x！=y的坑进了，不能读空串的坑进了，毒瘤状压第一问跪了。
鬼知道我能不能进复赛……感觉ZJ遍地90，传闻分数线能到100……
今天打了套普转提当初赛结束的康复训练。
T1有趣的数
第一眼以为是数位dp？？慌兮兮地写了个暴力然后准备跑路，仔细想想好像可以分类讨论直接算。
于是正解又双叒叕写挂了，好吧因为数位分类讨论确实比较麻烦。
正解是直接构造，然后验证是不是在合法范围内就行了，这个构造非常NB
总结1：对于枚举起来情况很多很恶心的题目，构造是应该考虑地方向
总结2：对于枚举类问题没如果合法或者不合法情况很少，考虑构造或者容斥
T2欢乐ABC
全场最水，我离正解就差个移项系列。
总结3：枚举判定，枚举的层数和式子有关，很多时候通过对式子的变化可以有效降低枚举层数，以达到优化复杂度的目的
T3数位问题
本来都准备放弃去肛T4的dp了，老刘中途良心提醒11的倍数的充要条件是其奇数位数字之和减去偶数位数字之和为11的倍数
瞎推了两下发现答案和0没关系，传统状压替爆搜，稳拿40稳个鬼啊因为没判-1丢了二十
总结4：以后要在演草纸上记下边界条件
正解dp，再次提醒我与答案有关的因素应该勇敢地丢到状态里，数据范围这么小。
T4魔王勇者打游戏
写了个10分就跑了，然鹅随后发现我在写10分的时候基本上写出了正解。
正解是贪心艹动规，就考你敢不敢大胆猜想并勇敢验证。（这不初赛套路么）
首先按照生命值从小到大排序
考虑一下，如果当前有残血为1的怪，放群攻收益最大，如果余怪超过2个，放群攻比放暴击收益更大，因为后者虽然有可能会先一步把最小的怪砍死，但会使你损失一个轮次，可以手玩验证。
根据10分贪心经验，或者你做过守望者的逃离，很容易证明先放大招更优。
所以首先枚举每一个大招暴击还是群攻，记录群攻次数，剩下的全都普攻。
普攻记录贡献，是每个怪物群攻后剩余生命值X其从小到大的排名
20191021
快乐无比的套题day1
T1你爸爸jjh的疑惑
神奇结论题？？感觉正解的证明有点清奇，考场上肯定不会严谨思考的
T2捉迷藏
套路树规，然鹅考虑的有点问题。其实在考虑暴力的过程中就应该意识到只需要减掉最小的以0为根的子树即可
维护这个东西可以用最长链换根dp的思路，只是细节有点杂乱。如果当前节点为0，对于它儿子节点的g函数，可以考虑把以x为根的一大坨子树删掉
不过这个应该只针对了一个关键点的情况，题目良心地给出来了
T3序列
每次有效的膜操作会至少使得左端点的数值除二，因此有效的段不超过log段
那么段的边界二分出来即可
20191028
鸽了好几天，总结一下这几天比较有感悟的几道题
雅礼首题day2T1
期望概念题，还是概率期望做得少。
考试的时候还枚举了出现相同的数的位置，完全没必要，因为对最终答案期望分解以后，设
这样一来相当于一定确定了两个数的位置。
雅礼首题day2T2
不带修，多次查询，且之和子树有关
考虑dfs序或者dsuontree
有根树问题常常把
本题就有典型的运用：以1为根的有根树中，任意一个祖先和其子孙的距离，通过分别处理他们到1的距离相减即可
ZR普转提day3T2汽水
总结：本题最大的其实在于类背包问题的又一种解决方案——最短路，前者主要在于“放得下”，后者更在于“刚刚好”
20191101
万圣节快乐
今天来总结一些有趣的数论结论
数论常见结论整理（整数划分向）
1 将一个正整数划分为几个正整数相加，使得这几个正整数乘积最大，应将其尽量划分为3，不够就化2
先说一个源于递推式的感性理解，设
递归地去考虑，最终我们必然会划分到1，而与1相乘没有任何意义，还不如回溯一步变成2或3
严谨证明可参考洛谷上题目题解
题目来源：[SCOI2006]整数划分（要用高精，灰常恶心）
2 给定整数1-n,试确定一个排列，使得序列a中数字的种类最多。定义序列a的首项为该排列的首项，此后每一项为排列中对应位置的数与a序列中对应位置前一项数的gcd
最贪心的想法是排列第一项为1-n中质因子最多的那个，可以反证法证明没有更优的做法。
如何确定这个数？
*这个数的质因子分解一定为$2^x3^y
对于大于等于5的质因子，可以用
对于y大于等于2，可以用
题目来源：大佬原创题目
今日份考试经验教训
一些与数划分有关的结论题
对于确定的结论，往往可以考虑找规律构造
类旅行商问题
非常在意什么东西已经处理，什么还没有处理，如果这两个东西可以明显形成动态规划的状态，往往状压dp
今日份做题总结
Telephone lines
第一种是分层图dp+spfa，因为常规dp思路是有后效性的，可以借助spfa直至最优解不再更新，即所有状态收敛
第二种是最常规的二分，本题的判定是一个亮点。
本题的check在本质上检查二分值的排名，所以我们可以把比它大的边定义权值为1，比它小的边定义权值为0，然后看最短路是否不超过k即可
最优贸易
对于先后关系分明的题目，往往暗示着遍历的顺序，本题和铺地毯就是很好的例子
20191102
感谢震哥的图论数据结构专练
A单调栈+二维差分
感觉真是道神仙题%%%
20191105
T1树上匹配
由于题目的特性，我们可以认为不能相互匹配的牌为同一类，考虑树形dp，一个显然的贪心是子树内能相互匹配的一定更优，跨越父亲节点的一定不优。
T2洗衣服
本题给我最大的启示是，这种类型题目往往具有答案单调性，因此常见做法是二分答案+贪心或者dp