G - Messy codeforces1262C

题目大意；

输入n和m，n是n个字符，m是m个前缀。对前缀的规定可以配对的括号。比如()，，（（（）））等等。在输入n个括号字符，对这个n个字符，通过交换使其满足m个前缀。交换次数不限，规则想当与reverse函数

题解：

先构造m-1个前缀,使其均为"()"。然后剩下的字符构造最好一个前缀。。。。。如果当前字符与构造的字符不同，那么从当前字符后面找到一个与当前字符相反的字符，然后直接swap.

这里为什么用户swap而不是reverse？

可以模拟一下。。比如）））（我们找的是第一个与当前字符相反的字符，也就是说当前字符和被到的字符之间的字符都是相同的，所以我们直接让开头和结尾交换一下就行了

#include<bits/stdc++.h>

using namespace std;

const int N=1E5+;

struct stu{

    int a,b;

}nu[N];

char arr[N];

void solve(){

    string s="";

    int n,m;

    cin>>n>>m;

    scanf("%s",arr);

    for(int i=;i<=m-;i++) s+="()";

    int num=(n-(m-)*)/;

    for(int i=;i<=num;i++) s+='(';

    for(int i=;i<=num;i++) s+=')';

    int numm=;

    for(int i=;i<n;i++){

        if(arr[i]==s[i]) continue ;

        int pos=i+;

        while(arr[i]==arr[pos]) pos++;

        nu[numm++]={i+,pos+};

        swap(arr[i],arr[pos]);

    }

    cout<<numm<<endl;

    for(int i=;i<numm;i++) cout<<nu[i].a<<" "<<nu[i].b<<endl;

    return ;

}

int main(){

    int t;

    cin>>t;

    while(t--) solve();

    return ;

}

巴特西

G - Messy codeforces1262C

最新文章

热门文章