补题-可达鸭编程杯"山东大学程序设计挑战赛

type

status

date

slug

summary

签到题。输入两个数n,m，有两种操作，进行n-1，m-2轮流操作，最早哪一秒完成。

直接计算即可

对字符串进行重排，并希望一个字符串的 回文的子串 尽可能多。

显然，将相同的字母排在一起即可保证回文字串数目最多，数量为每种字符个数阶乘之和。

题中给出字符串由小写字母组成，可直接统计后枚举字母。

满足以下条件的一个三元组是飞碟序列中的一个”红红蓝“组合

子序列可以表示成 `RRB` , `BBG` , `GGR` 这三个组合当中的任意一个，存在*表示可变色飞碟。

按中间的字母进行枚举，用前缀和统计三各字母在个区间的个数，同时加上变色*的个数，前后个数相乘即可计算以当前字母为中值时可组成组合的个数。注意容斥排除变色飞碟情况即可。

不少于，可发现使用二分来解决。选取最大值，直接暴力统计进行check即可

两种改变序列的方式，将未到的给到,将变更成。联想到线段树，但是发现第一项操作有些难以实现。可以发现每个点只与经过最后一次单点修改和最大的推平有关，于是进行预处理记录最后次单点修改和最大推平即可。

但是发现如果最大推平在单点修改前，之后推平可能还会改变值，于是在预处理记录每段修改时间最值即可。

在比赛时没有想到对操作进行记录的方法

轮流选择一段循环，也就是个群，不能选择的输。奇数个群z,偶数个群是w，交换一次不同的数即会改变群个数的奇偶性。算出开始序列中群的个数，将每次交换不同的数作为1求交换的前缀和，在提问每一段时用前缀和维护即可。