目錄

A.Alive Fossils

?H.Insert 1, Insert 2, Insert 3, ...

I.Make It Square

J.Permutation and Primes

---

A.Alive Fossils

思路：一開始題意看半天沒看懂，后面發現只需要輸出t組輸入中，都出現過的字符串即可。

代碼：

void solve() {int t;cin>>t;for(int i=1;i<=t;i++){int n;cin>>n;for(int i=1;i<=n;i++){string s;cin>>s;mp[s]++;}}vector<string>ans;for(auto x:mp){if(x.second==t){ans.push_back(x.first);}}cout<<ans.size()<<endl;for(auto x:ans) cout<<x<<endl;
}

?H.Insert 1, Insert 2, Insert 3, ...

思路：根據題意我們可以發現，因為數字是按順序1,2,3......插，所以若一段區間[l,r]滿足條件，那么[l,r'](r'<=r)也必然滿足條件。我們可以從后往前遍歷，也就是遍歷區間[i,n](i從n遍歷到1)。每次遍歷到a[i]時，因為插入是順序的，所以這個a[i]，一定能和a[i]+1這個值對應，把它“抵消”掉，所以若一個區間合法，那么這個區間會被“抵消”完，第i個點的貢獻為最左邊的沒被抵消完的端點-i。

舉個例子吧，拿樣例一來說，它的序列為：

1 1 2 2 3 3

從后往前遍歷，遍歷了i=5以及i=6，此時存入了兩個3，它們都不合法：

不合法的值：3 3

不合法的下標：5 6

貢獻為：最左邊的沒被抵消完的端點-i=5-5=0

然后遍歷到i=4，此時a[i]=2，他能與一個a[i]+1抵消，也就是把3給抵消了，此時：

不合法的值：2?3

不合法的下標：4?6

貢獻為：最左邊的沒被抵消完的端點-i=4-4=0

然后遍歷到i=3，此時a[i]還是2，他還是能把3抵消，此時：

不合法的值：2 2

不合法的下標：3 4

貢獻為：最左邊的沒被抵消完的端點-i=3-3=0

然后遍歷到i=2，此時a[i]是1，他能把一個2抵消，此時：

不合法的值：2 （1不放入不合法的值中，因為單個1合法）

不合法的下標：4

貢獻為：最左邊的沒被抵消完的端點-i=4-2=2

然后遍歷到i=1，此時a[i]還是1，他能把一個2抵消，此時：

不合法的值：?無（1不放入不合法的值中，因為單個1合法）

不合法的下標：無

此時后面都合法了，貢獻為i~n整個區間也就是6

總貢獻為 ：0+0+0+2+6=8

代碼：

vector<int>ans,pos[maxn];
//ans存最入不滿足條件的點
//pos[x]存入a[i]=x的位置
int a[maxn],st[maxn];
void solve() {int n,res=0;cin>>n;ans.push_back(n+1);//放入初始值，使得：若點i后面沒有不滿足條件的點，則答案加n-i+1，也就是i~n區間的貢獻。for(int i=1; i<=n; i++)cin>>a[i];for(int i=n; i>=1; i--) {if(pos[a[i]+1].size()) {st[pos[a[i]+1].back()]=true;//這個點被上一個點"抵消"了，標記這個點已經合法了pos[a[i]+1].pop_back();//消掉}if(a[i]>1) {pos[a[i]].push_back(i);//存入值對應的下標ans.push_back(i);//存入不合法的位置}while(st[ans.back()])ans.pop_back();//把合法的都彈出res+=ans.back()-i;}cout<<res<<endl;
}

I.Make It Square

思路：若字符串s的長度小于t，我們將兩個字符串翻轉后交換，仍可以使得字符串s大于t，所以我們考慮s長度大于t的情況。

通過手玩樣例我們可以發現，隨著字符串p和q長度的增加，對于字符串s，分割點是固定的，分割點在后綴大小為(s.size()-t.size())/2。舉個例子，比如樣例三：

s=abbabbababbab，t=bab。

當p.size()=q.size()=1時：

?p+s+q+t=?abbabbababbab?bab

分割為??abbabbab??abbab?bab

當p.size()=q.size()=2時：

?p+s+q+t=??abbabbababbab??bab

分割為???abbabbab??abbab??bab

以??abbabbab??abbab??bab舉例，

首先，若bab與abbabbab的后綴不重合，那么這兩個部分的字符串怎么都不會相等。然后可以看出，我們可以通過字符串abbabbab作為后綴，字符串abbab作為前綴，來求出已經不固定的字符個數。

若這兩個部分有重合，則判斷重合部分是否一樣，也就是abbabbab的重合前綴和abbab重合后綴是否一樣，利用z函數判斷即可，若重合部分一樣則答案為1，反之答案為0。

若這兩個部分沒重合，則計算不固定字符的個數，答案為26的冪次。

具體實現見代碼：

代碼：

vector<int> zFunction(string s) {int n = s.size();vector<int> z(n + 1);z[0] = n;for (int i = 1, j = 1; i < n; i++) {z[i] = max(0ll, min(j + z[j] - i, z[i - j]));while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {z[i]++;}if (i + z[i] > j + z[j]) {j = i;}}return z;
}
void solve() {k26[0]=1;for(int i=1; i<maxn; i++) {k26[i]=k26[i-1]*26%mod;}//預處理26的冪次string s,t;int n;cin>>n>>s>>t;int lens=s.size(),lent=t.size();if((lens+lent)%2) {//若字符串長度之和為奇數，那么它們怎么都不能分割成兩個相等字符串for(int i=1; i<=n; i++)cout<<0<<" ";return;}if(lens<lent) {reverse(s.begin(),s.end());reverse(t.begin(),t.end());swap(s,t);swap(lens,lent);}if(s.substr((lens+lent)/2-lent,lent)!=t) {//判斷字符串t作為后綴是否合法for(int i=1; i<=n; i++)cout<<0<<" ";return;}auto v=zFunction(s);reverse(v.begin(),v.end());//v[i]表示長度為i的后綴與前綴的最大公共前綴FOR(1,n) {int now=(lens+lent+2*i)/2;//當前一半的總字符串長度int p=abs(lens-now);if(lens>now) {//若有重合部分if(v[p]!=p) cout<<0<<" ";//重合部分是否全部相同else cout<<1<<" ";//答案為加1} else {cout<<k26[p]<<" ";//答案為26^(不確定字符的個數)}}
}

J.Permutation and Primes

思路：我們可以先構造長度為7的循環節：

i+3，i+6，i+1，i+4，i+7，i+2，i+5

那么若n%7不為0的時候怎么辦呢？我們可以先把前面的長度為7循環節給賦值，然后最后7+n%7個數，我們隨便找一組解滿足它與循環節的末尾形成奇質數，放預處理后面即可。

代碼：

int cmp[7][15] {{3,6,1,4,7,2,5},//長度為7的循環節{5,2,7,4,1,8,3,6},//最后8個數，此時n%7=1{9,6,3,8,5,2,7,4,1},//最后9個數，此時n%7=2{9,4,7,2,5,10,3,8,1,6},//最后10個數，此時n%7=3{11,8,5,10,7,2,9,4,1,6,3},//最后11個數，此時n%7=4{1,6,3,10,7,12,5,2,9,4,11,8},//最后12個數，此時n%7=5{1,4,9,2,7,12,5,10,3,6,13,8,11}//最后13個數，此時n%7=6
};
void solve() {cin>>n;int k=n/7;if(n==2) {cout<<"1 2"<<endl;} else if(n==3) {cout<<"1 2 3"<<endl;} else if(n==4) {cout<<"1 2 3 4"<<endl;} else if(n==5) {cout<<"1 4 3 2 5"<<endl;} else if(n==6) {cout<<"4 3 6 5 2 1"<<endl;}if(n<=6)return;for(int i=0; i<k-1; i++) {for(int j=0; j<7; j++) {a[i*7+j+1]=i*7+cmp[0][j];}}//前面的循環節賦值 for(int i=0; i<7+n%7; i++) {a[(k-1)*7+i+1]=(k-1)*7+cmp[n%7][i];}//最后放合法解 for(int i=1; i<=n; i++)cout<<a[i]<<" \n"[i==n];
}