A - A

Pak Chanek 有一個包含 $n$ 個正整數的數組$a$。由于他正在學習如何計算兩個數字的向下取整平均值，他希望在他的數組 $a$ 上進行練習。當數組 $a$ 至少有兩個元素時，Pak Chanek 將執行以下三步操作：

$?$選擇兩個不同的索引 $i$ 和 $j(1\le i,j\le \mid a\mid ;i\ne j)$，注意 $\mid a\mid$ 表示數組 $a$ 的當前大小。

$?$將 $?\frac{2a_i?+a_j}{2}?$? 附加到數組的末尾。

$?$從數組中移除元素 $a_i$ 和 $a_j$并連接數組的剩余部分。

例如，假設 $a=[5,4,3,2,1,1]$ 。如果我們選擇 $i=1$ 和 $j=5$ ，則結果數組將是 $a=[4,3,2,1,3]$ 。如果我們選擇 $i=4$ 和 $j=3$ ，則結果數組將是 $a=[5,4,1,1,2]$。

在所有操作完成后，數組將只包含一個元素 $x$。如果 Pak Chanek 進行最佳操作，找出 $x$ 的最大可能值。

---

? $?x?$ 表示 $x$ 的向下取整函數，即小于或等于 $x$ 的最大整數。例如，$?6?=6、?2.5?=2、??3.6?=?4$ 和 $?\pi ?=3$

---

找規律，可以通過打表發現，只要每次把兩個最小的元素合并起來，就能使最終的答案最大化。

那怎么找到最小的兩個值呢？怎么把合并的值放到末尾呢？怎么刪除選中的兩個值呢？這里我們可以偷個懶，因為要合并$n?1$次，我們就循壞$n?1$次，每次先把$a$數組排一遍升序，我們就鎖定了兩個最小值。

現在是最關鍵的時刻，雖然題目說每次會把合并之后的結果放在數組的末尾，但下一次循環我們還是會排序，所以先把它放在$a[1]$，由于每次操作$a$數組的最后一項都會躥到前面去，所以我們就先把它放在$a[2]$。

這樣我們就完美的刪除了選中的兩個數，并保留了$a$數組的其余項和選中的兩個數合并之后的結果。

#include<bits/stdc++.h>//獻上代碼
using namespace std;
int a[55],t,n; //數據水是我時間復雜度的證明，O(n log n)
int main(){cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<n;i++){sort(a+1,a+1+n-i+1); //注意，我們在a數組里刪除了值a[1]=(a[1]+a[2])/2,a[2]=a[n];}cout<<a[1]<<endl;//最后a數組只剩1個值了，于是輸出a[1]}return 0;
} 

B - B

給定一個由互不相同的整數組成的數組$a$。每次操作中，你可以選擇：

$?$選取數組的某個非空前綴$?$，并將其替換為該前綴的最小值；
$?$選取數組的某個非空后綴$?$，并將其替換為該后綴的最大值。

注意：你可以選擇整個數組$a$作為操作對象。

對于每個元素$a_i?$，判斷是否存在一系列操作能將數組$a$轉化為$a_i$——即最終數組$a$僅包含該元素$a_i$ 。

請輸出一個長度為$n$的二進制字符串，其中第$i$個字符為$1$表示存在這樣的操作序列，否則為$0$。

---

$?$數組的前綴是指由前$k$個元素組成的子數組（$k$為任意整數）。
$?$數組的后綴是指由后$k$個元素組成的子數組（$k$為任意整數）。

---

首先我們可以證明如果一個數是某個前綴的最小值，或是某個后綴的最大值，就一定可以保留下來。

因為如果這個數是某個前綴的最小值，就可以先進行一次前綴操作，后面不管是什么數就都能經過幾次后綴操作壓縮成一個數，最后再進行一次前綴或后綴操作就能保留該數。

例如，$a=${$5,6,3,1,7$}，此時我們想要判斷$a_3$能不能保留下來，就先判斷它是不是某個前綴的最小值，結果是的，就先進行一次前綴操作，$a=${$3,1,7$}，接著進行一次后綴操作，$a=${$3,7$}，最后再進行一次前綴操作，$a_3$就保留了下來。

注意，最后一次操作要根據情況判斷是進行前綴操作還是進行后綴操作。

C - C

Nene 發明了一種基于遞增整數序列 $a_1?,a_2?,\dots ,a_k$ 的新游戲。

在這個游戲中，最初有 $n$ 名玩家排成一行。在每一輪游戲中，發生以下情況：

Nene 找到第 $a_1?、a_2?、\dots$和 $a_k$名玩家，他們會同時被踢出游戲。如果第 $i$ 名玩家應該被踢出，但排成一行的玩家少于 $i$ 名，則跳過該玩家。

一旦在某一輪中沒有人被踢出游戲，所有仍在游戲中的玩家將被宣布為勝利者。

例如，考慮有$a=[3,5]$ 和 $n=5$ 名玩家的游戲。假設玩家按順序被命名為玩家 A、玩家 B、
…、玩家 E。

那么，在第一輪之前，玩家排成 ABCDE。Nene 找到第 $3$ 和第 $5$ 名玩家。這些是玩家 C 和 E。他們在第一輪被踢出。現在玩家排成 ABD。

Nene 找到第 $3$ 和第 $5$ 名玩家。第 $3$ 名玩家是玩家 D，而排成一行中沒有第 $5$ 名玩家。因此，只有玩家 D 在第二輪被踢出。

在第三輪中，沒有人被踢出游戲，因此游戲在這一輪結束。玩家 A 和 B 被宣布為勝利者。

Nene 尚未決定最初有多少人會加入游戲。Nene 給了你 $q$ 個整數 $n_1?,n_2?,\dots ,n_q$? ，你應該獨立回答以下問題：

如果游戲最初有 $n_i?$ 名玩家，最終會有多少人被宣布為勝利者？

---

先找出$n$數組的最小值，然后對于每次詢問只要輸出$(a_i)+1$%$mn+1$。怎么證明？

如圖，在$3$下標之后包括$3$下標的元素都被刪除了，最后只剩下兩個元素，如果還是不信邪的話，自己造幾個樣例試試吧！

D - D

給定兩個長度為n的排列$a$和$b$。排列是指包含$n$個從$1$到$n$不重復元素的數組。例如數組$[2,1,3]$是排列，但$[0,1]$和$[1,3,1]$不是。

你可以（不限次數）選擇兩個下標$i$和$j$，然后同時交換$a_i$ 與$a_j$? 以及$b_i$與$b_j$。

你需要最小化兩個排列中的逆序對總數。排列p中的逆序對是指滿足$i<j$且$p_i>p_j$的下標對$(i,j)$。例如當$p=[3,1,4,2,5]$時，共有$3$個逆序對（具體為$(1,2)、(1,4)$和$(3,4)$）。

---

首先用一個結構體接入a,b數組，然后按a數組排序，最后輸出就行了。

#include<bits/stdc++.h>
using namespace std;
struct tt{int a,b;
}c[200005];
bool cmp(tt x,tt y){return x.a<y.a;
}
int main(){int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;i++)cin>>c[i].a;for(int i=1;i<=n;i++)cin>>c[i].b;sort(c+1,c+1+n,cmp);for(int i=1;i<=n;i++)cout<<c[i].a<<" ";cout<<endl;for(int i=1;i<=n;i++)cout<<c[i].b<<" ";cout<<endl;		}return 0;
}

E - E

你有一個數組 $a_1,a_2,\dots ,a_n$。回答 q 個以下形式的查詢：

如果我們將數組的 $a_l,a_{l+1},\dots ,a_r$? 范圍內的所有元素改為$k$，整個數組的和會是奇數嗎？

注意，查詢是獨立的，不會影響后續的查詢。

---

前綴和數組來存儲區間總和。注意1，因為我們只需要判斷總和是不是奇數，所以我們可以%2。注意2，把一個區間的值都改成k等于把一個區間的值都加上k，當然，僅在本題生效。
為什么呢？當然是通過打表找規律發現的，想知道為什么的自己試幾組數據吧！

#include<bits/stdc++.h>
using namespace std;
long long a[200005],s[200005];
int main(){int t;cin>>t;while(t--){memset(s,0,sizeof s);memset(a,0,sizeof a);long long n,q,cs=0;//cs數組總和cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i],cs+=a[i]%2,s[i]=a[i]%2+s[i-1];while(q--){long long l,r,k,css=cs;cin>>l>>r>>k;css+=(r-l+1)*k%2-(s[r]-s[l-1])%2;if(css%2==1){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}}return 0;
} 

F - F

體面過于復雜，鏈接F - F

---

這題很顯然每次要合并最長的一條路徑才是最優操作，然而每次進行這種操作都會刪除2個葉子節點，所以先找出有多少個葉子節點，答案就是$\frac{?葉子節點數?}{2}$。