前言

新年快乐!终于活过 2020 年了。

WC2021 GZOI2021 NOI2021(如果有可能的话)rp++

学习内容

  • 欧拉函数
  • (ex)BSGS
  • 矩阵乘法的应用
  • 高斯消元
  • 基础分块
  • 基础线性代数
  • 数位 dp
  • 复杂度分析
  • 狄利克雷卷积
  • 莫比乌斯反演
  • 杜教筛
  • FFT

做题记录

21/01/01

  • EOJ monthly 2020.01 A+C+E rk80
  • P1072 [NOIP2009 提高组] Hankson 的趣味题

需要特别注意处理 a_0,a_1,b_0,b_1>\sqrt n 的情况

  • P2158 [SDOI2008]仪仗队

设左下角 (0, 0),右上角 (n-1, n – 1)。抛开 (1,0)(0,1)(1,1) 三个点,发现能看到的关于对角线对称,考虑一半即可。这一半就是求 1\le x\lt yx \perp y(x,y) 对数,发现对于每个 y 来说这样的 x 对数即为 \varphi(y)

答案为 \displaystyle3 + 2\sum_{i=2}^{n-1}\varphi(i),特判 n = 1 的情况

21/01/06

  • POJ3696 The Luckiest number

欧拉定理的推论 https://imyangty.com/oi/1280

  • P3846 [TJOI2007] 可爱的质数/【模板】BSGS

BSGS

21/01/07

  • P4861 按钮

求满足 k^x\equiv 1\pmod m 的最小正整数 x。由裴蜀定理可得有解的充要条件是 \gcd(k, m) = 1,所以直接 BSGS

  • P2485 [SDOI2011]计算器

快速幂取模 + exgcd + BSGS 综合题

21/01/09

  • P4195 【模板】扩展BSGS/SP3105 MOD – Power Modulo Inverted

exBSGS

  • CF1063B Labyrinth

双端队列优化 01bfs

  • CF786B Legacy

线段树优化建图模板

21/01/13

  • BZOJ2973 石子游戏

构造转移矩阵,矩阵乘法

21/01/14

  • P3389 【模板】高斯消元法

高斯消元

  • LOJ6208 树上询问

线段树维护矩阵和

  • P4035 [JSOI2008]球形空间产生器

推式子,二次项消去后高斯消元

21/01/15

  • LOJ#6277. 数列分块入门 1

区间修改单点求值

  • LOJ#6278. 数列分块入门 2

区间修改区间询问某数排名

  • P3372 【模板】线段树 1

分块重写

21/01/16

  • CF149D Coloring Brackets

区间 dp(记忆化搜索), f(i, j, k_1, k_2) 为合法序列 [i,j],两端状态 k_1, k_2,需注意合法序列两端未必就是匹配的,所以之前定义 f(i, j, k) 是错误的

  • CF242E XOR on Segment

区间 xor 区间求和,按位拆分方便处理区间 xor,对于每一位都建一棵线段树,xor 就是集体取反。

21/01/17

  • CF607A Chain Reaction

线性 dp,f_i 为从位置 i 开始激活最多保留的激光塔个数

  • P1005 [NOIP2007 提高组] 矩阵取数游戏

很水的区间dp,难点高精,int128 过之

  • LOJ#6279. 数列分块入门 3

区间修改区间询问某数前驱

21/01/21

  • LOJ#6280. 数列分块入门 4

区间修改区间查询

  • LOJ#6281. 数列分块入门 5

区间开根区间查询

21/01/23

  • POJ1830 开关问题

高斯消元求解 xor 方程组

  • P1102 A-B 数对

std::map 或二分

  • LOJ#6282. 数列分块入门 6

单点插入单点查询(块状链表)

  • LOJ#6283. 数列分块入门 7

区间乘区间加单点查询

  • LOJ#6284. 数列分块入门 8

区间查询某数出现个数并赋值

  • P4168 [Violet]蒲公英

强制在线区间众数

  • LOJ#6285. 数列分块入门 9

区间众数

21/01/24

  • P4127 [AHOI2009]同类分布
  • P2657 [SCOI2009] windy 数

数位 dp

21/01/25

  • Codeforces Round #697 (Div. 3)

A+B+C+E,是否 fst 未知

21/01/26

  • Codeforces Round #697 (Div. 3)

没有 fst,A+B+C+E

  • P3455 [POI2007]ZAP-Queries
  • P2522 [HAOI2011]Problem b
  • P2257 YY的GCD

莫比乌斯反演

21/01/27

  • P4213 【模板】杜教筛(Sum)

杜教筛

21/01/28

  • Codeforces Round #698 (Div. 2)

A + B,菜的我直接爬

21/01/29

  • P3803 【模板】多项式乘法(FFT)

FFT 板子

  • P1919 【模板】A*B Problem升级版(FFT快速傅里叶)

FFT 实现高精度乘法

  • Educational Codeforces Round 103

菜的抠脚依旧 A + B,C 没调出来

21/01/30

  • P3338 [ZJOI2014]力

转化式子之后使用 FFT

  • P3312 [SDOI2014]数表

莫反 + 树状数组,比较巧妙

  • P3377 【模板】左偏树(可并堆)

左偏树模板

21/01/31

  • P3723 [AH2017/HNOI2017]礼物

FFT/NTT 加速卷积

  • P2224 [HNOI2001]产品加工

奇葩的状态定义:https://imyangty.com/oi/1298

最后修改日期:2021年2月19日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。