T1
求一个只含 \(1,2\) 的序列的最长不下降子序列的长度，但你可以翻转一个子串。
先考虑不翻转的情况。
这个显然可以用一般的单调栈来做，但考虑如何利用只含 \(1,2\) 的性质。
发现最长不下降子序列一定是形如 \(1,\dots,1,2,\dots,2\) 的形式，于是可以预处理每个位置的前缀 \(1\) 的个数以及后缀 \(2\) 的个数，设分别为 \(p1,p2\)，答案就是 \(\max_{i=0}^n p1_i+p2_{i+1}\)，之所以从 \(0\) 开始是因为可能全为 \(2\)。
现在考虑对于每一个 \(i\) 怎么交换能使它的 \(p1_i+p2_{i+1}\) 最大。可以发现当我们将 \(i\) 前面的 \(1\) 换到 \(i\) 后面后结果会少 \(1\)，如果是 \(2\) 的话结果会多 \(1\)，对于后面换到前面也是类似的，于是我们可以写出 \(\mathcal O(n^2)\) 做法：
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,ans,a[N],p1[N],p2[N];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",a+i);for(int i=1;i<=n;i++) p1[i]=p1[i-1]+(a[i]==1);for(int i=n;i>=1;i--) p2[i]=p2[i+1]+(a[i]==2);for(int i=0;i<=n;i++){int r1=0,r2=0;for(int j=i-1,t=0;j>=1;j--){if(a[j]==2) t++;else t--;r1=max(r1,t);}for(int j=i+1,t=0;j<=n;j++){if(a[j]==1) t++;else t--;r2=max(r2,t);}ans=max(ans,p1[i]+p2[i+1]+r1+r2);}printf("%d",ans);return 0;
}
预处理一下就是 \(\mathcal O(n)\) 了：
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,ans,a[N],p1[N],p2[N],c1[N],c2[N];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",a+i);for(int i=1;i<=n;i++) p1[i]=p1[i-1]+(a[i]==1);for(int i=n;i>=1;i--) p2[i]=p2[i+1]+(a[i]==2);for(int i=1;i<=n;i++){if(a[i]==1) c1[i]=max(0,c1[i-1]-1);else c1[i]=c1[i-1]+1;}for(int i=n;i>=1;i--){if(a[i]==2) c2[i]=max(0,c2[i+1]-1);else c2[i]=c2[i+1]+1;}for(int i=0;i<=n;i++)ans=max(ans,p1[i]+p2[i+1]+c1[max(i-1,0)]+c2[i+1]);printf("%d",ans);return 0;
}
模拟赛签到题，比较简单，但我是在切完 T2 才优化到正解的。
不足之处是虽然一开始就想到了大致思路，但简单的预处理优化后面再看才想到。
以后想到思路要多向不同方面思考，特别是一些简单的小优化，往往加上就是正解。
不过好像官解是直接 DP 的
只有 \(1,2\) 的序列中一个不下降子序列肯定是形如 \(1,1,\dots,1,2,\dots,2\)，前面一些 \(1\) 后面一些 \(2\) 的形式。
那么翻转一次可以变成不下降子序列的子序列是什么形式呢？研究一下，可以发现是形如 \(1,1,\dots,1,2,2,\dots,2,1,1,\dots,1,2,2,\dots,2\) 的形式，也就是最多四段 1,2 交替。当然其中一些段可以为空。
那么我们直接从前往后逐位考虑，设 \(f_{i,j}\) 表示在前 \(i\) 个数选出的子序列末尾到了第 \(j\) 段（\(1\le j\le 4\)）的情况下最长的长度，然后递推即可。
T2
一道 KOI 的原题
首先考虑无解的情况，记 \(v\) 为剩余未访问卖的餐厅数量最多那种食物的数量，\(m\) 为剩余的餐厅数量，那么当 \(v>m-v+1\)（剩下的所有餐厅插在那种的中间都没法完全分隔最多的那种）时无解。
其余因为要求字典序最小，所以可以贪心，直接选当前第一个未访问且与上一个访问餐厅的食物不同的编号的餐厅就行。
但我们手玩样例一发现不对。发现当 \(v=m-v+1\)，此时就只能选最多的那种餐厅了，因为如果选了剩下的，那么就会变成无解的情况。
仔细想下怎么实现，我们要维护 \(v\) 与每种餐厅还未访问的第一个位置，还要支持修改，时间复杂度要在 \(\mathcal O(\log n)\) 及以下。发现 STL 里的 set 就能满足需求。
代码实现的比较烂：
#include<bits/stdc++.h>
#define N 300005
using namespace std;
int n,m,last,a[N],c[N],cnt[N];
vector<int>b[N];
set<pair<int,int>>s,t;
void mypop(int x){last=x;s.erase({cnt[x],x});s.insert({--cnt[x],x});t.erase({b[x][c[x]],x});if(cnt[x]) t.insert({b[x][++c[x]],x});
}
int main(){scanf("%d",&n),m=n;for(int i=1;i<=n;i++) scanf("%d",a+i),b[a[i]].push_back(i),cnt[a[i]]++;for(int i=1;i<=n;i++) if(cnt[i])s.insert({cnt[i],i}),sort(b[i].begin(),b[i].end()),t.insert({b[i][0],i});int v=(*s.rbegin()).first;if(v>m-v+1) return puts("-1"),0;for(int i=1;i<=n;i++){auto v=*s.rbegin();m=n-i+1;if(v.first==m-v.first+1){int p=v.second;mypop(p);printf("%d ",b[p][c[p]+!cnt[p]-1]);}else{auto p=*t.begin();if(p.second==last) p=*(++t.begin());mypop(p.second);printf("%d ",p.first);}}return 0;
}
对于这种同时要维护编号、数量和值的代码实现，很容易搞混，还是要养成写注释的习惯。
T3
字符串题，还没补出来。
T4
有一个长度 \(2n\) 的序列，里面的每个元素 \(a_i\) 是在 \([0,m]\) 随机的一个数，求 \(\sum\limits_{i=1}^n a_i>\sum\limits_{i=n+1}^{2n} a_i\) 的概率。
鸽着。