专栏文章

ABC391E题解

AAwsdkl
AT_abc391_e题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqcwg2l
此快照首次捕获于
2025/12/04 02:44
3 个月前
此快照最后确认于
2025/12/04 02:44
3 个月前
查看原文

题目翻译

对于一个长度为 3N3^N 的二进制字符串 BB，定义一种操作：将 BB 分成每组 33 个字符，取每组的多数值作为新的字符，生成一个长度为 3N−13^{N-1} 的新字符串。
现在给定一个长度为 3N3^N 的二进制字符串 AA，重复上述操作 NN 次，最终得到一个长度为 11 的字符串 A′A'，要求找出最少需要修改 AA 中的多少个字符（00 变 11 或 11 变 00），才能使最终的 A′A' 值翻转。

思路

可以把原题看成一颗三叉树，每个结点的值可以由它的左、中、右三个孩子得到。对于样例 11，我们可以有下图：

类似于一个树形 dp，可以记录在每个结点改变这个结点的值所需要的最小修改次数。
记当前结点为 pp，左、中、右儿子分别为 lp,mp,rplp, mp, rp，可以分为两种情况：
  1. 只需要改其中一个儿子即可修改当前结点。及三个儿子中有一个的值与其他两个不同。
  2. 需要修改两个儿子。及三个儿子的值相同。
对于第一种情况，我们只需要求那两个和当前结点的值相同的儿子的答案的最小值。
对于第二种情况，我们要求三个儿子的答案分别两两相加的最小值。
转移代码如下：
CPP
f[p] = 0x3f3f3f3f;
//只需要改一个的情况
if((nowv == 0 && cnt1 == 1) || (nowv == 1 && cnt0 == 1))
{
  if(lpv == nowv) f[p] = min(f[p], f[lp]);
  if(mpv == nowv) f[p] = min(f[p], f[mp]);
  if(rpv == nowv) f[p] = min(f[p], f[rp]);
}
//需要改两个的情况
else
{
  f[p] = min(f[p], f[lp] + f[mp]);
  f[p] = min(f[p], f[lp] + f[rp]);
  f[p] = min(f[p], f[mp] + f[rp]);
}
其中 nowv 为当前结点的值，cnt0，cnt1 分别是子节点中值为 00 和 11 的数量。

完整代码

CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

char s[1594323+5];
int n;

int f[(1594323<<2)+5];
int cnt = 1;

/// @param p 当前结点编号
/// @param l 当前结点对应字符串的左端点
/// @param r 右端点
/// @return 未修改时当前结点的值
int dfs(int p, int l, int r)
{
	if(l == r)
	{
		f[p] = 1;
		return s[r] - '0';
	}
	int lp = ++cnt, mp = ++cnt, rp = ++cnt;
	int len = (r - l + 1);
	int lpv = dfs(lp, l, 			l+len/3-1);		//左孩子的值
	int mpv = dfs(mp, l+len/3, 		l+len/3*2-1);	//中孩子的值
	int rpv = dfs(rp, l+len/3*2, 	r);				//右孩子的值
	int cnt0 = 0, cnt1 = 0;
	if(lpv == 0) cnt0++; else cnt1++;
	if(mpv == 0) cnt0++; else cnt1++;
	if(rpv == 0) cnt0++; else cnt1++;
	int nowv = cnt0 > cnt1 ? 0 : 1;					//当前结点的值
	f[p] = 0x3f3f3f3f;
	//只需要改一个的情况
	if((nowv == 0 && cnt1 == 1) || (nowv == 1 && cnt0 == 1))
	{
		if(lpv == nowv) f[p] = min(f[p], f[lp]);
		if(mpv == nowv) f[p] = min(f[p], f[mp]);
		if(rpv == nowv) f[p] = min(f[p], f[rp]);
	}
	//需要改两个的情况
	else
	{
		f[p] = min(f[p], f[lp] + f[mp]);
		f[p] = min(f[p], f[lp] + f[rp]);
		f[p] = min(f[p], f[mp] + f[rp]);
	}
	return nowv;
}

int main()
{
	scanf("%d%s", &n, s+1);
	dfs(1, 1, strlen(s+1));
	printf("%d", f[1]);
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...