前言
由于時間過少，這里僅僅記錄我自己的思路（給自己看的），如果你有興趣可以看看原題，再看看我寫的，但是一般情況下不會很友好，此類文章在以后都會標記“（記錄型博客）”

A

我們發(fā)現(xiàn)，所有的剩余量一定是
$a+\sqrt{2}b$或者是$C?(a+\sqrt{2}b)$的形式
把所有這些形式的全部抽出來
分析一下種類好像不是很多，然后建圖跑最短路即可

B

首先有個性質(zhì)，就是這么生成的樹的直徑一定是小于等于$\mathcal{O}(logn)$的
然后考慮dp
設(shè)$f_{u,l}$表示以$u$為根，直徑不超過$d$，距離$u$的最遠點距離不超過l的子樹最多包含的點數(shù)
轉(zhuǎn)移是對于每個$f_{u,l}$，加入兒子，枚舉兒子更新到的$l$，我們發(fā)現(xiàn)只需要$l+s+1\le d$即可，所以是一個前綴max形式，對于$s+1>l$的情況另外處理一遍即可
然后，在枚舉刪去點的數(shù)量的時候，我們只需要枚舉剩余直徑長度即可，所以要掃$\mathcal{O}(logn)$遍，每遍復雜度$\mathcal{O}(nlogn)$
綜上總復雜度$\mathcal{O}(nlo{g}^{2}n)$

C

排序后直接統(tǒng)計相鄰兩個數(shù)相差大于m的數(shù)量即可

D

感覺是構(gòu)造題？
$n$是奇數(shù)的話
$$\begin{array}{cccccc}1& 2& 3& ???& n?1& n\\ n& 1& 2& ???& n?2& n?1\\ n?1& n& 1& ???& n?3& n?2\\ ???& ???& ???& ???& ???& ???\\ 2& 3& 4& ???& n& 1\end{array}$$
就好了
然后若$n=4$
$$\begin{array}{cccc}1& 2& 3& 4\\ 4& 3& 2& 1\\ 2& 1& 4& 3\\ 3& 4& 1& 2\end{array}$$
之后就構(gòu)造了
設(shè)已經(jīng)求出答案為$n$的矩陣$A(n)$
沿著對角線翻轉(zhuǎn)的矩陣為$A^{\prime }(n)$
現(xiàn)在要對新的$n$求答案，設(shè)$n=2k$
$$A(2k)=\left\{\begin{array}{cc}A(k)+k& A^{\prime }(k)\\ A(k)\%k+1& A(k)+k\end{array}\right\}$$
由于$A(k)+k$本身不會不滿足對稱的性質(zhì)
考慮$A(k)\%k+1$和$A^{\prime }(k)$，原本$A(k)$和$A^{\prime }(k)$是完全對稱的，現(xiàn)在$A(k)$全部改了值，所以問題就解決了

E

建出所有免費走的地方之間的邊，跑最短路即可
復雜度$\mathcal{O}(n^{2}lo{g}^{2}n)$

F

按照權(quán)值從小到大加邊
新增點權(quán)為某個節(jié)點到當前點路徑的xor
然后建trie，加邊合并的時候啟發(fā)式在trie里查詢
總復雜度$\mathcal{O}(nlo{g}^{2}n)$

G

如果沒有最后的交換操作的話直接貪心取段，然后將最多的段數(shù)與k比較即可
然后考慮有交換的情況，這就非常麻煩了
我們考慮$[a_1,a_2][b_1,b_2][c_1,c_2][d_1,d_2][e_1,e_2][f_1,f_2]???$的情況
假設(shè)我們要交換兩段，我們發(fā)現(xiàn)左段的左端點一定是某段的左端點，右段的右端點一定是某段的右端點（否則一定能分開新的段）
假設(shè)我們現(xiàn)在左段左端在$x_1$，右段右端在$y_2$
我們發(fā)現(xiàn)若$x=y$則交換之后一定不成立
所以$x=y$
于是我們相當于要把一段內(nèi)部花一次交換的代價以分成更多段
我們發(fā)現(xiàn)只要確定第一段和最后一段的端點，中間的當成不能交換的問題做就好了
我們要把第一段和最后一段翻轉(zhuǎn)，所以第一段一定要包含R，最后一段一定要包含L，然后我們通過貪心把所有可以作為第一段的右端點的點都搞出來，我們發(fā)現(xiàn)這些點也可以成為最后一段的左端點，考慮這些分的段，如果除了第一段與最后一段剩下大于1段的，這兩段排序后將不有序，所以一定只有貪心出來的一段能繼續(xù)再分，于是我們就將每一段求出最大值取max即可
這里的段的示意圖$[x_k,n][x_{k?1},x_k)???[x_1,x_2)[1,x_1)$，我們每次算一個$[x_i,x_{i+1}]$的答案就好了
，總復雜度$\mathcal{O}(n)$
下面是AC代碼
題目鏈接

#include<cstdio> #include<cctype> #include<algorithm> //#include<ctime> #define rg register typedef long long ll; template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void Swap(T&a,T&b){T c=a;a=b;b=c;} //template <typename T> inline void swap(T*a,T*b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;} template <typename T> inline T square(const T x){return x*x;}; template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> inline void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } int n,k,a[1000001],maxplace,las=1; int ok[1000001],tot; void rt(const bool fla) {if(fla)puts("Yes");else puts("Poor Simon");exit(0); } int le,aaa[1000001]; int calc2() {int ma=0,an=0;for(int i=1;i<=le;i++){maxd(ma,aaa[i]);if(i==ma)an++;}return an; } int len,A[1000001]; int calc1() {maxplace=0;int ans=0,fst=0,la=1;for(int i=1;i<=len;i++){maxd(maxplace,A[i]);if(i==maxplace){fst++;if(fst!=1&&i!=len){le=i-la+1;for(int j=1;j<=le;j++)aaa[le-j+1]=A[la+j-1]-la+1;maxd(ans,calc2());}la=i+1;}}return ans+min(fst,2); } int check(int l,int r) {len=r-l+1;for(int i=1;i<=len;i++)A[len-i+1]=a[l+i-1]-l+1;return calc1()-1; } int main() {read(n),read(k);for(int i=1;i<=n;i++)read(a[i]);for(int i=1;i<=n;i++){maxd(maxplace,a[i]);if(i==maxplace)ok[i]=1,tot++;}if(tot>=k)rt(1);for(int i=1;i<=n;i++)if(ok[i]){if(tot+check(las,i)>=k)rt(1);las=i+1;}rt(0);return 0; }

H

我們發(fā)現(xiàn)只要贏的次數(shù)最多，直接貪心即可，兩行代碼足矣

I

大概是經(jīng)典的FFT題目，先轉(zhuǎn)化為原根求和，變成加法問題后直接用FFT做卷積即可

J

我們發(fā)現(xiàn)，我們要求的是最長不上升子序列即$0???01???1$形式
要求所有的$(su{m}_0+su{m}_1)su{m}_0=su{m}_0^2+su{m}_{1}su{m}_0$
考慮枚舉最右邊的一個$0$
我們要求的是$\sum su{m}_1$，并且要滿足這是最右邊的$0$，如果右邊有更多就不優(yōu)
考慮dp，$f_{i,j},g_{i,j}$分別表示到第i個數(shù)，1的數(shù)量，方案數(shù)推完即可，復雜度$\mathcal{O}(n^2)$（容易發(fā)現(xiàn)$1$的數(shù)量要一直大于$0$的數(shù)量）
再考慮求左側(cè)的情況，要求$\sum su{m}_0$非常方便，同理即可（不過這里容易發(fā)現(xiàn)$0$的數(shù)量要一直大于等于$1$的數(shù)量）
然后求$\sum su{m}_0^2$好像也沒啥區(qū)別，貢獻的時候有個平方就好了
然后就做完了
復雜度$\mathcal{O}(n^3)$

K

容易發(fā)現(xiàn)，對于原序列，每一個左括號都有相應(yīng)的有括號進行匹配，對于任何截取的一段$l,r$，括號匹配的要求是不變的，所以直接維護每個左括號匹配的右括號位置即可，每次詢問用一個區(qū)間max即可
）厲害的人可以搞一個$\mathcal{O}(n)?\mathcal{O}(1)$rmq

L

根據(jù)擴展歐幾里得可知x,y的通解
現(xiàn)在相當于求$ax(b+x)+cy(d+y)$
然后因為給出的系數(shù)都很小，好像枚舉就好了

結(jié)語

完

總結(jié)

以上是生活随笔為你收集整理的cometoj contest 6（记录型博客）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。