模拟赛记录
23-10-04¶
今天很唐。T2是个性质：
P3915 树的分解 - 洛谷 | 计算机科学教育新生态
这告诉我们要多尝试一下！
T3是个求导。不过确实学艺不精，忘了商式求导：上导下不导-上不导下导，除以分母的平方
同时也复习了一下链式求导，这个可以导出来商式求导：
有机会学一下费曼求导法。
T1是一个二合一。属于是考了俩板子根号算法，可惜我不会啊！！！分块真是个好东西啊，骗一些树套树的分。
T4要用长链剖分，用长链来贪心。还没补。
23-10-05¶
T1诈骗题。
T2赛时想到一点，注意：如果斜率丢精度的话可以同时把xy的最简分子分母存下来，并且不影响用x,y,b表示唯一一条直线。
T3打了20分暴力。还没补。又是计数题。
T4是个插头dp维护欧拉路。
23-10-06¶
T1场切了，猜出来结论加上Kruskal的思想就行。居然比马老师先想到（
冒泡排序趟数期望
T2是个计数。构造排列满足：
\(\max_{1\le i \le n} \sum\limits_{1\le j<i} [p_{j}>p_{i}] = k\)
讲人话就是每个数前面比他大的个数不能超过 \(k\)，且至少有一个等于 \(k\)。
考虑容斥原理，即 所有不超过 \(k\) 的方案 减去 所有小于 \(k\)（不超过 \(k-1\)）的方案。如图所示：
不超过 \(k\)：
第一位应该只能在 \([1,k+1]\) 中选择，后面以此类推，共 \(n-k\) 项。
T3经典拆贡献，要统计各个矩形内的点的数量 \(n\) 的 \(k=1,2,3\) 次方：
思考组合数的意义：在每个矩形内选 \(1,2,3\) 个点的方案数。于是，我们转化成对任意 \(1,2,3\) 个点，能被多少矩形包含在内。由此我们便拆开了 \(n^k\)。
23-10-07¶
我超，今天居然比马老师高！！！（但依然是个彩笔
T1 是傻逼题，打个表找找规律就行；
T2 有点意思，就是不知道为啥我直接贪心也能过。。。得复习一下递推逆元。。。
几个相互约束的量取最值，大概率会是加权/均值时取得最优解。并且，多元约束可以先考虑二元约束，列出两个状态在最优解时的表达式，然后尝试推广到多维。
T3 是第二类斯特林数反演，转化 \(m^n\) 成斯特林数和组合数。
T4 是分块+根号分治。是道YNOI的题。
好好好，考两道黑的是吧
23-10-08¶
今天放假，不知道补不补。
23-10-09¶
这两天一天比一天抽象。。。赛时也不知道咋搞的
T1 死活没想到。光想着怎么把乘积拆成和式了，结果这个题直接01背包统计每个因子出现的次数……方向错了是真的不行，以后一个方向不能卡太久，二十分钟没方向就换题。
T2 有一点：先想办法把约束形式化。把全部满足→换成对任意都满足。由此，转化成了只找到某个最（优/劣）的情况，是否还能满足要求。
23.10.10¶
23.10.11¶
23.10.12¶
今天打的还行。。。
T1 读完题写完暴力突然一下就会了。T2 想了一下感觉直接dfs就行。
然后九点多就开始坐牢。感觉我切题速度应该在1h一道？
T3 赛时想假了，结果直接就是板子最小生成树。用的是 Boruvka 算法，其最麻烦的在与快速求出最小边，依然是一个维护最优和满足某个约束的次优的形式（比如这个就是维护前缀最大值以及不和前缀最大值在同一个块的前缀最大值，那么如果最优无法满足就一定可以用次优）。
T4 考场上没思路，其实题本身不难，本质就是个前缀和。以后要多考虑清楚性质，仔细观察数据范围。
23-11-13¶
给定两个点，在无向图上的最长异或路径用线性基解决。P4151 [WC2011] 最大XOR和路径 - 洛谷 | 计算机科学教育新生态
在树上的最长异或路径等价于在一堆值中找两个异或结果最大，用 01-trie 解决。P4551 最长异或路径 - 洛谷 | 计算机科学教育新生态
然后今天的T2就是缝合怪，要考虑固定线性基的贡献。