Codeforces Round 800 (Div. 2)

基本情况

A题秒了。

B题写了个递推，但是T了，这种构造题还是得多练。

B. Paranoid String

我的解法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using ll = long long;
const int N = 2e5 + 10;
int t, n;
char ch;
int F[N], a[N];

void solve()
{
	std::cin >> n;
	for (int i = 1; i <= n; i++)
		std::cin >> ch, a[i] = F[i] = ch == '1' ? 1 : 0;
	ll tot = 0;
	tot += n;
	for (int i = 2; i <= n; i++)
	{
		for (int j = 1; j + i - 1 <= n; j++)
		{
			int l = j, r = j + i - 1;
			if (F[l] != a[r])
			{
				if (F[l] == 1)
					F[l] = 0;
				else
					F[l] = 1;
				tot++;
			}
		}
	}
	std::cout << tot << std::endl;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

用 F 保存上一轮长度下以 l 开头的区间的值，然后对比，修改，更新答案。复杂度 \(\operatorname O(n^2)\)。

显然超时了。

构造解法

思路

可以发现，这两种操作的本质都是删去两个不同字符中左边的一个。

以样例的倒数第二组数据为例，也就是 \(1001\)。

我们分别计算以第 \(i\) 个字符结尾并最终能转化为只有一个字符的字串有多少个。

以第 \(1\) 个字符结尾的显然只有它本身；
以第 \(2\) 个结尾的有 \(10,0\)；
以第 \(3\) 个结尾的也只有它本身；
以第 \(4\) 个结尾的可以有 \(1001,001,01,1\)。

可以发现一个有趣的性质：

如果 \(s_i\ne s_{i-1}\)，那么以 \(s_i\) 结尾，从 \(s_1,s_2,s_3,\cdots,s_i\) 开头的字串最终都能转化为只有一个字符的字串，一共有 \(i\) 个。
如果 \(s_i=s_{i-1}\)，那么以 \(s_i\) 结尾并能能转化为只有一个字符的字串的只有 \(s_i\) 本身。

时间复杂度 \(O(Tn)\)，可以接受。

注意：因为答案最大可能是

\(\sum\limits_{i=1}^ni=\dfrac{200000\times200000}{2}=2\times10^{10}\)

所以答案需要开 long long。

代码

#include<bits/stdc++.h>
using namespace std;
long long ans;
int main(){
    int t;
    cin>>t;
    while(t--){
        ans=0;
        int n;
        string s;
        cin>>n>>s;
        s=' '+s;//往后挪一格
        for(int i=1;i<=n;i++)
            if(s[i]!=s[i-1]) ans+=i;
            else ans++;
        cout<<ans<<endl;
    }
}