织梦做中英文企业网站,给特宝网站商家网址怎样做,模板网站建设一条龙,中国建筑网官网图片这题做得比较复杂。。应该有更好的做法 题目大意#xff1a; 有一个括号序列#xff0c;可以对其进行两种操作#xff1a; 向里面加一个括号#xff0c;可以在开头#xff0c;在结尾#xff0c;在两个括号之间加。 对当前括号序列进行循环移动#xff0…这题做得比较复杂。。应该有更好的做法 题目大意 有一个括号序列可以对其进行两种操作 · 向里面加一个括号可以在开头在结尾在两个括号之间加。 · 对当前括号序列进行循环移动即把最后一个括号拿到开头来。 上述两种操作可以做任意次要求添加最少的括号使得原序列变成一个合法括号序列。如果有多种可能输出字典序最小的那一个。( )。 题解 首先计算左括号和右括号的数量可以知道不妨假设左括号的数量大于右括号 那么最少的方案就是在字符串右侧补充右括号使得左括号的数量等于右括号的数量。 但是一个方案是否可行要使得前面的每个前缀都满足条件左括号的数量大于右括号 如果不满足就循环移动即可通过循环移动就一定会找到一个方案。 要输出字典序最小的方案就需要后缀数组了 把字符串循环复制一遍做后缀数组那么就知道每个方案的排名 找最小且可行的方案输出即可。 另一种情况是左括号的数量小于右括号也是同理的。 关于如何判断是否可行这里是用的平衡树 写出每个位置的条件每移动一次对所有的条件影响都是相同的所以用平衡树维护这些条件即可 #include iostream
#include cstring
#include cstdio
#include vector
#include map
#include set
using namespace std;
const int maxn 2e6 1000;
int Wa[maxn], Wb[maxn], Wv[maxn], Ws[maxn], sa[maxn];
int Rank[maxn];
int height[maxn];
setint S;
mapint, int M;
vectorint V;
int a[maxn];
int cmp(int *r, int a, int b, int l)
{return r[a]r[b] r[al]r[bl];
}
void get_sa(int *r, int *sa, int n, int m)
{int i,j,p,*xWa,*yWb,*t;for(i0; im; i) Ws[i]0;for(i0; in; i) Ws[x[i]r[i]];for(i1; im; i) Ws[i]Ws[i-1];for(in-1; i0; i--) sa[--Ws[x[i]]]i;for(p1,j1; pn; j*2,mp){for(p0,in-j; in; i) y[p]i;for(i0; in; i) if(sa[i]j) y[p]sa[i]-j;for(i0; in; i) Wv[i]x[y[i]];for(i0; im; i) Ws[i]0;for(i0; in; i) Ws[Wv[i]];for(i1; im; i) Ws[i]Ws[i-1];for(in-1; i0; i--) sa[--Ws[Wv[i]]]y[i];for(tx,xy,yt,p1,x[sa[0]]0,i1; in; i)x[sa[i]]cmp(y,sa[i-1],sa[i],j)?p-1:p;}
}
void get_height(int *r, int *sa, int n)
{int i, j, k0;for(i1; in; i) Rank[sa[i]]i;for(i0; in; height[Rank[i]]k)for(k?k--:0,jsa[Rank[i]-1]; r[ik]r[jk]; k);
}void Hinsert(int x){if(M[x] 0) S.insert(x);M[x];
}
void Herase(int x){if(M[x] 1) S.erase(x);M[x]--;
}
char str[maxn];
int tr, tl;
int main()
{cinstr;int n strlen(str), nl 0, nr 0;for(int i 0; i n; i){if(str[i] () nl, str[i] 1;else nr, str[i] 2;}if(nl nr){tl 0;for(int i n-1; i 0; i--){if(str[i] 1) tl;a[i] 2*tl-(n-i);Hinsert(-a[i]);}tl 0;for(int i n-1; i 0; i--){if(-(*S.begin()) -(n-i-1)2*tl) V.push_back(i);Herase(-a[i]);if(str[i] 1) tl;Hinsert(-(2*nl-n-(n-i)2*tl));}int N 2*n-1;for(int i 0; i n; i) a[i] str[i];for(int i n; i N; i) a[i] str[i-n];get_sa(a, sa, N1, 4);for(int i 1; i N; i) Rank[sa[i]] i;int maxr N100, Kr 0;for(auto i : V){if(i1 N) break;if(Rank[i1] maxr){maxr Rank[i1];Kr i1;}}a[N] a[N-n];for(int i 0; i nr-nl; i) printf(();for(int i Kr; i Krn; i) printf(%c, a[i] 2 ? ) : ();} else {tr 0;for(int i 0; i n; i){if(str[i] 2) tr;a[i] 2*tr-i-1;Hinsert(-a[i]);}tr 0;for(int i 0; i n; i){if(-(*S.begin()) -i2*tr) V.push_back(i);Herase(-a[i]);if(str[i] 2) tr;Hinsert(-(2*nr-n-i-12*tr));}int N 2*n-1;for(int i 0; i n; i) a[i] str[i];for(int i n; i N; i) a[i] str[i-n];get_sa(a, sa, N1, 4);for(int i 1; i N; i) Rank[sa[i]] i;int maxr N100, Kr 0;for(auto i : V){if(Rank[i] maxr){maxr Rank[i];Kr i;}}for(int i Kr; i Krn; i) printf(%c, a[i] 2 ? ) : ();for(int i 0; i nl-nr; i) printf());}
} 转载于:https://www.cnblogs.com/Saurus/p/7591531.html
