马鞍山网站制作,专业网站建设哪家效果好,成都 做网站,wordpress后台加速AGC026E - Synchronized Subsequence
题目描述
Solution
定义cnt[x][0],cnt[x][1]cnt[x][0],cnt[x][1]cnt[x][0],cnt[x][1]表示在前xxx个数中0的个数和1的个数分别是多少。
然后把整个串sss划分为若干个子串#xff0c;划分点在所有cnt[i][0]cnt[i][1]cnt[i][0]cnt[i][1]c…AGC026E - Synchronized Subsequence
题目描述
Solution
定义cnt[x][0],cnt[x][1]cnt[x][0],cnt[x][1]cnt[x][0],cnt[x][1]表示在前xxx个数中0的个数和1的个数分别是多少。
然后把整个串sss划分为若干个子串划分点在所有cnt[i][0]cnt[i][1]cnt[i][0]cnt[i][1]cnt[i][0]cnt[i][1]的位置iii显然这样划分不同的子串之间互不影响最后合并所有子串pickorbanpick\;\;or\;\;banpickorban就是最终答案了。
显然这样划分子串之后可以把子串分为两类 1.a的前缀个数始终大于b例如aababb。 2.a的前缀个数始终小于b例如bbbaabaa。
对于第一类字典序最大的方案即为若干个ab拼接例如aababb最优选择是abab。 对于第二类答案一定是它的一个后缀。
所以对于每一个子串我们可以在O(n2)O(n^2)O(n2)的时间内求出答案。
然后我们考虑合并答案直接dpdpdp计算即可我用错误的排序特判卡过去了hhhhhhhhh。
总时间复杂度O(n2)O(n^2)O(n2)。
以下是错误的程序
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN6005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
char ST[MAXN1][MAXN],st[MAXN],ch[MAXN];
int c[MAXN],ID[MAXN],id[MAXN],cnt[2];
PR p[MAXN];
int compare(char *x,char *y)
{int lenxstrlen(x1),lenystrlen(y1),ans0; bool flag1;for (int i3;ilenx;i)if (x[i]!x[i-2]) { flag0; break; }for (int i3;ileny;i)if (y[i]!y[i-2]) { flag0; break; }if (flag){if (x[1]y[1]x[2]y[2]) return 2;}int lenmax(lenx,leny);for (int i1;ilen;i)if (x[i]y[i]) return ans^1;else if (x[i]y[i]) return ans;return 2;
}int compare(char *x,char *y,int len)
{for (int i1;ilen;i)if (x[i]y[i]) return 1;else if (x[i]y[i]) return 0;return 2;
}
int comparec(int x,int y){ return xy; }
void solve(int t,int l,int r)
{if (st[l]a){int mx0;for (int il;ir;i)if (st[i]a){int tmp0;for (int ji;jr;j)if (st[j]a) tmp,jp[id[j]].se;upmax(mx,tmp);}for (int i1;imx1;i2) ST[t][i]a,ST[t][i1]b;}if (st[l]b){int num0;for (int il;ir;i) if (st[i]a) c[num]id[i];sort(c1,cnum1,comparec);for (int i1;ir-l1;i) ST[t][i]st[il-1];for (int i1;inum;i){int len0;for (int jl;jr;j)if (id[j]c[i]) ch[len]st[j];
// coutch1endl;if (compare(ch,ST[t],len)1){for (int j1;jlen;j) ST[t][j]ch[j];for (int jlen1;jr-l1;j) ST[t][j]NULL;}}}
// coutST[t]1endl;
}
int compareid(int x,int y) { int tcompare(ST[x],ST[y]); return (t1||t2xy); }
int main()
{
// freopen(a.in,r,stdin);
// freopen(a.out,w,stdout);int nread();scanf(%s,st1);int numa0,numb0;for (int i1;in1;i){if (st[i]a) p[numa].fii,id[i]numa;if (st[i]b) p[numb].sei,id[i]numb;}int t0;for (int i1,lst1;in1;i){cnt[st[i]-a];if (cnt[0]cnt[1]) ID[t]t,solve(t,lst,i),lsti1;}sort(ID1,IDt1,compareid);
// coutendl;
// for (int i1;it;i) coutST[i]1 ID[i]endl;int smax0;for (int i1;it;i)if (ID[i]smax) printf(%s,ST[ID[i]]1),smaxID[i]; return 0;
}
/*
10
ba ab ba ba bbabbbaaaa ab20
ba ab bbabaa bbbabbabbabbaaaaaa aabb aabababb
*/
