1832 字
9 分钟
训练记录
2025-11-24
未分类
无标签

11.24#

学#

待学#

  • 扫描线算法
  • 线性基
  • 莫比乌斯函数和莫比乌斯反演

待写#

  • 2025ICPC上海补题

11.25#

学#

  • 数论分块
  • 思维题
    • 2107C: 先思考”最差情况”. 再考虑非最差情况的情况下0的数量, 再想办法把多个0的情况化归为1个0的情况(注意到核心性质: 进行操作后其最大子序列和一定不减).

11.26#

  • 思维题
    • 2077A(重排后进行阿贝尔变换, 使构造出的结果必然大于最大值)
    • 2072E(暴力即可, 无营养)
    • 2057C(注意到最大值的情况是两0一1或一0两1, 所以若一个数为0, 一个数为1, 剩下一个数可以取任何值. 再注意到排除相同高位数字后, 区间内必然存在…1000…和…0111…, 此时无论第三个数怎么取都不影响结果)
    • 2049C(先考虑不含x, y的情况, 环状地填入. 含x, y的情况就是两个环合并起来)
    • 2026C(设免单的数量为k, k的合理性显然满足二分条件, 能想到就能做出来)
    • 1924A(很难想到的一个贪心, 构造针对性反例, 每次取最差情况)
    • 1891C(模拟即可, 无营养, 但还是交了好几发, 说明耐心和思维缜密程度还远远不够)
    • 1873G(正解极其巧妙)
    • 1814C(典型贪心, 思想类似哈夫曼编码, 无营养)
    • 1809C(非常有趣的题目, 隐藏的逆序对问题)
    • 1800E2(思维不难, 但是有一些小细节)

11.27#

  • 思维题
    • 1774B(不难)
    • 1767D(结论好猜)
    • 1753A2(1和-1的数量只能是偶数, 因为每个1或-1都会使sum奇变偶, 偶变奇; 在知道这个性质之后, 可以两个两个分组构造)
    • 1742F(水题懒得说)
    • 1740D(类似华容道的结构)
    • 1739C(博弈论+组合数学)
    • 1737C(简单, 但还是交了好几发)
    • 1722G(不难, 注意debug的耐心)
    • 1710A(题目引导很多, 注意开long long)
    • 1646C(为什么冒出来一道搜索, 注意好unsigned整数的使用方式)
    • 1630A(位掩码, 不难但巧妙)
    • 1614C(正解极为巧妙, 震撼人心. 结论惊为天人, 涉及范围广, 包括按位与, 按位或, 按位异或, 快速幂, 组合数学, 但代码和结论非常简洁)

11.28#

11.29#

11.30#

周日休息.

12.01#

  • 思维题

    • 743C(简单的构造, 不过非常有趣)

  • 补题

    • 2170D(1. 分割每一段问号; 2. 如果问号段前面是I, 或者后面不是I, 那么也会对问号段造成影响, 添加进问号段中; 3. 问号段的优惠具有先增, 再平, 再减的特征. 我们可以去考虑增的数量和平的数量; 4. 计算总的增数量和平数量)
    • 2170E(以分割点为状态进行dp)
    • 434e(考虑图论性质, 然后并查集解决连通块问题, 注意并查集环的求法).

  • dp

  • 图论

  • 待补

    • 2170F(线性基, dp, dp状态设计非常复杂, 没看懂)
    • 2158E
    • 434f(什么Z函数, 根本没学过)

12.02#

12.03#

12.04#

  • 图论
    • 1167C(并查集板题)
    • 20C(dijkstra+得到路径)
    • 25D(并查集)
    • 1433G(全源最短路预处理+中间点)
  • 树上问题
  • 思维题
    • 1352G(简单)
    • 1368B(轮流加)
    • 1365D(注意到一个点要么是可以逃出的, 要么是不能逃出的, 所以可以贪心地封锁最少可以被坏人逃出的点)

12.05#

12.06#

12.7#

周日休息.

12.8#

  • VP

  • 补题

    • 2163C(对于每个l, 把可行的r的数量加起来, 而非l的数量乘以r的数量)
    • 2145D 几个关键观察:
    1. i < j, 即原问题等价于求所有长度大于1, 逆序数量>=1的子段和
    2. 等价于所有长度大于1的子段和数量 - 长度大于1, 逆序数量等于0的子段和数量
    3. 若某子段的逆序数量等于0, 则该子段一定单调递增. 即该子段一定包含于某个极大递增子段. 反过来说, 对于每个极大递增子段, 其子段一定单调递增.
    4. 这时问题转化为, 求原数组的一个分割L1, L2, …, Lm, 使得所有部分的子段数量和为k. 即背包问题, 取len个时贡献为len * (len - 1) / 2, 所有len相加等于n.
    5. 一个维度枚举所有终点, 另一个维度枚举所有len即可, 同时记录转移方向, 最后输出.

  • 待补

12.9#

12.10#

  • 训练
    • 2124D(回文串的本质, 第1个位置字符等于最后一个位置字符, 第2个等于倒数第二个…所以可以用双指针来找回文子序列)
    • 2123F
    • 2164D(又来一道水题)
    • 2155D(循环数组)

今天实在太困了, 摆一天, 明天补回来.

12.11#

12.12#

顶不住了, 我需要休息.

12.13#

12.14#

  • 周日休息
  • 打卡

12.15#

12.16#

12.22#

12.23#

12.24#

训练记录
https://fuwari.vercel.app/posts/训练记录/
作者
ykindred
发布于
2025-11-24
许可协议
CC BY-NC-SA 4.0
竞赛算法(4) 数论
竞赛算法(2) 排序, 二分
© 2026 ykindred. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari