2022年秋季刷题表
本文最后更新于 405 天前,内容如有失效请评论区留言。

[toc]

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

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的反图

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇