由于各种原因,记录可能不是很全
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来动态申请和释放内存
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的点
ICPC 2021 昆明
题意:有 $n$ 个珠子排成一排,每次有一定 $p_i$ 概率选中第 $i$ 个,当 $m \to \infty$ 时,求第 $m$ 次操作的期望代价
ICPC 2021 澳门
D.Shortest Path Fast Algorithm
ICPC 2020 南京
题目质量高,当时感觉还不卷,我们6题快速竟然金了
ICPC 2021 EC-Final 西安
打铁了,被博弈大讨论薄纱,差一点点就出了
ICPC 2020 上海
贡献基本只有签到,剩下全靠队友
C. Sum of Log
有点技巧的数位DP,枚举最高位1的位置,把时间复杂度降到一个log
B. Mine Sweeper II
结论是正图和反图的数字之和是相等的,所以答案要么为A的正图,要么为A的反图
Comments | NOTHING