牛客挑战赛67 B数据结构
你有一个长度为n的字符串,其中包含'0','1','2'三种字符。问字符串中有多少个字串满足'0','1','2'三种字符数量相等。 \(1 <= n <= 3e5\)
一开始想了一个暴力做法。
对于一个左端点来讲,符合条件的右端点的个数等于它右侧距离最近的,且这段区间符合条件的点的对应的个数+1
也就是满足\([i,j]\)是合法区间的最小的j对应的个数+1.
问题就成了怎么对于每一个i找到其对应的j。
从3开始枚举长度,而长度一定是3的倍数。
若当前区间不符合那么下一个可能符合的最小区间的长度是3 * max(Num[0] , Num[1] , Num[2]);
这个做法卡着牛客的TILE10连测。
正解是将‘0’,‘1’,‘2’三种字符转化成数字,然后判断前缀和。
首先先考虑分别转化成1,2,-3这样是否可行。
发现这样无法区分"0002"这种情况,仔细考虑一下发现是没法将个数这个信息表示出来。
那么将其转化成1 + 1e6 , 2 + 1e6 , -3 - 2e6
因为有了1e6这个大数,如果个数不符合的话一定是不能相等的,这样就解决了。
#include<iostream>
#include<map>
using namespace std;
int main()
{
int T , n;
long long t , res;
char *s;
map<long long , int> mp;
cin >> T;
while(T--)
{
cin >> n; s = new char [n + 5];
cin >> (s+1);
t = res = 0; mp[0] = 1;
for(int i = 1 ; i <= n ; ++i)
{
if(s[i] == '0')
t = t + 1 + 1e6;
else
if(s[i] == '1')
t = t + 2 + 1e6;
else
t = t - 3 - 2e6;
res += mp[t]; mp[t]++;
}
delete s; mp.clear();
cout << res << '\n';
}
return 0;
}
标签:int,67,个数,cin,牛客,1e6,挑战赛
From: https://www.cnblogs.com/sybs5968QAQ/p/17241547.html