A.B-Suffix Array
题目链接
想法：
给你串a，先求出整个串的b数组
a的任意后缀的b数组有个特点是：
第一次出现‘a’ 的下标是posa , 第一次出现 'b'的posb , 一定有:
①：b[posa] = b[posb] = 0 ,
②：b[posa + 1 ~ posb - 1] = 1 (下标 posa + 1 到 posb - 1 （或[posb + 1 ， posa - 1]）之间的b数组的值一定为 1)
把所有的后缀的b数组分成两部分：
第一部分：类似 011...110 （00和0111也算）
第二部分：第二个0之后的所有部分 （如果是01111 ，那么这项为空，也就是置为0）
然后进行排序：
第一关键字：如果 第一个0 和 第二个0 相差的越多 ，也就是第二个0出现的越晚 ，也就是第一部分越长 ， 这个后缀的b就大
第二关键字：如果 第一个0 和 第二个0 相差的一样大 ， 那就比较第二部分
第二部分怎么比较：
后缀数组：可以对后缀进行排序 ，给他一个char数组s，他就会给你一个 每个后缀的名次 和 后缀的排行榜 -> rank数组和sa数组
所以先用后缀数组把b数组的后缀排名都求出来
然后 两个不同的后缀 就可以 o（1）进行比较了
所以步骤就是：
① 把char a[] 先整个求出 b[]
② for 循环一遍 ， 找到 当前位置开始的后缀 第一次出现'a'和'b'的位置
③ b数组过一遍 后缀数组 ， 得到每个后缀的排名 和 第i个后缀排第几
④ 进行排序 ， 优先排 011...110 的部分 如果相同 排第二个0之后的 那段后缀
⑤ 排序完输出结果
代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; char ch[maxn]; char s[maxn]; int sa[maxn],rk[maxn],tp[maxn],tax[maxn]; int n,m,p; void SA_Sort(){for(int i=0;i<=m;i++){tax[i]=0;}for(int i=1;i<=n;i++){tax[rk[i]]++;} for(int i=1;i<=m;i++){tax[i]+=tax[i-1];}for(int i=n;i>=1;i--){sa[tax[rk[tp[i]]]--]=tp[i];}} void getsa(){m=n;for(int i=1;i<=n;i++){rk[i]=s[i],tp[i]=i;}SA_Sort();for(int k=1;k<=n;k<<=1) {p=0;for(int i=n-k+1;i<=n;i++){tp[++p]=i;}for(int i=1;i<=n;i++){if(sa[i]>k){tp[++p]=sa[i]-k;}} SA_Sort();for(int i=1;i<=n;i++){tp[i]=rk[i];}rk[sa[1]]=p=1;for(int i=2;i<=n;i++){ if(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k]){rk[sa[i]]=p;}else{p++;rk[sa[i]]=p;}} if(p==n)break;m=p;}}///s数组 struct node { int pre , nex; }; node ans[maxn]; bool cmp(node t , node tt) { if(t.nex - t.pre == tt.nex - tt.pre)return rk[t.nex + 1] < rk[tt.nex+ 1]; return t.nex - t.pre < tt.nex - tt.pre; } signed main() { while(~scanf("%d" , &n)){ scanf("%s" , ch + 1); int aa = -1 , bb = -1; for(int i = 1 ; i <= n ; i ++){ if(ch[i] == 'a'){ if(aa == -1) s[i] = 0; else s[i] = i - aa; aa = i; } else{ if(bb == -1)s[i] = 0; else s[i] = i - bb; bb = i; } } getsa(); rk[n + 1] = -1 , rk[n + 2] = -2; aa = n + 1 , bb = n + 1; for(int i = n ; i >= 1 ; i --){ if(ch[i] == 'a')aa = i , ans[i].pre = i , ans[i].nex = bb; else bb = i , ans[i].pre = i , ans[i].nex = aa; } sort(ans + 1 , ans + 1 + n , cmp); for(int i = 1 ; i <= n ; i ++) printf("%d ",ans[i].pre); printf(" "); } return 0; }
F . Infinite String Comparision
题目链接
想法：
延伸到两倍同等长度，比较大小
代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 2e6 + 10; #define ll long long #define ios std::ios::sync_with_stdio(false) const ll INF(0x3f3f3f3f3f3f3f3fll); const int inf(0x3f3f3f3f); #define int long long char a[maxn] , b[maxn]; signed main() { //ios,cin.tie(0); while(cin >> a >> b){ int la = strlen(a) , lb = strlen(b); int maxx = 2 * max(la , lb); int ok = 0; for(int i = 0 ; i < maxx ; i ++){ if(a[i % la] > b[i % lb]){ ok = 1;break; } if(a[i % la] < b[i % lb]){ ok = 2;break; } } if(ok == 0){ cout << '=' << ' '; } else if(ok == 1){ cout << '>' << ' '; } else if(ok == 2){ cout << '<' << ' '; } } return 0; }
J.Easy Integration
题目链接
结论：
推导过程：
代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; #define ll long long #define ios std::ios::sync_with_stdio(false) #define int long long ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;}//xµÄn´Î·½mod const int mod = 998244353; unsigned ll nn[2 * maxn + 1]; signed main() { //ios,cin.tie(0); nn[1] = 1; for(int i = 2 ; i < 2 * maxn ; i ++){ nn[i] = nn[i - 1] * i; nn[i] %= mod; } unsigned ll n; while(cin >> n){ cout << (nn[n] * nn[n] % mod * pow_mod(nn[n * 2 + 1] , mod - 2 , mod)) % mod << ' '; } return 0; }