這場簡單，甚至賽時90分鐘不到就AK了。比賽鏈接，隊友題解友鏈

剛入住學校監獄，很不適應，最近難受的要死，加上最近幾場CF打的都不順利，san值要爆掉了，只能慢慢補題了。

這場C是個滑動窗口，D是貪心，E是有點麻煩的構造，FG是數論。

---

A 小紅的字符串切割

思路：

記錄一下字符串長度，然后從中間拆開。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;string s;int main(){cin>>s;cout<<s.substr(0,s.length()/2)<<endl<<s.substr(s.length()/2);return 0;
}

---

B 小紅的數組分配

思路：

統計一下每個數字出現的次數，然后兩個兩個拿走，如果有一種數字剩下了奇數個，就說明這種數字不能平分給兩個數組，直接返回-1。

code：

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
const int maxn=1e5+5;int n,a[maxn];
map<int,int> mp;int main(){cin>>n;for(int i=1,t;i<=2*n;i++){cin>>t;mp[t]++;}for(int i=1;i<=n;i++){if(mp.begin()->second==1){cout<<-1<<endl;return 0;}a[i]=mp.begin()->first;mp.begin()->second-=2;if(mp.begin()->second==0)mp.erase(mp.begin());}for(int i=1;i<=n;i++)cout<<a[i]<<" ";puts("");for(int i=1;i<=n;i++)cout<<a[i]<<" ";return 0;
}

---

C 小紅關雞

思路：

如果把雞窩的位置放在數軸上，那么我們其實就是要找一段長為 $k$ 的區間，使得這個區間包含的雞窩（也就是數軸上的點）的個數最多。

這有點像滑動窗口。假設有個長為 $k$ 的窗口，從最左邊的雞窩開始向右滑動，右端點每次移動到下一個雞窩，然后把左邊超出范圍的雞窩刪掉，考慮用雙端隊列維護這個過程，每滑動一次就記錄一下當前窗口中有多少雞窩，取最大的即可。

code：

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;int n,k;
int a[maxn];
deque<int> q;int main(){cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);int ans=0;for(int i=1;i<=n;i++){q.push_back(a[i]);while(a[i]-q.front()>k)q.pop_front();ans=max(ans,(int)q.size());}cout<<1.*ans/n;return 0;
}

---

D 小紅的排列構造

思路：

題意說白了就是修改數組中的某些數，讓 $1～n$ 出現一次且僅一次。

貪心地來想，如果排列中的某個數在給出的數組中有的話，我們就可以保留其中一個。而多余的和超出范圍（$>n$）的數我們就需要把它修改成其他數。

所以做法就比較明確了，統計一下不符合條件的下標，然后再給它們分配排列中沒有用到的數字。

code：

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;int n;
vector<int> a;int main(){cin>>n;set<int> S;int cnt=0;for(int i=1,t;i<=n;i++){cin>>t;if(!S.count(t) && t<=n)S.insert(t);else {cnt++;a.push_back(i);}}cout<<cnt<<endl;int i=1;for(auto x:a){while(S.count(i))i++;cout<<x<<' '<<i<<endl;i++;}return 0;
}

---

E 小紅的無向圖構造

思路：

比較麻煩的一道構造。

先不考慮湊出 $m$ 條邊，單純想怎么湊出滿足 $a$ 數組。考慮一棵樹，深度其實就是它到根節點的距離，深度為 $h$ 的點一定連著至少一個深度為 $h?1$ 的點，并且它一定不能去連其他深度的點，否則它本身或者連接的另一個點的深度就會發生變化。

也就是說，至少要有 $n?1$ 條邊才能保證圖聯通。并且對一個距離 $1$ 號節點距離 $a_i$ 的點，至少要有一個距離為 $a_i?1$ 的點給它連著。也就是不能斷層。

另外因為不允許重邊和自環，因此 $m$ 太大的時候也是無解的。怎么找到這個最大值以及怎么構造呢？考慮深度為 $h$ 的點一定只能連著深度為 $h?1$ 或 $h$ 的點，因此深度為 $h$ 的點最多可以連出 $siz{e}_{h?1}?siz{e}_h$ 和 $C_{siz{e}_h}^2=\frac{siz{e}_h?(siz{e}_h?1)}{2}$ 條邊，我們算出這個最大的可以連邊的數量，然后和 $m$ 比較一下就知道有沒有解了。

那么怎么連邊呢。首先我們需要保證聯通，所以需要先把最低限度的邊連好。我們用個vector把每個深度的點存一下，然后深度為 $h$ 的所有點先跟 深度為 $h?1$ 的某個點連好邊。然后再去連沒有必要的邊，并記錄一下連了多少個，夠了后面就不用再連沒必要的邊了。

code：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;int n,m,d[maxn];
vector<int> a[maxn];int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>d[i];a[d[i]].push_back(i);}if(m<n-1){cout<<-1;return 0;}ll maxx=0,cnt=1;for(int i=1;a[i].size()!=0;i++){cnt+=a[i].size();maxx+=1ll*a[i-1].size()*a[i].size();maxx+=1ll*a[i].size()*(a[i].size()-1)/2;}if(maxx<m || cnt!=n){//m超出最大的邊數 或 出現斷層cout<<-1;return 0;}m-=n-1;vector<pair<int,int> > e;for(int i=1;a[i].size()!=0;i++){for(auto x:a[i])//必要的邊e.push_back(make_pair(a[i-1][0],x));for(int j=1;j<a[i-1].size() && m;j++){//非必要的邊 h-1 -> hfor(auto x:a[i]){e.push_back(make_pair(a[i-1][j],x));m--;if(!m)break;}}for(int j=0;j<a[i].size() && m;j++)for(int k=j+1;k<a[i].size() && m;k++){//非必要的邊 h -> he.push_back(make_pair(a[i][j],a[i][k]));m--;if(!m)break;}}for(auto x:e)cout<<x.first<<" "<<x.second<<endl;return 0;
}

---

F，G 小紅的子序列權值和

思路：

對一種選取方案，發現其實 $1$ 對乘積的結果是沒有影響的，所以先不看 $1$，只看 $2$ 和 $3$。假如 $n$ 個數里一共有 $a$ 個 $2$ 和 $b$ 個 $3$。某種選取方案有 $x$ 個 $2$ 和 $y$ 個 $3$，那么總的因子個數就是 $(x+1)?(y+1)$（乘積結果為 $2^x?3^y$，對一個因子，從 $x$ 個 $2$ 里可以選 $0～x$ 個 $2$，從 $y$ 個 $3$ 里可以選 $0～y$ 個 $3$，總的方案數就是 $(x+1)?(y+1)$。這個結論可以推廣，對 $n=p_1^{c_1}?p_2^{c_2}???p_m^{c_m}$ 的因子個數就是 ${\prod }_{i=1}^m(c_i+1)$）。而選到這個方案總的次數就是從 $a$ 個 $2$ 里選 $x$ 個 $2$，以及從 $b$ 個 $3$ 里選 $y$ 個 $3$，也就是選取 $x$ 個 $2$ 和 $y$ 個 $3$ 的方案的總貢獻是 $C_a^x?C_b^y?(x+1)?(y+1)$。

最后對每個選取方案，我們可以往里面添加 $n?a?b$ 個 $1$ 中的任意個，也就是最后結果乘以 $2^{n?a?b}$，最后再減掉一個 什么都不選 的方案就行了。答案為：$$2^{n?a?b}?\sum _{x=0}^a\sum _{y=0}^b{C}_a^x?C_b^y?(x+1)?(y+1)?1$$$O(n)$ 預處理一下階乘和階乘的逆元，就可以 $O(n^2)$ 進行累加，可以過 F 題。

其實你會發現 $C_a^x$ 和 $(x+1)$ 這個部分和 $y$ 沒有一點關系，所以可以提出來，同理 $C_b^y$ 和 $(y+1)$ 這個部分和 $x$ 沒有一點關系，所以可以提出來。于是就得到了：$$2^{n?a?b}?\sum _{x=0}^a{C}_a^x?(x+1)?\sum _{y=0}^b{C}_b^y?(y+1)?1$$兩個部分分開計算，時間復雜度 $O(n)$，可以通過 G 題。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const ll mod=1e9+7;ll n,a,b;
ll fac[maxn],ifac[maxn];ll qpow(ll a,ll b){b%=mod-1;ll base=a%mod,ans=1;while(b){if(b&1){ans*=base;ans%=mod;}base*=base;base%=mod;b>>=1;}return ans;
}
ll inv(ll x){return qpow(x,mod-2);}
ll C(int a,int b){//C_a^b return fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}int main(){cin>>n;fac[0]=ifac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;ifac[n]=inv(fac[n]);for(int i=n;i>=1;i--)ifac[i-1]=ifac[i]*i%mod;a=b=0;for(int i=1,t;i<=n;i++){cin>>t;if(t==2)a++;else if(t==3)b++;}ll t1=0,t2=0;for(int y=0;y<=b;y++){t1=(t1+C(b,y)*(y+1))%mod;}for(int x=0;x<=a;x++){t2=(t2+C(a,x)*(x+1))%mod;}ll ans=t1*t2%mod;cout<<(qpow(2,n-a-b)*ans%mod-1+mod)%mod;return 0;
}