JZTXT

做题记录202312

发布时间 2023-12-19 10:17:32作者: dddddadaplllllane

模拟赛题

题意：将长度为 \(n\le10^{18}\)插入间隔，要求每个（所有空格小于等于 \(k\le50\) ）的连续段段内必须有一个段空格为 \(k\) ，求方案数

  1. 矩阵快速幂可以预处理，复杂度变为 \(O(n^2(n+T)logn)\)

  2. 对于过于繁杂的边界和细节问题，可以先求出一个大致，统计答案的时候再进行修正，这里统计答案时分为 \([1,n]\) ,\([1,i]\) ,\([i,n]\),\([i,j]\) 几类统计

loj 6089

  1. 对于两类感觉限制不同的，进行根号分治

  2. （ \(\ge \sqrt n\) ）转移后置：每次让他垫上一层，或者让他多加一个

\[ dp_{i,j}=dp_{i-1,j-B}+dp_{i,j-i} \]

P5336

  1. 状态要表示清楚当前状况，可以为状压，个数，值域，组数等

  2. 可以将状态表示成为剩余状态

  3. 考虑加入单点转移

AT_agc035_d

  1. 通过点权\(\times\)系数来考虑每个点对答案的贡献

  2. 当正着dp不行时，可以考虑记忆化搜索，发现：如果合法状态不多，可以用来确定dp状态

  3. 不会的凭感觉加记搜可能蒙中

模拟赛题

题意：给定\(n\le 5e5\)个区间，你需要求出能够最多选出多少对区间，使得两个区间不交。要求一个区间最多属于一对选出的区间。

  1. 尝试排序+严谨证明

模拟赛题

有向图，点（\(n\le200\)）个，边（\(m\le500\)）个，要求选择若干个点，满足从s到t的任意路径都有（\(k\le5\)）个选择的点

  1. 从部分分可以获得启发

  2. “没用”割：建分层图，在每一层上的流量都是点权，再从\((u,i,0)--inf->(u,i+1,1),(u,i+1,0)\) ，这样就能够让他割了就往下跑，等于白割

模拟赛题

题意：现在有一张 \(2n\) 个点的二分图，左边 \(n\) 个点，右边 \(n\) 个点。其中左边第 \(i\) 个点与右边 \([1,a[i]]\) 个点有边。

你需要求出图中总共有多少个不同的简单环。简单环在这里指一个点只被经过至多一次的环。

  1. 梳理信息（排序，统计，等）

  2. 对于dp环的表示方法 通过链数量来统计，通过前后顺序来考虑，这样只用在答案/2就行了，不需要考虑连哪个端点

  3. 可以拆步骤转移

AT_arc132_e Paw

  1. 从最终状态来考虑

  2. dp时可以通过两个暴力识字相减得到与上一个式子相关的答案

\[dp_i=a_1\times dp_{i-1}+a_2 \times dp_{i-2}+... \]

\[dp_i-1=a1\times ...+a2\times ... \]

\[dp_i=(...)dp_{i-1} \]

CF1610H

大胆贪心猜结论，一定要证明

CF1253F

充电问题

每个点考虑最近一个可以充电的点（突破口），发现能充就充一定更优

P5324

考虑合法状态，转化图论，再用数据结构维护

P3733

  1. 异或最大线性基

  2. 以增删代改，以出现时间区间代删，最后再跑线段树分治

P9058

  1. 感觉\(O(n^2)\)对中，很多是没用的，所以感觉可以支配对

  2. 考虑支配对证明办法，一个点比上一个点大并且更有用

  3. 这里又和树有关，又和点编号有关，考虑点分治

  4. 发现在每一层每个点只有常数个是不会被支配的

P7215

  1. 原问题逻辑转图论

  2. 学会建虚树

CF888G

B开头最小生成树算法：每个点集找最小边连出去，只会连log次

P3703

  1. 考虑到序列上染色经过段数均摊\(O(n)\)，在树上相当于对于序列染\(O(logn)\)次，因此段数均摊是\(O(nlogn)\)的

  2. 树上复杂查分可变为\(w_x+w_y-2w_{lca}+1\) 先彻底删去，再加上lca

模拟赛题

题意：给一个带权二分图(\(n\le10^3\),\(m\le10^5\))，求完成\([1,n]\)个匹配所需要的最大边权的最小值

  1. 重点：匈牙利不能用来乱加边

  2. 考虑利用好残余网络，每从小到大加一条边对残余网络增广。因为是二分图，每次增广是\(O(m)\)，总复杂度\(O(m^2)\)

  3. 发现只会增广\(O(n)\)次，只要在\(O(m)\)的时间复杂度内维护s到t是否连通即可。

  4. 发现每次多连通的点不多，每次从多出来的点寻找连通块即可，复杂度被均摊了

模拟赛题 P7294

  1. 通过部分分思考，得到大致走法

  2. 调整法证明并删去不合法情况

  3. 通过数学模型就能够处理最优情况，如二次函数

AT_agc039_e

圆连线问题

  1. 通过确定某特殊点的方法转到区间+特殊点

  2. 从外向内剖分，处理更为普遍的情况

  3. 记录重复状态优化