---

C. Make it Alternating

原创 于 2023-09-27 09:42:06 发布 · 粉丝可见 · 370 阅读 · 1 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/133340183

题目：

样例：

cobol<br/>3<br/>10010<br/>111<br/>0101<br/>

1 2 2 6 0 1

思路：

数学组合问题，在这里中要求 ans1 和ans2 两个答案，其中 ans1 表示最少操作次数，这是最容易求的，难点在 ans2 ，这里 ans2 是组合求总数的问题。其次，我们记录操作数，所求的答案它们的初始化，也是需要考虑的地方。

第二个答案就是一个组合数学 1 2 还有 2 1 是两种不同的情况
然后部分不同的情况也会造成总的也会有不同的情况
比如 [12 12] [21 12] [12 21] [1  1  2  2] 等等等等

代码详解如下：

#include <iostream>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10,MOD = 998244353;
 
inline void solve()
{
	string s;
	cin >> s;
	int n = s.size();
	// ans1 表示最少操作删除的次数
	// ans2 表示有多少种不同的删除方法后序列
	// 这里 ans2 = 1 是因为至少有一种操作后的序列，
	// 操作次数是 0 ，也算是一种操作后的序列
	
	// 而这里 cnt = 1 ， 是求 ans2 的组合性质，方法数之间相乘
	
	int ans1 = 0,ans2 = 1;
	int cnt = 1;
	
	for(int i = 1;i < n;++i)
	{
		// 如果相邻相同，那么删除的操作次数增加
		if(s[i] == s[i - 1]) ++cnt;
		else
		{
			// 这里 ans1 累加最少操作次数
			// cnt - 1 是因为初始化时 cnt = 1
			ans1 += cnt - 1;
			
			// 这里 cnt 不 - 1 是防止 cnt = 1 时 ans2 相乘后不为零
			// ans2 求操作删除的不同序列
			ans2 = ans2 * cnt % MOD;
			
			// 这里操作删除过后，恢复删除后的 cnt初始次数，即重新开始计数删除
			cnt = 1;
		}
	}
	// 这个操作是，防止一直都是相邻相同的情况
	if(cnt > 1)
	{
		// 这里 ans1 累加最少操作次数
		// cnt - 1 是因为初始化时 cnt = 1
		ans1 += cnt - 1;
		
		// 这里 cnt 不 - 1 是防止 cnt = 1 时 ans2 相乘后不为零
		// ans2 求操作删除的不同序列
		ans2 = ans2 * cnt % MOD;
		
		// 这里操作过后，恢复删除后的 cnt初始次数，即重新开始计数删除
		cnt = 1;
	}
	
	// 开始组合求不同操作次数的序列
	// 这里 now = 1 是至少有一种序列。 即  序列长度是 1 也是一种序列
	int now = 1;
	
	// 组合相乘
	for(int i = 1;i <= ans1;++i)
	{
		now = now * i % MOD;
	}
	
	// 总组合总数相乘
	ans2 = ans2 * now % MOD;
	
	cout << ans1 << ' ' << ans2 << endl;
}
 
 
int main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}

最后提交：