ABC237 做题笔记

MatrixGroup · 2022-01-30 22:05:06 · 算法·理论

A,B

简单题，不讲。

顺带一提，A 的标题提示你了可以用自然溢出。

顺带一提，B 题面错了是怎么造成的啊，是 B 和 D 发音像吗（

C

首先如果开头和结尾的字符都是 \texttt a 显然可以抵消。

接着如果结尾是 \texttt a 不能和原来串的字符匹配（刚才都消掉了），但可以加 \texttt a，就可以把它删了。

看剩下的字符串是否回文即可。可以用 [l,r] 表示剩下的范围，由此做到 O(|S|)。

D

不难证明最后几次加的数是在一个连续的区间内。（归纳）

然后前一次时要么在最左边加要么在最右边加。

逆序操作然后 std::deque<int> 维护即可。

E

如果直接双向连边（注意不是连无向边）的话是 O(nm) 的，会 TLE。

考虑开心值加上高度就只有非正权边了。都取负号编程非负，跑 dijkstra 即可。（当然可以直接跑负权边最长路）

F

有一种人尽皆知的求 LIS 方法：二分。具体是这样的：维护一个数组，每次新的数都想办法替换。这里不对其正确性作证明。

然后考虑 dp_{i,x,y,z} 表示考虑到前 i 个数维护的数组是 [x,y,z] 的可能情况数。枚举添加的数即可。复杂度 O(nm^4)。

实现

膜拜 Breakplus 做了 7 题。/bx/bx/bx

G 补题笔记

发现数都只和 x 的大小关系有关系。

把 > x 的赋为 2，x 赋为 1，< x 的赋为 0。

发现区间和足以知道各个数的个数。（奇偶性确定 1，剩余除以 2 得 2 的个数，0 的个数用区间长度减）

排序就是放 0,1,2，写一棵线段树，区间覆盖区间和即可。

复杂度 O((q+n)\log n)（如果最后一个一个找 1）或 O(q\log n+n)（稍微用点 trick）