训练日志

· · 个人记录

8.4
今日学了贪心，二分，于我而言难
SP32079 体验分治,每次折半，跨越中间的数据可以用前半后缀与后半前缀解决，——gcd较少，故用map去存，后用乘法原理
P4403 二分 奇偶数的相加性质重要，遇到奇数说明答案在那个区间里
P4377 要会分数规划，将比值转为加减法运算，二分枚举可能的答案，精度要控制在1e-5之内。考虑牛只有选和不选两种状态，用01背包检查答案，注意到体重下限，状态转移有所不同。
P4107 观察数据找线索，发现合并后无影响，便从最小的开始操作，先搜到底再操作，从最下面开始，建树，深搜要加强。
P1080 学会推导出状态关键点，高精度要注意。
P2748 反悔贪心要有储存状态的意识，常用堆，这题思维强，有些难以理解，拆分已知量与未知量后找到关键。
CF865D 学会反悔贪心，记录之前的状态，以便反悔更新状态。

8.6
昨天的东西学了也写不出来，写写今天的日志： 今天主要练习了搜索
P4799 观察到40场比赛，10000元的预算，背包会炸，爆搜2的40次方不可行，选择折半搜索，将2的40次方拆成两个2的20次方组合，重点在于最后的整合，先将一个数组排序，再用二分找预算-另一数组在有序数组中的位置，用lower_boun很好使。
P1379 经典八数码问题，宽搜即可，但要注意在边缘时不可左右移动 P5691 方程的解 先转化表达式，折半搜索，重点仍是匹配答案，求出有序数组中某个数的个数可以用upper-lower!
AT_abc213_e [ABC213E] Stronger Takahashi
重点是用拳头和双端队列，不用的优先级高，放front，用了的优先级低，放back

P2346 四子连棋
有意思的宽搜，两个空格要分别判断
P2324 [SCOI2005] 骑士精神
应用迭代搜索，不断拓宽dfs的深度，再计算差别价值，当预估差别+当前数据大于深度时，即刻退出，限制深度才能节省时间，估价函数是最完美的状态，如本题中一步到位，如果最完美的情况都没法满足要求，就没有做下去的必要
明天再搞树状数组的题，最近太累了，每天晚上状态奇差，想回去，真坐牢！！！
明天会有数理的人来，也不知未来要不要一起上课，我希望可以减轻负担，我想开学后的日子也不好过了。
距离集训结束还有4个轮回：12天

8.7
现在是8.8，我来补一补昨天的日志，昨天心情好了许多，主要还是出了太阳，基本躺平，学dp学不明白，但是一想到打完csp退役，也还好
P1833 樱花 混合背包，注意模板应用，01背包从高到低，完全背包从低到高（可重复选），多选背包注意可选个数
P3478 [POI 2008] STA-Station 树上dp,真搞不明白，还得是题解，换根后记得减去查重子树中点，加上距离增加了的点；
P3047 [USACO12FEB] Nearby Cows G 重点仍在查重，要减去被重复计算的距离-2的子树，但要加上距离父亲处距离为1的子树。 P3188 [HNOI2007] 梦幻岛宝珠 懒得说，反正我不会
P2901 [USACO08MAR] Cow Jogging G A*算法，要注意搜索优先级，短路反向跑一遍dij,并以此作为估价函数，h(x)=now(x)+dij(x),并用优先队列维护，也应该学会自己写自定义优先队列。
就这样吧，这篇日志写于8.8日周五，没有对代码的渴望，只有想回家，还有一天放假，已经适应的不错了，另外数理班的人也见了，真是越来越好。
希望周六可以早点放人！
过完今天距离集训结束还有：10天！

  1. 8 今天写两篇日志，今日学了树上dp,以及树链剖分，依我看还是太超前了，难难难！！！ P3177 [HAOI2015] 树上染色 状态转移有些复杂，重点在于dp[i][j]表示以第i个节点为分割，子树内有j个黑节点的方案总数。计算val用两边同色的点个数乘以边权，在递归后加上
    P5903 【模板】树上 K 级祖先 模板+不会，树链剖分什么鬼东西，代码都要ai辅助阅读，好歹知道了一些知识，算了。 今天为了搞所谓树链剖分，还重修了一次LCA,这玩意也不咋地，其实没什么意思，tarjan老爷子的方法好写，但只支持两点去查，不可多点，而且离线不好操作。明天学学倍增搞LCA! 杂记：虽然上午已经说过了，但我仍旧很期待周日假期的到来，数理那边也是单休吧，等我回家那些群里估计爆掉了，开学就退新生群吧。。。
    想写回信，别人那么用心，心里的思绪不能忍着，但总要考虑别人的感受，多么希望我的高中三年能续上前缘，与她共同进步。。
    今天也做了数学题，还要学学物理，几天下来也不那么忧郁了，多亏了那些同学们，感谢！
    距离放假还有24小时，距离集训结束还有10天，加油！！！
    邮箱密码：000085814201 8.11
    今天是周一，我又来莞中。 前天打了模拟赛，爆砍73分位列第九，其实可以更高，第四题可以写更多，在我退役前还能有几场比赛呢？ 可惜第一题的代码没保存，主要思路在将区间变为小区间，检测有几个区间覆盖小区间，共len(pow(2,fugai)-1)pow(2,n-fugai).
    题解也难，到是研究了LCA倍增，新的一周，加油！
    算上今天，距离集训还有：9天，三轮回
    我希望可以回家住几天。 周末和她聊了聊，压力大减轻。

8.11做题日志： kknd的忠告：
调小你的阈值，用空间换时间（尤其是使用 bitset 的时候）。
检查到底要对什么进行根号（是点数还是边数）。
减小其他部分的复杂度（比如 STL），以及适当卡常。
如果一直过不了，那么可能是写法的问题，建议换一种写法或重构。
值得学习，减少复杂度，接下来应该学习STL与bitset,尽量不看题解写题。今天学了分块，对顶堆；
P1801 黑匣子 对顶堆的应用，重点是一个小根堆与一个大根堆维护序列，以小根堆的堆顶作为第k大元素，当大根堆里的元素超过k个时，弹出堆顶，放进小根堆。
查询堆内元素个数用.size（）
P3396 哈希冲突 根号分治题，暴力核心代码只有几行，但会超时，找寻平衡点，两次暴力，发现模数p若小于sqrt（n),要遍历的位置较多，故在以上情况时提前用n2的预处理跑一遍，做到O(1)查询，即可通过
CF797E Array Queries CF题，同样以sqrt(n)为分界，大于则暴力枚举，否则以dp预处理，注意dp从后往前更新，因为后面可以一步跳出。
P3203 [HNOI2010] 弹飞绵羊 同样如此，以sqrt(n)为分界，大于则直接跑，小于就提前预处理，分块，以sqrt（n）为一块。jump记录会跳到哪，step记录该点要跳几步才能跳出，从块尾向块首预处理。 每次直接跳过一个块。
另外修改时由于只对块内有影响，故直接暴力修改。
P8250 交友问题 万恶，难以理解
朴素算法是枚举每个人的邻居，但由于边非常多，所以会超时，这时要用分治算法，分治界限定为出度B，小于B的点是小点，可以直接枚举。如果是大点，由于数量较少，使用Bitset直接维护邻居，查询时若两个大点则取交集再减，一大一小则遍历小点，计数后减。
bitset 较为实用，应该看看。 周一已经过完了，好消息是20日下午放学，集训结束不远了！加油！！

8.12训练日志：哈几张你这家伙天天在日志里写些没用的东西[○･｀Д´･ ○]
U502676 线段树上二分模版 无评定，没啥成就感，具体而言，在每次要查询时从根而下，维护一个区间内的最大值，如果找的是区间内第一个比k大的数，那就从左子树的最大值比起，如果左子树的最大值比k大，就遍历左子树，直到遍历到长度为1的区间。
重点在于如果左边没有（返回-1）就去右边找，由于线段树左子树所存的变量原始下标比右子树原始下标大，所以找大从左开始，找小则反之。
P4145 上帝造题的七分钟 2 / 花神游历各国
复习题目，主要难度在于如何维护开平方，但是观察到数据最多开六次平方就会变成一。故考虑暴力修改，单点修改后记得回溯回去更改父亲节点的值。省下时间：记录每个区间里的最大值，如果发现最大值为1，直接跳过修改。 T125847 【模板】动态开点线段树 不喜欢，调了很久。 适合AI去写而不是人去写，这东西针对着阈值极大（1e9） 但点数较少的树有效，每次拓展左右儿子时才新建节点，pushdown操作要熟练
P4198 楼房重建 大份思维题
主要写写思路，看到视线想到斜率，斜率较大可以看到。 发现有修改操作，考虑线段树，维护一个区间的斜率最大值，与站在这个区间左边能看到的屋子。
比较加值时，一个大区间可见左1，我们可以先查找右区间的左区间的最大值，如果这个最大值比左区间的最大值小，那么右区间的左区间的所有答案一定看不到，直接跳了。所以我们就可以递归查找右区间的右区间，同上。

如果右区间的左区间的最大值比左区间的最大值大，那么原来被右区间的左区间挡住的现在一样会被挡住，我们就可以加上右区间的答案，所以我们可以递归查找右区间的左区间

但是这里题解有一个坑点，右区间的答案不一定是ans[右区间的右区间]，因为这个答案是建立在右区间的1号基础之上，而我们要求的则是建立在左区间1号基础上的右区间答案，这里难以理解。
所以右区间的答案应该是ans[右区间]-ans[右区间的左区间],这样才能得到右区间的答案。实现O(logn);
今天学线段树，真是恶心，好在晚上没有荒废，学了数学，写了字帖，轮回还有1天结束，明天加油！！！！！
距离集训结束还有7天。

8.13 与其说是日志，倒不如说是日记，算法源于生活，编程来于快乐。先记录生活吧，放一句前几天看到的话：OI,一些人追求的梦想，一些人放弃的理想。
挺符合我现在的处境，不是吗？
但愿未来会美好，顺利进入初赛，怎么说也是最后一次了，再拼一把，就算只会暴力，好好告个别，OI.
学习方面今天写了字帖，明天就把字帖搞完了，数学善待我！
生活方面，去了门外的东东美食店吃饭，差评！不好吃，贵，环境好像还不太卫生=（，还是食堂好！
算法：今天研究了各种二维偏序问题的维护方法； P1908 逆序对 先以逆序对引入，坐标已有序，需维护即为值，使用树状数组维护，先离散化数据，每有一个数就在对应的离散化数组里加1，统计答案时就相当于查找自己之前有多少人比自己小，就是前缀和，再用i-que(ai)就是比自己大的数，也就是逆序对。
3919 【模板】可持久化线段树 1（可持久化数组）
传说中的主席树，这玩意支持历史查询，具体说来在每次修改时都新建一个根节点，这颗线段树保留了原有的一些节点与更改后的节点，修改时O（logn）,每次建边时就新建节点，更改时就找出先前版本记录过的改，复制。
难难难！！！ 看来手搓不太可能，先搞明白线段树吧，(/ω＼)
P3834 【模板】可持久化线段树 2
这也是个**题，难难难！！！！！！
先将数据去重后离散化，可以用unique函数，再lower_bound定位到映射值。
不同于普通线段树的是主席树的左右子树节点编号并不能够用计算得到，所以我们需要记录下来，但是对应的区间还是没问题的。真写不明白，抄题解抄了很久，AI调了很久，真难受！！！！！！！！！
P1856 [IOI 1998][USACO5.5] 矩形周长 Picture
I AK IOI!! 开个玩笑，二维偏序题，超模.
扫描线法，先将矩形从下到上排序，扫到一个下边，就在这个矩形，左右区间里加一，到了矩形上边再减一，记得去重。每次统计的答案就是覆盖长度差的绝对值，可以想象一个两个矩形，上大下小，要加的周长就是暴露在外长边剪短边。
对于竖边，可以交换横纵坐标再扫一遍，也可以记录有几个端点，再乘上高度差即可。

距离集训结束还有6天，加油！！
说实话天天搞线段树没什么体验感，不想搞=（，但总比dp好！
8.14开头：昨天星期三，今天星期四。两天就放假，还要加把劲。
又来写日志，今天挺有意思的。大家晚上都不做事。编程班是这样的。
P4168 [Violet] 蒲公英 大份题
分块解法，每次维护一个块内的众数，原数组还要离散化才能通过，采用前缀和数组记录每个区间内数字出现的次数，重点：s[i][j]+=s[i-1][j];可以做到统计次数。 再用一个f数组维护各个区间里的众数，f[i][j]表示区间到j之间的众数，如果查询区间的左右端点距离小于一个块，那就暴力搞。否则先记录大区间里的众数，再检查两端会不会产生行的众数，唯一要注意的是边界的判断，左从l到sqrbl;右从r到sqr(br-1)+1.这样问题就迎刃而解了。
P1494 [国家集训队] 小 Z 的袜子 也是进上国家集训队了。
曾今做过，主要在于莫队思想与修改，先把询问排序了，再一点一点修改。
P1903 [国家集训队] 数颜色 / 维护队列 带修莫队 再加了一个时间的维度，先调左右端点，再调时间维度，时间维度的调法在于先看要修改的点在不在区间内，如果在的话，那就删去原先的点，加上修改后的的点。
这里有一个小巧思，每次修改操作后将原先值和修改值互换，由于每次修改时间总会在这两个状态间循环，所以可以这样干。
P3674 小清新人渣的本愿 背景太乱了吧 这题有些新奇，虽然只是普通莫队，采取s数组记录区间内的数字个数，由于数字小，可以直接存储，否则应该使用离散化数组，运用点集bitset，若a-b=x,即将存在状态f左移x位后，b与a的位子上映射为1。
如果是加法的话，先维护一个g点集，记录C-a,那么a+b=x,可以转化为C-y+b=x（C-y=a）即b-y=C-n同上
如果是乘法就直接枚举因数，最多sqrt(x)次，可接受。
莞中食堂也有一个祛魅的过程，今天牢郑说食堂不像以前那样好吃，再正常不过了。lilong学长还是值得尊敬的，起码在OI这一块。
距离集训结束还有：5天；
距离假期还有：2天
周六不想打模拟赛=（ 8.15 下了暴雨，非常无奈啊； P3384 【模板】重链剖分/树链剖分 其实就这个主要一些，两次dfs，记录父亲，重儿子，深度，子树等信息，再用线段树维护，达到树上查询修改等操作，要记得找祖先的操作，但是代码动辄200行，写不明白。
P2486 [SDOI2011] 染色，P1505 [国家集训队] 旅游
同上，唯一的作用是恶心你。
只是P1505中边权转化有点意思，将边权转到深度较大的节点，由于先从下往上遍历。
8.16 搞完比赛精疲力尽，水水得了，最后一题的数学方法无法推出式子，没办法，第二题的线段树遇上区间异或无法战胜，但大意是用一个数组记录每个二进制位，异或的性质导致一个数异或0不变，异或1取反，这样就可以枚举哪些位是1，而后再分别修改
异或核心逻辑：异或k会翻转二进制位中k为 1 的位，因此 1 的个数变为 “区间大小 - 原个数”，总和也相应更新（变化量为位的权重乘以个数变化）。 8.18 又是新的一周，美好周末say good bye;
周末和她聊了聊，压力大减轻。
新的一周上三天军训，希望好过些，另外，最近要背古诗词，学学数学，还要写信（ =））。
8.18日志2
题写不完？知识点学不懂？ 让我们来看看第三个大招。 又不知在搞什么，还是太超模了（抄抄模板）。
P3366 【模板】最小生成树 怎么好像以前学过？
老Y干的吧，用kruscal算法，按边权排序，每次加入最短的边，并用并查集维护点的关系，防止构成环。直到加到第n-1条边，就是图的最小生成树。
题外话：这已经是最简单的了 (￣ェ￣;)(￣ェ￣;) P4768 [NOI2018] 归程 狄杰克斯特拉的回旋镖还是击中了我的心，这题要用kruscal重构树，将两个节点的边权转化为一个新的虚拟节点的点权，这样的点最多有n-1个，每个连通块所在的集合将变成一颗二叉树。
摘抄题解：1.树上除叶子结点以外的点都对应着原来生成树中的边，叶子结点就是原来生成树上的节点。
2.由于新点的创建顺序与原来生成树上边权的大小有关，可以发现，从每个点到根节点上除叶子结点外按顺序访问到的点的点权是单调的。
3.出于kruskal算法贪心的性质，两个点u和v的lca的点权就对应着它们最小生成树上的瓶颈。
4.实际上这棵树就是一个二叉堆 这题构建以海拔为关键字的小根堆，只要水位线低于子树根节点的海拔，子树内节点就可以直接到达。再找叶子结点到1的最短路，代表必须用脚走路的地方。
再模拟不同节点作为根节点？我也不太理解，还要用树上差分，真是毒瘤，不过貌似骗骗能有45分？
P5854 【模板】笛卡尔树
两个维度建树，其中一个维度满足二叉搜索树，另一个维度满足堆的性质。
搜索树的性质：左节点都大于根节点，右节点都小于根节点。 以模板为例，用单调栈O(n)维护“上一个比自己大的”，若j>i.且a[j]>a[i],那么j为i的右儿子。
若新元素导致栈内弹完，说明他比栈内数都小，就让最后弹出的东西作为他的左儿子。。。
如果新元素不会导致弹栈（val比栈顶的val还大），因为先加入的元素的 key一定小于当前元素的key ，因此当前元素应作为栈顶元素的右儿子。
如果新元素直接导致栈弹完，我们取最后一个弹出的元素，将其作为当前元素的左儿子，因为其key 都小于当前元素的key
如果导致弹栈但并未弹完，让最后一个弹出的元素作为当前元素的左儿子，让当前元素作为栈顶元素的右儿子。
每次操作完成后，都要把当前元素压入栈中。
这是什么东东，我也不知道。。。
8.18距离集训结束只剩两天了，加油！！！

8.19 The last diary
It is time to say goodbye; 今日专题：最短路
模板两题不提；
P1993 小 K 的农场 首次接触差分约束，具体说来，若一个不等关系a[i]<=b[i]+c; 可以视作在b[i]与a[i]之间有一条长度为c的边。若a[i]>=b[i]+c则可以视作a[i]与b[i]之间有一条长为-c的边，检测有没有解就检测最短路，观察有无负环，负环出现则代表无解。
用spfa可以检测负环，每次如BFS拓展节点，入队的节点标记一次，出队的节点取消标记，这样可以保证不重。如果有负边权，这个节点会入队无数次（最优），此时只要加入计数数组，统计每个节点入队次数，超过n+1则为负环。
P1525 [NOIP 2010 提高组] 关押罪犯 贪心加种类并查集
优先考虑危害大的，这样可以最小化答案，u,u+n,两个节点分别表示在不同的监狱里。若两个人有冲突，就将（u，v+n）放在一起，这里v+n代表v的反状态，v同理，当u，u+n||v,v+n在一起时，输出答案。
P2024 [NOI2001] 食物链
维护三倍的并查集，表示三个种类。说a&b同，检测a能否吃b,即测（a，b+n）是否在一个集合里，检b同理。
检测吃与被吃的关系，先查是否相同，再查方向。 两种操作合并时都要操作三个维度，记得特判
P1196 [NOI2002] 银河英雄传说
在并查集中路径压缩时维护了深度等信息，记录深度与飞船数，“先找根” 的核心目的是：确保父节点的权重已经是 “父节点到根” 的正确值，其余与并查集相同。
P3275 [SCOI2011] 糖果 状态非常多的差分约束，描述：如果 X=1， 表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的糖果一样多；
如果 X=2， 表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果；
如果 X=3， 表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到的糖果；
如果 X=4， 表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果；
如果 X=5， 表示第 A 个小朋友分到的糖果必须不多于第 B 个小朋友分到的糖果；
若x=1,在A,B间建双向0边
若x=2,在A,B间建A to B 1边，表示A最少要多一个才能到达B
若x=3,在A,B间建B to A 0边，表示B最少要与A相等才能到达A
若x=4,在A,B间建B to A 1边，表示B最少多一个才能到达A 若x=5,在A,B间建A to B 0边，表示A最少要与B相等才能到达A 再跑spfa,寻找最长路正环检测有解或无解。
距离集训结束只剩最后一天，好好好 !!
8.20 集训最后一天，爽快，马上结束了！！