Problems - 题目汇总

日期题号标题算法题面题解难度
2022.08.22LG-P3803【模板】多项式乘法（FFT）FFT多项式乘法模板FFTV
2022.08.22LG-P3803【模板】多项式乘法（FFT）NTT多项式乘法模板大于 92×106 模数的NTTVI
2022.08.23LG-P2704[NOI2001] 炮兵阵地状压DP在有障碍的矩阵图上放置影响范围为四个方向各延申2的点，问最大能放多少个令 dp(i,j,k) 表示计算到第 i 行，当前行状态为 j，上一行状态为 k，最大可以放的个数，预处理每一行可能合法的状态，DP 时判断列的合法性IV
2022.08.23LG-P1879[[USACO06NOV]Corn Fields G状压DP简化的炮兵阵地思路与炮兵阵地类似IV
2022.08.23LG-P1896[SCOI2005] 互不侵犯状压DP加强版的1896，给出需要放的点数求方案数显然需要一维记录已选择的国王数，令 dp(i,j,k) 表示计算到第 i 行，已经放置 j 个国王，当前行状态为 k，然后枚举 i 和 k 以及上一行的 j 和 kV
2022.08.23LG-P3377【模板】左偏树（可并堆）可并堆左偏树可并堆+并查集模板左偏树模板，Merge 或 Delete 后用并查集维护父子关系。V
2022.08.24Exam-T4 / LG-P1344Exam / [USACO4.4]追查坏牛奶Pollutant Control网络流ExamExamVI
2022.08.25Exam-T1 / LG-P1533Exam / 可怜的狗狗主席树ExamExamV
2022.08.25Exam-T3 / JSK-42386Exam / Function!数学Function!Function!VII
2022.08.26LG-P3369【模板】普通平衡树Treap平衡树模板带旋Treap实现VI
2022.08.27ExamExamExamExamExam\
2022.09.XXCOCICOCI2021-2022 Contest1COCICOCI2021-2022 Contest1 SolutionCOCI2021-2022 Contest1 Solution\
2022.09.xxCOCICOCI2021-2022 Contest2COCICOCI2021-2022 Contest2 SolutionCOCI2021-2022 Contest2 Solution\
2022.09.13ExamExamExamExamExam\
2022.09.14ExamExamExamExamExam\
2022.09.16ExamExamExamExamExam\
2022.09.19ExamExamExamExamExam\
2022.09.20LG-P5285[十二省联考 2019] 骗分过样例莫比乌斯函数 原根 数学 MillerRabin各种较为基础的操作融合在一起SolutionVIII
2022.09.20LG-P3879[TJOI2010] 阅读理解STL Trie给你一些词组成文章，问词在哪些文章出现过可以写 Trie，更简单的是直接 map 套 setIII
2022.09.20LG-P8306【模板】字典树TrieTrie 模板Trie 模板III
2022.09.20LG-P3478[POI2008] STA-Station换根DP换根DP模板，求不同点为根时深度标准换根DP，两次搜索即可IV
2022.09.21ExamExamExamExamExam\
2022.09.21LG-P3865【模板】ST 表ST表ST表模板ST表模板IV
2022.09.22LG-P3379【模板】最近公共祖先（LCA）LCA(Tarjan)LCA模板Tarjan解决，LCA模板III
2022.09.22LG-P3379【模板】最近公共祖先（LCA）LCA(倍增)LCA模板倍增解决，LCA模板IV
2022.09.22JDOJ-2785商之和数论分块数论分块模板数论分块模板III
2022.09.22JDOJ-2786余之和数论分块数论分块模板plus数论分块时快速乘防止爆 long long，求和时用一下逆元IV
2022.09.22UVA-11526H(n)数论分块就是商之和。。。双倍经验III
2022.09.22LG-P2257YY的GCD莫比乌斯反演标准莫反推式子比较常规的套路的莫反VI
2022.09.22LG-P3455[POI2007]ZAP-Queries莫比乌斯反演比 2257 更简单的莫反套路莫反V
2022.09.22LG-P2522[HAOI2011]Problem b莫比乌斯反演3455 的加强版，给定区间而不是从 1 开始和 3455 差别不大，套个简单的容斥即可V
2022.09.22LG-P1403[AHOI2005]约数研究数论分块求因数个数和简单推一下就行，很水的数论分块III
2022.09.23LG-P2260[清华集训2012]模积和数论分块模积求和把模运算展开为乘除法之后常规数论分块即可，需要注意的细节较多。VI
2022.09.23LG-P1447[NOI2010] 能量采集莫比乌斯反演求 gcd 的和将式子推导展开后最终转换为欧拉函数即可，也可直接使用欧拉反演。VI
2022.09.24LG-P4318完全平方数容斥求第 k 个不含平方因子的数二分答案，容斥求出从 1 开始的不含平方因子的数的个数。VII
2022.09.26LG-P8546小挖的 X 献身搜索 模拟01 方阵中找 X 型嗯搜模拟即可III
2022.09.27LG-P6175无向图的最小环问题最小环Floyd 求最小环跑 Floyd 的时候枚举由 k 和小于 k 的点可能构成的环。III
2022.09.27LG-B3611【模板】传递闭包传递闭包Floyd 求传递闭包跑 Floyd 的时候取最小值改为取或，取和改为取与即可，可以 bitset 优化。III
2022.10.03LG-P1989无向图三元环计数三元环计数求无向图中三元环数将无向图定向，从度数由小到大连，度数相同的编号由小到大连，然后枚举所有点，标记其连接的节点为该节点，枚举子节点的子节点，若已被标记为该节点则答案数 +1。IV
2022.10.09POI2013POI2013POI2013POI2013POI2013 
2022.10.10LG-P5970[POI2016]Nim z utrudnieniemNIM游戏 DP将石子去掉 d 的倍数堆后进行 NIM 游戏，求去掉的方案数NIM 游戏的结论：每堆石子数异或和为 0 则后手必胜，利用此性质设状态 dp(i,j,k) 表示前 i 个里选择 ξmodd=j 个异或和为 k 的方案数，然后因为一个数和比它小的数异或之后不会大于最接近且大于它的 2ϵ，升序排列后根据总石子数可证复杂度正确，然后滚动数组压一下空间。VII
2022.10.10LG-P3531[POI2012]LIT-Letters树状数组 逆序对给定两个只有大写字母的字符串 A,B，每次可以交换 A 中任意两个字符，求最少交换次数使 A,B 相同，保证有解记录一下在 B 中每个字符第 i 次出现的位置，将 A 中每个字符变为在 B 中第 i 次出现的位置，然后对于最后的位置数组做一遍树状数组求逆序对即可，复杂度 O(nlog⁡n)，也可以开 26 个头指针表示对应字符在 B 中未使用的最新出现的位置，维护这个最后的复杂度应为 O(26n)，套个平衡树然后区间维护最后复杂度为 O(nlog⁡26)。V
2022.10.10LG-P1966[NOIP2013 提高组] 火柴排队树状数组 逆序对给定两个序列，用最少的操作次数使第一个序列和第二个序列相同，求操作次数算是 LG-P3531 的弱化版，记录一下前者在后者中的位置然后把位置求个逆序对即可IV
2022.10.11LG-P4220[WC2018]通道虚树分治 爬山给定三棵树，选择一个起点和终点，最大化在三个树中的路径长度和，输出最大值虚树分治不可能的，随机选择一个起点找到最优值的终点再将其作为起点，数次之后再随机新的起点，加个卡时即可过。对于 Hack 数据，先跑十遍左右原来的思路，然后仅考虑三棵树中某几棵树状态跑一遍爬山，写个类似枚举子集的东西即可，中间加个卡时超时直接结束程序，即可通过全部网站上的全部数据。VI
2022.10.11LG-P5956[POI2017]Podzielno性质给定 B 进制数中每个数出现的次数，要求组成一个最大的 B 进制数 X，使得其为 B−1 的倍数，Q 次询问输出其以第 0 位为起始的第 k 位是什么。存在一个性质：B 进制下能被 B−1 整数的数，各位数字加和整除 B−1，将其按 B 进制拆分后分别取模即可证明。于是记录 B 进制下 i 的个数，然后将整各位数字加和，若 totmodB−1 不为 0 则对应的值的数去掉一个，这样得到的数一定是最大的，二分找到第 k+1 个数即可。V
2022.10.11LG-P5957[POI2017]Flappy Bird性质Flappy Bird 游戏，求到达 X 最少的向上飞次数。维护一个能到达的区间的上下端点，通过两个障碍物之间的距离可以直到前者的限制，和后者比较，同时判断奇偶性即可，注意最后一段会使最终的位置再向下一段。V
2022.10.12CF915EPhysical Education Lessons线段树 动态开点动态开点线段树模板题动态开点线段树模板题V
2022.10.12SP685SEQPAR - Partition the sequence线段树 动态开点 DP给定 n 个数的数列 an，给定 k，将数列分成 k 段，满足每一段的元素和不大于 m，求最小的 mSolution-SP685VII
2022.10.13CF896CWillem, Chtholly and SenioriousODTODT 模板ODT 模板V
2022.10.13P4344[SHOI2015]脑洞治疗仪线段树 ODT比较简单的 ODT，不过存在 ODT 的 Hack 数据在普通 ODT 的基础上考虑如果连续的 01 串很长且结尾很接近 n，那么我们就可以认为整个序列都是一个 01 串，然后以此直接输出答案便可用不正确的方法过掉这道线段树的题。VI
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       

难度 List

I => 入门

II-III => 普及

IV-V => NOIP

VI-VIII => 省选

IX~X => NOI