C. 二进制字符串复制

每次测试的时间限制2秒
每个测试的内存限制256兆字节
输入标准输入
输出标准输出

给你一个字符串s包含由...组成n个0或1。给出m次操作，让i-th 副本是字符串ti。然后，您对每个副本执行一次操作：i-th 副本，您对其子字符串进行排序[li,ri]（子字符串来自原字符串第 li个字符到ri个字符，包括两个端点）。注意，每个操作只影响一个副本，每个副本也只受一个操作影响。

你的任务是计算其中不同字符串的数量t1,t2, … ,tm。注意初始字符串s仅当至少有一份副本在操作后保持不变时才应计数。

输入

第一行包含一个整数t（1≤t≤1e4) — 测试用例的数量。

每个测试用例的第一行包含两个整数n和m（1 ≤ n ，m ≤ 2*1e5) — 的长度s和份数。

第二行包含n字符01 — 字符串s。

然后m行如下。这其中 i-th 包含两个整数l,r;
(l<n,r<n)
总数是n所有测试用例不超过2·105。总数是m所有测试用例不超过2·1e5。

输出

输出更改后不同字符串的数量

input

output

3
3
1

题意:

首先我们看到不同就可以很快地想到我们的老朋友 set 因为set可以自动的进行去重,最后直接输出一手set.size(),爽歪歪~
直接上一手代码:

#include <bits/stdc++.h>
using namespace std;
int t;
int n,m,l,r;
set<string> q;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--)
	{
	cin>>n>>m;
	string t,s;
	cin>>s;
	q.clear();
	for(int i=0;i<m;i++)
	{
	    int l,r;
    	cin>>l>>r;
    	t=s;
    	sort(t.begin()+l-1,t.begin()+r);
	    q.insert(t);
	}
		cout<<q.size()<<endl;	
	}
	return 0;
}

一波验证样例后自信提交结果获得一发MLE QAQ~~~

MLE确实没见过,也不知道有啥优化的方法
这时候从同学手中获得了一份神犇的"独家提示"

坑爹呐这是!!!,我咋知道这种题是咋做的??????

随后是漫长的坐牢时间.....

赛后补题(jianglyの正解)

首先,为啥会MLE嘞,我猜测可能是因为把每个字符串都存进set中,就会时间复杂度过高,所以就要简化一下
对01字符串的某一区间进行排序,其实就是把0放在前面,把这个区间里的1放在后面
比如:
对于 0 1 0 1 0 1 1
1 2 3 4 5 6 7
所以(1,7)和(2,5)实际上就是相同的这样的话,我们不用存储每个字符串,只需要存储两个端点即可
在存储字符串之前先进行一个预处理

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
char g[N];
int y[N],l[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,ans=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>g[i];
        y[n+1]=n+1;
        l[0]=0;
        for(int i=n;i>=1;i--)
        {
            y[i]=y[i+1];
            if(g[i]=='1')y[i]=i;
        }
        for(int i=1;i<=n;i++)
        {
            l[i]=l[i-1];
            if(g[i]=='0')l[i]=i;
        }
        set<pair<int,int>> s;
        while(m--)
        {
            int p,q;
            cin>>p>>q;
            p=y[p],q=l[q];
            if(p>q)ans=1;
            else s.insert({p,q});
        }
        cout<<s.size()+ans<<endl;
        s.clear();
    }
}