codeforces刷题(1100):1917B_div2

发布时间 2023-12-26 16:23:50作者: Tom-catlll

模板

B、Erase First or Second Letter

跳转原题点击此:该题地址

1、题目大意

  给你一个字符串,可以执行任意次以下操作,生成最终的字符串(不可为空),问你能生成的不重复字符串数为多少。

  1. 操作一:删除字符串第一个字符;
  2. 操作二:删除字符串第二个字符。

2、题目解析

  发现,操作一:即选定任意一个字符的后缀字符串;操作二:选定任意一个字符,和后面相隔一个字符的后缀字符串。
  例如案例4:bcdaaaabcdaaaa,其答案为50:
  具体操作如下:
  1、删除第\(-1\)位置(即保留第一个字符b)的字符,然后通过操作二不断删除后面的字符:bdaaaabcdaaaa、baaaabcdaaaa、baaabcdaaaa、\(\cdots\)、b,这样加上本身就有14种不同的方案(长度不同肯定不一样);
  2、然后删除第0位置的字符(即第一个字符b),就通过操作二不断删除后面的字符:caaaabcdaaaa、caaabcdaaaa、\(\cdots\)、c,加上本身(caaaabcdaaaa)一共13种。
  之后发现一直到第四次结束答案就已经为50了,说明后面的操作是重复的了。原理在于:如第五次的aaabcdaaaa,就能通过第四次的aaaabcdaaaa来完全实现。
  也就是说在这种思想下:只要前缀相等,那就能通过不断地操作一来实现。所以只要前缀字符不相等,那么该前缀字符+其后缀的长度的就是不重复的方案数。

#include<bits/stdc++.h>

using namespace std;

int t;
int n;
string s;

void solve()
{
	cin >> n >> s;
	
	set<char> se;
	int ans = 0;
	
	for(int i = 0; i < s.size(); i++)
	{
		if(!se.count(s[i]))	// 只要其前缀字符没有出现过
		{
			se.insert(s[i]);	// 那么加上其通过操作二得到的方案数即可
			ans += n - i;	// 因为i初始是0,并且其本身也是一种方案,所以n-i即可
		}	
	}
	cout << ans << endl;
}

int main()
{
	cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}