2024.10 训练日记
从现在开始需要做到的就只有踏实，把打好每一场比赛定为自己目标。
我们将难度分为 5" role="presentation">5 个等级:
★" role="presentation">★ 简单题，根本不配进入 NOI 的考场，做着玩玩。或者为模板题。
★" role="presentation">★ 签到题，在 NOI 赛场上强银选手几乎人人都会，如果赛场上不会的话对冲银的影响是非常大的，要避免。
★" role="presentation">★ 中等题，在 NOI 赛场上有区分度的题，能区分出银牌选手，这种题是决定比赛的关键。
★" role="presentation">★ 困难题，在 NOI 赛场上比较难的题，如果能够做出来的话金牌基本就稳了。
★" role="presentation">★ zak 题，国家队水平的题，做这种题可以开拓视野，启迪思维。
查阅题解的题目会用 ♣" role="presentation">♣ 标出，要避免。
题目后面会写一点评价与感悟。按照 Linshey 意见，一套模拟赛算 1" role="presentation">1 题。
日期范围：2024.10.1∼2024.10.31" role="presentation">2024.10.1∼2024.10.31。总计过题：?" role="presentation">?。
[2024/10/01]" role="presentation">[2024/10/01]#
当天过题数：3" role="presentation">3。
★" role="presentation">★ P8084，写个好一点的暴力。
♣" role="presentation">♣ ★" role="presentation">★ b6e7，很厉害的竞赛图三染色构造题。
♣" role="presentation">♣ ★" role="presentation">★ 随机逆序对，简单数学推导 +BIT 优化。
[2024/10/02]" role="presentation">[2024/10/02]#
当天过题数：2" role="presentation">2。
♣" role="presentation">♣ ★" role="presentation">★ P4581，感受那股劲。但是存在正确性更好的 Hyperloglog 算法。
♣" role="presentation">♣ ★" role="presentation">★ CF241D，观察到往后添加一个数 modp" role="presentation">modp 较为随机，保留 [1,24]" role="presentation">[1,24] 内的数爆搜即可。
[2024/10/03]" role="presentation">[2024/10/03]#
nfls 模拟赛 ×1" role="presentation">×1，100+100+100+0=300" role="presentation">100+100+100+0=300，rk. 20。
T4 没打暴力，下次要加油。T2 这种反悔贪心还是太容易被卡了，下次要注意。
当天过题数：3" role="presentation">3。
♣" role="presentation">♣ ★" role="presentation">★ AGC031C，很厉害的构造题！依然是递归构造。
♣" role="presentation">♣ ★" role="presentation">★ AGC034D，简单拆绝对值费用流建模题。
[2024/10/04]" role="presentation">[2024/10/04]#
nfls 模拟赛 ×1" role="presentation">×1，5+100+100+0=205" role="presentation">5+100+100+0=205，rk. 33。
T1 出题人直接开 107" role="presentation">107 的数据，导致我想了个复杂做法然后挂成 5" role="presentation">5 分了，然后还有看错比赛结束时间导致 T4 暴力没打。下次需要注意。
当天过题数：3" role="presentation">3。
★" role="presentation">★ AGC002D，自己想了一个俩 log" role="presentation">log 做法，学习了牛牛单 log" role="presentation">log 做法。
♣" role="presentation">♣ ★" role="presentation">★ AGC029E，其实是简单找性质题，不思考导致的。
[2024/10/05]" role="presentation">[2024/10/05]#
当天过题数：3" role="presentation">3。
♣" role="presentation">♣ ★" role="presentation">★ P7423，困难推式子 + NTT。
♣" role="presentation">♣ ★" role="presentation">★ P8979，猜测、寻找齐次递推，然后上板子。
★" role="presentation">★ P5881，初见读错题了，考察数学基本功。
[2024/10/06]" role="presentation">[2024/10/06]#
当天过题数：3" role="presentation">3。
★" role="presentation">★ qoj 9434，简单算几，上个双指针就行了。注意过程中尽量不要出现浮点数，会掉精度然后坠机。
★" role="presentation">★ ABC374G，缩点加最小可重链覆盖板子题。
★" role="presentation">★ 染色方案，上一题构造方案版本，代码实现有点小难。
[2024/10/07]" role="presentation">[2024/10/07]#
当天过题数：6" role="presentation">6。
★" role="presentation">★ gym105143C，很厉害的构造题，用到的 trick 有点多。
♣" role="presentation">♣ ★" role="presentation">★ P4298，构造方案很难。
♣" role="presentation">♣ ★" role="presentation">★ CF590E，ACAM + 最长反链构造方案。
♣" role="presentation">♣ ★" role="presentation">★ CF1693F，很深刻的贪心，但是代码小清新。
♣" role="presentation">♣ ★" role="presentation">★ P10779，仙人掌最大独立集问题，在 tarjan 过程中 dp。
★" role="presentation">★ P11175，板子题，推销博客！
[2024/10/08]" role="presentation">[2024/10/08]#
nfls 模拟赛 ×1" role="presentation">×1，100+0+30+0=130" role="presentation">100+0+30+0=130，rk. 29。
T2 是半群多项式乘法，应该多想想能想出来的。后俩题有点难度，可以尝试多打点暴力的。
当天过题数：4" role="presentation">4。
♣" role="presentation">♣ ★" role="presentation">★ mex2，界很紧啊，很困难的构造题。
★" role="presentation">★ P11170，大胆猜测所有环 xor 和必须为 0" role="presentation">0，用线性基口胡感性理解一下。然后 dfs 一遍做完了。
★" role="presentation">★ P3354，简单 dp，记下祖先第一个被选的即可。
[2024/10/09]" role="presentation">[2024/10/09]#
当天过题数：4" role="presentation">4。
★" role="presentation">★ P9197，困难的连续段 dp 经典例题。
★" role="presentation">★ P2300，单调队列优化 dp，但是由于数据随机暴力似乎能过？
★" role="presentation">★ P3203，分块经典例题，第一次居然想假了，有点太菜了。
★" role="presentation">★ P7446，抛去卡常因素几乎和上一题一个套路，再配合点树剖跳 lca 的思想即可。
[2024/10/10]" role="presentation">[2024/10/10]#
当天过题数：5" role="presentation">5。
♣" role="presentation">♣ ★" role="presentation">★ AGC059E，很深刻的三染色构造题。
♣" role="presentation">♣ ★" role="presentation">★ ARC089C，感觉这个思路其实用烂了，警钟！
★" role="presentation">★ CF1027E，很好的推式子题，难度一般。
♣" role="presentation">♣ ★" role="presentation">★ ARC136E，其实是简单找性质题，多练。
♣" role="presentation">♣ ★" role="presentation">★ loj 4158，又是交互求树的结构，要多想！应该想出来的！
[2024/10/11]" role="presentation">[2024/10/11]#
nfls 模拟赛 ×1" role="presentation">×1，100+20+40+0=160" role="presentation">100+20+40+0=160，rk. 34。
T2 没想到关键性质，然后 T4 暴力一点没打，下次应该注意。
当天过题数：3" role="presentation">3。
♣" role="presentation">♣ ★" role="presentation">★ 保护隐私，很好的直径加上点边容斥题，学到很多！
♣" role="presentation">♣ ★" role="presentation">★ ARC065D，简单 dp 题，确定一下前缀 1" role="presentation">1 的个数的上下界而后转移即可。
[2024/10/12]" role="presentation">[2024/10/12]#
打了 The 3rd Universal Cup. Stage 12: Qinhuangdao，开场疯狂杀杀杀，过了 (4/8)" role="presentation">(4/8) 题。
由于某些原因带着怒气打的，我们队伍甚至由于课业原因实际上只有两个人，一度领先 wmh+hhoppitree+ 某前国家集训队成员组成的队伍。后面去看运动会就开摆了，其实再多打打说不定真的能爆超。
当天过题数：1" role="presentation">1。
[2024/10/13]" role="presentation">[2024/10/13]#
当天过题数：1" role="presentation">1。
♣" role="presentation">♣ ★" role="presentation">★ CF1781G，很深刻的二叉树黑白染色构造题。
[2024/10/14]" role="presentation">[2024/10/14]#
nfls 模拟赛 ×1" role="presentation">×1，100+100+100+30=330" role="presentation">100+100+100+30=330，rk. 8。
T4 暴力少打了一个 15pts 后面开摆了，可以改进。
当天过题数：4" role="presentation">4。
♣" role="presentation">♣ ★" role="presentation">★ P9067，lxl 说过，这种邻域信息维护父亲一定死。只维护子方向的邻域，想想如何启发式合并。
★" role="presentation">★ qoj 5，参考 O(p0.75/log⁡p)−O(log⁡p)" role="presentation">O(p0.75/logp)−O(logp) 的离散对数，自创了个 O(B)−O(log⁡(p/B))" role="presentation">O(B)−O(log(p/B)) 的在线逆元做法。
♣" role="presentation">♣ ★" role="presentation">★ nflsoj P16076，形式化表示 0010 和 1101 的总数，然后由于 01" role="presentation">01 个数守恒，设计 dp 即可。
[2024/10/15]" role="presentation">[2024/10/15]#
nfls 模拟赛 ×1" role="presentation">×1，100+30+40+65=235" role="presentation">100+30+40+65=235，rk. 41。
T4 被卡常 100→65" role="presentation">100→65，其他感觉没啥问题。
当天过题数：5" role="presentation">5。
♣" role="presentation">♣ ★" role="presentation">★ P11192，按照 P3923 的方法构造 2n/2" role="presentation">2n/2 元有限域，然后考虑构造 S={2n/2x+(x3)R:x∈[0,2n/2)}" role="presentation">S={2n/2x+(x3)R:x∈[0,2n/2)}，其中 (x3)R" role="presentation">(x3)R 表示 x" role="presentation">x 用有限域乘法取立方。注意到有限域上的加法其实就是异或操作，且根据有限域的性质 a+b=c+d,a3+b3=c3+d3⇒ab=cd⇒{a,b}={c,d}" role="presentation">a+b=c+d,a3+b3=c3+d3⇒ab=cd⇒{a,b}={c,d}，于是集合 S" role="presentation">S 符合题意。
★" role="presentation">★ ARC185E，简单数论题。
♣" role="presentation">♣ ★" role="presentation">★ ARC185B，又是不会的经典 trick，考虑先确定最终序列，然后判断是否合法。
♣" role="presentation">♣ ★" role="presentation">★ ARC066C，观察到括号一定在减号后面，并且括号嵌套不超过 2" role="presentation">2 层，dp/贪心即可。
[2024/10/16]" role="presentation">[2024/10/16]#
当天过题数：5" role="presentation">5。
★" role="presentation">★ P11197，四维偏序计数，考虑容斥降维，最终转化成求若干次二维偏序。
♣" role="presentation">♣ ★" role="presentation">★ P10872，很深刻的构造，考虑先算出下界，然后构造顶到下界。
♣" role="presentation">♣ ★" role="presentation">★ P9388，推推性质，然后主席树维护前 k" role="presentation">k 小之和。
★" role="presentation">★ Bell numbers，找规律题，行列式是 ∏k=0nk!" role="presentation">∏k=0nk!，但是证明不会。
★" role="presentation">★ P6623，对每一个树上的节点，考虑其的每一个二进制位会对哪些祖先贡献，树上差分推一推。
[2024/10/17]" role="presentation">[2024/10/17]#
当天过题数：4" role="presentation">4。
♣" role="presentation">♣ ★" role="presentation">★ P8906，考虑充分利用 meet-in-the-mid 思想，记录经过两条边的最短路然后转移即可。
♣" role="presentation">♣ ★" role="presentation">★ 退休计划 II，很深刻，建出 dfs 生成树后考虑主席树查第 k" role="presentation">k 小那样构造，然后能证明一定有解。
♣" role="presentation">♣ ★" role="presentation">★ P11203，按 r" role="presentation">r 排序，考虑每个点之和后缀 l" role="presentation">l 的最小值的位置连边，然后上数据结构。
★" role="presentation">★ CF1788D，简单找性质题，发现聚合一定是 >>>>><<< 状物，然后枚举分界点处两个端点算有多少贡献即可。
[2024/10/18]" role="presentation">[2024/10/18]#
nfls 模拟赛 ×1" role="presentation">×1，100+100+25+4=229" role="presentation">100+100+25+4=229，rk. 29。
T3,T4 或许能得更多暴力分，是努力的方向。
当天过题数：4" role="presentation">4。
♣" role="presentation">♣ ★" role="presentation">★ AGC034E，枚举最后那个点，拎出来当根，然后经典的按照绝对众数那套做个 dp 处理细节。存在换根优化到 O(n)" role="presentation">O(n) 的做法。
♣" role="presentation">♣ ★" role="presentation">★ AGC016E，留着你是因为以后要炖了你，然后考虑时光倒流，观察性质即可。
★" role="presentation">★ P10871，很妙的国际象棋皇后构造题，终于是独立想出来了！
[2024/10/19]" role="presentation">[2024/10/19]#
校内模拟赛 ×1" role="presentation">×1。
傻逼。挂分的点很多，算是在 csp 前狠狠地吃教训了。
打了 The 3rd Universal Cup. Stage 13: Sendai，过了 (4/10)" role="presentation">(4/10) 题，最后 10 分钟极限过题！打得最牛的一场，斩获 rk 前 20" role="presentation">20。
当天过题数：2" role="presentation">2。
[2024/10/20]" role="presentation">[2024/10/20]#
当天过题数：3" role="presentation">3。
♣" role="presentation">♣ ★" role="presentation">★ ABC135F，倍长字符串，然后哈希判断，然后猜一点结论就过了。
★" role="presentation">★ P11212，枚举即可。
★" role="presentation">★ P11211，用下原根和 exgcd，剩下的就是枚举的事。
[2024/10/21]" role="presentation">[2024/10/21]#
nfls 模拟赛 ×1" role="presentation">×1，100+73+0+0=173" role="presentation">100+73+0+0=173，rk. 41。
傻逼场，T2 写了个假做法，猜了个大数据下卡不掉的做法，改改阈值就过了。
当天过题数：3" role="presentation">3。
★" role="presentation">★ P4252，一般图直径求解的题答，按度数排序搜索很优秀，加点随机化。
♣" role="presentation">♣ ★" role="presentation">★ P4198，兔队线段树板子题。
[2024/10/22]" role="presentation">[2024/10/22]#
当天过题数：6" role="presentation">6。
★" role="presentation">★ qoj 6506，简单结论题。
★" role="presentation">★ qoj 6510，考虑最小的 2t>k" role="presentation">2t>k，然后按 /2k" role="presentation">/2k 分组，观察性质即可。
♣" role="presentation">♣ ★" role="presentation">★ qoj 6504，随机赋矩阵的 trick。
★" role="presentation">★ P11088，观察性质，一个时刻一个能放后面也都能放，类似拓扑序做即可。
★" role="presentation">★ P10089，注意到奇偶分别有单调性，二分加哈希即可。
♣" role="presentation">♣ ★" role="presentation">★ 4077，首先 q=1" role="presentation">q=1 用线段树简单优化 dp，然后发现决策点一定在凸包上，用最小乘积生成树的 trick 做，查询二分凸包即可。
相关知识
狗狗的训练日记
训练师日记游戏多版本合集
训练师日记游戏下载
训练师日记游戏官方版下载
什么是训练日记以及如何创建它？
我家狗子的训练日记
训狗日记
【热门】动物日记三篇
【日记】狗狗日记(12)
宠物狗狗养成日记手游下载
网址: 2024.10 训练日记 https://m.mcbbbk.com/newsview435507.html
| 上一篇: 训练日记 |
下一篇: 【前瞻福利玩法】猫咪日记＆散步地 |
