2022年秋季刷题表

发布于 28 天前  25 次阅读


由于各种原因,记录可能不是很全

9.14

P4245 【模板】任意模数多项式乘法

P4491 [HAOI2018]染色

二项式反演 + NTT

9.15

P5339 [TJOI2019]唱、跳、rap和篮球

二项式反演 + 暴力卷积
由于数据范围比较小,写得也很暴力,把4个EGF暴力乘起来即可

9.20

P4921 [MtOI2018]情侣?给我烧了!

P4931 [MtOI2018]情侣?给我烧了!(加强版)

神奇的递推

P4389 付公主的背包

传说中的名题,生成函数取 ln 的一个套路

9.21

CF438E The Child and Binary Tree

不戳的生成函数题

P4705 玩游戏

生成函数 + 推式子题,注意分配空间,用到了C++的new和delete来动态申请和释放内存

image-20220921210621249

Edu CF 136 Div.2

A,B

签到,没什么好说的

C-Card Game

好具有迷惑性,明明O(n)就可以出解的
可以大概推出来每次每个人都出点数最大的牌是最优的

$$
f(n) = C(n-1, n/2) + C(n-4, n/2 - 1)[n >= 6] + f(n - 4)
$$

D-Reset K Edges

如果选择一个深度为d的结点,那么操作后以该节点为根的子树的所有结点的深度都会-(d-1)
容易想到二分答案,推一下可以发现,对于一个深度为d且超出lim的结点,为了使它满足条件,当且仅当由它到深度为d-lim+1的祖先的路径上有至少一个结点被操作
优先考虑深度大的进行操作,每次都操作该结点的深度为d-lim+1的祖先,这样是最优的

2022 年上海市大学生程序设计竞赛

I-It Takes Two of Two

i题调了1年qaq
29行处,max(k-4, 0),不是max(k-2,,0),因为这个调了一晚上,还手算n=4的样例
f[i][j][k]表示还有i个节点的度为1或2,j个节点的度为1,k个节点的度为1且连接度为1的点

image-20221004222226042

image-20221004222235091

ICPC 2021 昆明

题意:有 $n$ 个珠子排成一排,每次有一定 $p_i$ 概率选中第 $i$ 个,当 $m \to \infty$ 时,求第 $m$ 次操作的期望代价

img

ICPC 2021 澳门

D.Shortest Path Fast Algorithm

image-20221031210705426

ICPC 2020 南京

题目质量高,当时感觉还不卷,我们6题快速竟然金了

ICPC 2021 EC-Final 西安

打铁了,被博弈大讨论薄纱,差一点点就出了

ICPC 2020 上海

贡献基本只有签到,剩下全靠队友

C. Sum of Log

有点技巧的数位DP,枚举最高位1的位置,把时间复杂度降到一个log

B. Mine Sweeper II

结论是正图和反图的数字之和是相等的,所以答案要么为A的正图,要么为A的反图


昨日的月光悄然退场,曦阳已经渐亮