Codeforces 掉分日常(八):组合 dp 几则

Codeforces 上最近的几个组合dp问题

近况总结

距离上篇 CF 掉分日常过去快三个礼拜了,期间发生了很多事,忙里偷闲写篇博客记录一下。

11 月下旬研究了两场 ERC 欧洲区域赛(一句话题解系列博客),那段时间的 CF 比赛比较少,参加了一场都是水题的 div.2 比赛,加了 100 分,但没遇到什么有意思的题;还有一场 div.1+div.2 的比赛因为时间比较晚,看了看题但没有参加,后来补了几个题;此外最近抽空完善了一下自己的 CF 板子,并刷了几个模板题做测试。

上周入职了鹅厂的实习,加上最近实验室项目和本科毕设的三线程操作,最近还挺忙的。虽然工作量其实都不是很大,每天真正工作的时间也就 4-6 个小时,周末也比较空闲,但对精力的消耗还是挺大的,写算法题的心思和时间都比较零散。零零碎碎地思考了两三个题,写了一两个。以下记录一下几个比较有意思的思路。

这个周末非常震惊,两天有三场比赛... 如果没什么事的话就都参加一下,那可真是 Codeforces Weekend 了。

1263 E. Editor

题意:给定一个光标和一个初始为空的、无限长的字符串,有以下几种操作:光标向左/右一格、光标位置输入字符(可能是左括号、右括号、普通字母),问得到的字符串中括号是否匹配,匹配时求括号的深度。

乍一看,括号是否匹配、括号的深度,都可以通过维护前缀和来判断(详细点说,就是将左括号看做 1,右括号看做 -1,其余字符看做 0,然后求数列的前缀和;括号匹配等价于前缀和均非负且总和为 0;括号的深度等价于前缀和的最大值)。对于修改操作,单点修改相当于是对前缀和数组的区间修改,用线段树维护一下区间的 min/max/sum 即可。这样看起来就是一个“线段树 with mass 区间信息"的裸题。顺便说一下,对线段树不是特别熟悉的同学,可以把问题转化为单点修改+区间查询会更好写一点,因为那样就不用维护 lazy 了。

比赛时我写的就是线段树的 的做法,400+ ms 过了;但看到 n=1e6 的数据量题目只给了 1 秒的时限,感觉不大符合 CF 的风格。后来看到题解给了一个 的解法,感觉还是挺巧妙的,简述如下:

由于题目中“光标”移动的次数是 的,因此可以考虑维护光标左边右边的信息,然后每次光标左移/右移时更新信息。这里需要维护的信息就是上面所说的前缀和的 min、max、sum。由于支持在光标处修改,因此我们可以用两个栈来维护所有被修改的坐标。每次移动的时候,首先将当前节点的信息入栈,然后把下一节点的信息出栈,根据这两个数,容易 地更新当前维护的总信息,如 min、max、sum 等。也就是说总共需要 6 个栈。

参考代码略。

 

1260 E - Tournament

题意:一群 个人打单败淘汰赛,每个人有一个能力值,能力强的必胜能力弱的,还有一个贿赂值,表示付他 a_i 块钱可以打假赛,让(比他弱的)对手赢;其中有一个人是你的朋友,你可以安排比赛的顺序,也可以进行一些贿赂,问至少付出多少钱能让你的朋友获得冠军。

首先根据能力值对所有人排序。那么所有比“朋友”的能力强的人就是我们需要花钱打败的对象。容易发现,无论如何,能力最强的那个人我们是一定要花一次钱的,因此贪心地想到,可以先让这个人帮我们“打工”,干掉一半的对手,然后在总决赛中与我们的朋友PY。因假如“朋友”的能力在一半以上,那么答案就是最强选手的要价;否则就需要找到第二个打工的选手,然后递归下去即可。

现在的问题是,每次选出一个打工的选手后,安排他打败哪些选手呢?按照能力从强到弱来打是不可行的,比如 [-1 3 2 1] 这种情况;按照要价从高到低也是不可行的,比如 [-1 8 7 6 3 4 5 2] 这种情况(按照要价贪心则依次选取 2 5 3 这三个人,但事实上选取 2 3 4 是最优的)。

这时要换个角度考虑问题:每次选取一个工具人后,不用立即确定他的对手,而是更新下一个人的可选的范围。因为根据最开始的贪心,下一个人一定是所有没有被安排的人中最强的。因此按照我们根据强度的排序,第二个工具人的可选范围只能是 (其中 );再往后推一步,可知第三个工具人的可选范围是 ... 也就是说,我们每次可以先在相应范围内找到开价最低的选手,然后再将其他选手安排给相应的工具人去打(假如要输出方案的话,此题就省略此步了)。

这样,问题就转化为找区间 的第 i 小值。暴力的复杂度是 足以通过此题;用堆则可以将复杂度优化为

参考代码:

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int, int>;
int read(){
	register int res = 0, c, d=0;
	while(c=getchar(), c<'0'||c>'9')d=c=='-';
	do{
		res=res*10+(c^48);
	}while(c=getchar(), c>='0'&&c<='9');
	return d?-res:res;
}
int main() {
	int N=read(), T=-1, K=1;  
	while((1<<K)<N)K++;
	vector<int> s(N+1);
	vector<pii> t(N+1);
	for(int i=1; i<=N; i++){
		s[i]=read();
		if(s[i]<0)T=i;
		else if(T==-1)s[i]=0;
		t[i]={s[i], i};
	}
	long long ans = 0;
	vector<bool> vis(N+1, 0);
	for(int k=K; k>=0; k--){
		if(T>=1<<k){
			break;
		}
		int mi=0x3f3f3f3f, mip;
		for(int i=1<<k; i<=N; i++){
			if(!vis[i]){
				if(s[i]<mi){
					mi = s[i];
					mip = i;
				}
			}
		}
		ans += mi;
		vis[mip] = true;
	}
	printf("%lld\n", ans);
	return 0;
}

 

1227 F - Wrong Answer on test 233 (Hard Version)

一个数学题,div 2 的压轴题,但其实题意比较难分析,最后的式子还是很简单的。

由于所有题的答案都 Shift 一格,对于相邻的答案相同的题,无论选什么,它们对结果都没有贡献,直接在答案上乘一个幂,略过。对于剩下的题,每题有增加结果、减少结果和对结果不变三种情况,枚举后排列组合是 的,可以过 Eazy version。其中有个组合数求和的式子可以通过组合数定义转化为 2 的幂的形式,降低复杂度到 ,比较巧妙。

由于公式挺复杂的,博客上就不打了,详情参见官方题解 https://codeforces.com/blog/entry/71740

 

1264D - Beautiful Bracket Sequence

读错题意想了半天。本来以为要求整个串合法,求整个串的最大深度,然后发现 可以递推,就想了半天怎么 之类。最后发现是求最大深度的合法子序列,这完全不是一个问题了啊!

记数问题还是比较深奥的,简单记录一下这道题的思路。首先考虑计算某个没有问号的字符串的深度。我们把深度拆成 k 个 +1,分摊到 k 个位置上。思考哪些位置对结果有贡献?对于每个左括号,如果其左边的左括号数量比右边的右括号数量严格小,那么这个左括号就有一个贡献。

然后再扩展到有问号的情况,对于每个位置,计算该位置有贡献的所有情况数。这就把深度计算问题转化为了排列组合问题。这道题中,排列组合列出一个 的式子,通过一些数学推导可以化为可 预处理的问题,也挺巧妙的。具体参见官方题解 https://codeforces.com/blog/entry/71995