5.1 ~ 5.31 做题总结

· · 个人记录

有题解的题挂链接,没题解的题简要说明思路。过水的题不记录。

由于 APIO 之后回归 whk 了,做题数少的可怜 /ll

难度评价系统来自 https://www.luogu.com.cn/article/u98dxgp0。贺个图:

【1+】P3599 Koishi Loves Construction

https://www.luogu.com.cn/article/wqhyaya6。

【1+】AT1202Contest_j Hated Number

https://www.luogu.com.cn/article/pkbka1ys。

【3】AT1202Contest_d Coincidence

【4】QOJ4214 Deja Vu

【0】P2633 Count on a tree

对每个节点维护根链的权值线段树,查询树上差分。可持久化一下就是四棵树上同步二分。

【2】AGC016D XOR Replace

【0】P7228 [COCI 2015/2016 #3] MOLEKULE

诈骗题,奇偶分层以后一层向上一层向下,答案就是 1。

【0】ABC456E Endless Holidays

拆点,然后 DFS 有向图判环即可。

【0】ABC456F Plan Holidays

写一个 dp 出来,然后线段树维护 (\min,+) 矩乘。

【1】ABC456G Count Holidays

https://www.luogu.com.cn/article/8pp570kp。

【1】P3246 [HNOI2016] 序列

单调栈求出 a_i 为最小值的极长区间 [x_i,y_i],注意一个端点取等一个不取。将 (l,r) 刻画到二维平面上,那就是先 n 次 4-side 矩形加然后 q 次 2-side 矩形求和,做法参见 https://www.luogu.com.cn/article/dxdsfd1r。

口胡,没写代码。

【3】QOJ9459 Tree Equation

用1exgcd 枚举 |X| 以后维护树哈希,暴力复杂度是对的。

【2】QOJ8542 Add One 2

铲雪题。

【1】P16414 【MX-X28-T3】「FAOI-R12」寄清梦

https://www.luogu.com.cn/article/lploygux。

【2】P16415 【MX-X28-T4】「FAOI-R12」落花雨

https://www.luogu.com.cn/article/w8w4uuj7。

【2】P10102 [GDKOI2023 提高组] 矩阵

随机一个向量 X,并检查 X \times A \times B=X \times C 是否成立。

【2】P6817 [PA 2013] Filary

【0】ARC218A Many Sets

考虑枚举每个值算贡献,然后单步容斥得 m^n-\prod(m-c_{i})。

【1】ARC218B All Minus

https://www.luogu.com.cn/article/5fd4bssv。

【1+】ARC218C Amidakuji

https://www.luogu.com.cn/article/q0d932tz。

【0】P3605 [USACO17JAN] Promotion Counting P

自底向上 dfs,需要知道 p_i 的排名,权值树状数组即可。口胡没写代码。

【1】ABC366F Maximum Composition

https://www.luogu.com.cn/article/pbsgdp0p。

【1+】P7515 [省选联考 2021 A 卷] 矩阵游戏

不该不会的,黑白染色和差分约束都想到了,怀疑了半天初始解能不能构造,wssb。

https://www.luogu.com.cn/article/nsswcnh2。

【1】P7514 [省选联考 2021 A/B 卷] 卡牌游戏

讨论 \min, \max 是哪个位置以及是否翻,可以二分优化。口胡,但是代码应该挺难写的。

【1】P7521 [省选联考 2021 B 卷] 取模

枚举 k,然后分 a_i+a_j 和 a_k 大小关系讨论,加个最优性剪枝复杂度就是对的了。要敢于写代码,不要空想。

【2】CF1270G Subset with Zero Sum

https://www.luogu.com.cn/article/9sa8kk5s。

【1+】CF1545B AquaMoon and Chess

被诈骗了。11 的数目和 0 的数目算出来以后可以任意放,答案是组合数。

【1+】CF1844B Permutations & Primes

被 *1000 诈骗说是。找降智题做的坏处。2 3 放两边 1 放中间,根本不用管大质数。

【?】ARC214D Distinct Sum Grid Path

【2】P10873 [COTS 2022] 帽子 Šeširi

https://www.luogu.com.cn/article/jhp1w06t。

【2】QOJ14559 并行计算

https://www.luogu.com.cn/article/7z7gltzo。

【1】CF1325F Ehab's Last Theorem

https://www.luogu.com.cn/article/j82vxuoi。

【2】QOJ14945 友谊地久天长

【4】P16433 [APIO 2026 中国赛区] 上升

【2】P16434 [APIO 2026 中国赛区] 蛋糕

【4】P16435 [APIO 2026 中国赛区] 集宝

【3】P8329 [ZJOI2022] 树

https://www.luogu.com.cn/article/rua1slet。

【0】UVA11481 Arrange the Numbers

https://www.luogu.com.cn/article/jwhfr3ny。