2023.9-2023.10 做题记录

发布时间 2023-10-05 14:59:09作者: pjykk

好菜啊,被爆杀了/kk

1. CF1572A Book

模拟赛上看错题了 !#$%!#&%^&#*

2. CF348D Turtles

类似 Catalan 数的推导

3. CF1271D Portals

贪心题。

4. CF1545B AquaMoon and Chess

数数题。注意两个连续的 1 的移动即可。

5. AT_agc007_b [AGC007B] Construct Sequences

简单题。注意值域可以是 \(O(n^2)\) 的。

6. AT_agc001_e [AGC001E] BBQ Hard

组合意义,然后 dp 推上去就行。

7. AT_agc003_c [AGC003C] BBuBBBlesort!

逆序对题。

8. AT_agc006_e [AGC006E] Rotate 3x3

和上面差不多,注意奇数和偶数(几乎)独立。

9. CF1515F Phoenix and Earthquake

树上归纳构造。

10. AT_agc002_f [AGC002F] Leftmost Ball

感觉最直观的方法还是像官方 editorial 里面把偏序关系连成 DAG。
然后一个简单 dp,做完了。

11. CF1718A2 Burenka and Traditions (hard version)

直接一个猜结论,然后贪心。

12. P2949 [USACO09OPEN] Work Scheduling G

反悔贪心。

13. CF865D Buy Low Sell High

还是反悔贪心,注意反悔和选取操作可以作用于一个位置。

14. AT_agc048_d [AGC048D] Pocky Game

博弈论 dp,这个状态的设计好巧妙啊。

15. P1537 弹珠

练习 bitset 优化背包。

16. P5020 [NOIP2018 提高组] 货币系统

练习 bitset 优化背包。

17. P5365 [SNOI2017] 英雄联盟

背包题。

18. P1776 宝物筛选

多重背包板子,之前没写过!

19. P1854 花店橱窗布置

无脑 dp 复健。

20. P1450 [HAOI2008] 硬币购物

简单容斥题。

21. P2796 Facer的程序

无脑 dp 复健。

22. P1541 [NOIP2010 提高组] 乌龟棋

无脑 dp 复健。

23. AT_dp_e Knapsack 2

交换维度即可。

24. CF788D Finding lines

不完全是二分。反正要想到只问 \(y=x\) 上的点。

25. CF1681D Required Length

dijkstra。

26. CF1628D2 Game on Sum (Hard Version)

博弈论,考虑倒着 dp。对于 Hard Version 要算贡献。

27. P6280 [USACO20OPEN] Exercise G

首先有置换的熟知结论,然后对着素数 dp。

28. P4161 [SCOI2009] 游戏

同上

29. CF1614D2 Divan and Kostomuksha (hard version)

dp 状态都设不出来,我该怎么办/ll
Dirichlet 后缀和可以优化倍数个数的计算。

30. UVA1608 不无聊的序列 Non-boring sequences

中途相遇法。又学到了奇怪的技巧。

31. AT_arc136_c [ARC136C] Circular Addition

非常 atc。

32. AT_arc058_b [ARC058D] いろはちゃんとマス目

简单题。

33. CF1842G Tenzing and Random Operations

贡献滞后计算,太神奇了。

34. CF444E DZY Loves Planting

知道怎么维护连通块,然后不会判断。
动点脑子吧动点脑子吧动点脑子吧动点脑子吧动点脑子吧动点脑子吧动点脑子吧动点脑子吧