【比赛记录】ABC357

KSCD_ · 2024-06-10 22:54:13 · 个人记录

记录

是目前打得最好的一场了，切得比较顺利，数据结构竟然没调一遍写对了，G 题太难了没补。

题解

A - Sanitize Hands

基本题，略过不表。

B - Uppercase and Lowercase

基本题，略过不表。

C - Sierpinski carpet

递归下去分别填即可，略过不表。

D - 88888888

有两种思路，一种是等比数列求和，没想出来。考虑类似快速幂的计算方式，在函数中同时记录已经计算了 t 个 n，若 n 长度为 k，下次乘的时候要乘上 10^{kt}

E - Reachability in Functional Graph

基环树基本题，发现所有环上的点互相可达，环外的点可达的点有对应环上的所有点和该点到环路径上的所有点，拓扑排序跑出环来，建反边从环上 dfs 统计答案即可。

F - Two Sequence Queries

考虑用线段树维护，发现区间 a+x 相当于区间和增加 x\sum b，b+x 相当于区间和增加 x\sum a，因此维护区间 a,b,ab 的和，进行区间操作和懒标记下传即可。