计分板
假设bob得分s,alice得分t。枚举s修改后与t的最长公共前缀长度x,那么s中前x位固定,贪心找最近的对应字符移过去。对于x+1位,任意找一个比t中对应位置小的字符移过去即可。
病毒
考虑拆点,颜色为 ACT 的点分别拆成 AA,AC,AT,CA,CC,CT,TA,TC,TT,表示当前点的颜色和下一步要走的点的颜色,那么相当于找一个 AA,AC,CC,CT,TT,TA 循环 的一个环。考虑建一个新图 G’,如果原图 G 中存在边(A,A),就在 G’连边(AA,AC), C 中存在边(A,C),就在 G’中连边(AC,CC),G 中存在边(C,C),就在 G’中连边(CC,CT), C 中存在边(C,T),就在 G’中连边(CT,TT),G 中存在边(T,T),就在 G’中连边(TT,TA), C 中存在边(T,A),就在 G’中连边(TA,AA)。那么可以发现 G’中存在任意一个环就等价于 C 中存在 AACCTT 无限循环的路径。用拓扑排序判环即可。
还有一种较为简单的方法,将 G 中同色点之间的边看做白边,异色点之间的边看做黑边,那么题目就等价于找一个黑白相间的环,可以用 dfs 判环。
连边问题
对树进行二分图染色,可以发现任意黑点和任意白点之间均可以连一条边,那么答案就是黑点个数乘以白点个数减去N-1。
持续攻击
先删掉 t>m 的敌人,问题转化为每种类型敌人中恰好选出一个,使得 h 的最小值减去 t 的最大值加上 m 最大。考虑从小到大枚举每个 t 作为最大值的情况,然后只要让 h 的最小值最大即可。维护一个序列 f,f[i]表示第 i 种类型当前 a 的取值,先初始化 f 全为负无穷。那么每当枚举到一个 t 值,就把对应类型的 f 修改为 max(f,h),然后求出 f 的最小值更新答案即可。
连通块
建图,dfs 遍历每个连通块更新答案即可,复杂度是 O(N^2) 。还可以动态维护一个单调栈,用并查集连边,这样能做到 O(NlogN) 复杂度。
字符串排序
一个串 si 可以用原字符串 a 的若干段区间表示。可以用哈希 O(klogk) 比较两个字符串的字典序,总排序复杂度就为 O((klogk)^2)。
矩形求和
要求的是$\sum\limits_{x=x1}^{x2}\sum\limits_{y=y1}^{y2}min(x,y)$,分类讨论去掉min,拆成几个等差序列和平方序列求和,复杂度O(1)。