T1：最长不下降子序列 (sequence)
思路：
依据做传统最长不下降子序列的的经验，这题用 \(dp\) 。
因为 \(a\) 的值只有 \(1,2\) ，并且翻转操作只进行一次，所以我们考虑什么样的情况一次翻转能产生最长不下降子序列呢？
当序列形如 \(\{1,...,1,2,...,2,1,...,1,2,...,2\}\) 时一次翻转会产生最长不下降子序列。
因此，我们设 \(dp_{i,j}\) 表示前 \(i\) 个数，到了第 \(j\) 组的最长不上升子序列的长度。
转移方程为
代码：
$code$
#include<iostream>
using namespace std;
const int N=1e6+5;
int n,a[N],dp[N][5],ans;
int t[5]={0,1,2,1,2};
int main(){
// freopen("sequence.in","r",stdin);
// freopen("sequence.out","w",stdout);ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){for(int j=1;j<=4;j++){for(int k=1;k<=j;k++){dp[i][j]=max(dp[i][j],dp[i-1][k]+(a[i]==t[j]));}ans=max(dp[i][j],ans);}}cout<<ans<<'\n';return 0;
}
/*
10
2 2 2 1 2 2 1 1 1 1*/
T2：美食节 (food)
思路：
首先考虑在什么情况下无解。显然，当众数的个数大于 \(\lceil \frac{n}{2} \rceil\) 无解。
同时，我们需要在有解的情况下使答案的字典序尽可能的小。
那么我们不妨这样考虑：
从前向后的往答案里填数，若此时的众数正好等于剩余数的一半，那么我们必须填此众数，否则就无解了；否则，我们就把剩下的数中字典序最小的填进去，当然不可以和前一个数种类一样哦。
最后我们只需要找一个东西来维护就好啦，线段树和 \(set\) 都可以。我写的 \(set\)（ \(STL\) 万岁 ୧(﹒ᴗ﹒)୨ ）
代码：
$code$
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int N=300000+5;
int n,m,a[N],cnt[N],last,c[N];
vector<int> v[N];set<pair<int,int>> s,t;
int main(){
// freopen("food.in","r",stdin);
// freopen("food.out","w",stdout);ios::sync_with_stdio(false);cin>>n;m=n;for(int i=1;i<=n;i++){cin>>a[i];v[a[i]].push_back(i),cnt[a[i]]++;}for(int i=1;i<=n;i++) if(cnt[i]) s.insert(make_pair(cnt[i],i)),t.insert(make_pair(v[i][0],i));int x=(*s.rbegin()).first;if(x>(n+1)>>1){cout<<-1<<'\n';return 0;}for(int i=1;i<=n;i++,m--){pair<int,int> q=*s.rbegin();if(q.first*2-1==m){last=q.second;s.erase(make_pair(cnt[q.second],q.second));s.insert(make_pair(--cnt[q.second],q.second));t.erase(make_pair(v[q.second][c[q.second]],q.second));if(cnt[q.second]) t.insert(make_pair(v[q.second][++c[q.second]],q.second));cout<<v[q.second][c[q.second]+!cnt[q.second]-1]<<' ';}else{pair<int,int> p=*t.begin();if(p.second==last) p=*(++t.begin());last=p.second;s.erase(make_pair(cnt[p.second],p.second));s.insert(make_pair(--cnt[p.second],p.second));t.erase(make_pair(v[p.second][c[p.second]],p.second));if(cnt[p.second]) t.insert(make_pair(v[p.second][++c[p.second]],p.second));cout<<p.first<<' ';}}return 0;
}
T3不会(╥╯^╰╥)
T4：概率 (pr)
思路：
显然，前一半的和大于后一半的和=前一半的和小于后一半的和=(1-前后相等)/2
总方案数是好求的，\((m+1)^{2n}\)
我们只需要容斥一下前后相等的方案数就行。
我们不妨令后一半的数都为负数，这样前后的和就为 \(0\) 了。然后再给后一半的每一个数加上 \(m\) ，则这 \(2n\) 个数的和为 \(nm\) 。
这时问题就转化为了基于容斥原理解决不定方程非负整数解计数问题
我们先忽略每个数属于 \([0,m]\) 的限制范围。那么此时的方案数可以用插板法来求。
我们现钦定 \(f_i\) 表示有 \(i\) 个位置的数大于 \(m\) 。
则
如何来理解呢？
首先我们需要从 \(2n\) 个位置里选出 \(i\) 个值超出范围的位置。然后给这些位置每一个先放上 \(m+1\) ，然后剩下的数用插板法分下去即可。
接着，我们设 \(g_i\) 表示恰有 \(i\) 个位置超出范围，由二项式反演得
最后照着式子敲代码即可，记得取模哦~~
代码：
$code$
#include<iostream>
#define int long long
using namespace std;
const int N=4e6+10;
int T,n,m,mod,fac[N],inv[N],ans,flag;
inline int qpow(int x,int y){int res=1;while(y){if(y&1) res=(res*x)%mod;x=(x*x)%mod;y>>=1;}return res;
}
inline int C(int n,int m){if(n<m) return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
// freopen("pr.in","r",stdin);
// freopen("pr.out","w",stdout);ios::sync_with_stdio(false);cin>>mod>>T;fac[0]=1;for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;inv[N-1]=qpow(fac[N-1],mod-2);for(int i=N-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;while(T--){ans=0;flag=1;cin>>n>>m;for(int i=0;i<=2*n;i++){ans=(ans+flag*C(2*n,i)%mod*C(n*m-(m+1)*i+2*n-1,2*n-1)%mod+mod)%mod;flag=-flag;}ans=(qpow(m+1,2*n)-ans+mod)%mod;cout<<ans*qpow(2,mod-2)%mod*qpow(qpow(m+1,2*n),mod-2)%mod<<'\n';}return 0;
}
后言：
闲话
我等皆是修罗恶鬼，自有一套行事准则 ——《第一召唤师》 沈烟