2025西安三色团子 B. Beautiful Dangos 问题总结

赛后补题之前，以为是个挺简单的题，一看就是二分，一写就挂
其实是个大分类讨论，分类不出来，看别人题解，发现可以用摩尔投票的技巧
避免了分类讨论

题意：给出一串三色团子，你不想让同色团子相邻，可以重新排列一个子串的团子，子串连续
问是否可以，通过排列使同色团子不相邻，给出具体操作

显然，可以通过二分来查找答案的区间长度
然后我们需要一个技巧
对于L到R这个区间来说，首先看三色团子各有多少个
如果最多的团子太多，那么肯定不行
传统方法是这里写分类讨论，判断这个区间是否合法

但是如果我们给每种团子权值呢？
L到R这个区间里，当前团子颜色为i，则另外两个团子的权值-=1，当前颜色的团子权值+=1
对于R+1的团子，对应的颜色权值+=1
对于L-1的团子，对应的颜色权值+=1
R+1和L-1的意义在于，你也不想填到最后一个不得不填的时候，发现颜色相同
先把右区间的相同的颜色那个填上，避免了这种尴尬的情况

这是一个结论，如果三色团子的权值都<=1的话，说明这个区间可以
然后二分找到区间和区间长度之后，就使用相同的方法，每填一个团子，就计算这个区间各种团子的权值
填权值最大的团子

就做完了，注意细节！
代码：代码后是细节


#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
#define ffp(x,y,z) for(int (x) = (y);(x)<=(z);(x++))
#define ll long long int
#define q_ (qd())
long long int qd() {
	long long w = 1, c, ret;
	while ((c = getchar()) > '9' || c < '0')
		w = (c == '-' ? -1 : 1); ret = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		ret = ret * 10 + c - '0';
	return ret * w;
}

struct tuan
{
	int v1; int v2; int v3;
	tuan operator+(tuan b)
	{
		tuan c = b;
		c.v1 += v1;
		c.v2 += v2;
		c.v3 += v3;
		return c;
	}
	tuan operator-(tuan b)
	{
		tuan c = { v1 - b.v1,v2 - b.v2,v3 - b.v3 };
		return c;
	}
	int tuansum()
	{
		return v1 + v2 + v3;
	}
	int mx()
	{
		return max(max(v1, v2), v3);
	}
	int get(int s)
	{
		if (s == 1)return v1;
		else if (s == 2)return v2;
		else return v3;
	}
};

int cnt = 0;
string aans[2000000+1];                    //为什么要先存答案？因为我在debug，手头没有数据，只能从oj上一点点摸

void solve()
{
	cnt++;
	int n = q_;
	vector<int>co(n + 10, 0);
	vector<tuan>pre(n + 10, {0,0,0});
	vector<int>vis(n + 10, 0);
	vector<int>bd;
	ffp(i, 1, n)
	{
		char temp;
		cin >> temp;
		if (temp == 'C') { co[i] = 1; pre[i] = { 1,0,0 }; }
		if (temp == 'W') { co[i] = 2; pre[i] = { 0,1,0 }; }
		if (temp == 'P') { co[i] = 3; pre[i] = { 0,0,1 }; }
		if (co[i] == co[i - 1])
		{
			if (vis[i - 1] == 0)bd.push_back(i - 1), vis[i - 1] = 1;;
			if (vis[i] == 0)bd.push_back(i), vis[i] = 1;
		}
		pre[i] = pre[i] + pre[i - 1];//优先记录下所有坏区间的位置
	}
	//二分区间长度，判断是否能够改变这个区间，来使得所有区间变好
	
	if (bd.size() == 0)
	{
		aans[cnt] = "Beautiful";
		aans[cnt].push_back('\n');
		return;
	}

	auto check = [&](int now)->int
		{//枚举所有坏区间的位置
			int l, r;
			for (int e = 1; e <= n - now + 1; e++)
			{
				l = e; r = e + now - 1; 
				if (bd[0] + 1 < l || bd.back() - 1 > r)continue;
				tuan temp = pre[r] - pre[l - 1];
				vector<int>se(4, 0);
				se[1] = temp.v1 - temp.v2 - temp.v3;
				se[2] = temp.v2 - temp.v1 - temp.v3;
				se[3] = temp.v3 - temp.v2 - temp.v1;
				se[co[l - 1]]++;
				se[co[r + 1]]++;
				if (se[1] <= 1 && se[2] <= 1 && se[3] <= 1)
				{
					return e;
				}
				else { continue; }
			}
			return 0;
		};
	int ans = 0;
	int l = 2; int r = n;
	while (r > l)
	{
		int mid = (l + r) >> 1;
		int p = check(mid);
		if (p)r = mid, ans = p;
		else l = mid + 1;
	}
	ans = check(r);
	if (ans)
	{//只用修改ans位置的就好了
		aans[cnt] = "Possible";
		int L = ans;
		int R = ans + r - 1;
		vector<int>se(4, 0);
		vector<int>sum(4, 0);
		tuan temp = pre[R] - pre[L - 1];
		sum[1] = temp.v1;
		sum[2] = temp.v2;
		sum[3] = temp.v3;
		ffp(i, L, R)
		{
			se[1] = sum[1] - sum[2] - sum[3];
			se[2] = sum[2] - sum[1] - sum[3];
			se[3] = sum[3] - sum[2] - sum[1];
			se[co[i - 1]]++;
			se[co[R + 1]]++;
			if (i - 1 == 0)
			{
				int maxx = (se[1]>se[2]?1:2);
				maxx = (se[maxx] > se[3] ? maxx : 3);
				co[i] = maxx;
				sum[co[i]]--;
				continue;
			}
			if (co[i - 1] == 1)//应该先填
			{
				if (sum[2] && sum[3])co[i] = (se[2] > se[3] ? 2 : 3);
				else if (sum[2] == 0)co[i] = 3;
				else co[i] = 2;
			}
			if (co[i - 1] == 2)
			{
				if (sum[1] && sum[3])co[i] = (se[1] > se[3] ? 1 : 3);
				else if (sum[1] == 0)co[i] = 3;
				else co[i] = 1;
			}
			if (co[i - 1] == 3)
			{
				if (sum[2] && sum[1])co[i] = (se[2] > se[1] ? 2 : 1);
				else if (sum[1] == 0)co[i] = 2;
				else co[i] = 1;
			}
			sum[co[i]]--;
		}
		aans[cnt].push_back('\n');
		aans[cnt] = aans[cnt] + to_string(L) + " " + to_string(R) + "\n";
		ffp(i, 1, n)
		{
			if (co[i] == 1)aans[cnt].push_back('C');
			if (co[i] == 2)aans[cnt].push_back('W');
			if (co[i] == 3)aans[cnt].push_back('P');
		}aans[cnt].push_back('\n');

	}
	else
	{
		aans[cnt] = "Impossible";
		aans[cnt].push_back('\n');
		return;
	}
}

int main()
{
	int t = q_;
	int sz = t;
	while (t--)
	{
		solve();
	}
	ffp(i, 1, sz)
	{
		cout << aans[i];
	}
	return 0;
}

/*
⡀⠎⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣄⠃⠈⣶⡛⠿⠭⣉⠛⠿⡿⠛⠉⣀⣠⣤⣭⡏⠴⢀⣴⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣷⣱⣬⠛⠉⠀⠀⢠⠀⠀⠀⢀⣀⠀⠉⠿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠈⡿
⠀⠀⠀⠀⠀⠀⠀⢀⢿⣿⣿⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⡏⠀⠀⠀⠀⠈⠳⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⠋⠀⣇⠀⠀⠀⠀⠀⠀⠀⠀⠈
⠀⠀⠀⠀⠀⠀⠀⣸⠀⣿⣿⣿⣿⠟⠀⠀⠀⠂⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠈⡀⠀⠀⠀⠻⣿⣿⣿⣿⣷⡀⠘
⠀⠀⠀⠀⠀⠀⠀⣧⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠙⣿⣿⣿⣿⣿⣄⣧
⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠀⠀⠀⠀⠈⢿⣿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⢂⠻⣿⣿⣿⣿⣿⣄
⠀⠀⠀⠀⠀⣿⣿⣿⣿⣹⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣇⠀⠀⠀⠀⠀⡄⠈⢿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⣿⣿⣿⣿⠁⡇⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠐⠸⠀⠀⠻⣿⣿⣿⣆⢦
⠀⠀⢠⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡏⣧⠀⠀⠀⠀⠐⣇⠀⠀⠙⣿⣿⣿⡄⠙⣄
⠀⣴⣿⣿⣿⣿⠏⠀⢸⠀⠀⠀⠀⠀⠀⡿⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣃⣈⣦⠀⠀⠀⠀⢹⠀⠀⠀⠸⣿⣿⣿⠀⠀⠳⣀
⠋⣸⣿⣿⣿⡟⠀⠀⠀⡆⠀⠀⠀⠀⠀⡏⠙⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠀⢠⠀⠀⠀⢧⠀⠀⠀⠀⡇⠀⠀⠀⠘⣿⣿⣷⠀⠀⠘
⠀⣿⣿⣿⢩⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⣀⠀⢱⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠂⢀⣴⣶⣿⣿⡀⠀⠀⢻⠀⠀⠀⠀⠹⣿⣿⡄
⢸⣿⣿⠃⠈⠀⠀⢸⠀⣿⣆⠀⠀⠀⠀⣿⣿⣿⠷⠘⡀⠀⠀⠀⠀⠀⠀⢠⢹⡀⠈⡿⠻⣿⣛⢿⣿⣷⡀⠈⠀⠀⠀⠀⠀⢻⣿⣿
⣿⣿⣿⠀⠀⠀⠀⢸⠀⡇⣼⣄⠀⠀⠀⢻⣿⡄⠑⠑⣿⡀⠀⠀⠀⢀⠀⠂⠇⠀⠀⠖⠛⢿⣿⣿⣌⢿⣿⣿⡆⠀⠀⠀⠀⠀⣿⣿⡀
⣿⣿⡇⠀⠀⠀⠀⢸⠀⣾⣿⣿⡷⠿⣷⣤⣿⣿⡄⠀⠀⠀⠑⠤⡀⠀⠃⠀⠀⠀⠀⣿⣶⣿⣿⣿⣿⣆⠙⣿⣧⠀⠀⠀⠀⠀⣿⣿⡇
⣿⣿⠁⠀⠀⠀⠀⠘⣾⣿⣿⠁⣴⣿⣿⣿⣿⣿⣇⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠸⡏⠙⣿⠉⠻⣿⠀⠀⣿⠀⠀⠀⣄⠀⣿⢸⣷
⣿⣿⡇⠀⠀⠀⠀⠀⣿⣿⠁⠀⣿⣿⠋⣿⠏⠙⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⢀⢻⠀⠀⢀⡟⢀⣿⣸⢃⠟
⣿⣿⣿⠀⡄⠀⠀⠀⠘⠻⡄⠀⢹⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡘⠀⢀⣿⠃⣿⣿⡗⠁
⣧⣿⣿⣧⢹⡀⠀⠀⠀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⣴⣿⣿⣾⣿⣿⣿
⢿⠘⣿⣿⣿⣿⣤⠀⠢⡀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣵⣿⣿⣿⣿⣿⣿⣿⣿⣷
⠀⠉⣿⣿⣿⡿⣿⠻⣷⣬⣓⣬⣄⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠉⠈⠈⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⠃⠼⢉⣿⣿⣿⣿⣿⣿⣿
⠀⠀⣿⣿⣿⣷⠀⠀⠀⠘⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⡏⠀⠀⢸⠀⢻⢿⣿⣿⡏⣿
⠀⢸⣿⣿⣿⣿⠀⠀⠀⠀⢻⣿⣿⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⣾⣿⣿⣿⣿⠀⠀⠀⢸⠀⠀⢸⣿⣿⠘⡀
⢦⡿⣿⣿⣿⢿⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣶⣶⣦⡄⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠘⡄⠀⠈⣿⣿⡄⠱
⣴⠛⣾⣿⣿⢸⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⡄⠀⠀⠀⠀⠀⠀⠀⣯⠛⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⣇⠀⠀⣿⣿⣿
⠿⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⠟⠰⡾⠃⠀⠀⠀⠀⠀⠀⠀⠙⡟⠀⢻⣿⣿⣿⣿⣿⡆⠀⠀⠀⠸⠀⠀⠸⣿⣿⣷
⠆⢳⣿⣿⡇⠀⠀⠀⠀⠀⠀⣿⣿⣿⠛⠿⠿⢿⡟⠀⠀⠉⠦⣀⡤⢶⠀⠖⠲⠶⠊⠀⠀⠀⢻⡛⠛⠛⣿⣿⠀⠀⠀⠀⠃⠀⠀⢿⣿⣿
*/

——
——
——
——
——————
——
——
——
——
细节部分：

struct tuan
{
	int v1; int v2; int v3;//千万不要像个傻逼真的开单独的三个变量
	tuan operator+(tuan b)//不能通过编号来查看相应的数值，必须写三个if，还有一堆判断
	{
		tuan c = b;
		c.v1 += v1;
		c.v2 += v2;
		c.v3 += v3;
		return c;
	}//v123代表颜色为1，2，3的团子的数量，因为频繁的前缀和，所以写个运算
	tuan operator-(tuan b)
	{
		tuan c = { v1 - b.v1,v2 - b.v2,v3 - b.v3 };
		return c;
	}
	int tuansum()//简便一点，要不然就写成x.v1+x.v2+x.v3 ，相当之傻逼
	{
		return v1 + v2 + v3;
	}
	int mx()
	{
		return max(max(v1, v2), v3);
	}
	int get(int s)//因为不能像数组一样索引，所以写了个这个，但是没用上 纯傻逼
	{
		if (s == 1)return v1;
		else if (s == 2)return v2;
		else return v3;
	}
};

ffp(i, 1, n)
{
	char temp;
	cin >> temp;
	if (temp == 'C') { co[i] = 1; pre[i] = { 1,0,0 }; }//pre表示前缀和，存下三种团子各有多少种
	if (temp == 'W') { co[i] = 2; pre[i] = { 0,1,0 }; }//这个写法相当傻逼，就因为结构体里存的不是数组
	if (temp == 'P') { co[i] = 3; pre[i] = { 0,0,1 }; }
	if (co[i] == co[i - 1])
	{//标记有相邻同色团子的区间，答案必须覆盖这里所有区间，否则不行
		if (vis[i - 1] == 0)bd.push_back(i - 1), vis[i - 1] = 1;;
		if (vis[i] == 0)bd.push_back(i), vis[i] = 1;
	}
	pre[i] = pre[i] + pre[i - 1];//优先记录下所有坏区间的位置
}

auto check = [&](int now)->int
	{//枚举所有坏区间的位置
		int l, r;
		for (int e = 1; e <= n - now + 1; e++)
		{
			l = e; r = e + now - 1; //遍历一遍所有的区间，注意，千万不要只拿坏区间为首的区间
			if (bd[0] + 1 < l || bd.back() - 1 > r)continue;//因为答案中的坏区间可能存在于答案的中间 **##**这样的
			tuan temp = pre[r] - pre[l - 1];
			vector<int>se(4, 0);
			se[1] = temp.v1 - temp.v2 - temp.v3;
			se[2] = temp.v2 - temp.v1 - temp.v3;
			se[3] = temp.v3 - temp.v2 - temp.v1;
			se[co[l - 1]]++;
			se[co[r + 1]]++;
			if (se[1] <= 1 && se[2] <= 1 && se[3] <= 1)//类似摩尔投票的算法，我也不知道叫什么
			{
				return e;
			}
			else { continue; }
		}
		return 0;
	};

int ans = 0;
int l = 2; int r = n;//注意，没有长度为1的区间
while (r > l)
{
	int mid = (l + r) >> 1;
	int p = check(mid);
	if (p)r = mid, ans = p;//存下最短的区间的开头是哪里
	else l = mid + 1;
}
ans = check(r);//最傻逼的地方，忘记了这里，会有一个特殊样例，使得二分中没有给ans数值，结果就是答案错误

	if (ans)
	{//只用修改ans位置的就好了
		aans[cnt] = "Possible";
		int L = ans;
		int R = ans + r - 1;
		vector<int>se(4, 0);
		vector<int>sum(4, 0);
		tuan temp = pre[R] - pre[L - 1];
		sum[1] = temp.v1;
		sum[2] = temp.v2;
		sum[3] = temp.v3;
		ffp(i, L, R)
		{
			se[1] = sum[1] - sum[2] - sum[3];   //重点每填一个团子，区间中剩余的团子数量会更新，团子的权值也会更新
			se[2] = sum[2] - sum[1] - sum[3];
			se[3] = sum[3] - sum[2] - sum[1];
			se[co[i - 1]]++;//边界团子不要忘记
			se[co[R + 1]]++;
			if (i - 1 == 0)  //易错点，i==1时不特判，会出错
			{
				int maxx = (se[1]>se[2]?1:2);
				maxx = (se[maxx] > se[3] ? maxx : 3);//填权值最高的就是了
				co[i] = maxx;
				sum[co[i]]--;
				continue;
			}
			if (co[i - 1] == 1)
			{
				if (sum[2] && sum[3])co[i] = (se[2] > se[3] ? 2 : 3);
				else if (sum[2] == 0)co[i] = 3;
				else co[i] = 2;
			}
			if (co[i - 1] == 2)
			{
				if (sum[1] && sum[3])co[i] = (se[1] > se[3] ? 1 : 3);
				else if (sum[1] == 0)co[i] = 3;
				else co[i] = 1;
			}
			if (co[i - 1] == 3)
			{
				if (sum[2] && sum[1])co[i] = (se[2] > se[1] ? 2 : 1);
				else if (sum[1] == 0)co[i] = 2;
				else co[i] = 1;
			}
			sum[co[i]]--;
		}
		aans[cnt].push_back('\n');
		aans[cnt] = aans[cnt] + to_string(L) + " " + to_string(R) + "\n";
		ffp(i, 1, n)
		{
			if (co[i] == 1)aans[cnt].push_back('C');
			if (co[i] == 2)aans[cnt].push_back('W');
			if (co[i] == 3)aans[cnt].push_back('P');
		}aans[cnt].push_back('\n');

	}
	else
	{
		aans[cnt] = "Impossible";
		aans[cnt].push_back('\n');
		return;
	}

posted @ 2025-10-28 23:24 粉紫系超人气月兔铃仙阅读(23) 评论(0) 收藏举报

刷新页面返回顶部

Reisentyan

2025西安三色团子 B. Beautiful Dangos 问题总结

公告