【luogu P8293】[省选联考 2022] 序列变换(贪心)(分类讨论)

2022/5/1 6:16:15

本文主要是介绍【luogu P8293】[省选联考 2022] 序列变换(贪心)(分类讨论),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

[省选联考 2022] 序列变换

题目链接:luogu P8293

题目大意

给你一个括号序列,每次你可以把 p(A)(B)q 的串变成 P(A()B)q。
你还可以不用花费交换任意两个相邻合法括号序列的位置。
其中 A,B 是合法括号序列,p,q 可以不是。
然后每个左括号有费用,每次边的费用是左边左括号费用和右边左括号费用分别乘 x,y 的和。
x,y 都是 0/1,要你用最小费用使得不能找到可以变换的串。

思路

首先考虑这个变换是什么鬼,你会发现弄完之后原本两个括号有一个被弄进另外一个里面去了。
然后因为你可以交换位置,所以你可以选择放什么进去。

所以问题就变成了有若干个数,分布在一些层。
然后你会从上往下走,每次把一些数放下去,留下一个,然后操作有对应的费用。
然后到每一层你就会加上这一层的数。

考虑分类讨论。
首先 \(x=0,y=0\) 就随便搞答案是 \(0\)。


\(x=0,y=1\)

那这个时候是放进去的括号要费用。
那不放进去的后面就不见了那我们肯定要让不优的做这个位置,也就是权值最大的括号。
所以你就用一个堆维护最大值,每次取出最大值和放值进去就可以了。(维护堆中所有数的和)


\(x=1,y=1\)

那这个时候是你利用一个踏板把一个数放进去,那这两个数都要有费用。
那不难看出自然也是留下最大的,那怎么算贡献呢?
那你考虑到被传下去的数它自己自然要贡献,那我们就尽可能让踏板的贡献尽可能小。
那我们就拿最小值做踏板送下其它要下去的数,然后再用最大的数做踏板把自己送下去。
这样是最优的因为你最大的数一定要做至少一次踏板,就是最后剩下两个数的时候。

所以总结一下就是每次是堆中所有数的和加上最小值(它不可能被弹出,所以可以直接一个变量记录维护这)乘堆大小-2。
(当然如果堆中只有一个元素那我们就不用管它啦)


\(x=1,y=0\)

这个就是这题最难的部分啦。
(不过其实也还好,主要是贪心的方法不要搞错)
那这个是什么个意思呢?就是你传下去的数不用贡献,但是踏板它要贡献。

我考场胡了个什么垃圾贪心现在忘了,但一个很重要的点就是我们要拿最小的把别的要下去的给送下去。
而且因为你送下去是不用贡献的,那我们自然是尽量把最大的给送下去,让它永远不会贡献。

那同时呢,我们也要用小的把别的给送下去,所以我们贪心的重点就是这个:既要传最大值,也要传最小值。

那对于这个我们再分类讨论一下,就考虑当前一个层数你会有多少个数(这个可以预处理出来)。
考虑对于当前这一层的个数 \(sz\):

\(sz>2\):那这个简单,就随便选一个留下,只要不是最大和最小就可以。
\(sz=1\):这个也简单,你只能留这个,没有别的可以选。
\(sz=2\):那我们考虑怎样会出现这个情况。


于是我们考虑找找预处理出的数组的性质。
你会发现到了一个没有的层数(就是会减少)会怎样。
你会发现那后面一定都没有了(因为你是要一层一层类似一棵树的结构,你总不可能有一个断层吧)
所以你可以发现它是一个这样的:先是一段中每个都是不变或者变大,然后从一个分界点开始一直每次减一最后到 \(1\)。
然后你再看 \(2\) 可能出现在哪里:
\(...,2,2,...,2,...,k,k-1,...,2,1\)(\(k\) 是开始减少的地方)

你会发现你就可以分成两个部分,\(2\) 就是左边的连续一段和右边的一个。
那右边的一个我们自然是优先选最大的下传,毕竟这已经是最后一次。

那再看前面的一段,那我们先暴力的话就是枚举每个作为最后传下来的,然后这么模拟就是 \(O(n^2)\)。
但显然只有一些是用得上的,我们再看会我们贪心的原则:传最大的和最小的。

那就简单了,我们只要试着留下最大的和最小的,分别模拟一次,就可以啦。
那这个直接就是 \(O(n)\) 的了。

(别的两个要操作的因为用堆是 \(O(n\log n)\))

然后这道题就好啦!

代码

#include<queue>
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

const int N = 4e5 + 100;
ll n, x, y, snum, num, sz;
ll a[N], ans, sum, minn, b[N];
ll Mx[N], Mn[N];
vector <ll> deg[N];
priority_queue <ll> q;
char s[N << 1];

int main() {
//	freopen("bracket.in", "r", stdin);
//	freopen("bracket.out", "w", stdout);
	
	scanf("%lld %lld %lld", &n, &x, &y);
	if (!x && !y) {printf("0"); return 0;}
	
	if (x && y) {
		scanf("%s", s + 1);
		for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
		for (int i = 1; i <= n * 2; i++) {
			if (s[i] == '(') deg[++snum].push_back(a[++num]);
				else snum--;
		}
		
		minn = INF;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < deg[i].size(); j++) sum += deg[i][j], q.push(deg[i][j]), sz++, minn = min(minn, deg[i][j]);
			if (sz != 1) ans += sum + minn * (sz - 2);
			sum -= q.top(); q.pop(); sz--;
		}
		printf("%lld", ans);
		
		return 0;
	}
	
	if (x == 0 && y == 1) {
		scanf("%s", s + 1);
		for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
		for (int i = 1; i <= n * 2; i++) {
			if (s[i] == '(') deg[++snum].push_back(a[++num]);
				else snum--;
		}
		
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < deg[i].size(); j++) sum += deg[i][j], q.push(deg[i][j]);
			if (sz != 1) ans += sum - q.top();
			sum -= q.top(); q.pop();
		}
		printf("%lld", ans);
		
		return 0;
	}
	
	if (x == 1 && y == 0) {
		scanf("%s", s + 1);
		for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
		for (int i = 1; i <= n * 2; i++) {
			if (s[i] == '(') deg[++snum].push_back(a[++num]);
				else snum--;
		}
		
		b[0] = 1; for (int i = 1; i <= n; i++) b[i] = b[i - 1] + deg[i].size() - 1;
		int L = 1; while (L <= n && b[L] == 1) L++;
		int R = L - 1; while (R < n && b[R + 1] == 2) R++;
		Mx[L - 1] = -INF; Mn[L - 1] = INF;
		for (int i = L; i <= R; i++) {
			Mx[i] = Mx[i - 1]; Mn[i] = Mn[i - 1];
			for (int j = 0; j < deg[i].size(); j++)
				Mx[i] = max(Mx[i], deg[i][j]), Mn[i] = min(Mn[i], deg[i][j]), sum += deg[i][j];
		}
		for (int i = R + 1; i < n; i++) {
			if (i == R + 1) Mx[i] = -INF, Mn[i] = INF;
				else Mx[i] = Mx[i - 1], Mn[i] = Mn[i - 1];
			for (int j = 0; j < deg[i].size(); j++)
				Mx[i] = max(Mx[i], deg[i][j]), Mn[i] = min(Mn[i], deg[i][j]), sum += deg[i][j];
		}
		ll ans1 = sum - max(Mn[R], Mx[n - 1]);//留下小的 
		ll ans2 = sum - max(Mx[R], Mx[n - 1]);//留下大的 
		for (int i = R + 1; i < n; i++) {
			ans1 += (b[i] - 2) * min(Mn[R], Mn[i]);
			ans2 += (b[i] - 2) * min(Mx[R], Mn[i]);
		}
		
		printf("%lld", min(ans1, ans2));
		
		return 0;
	}
	
	return 0;
} 


这篇关于【luogu P8293】[省选联考 2022] 序列变换(贪心)(分类讨论)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程