模擬賽25

最近怎么狂掛不止。

1. 博弈

   考慮策略，首先是優先最小的，但是由于有重復的，所以在最小個數為偶數時會敗，以此類推，可以想到當有一個數出現次數時奇數先手必勝，否則必敗。

   考慮將相同的兩兩相消，發現 \(u\to v\) 和 \(u\to 根\to v\) 是等價的。

   于是每個點維護一下當前的數，問題變成了求和當前集合相同的集合有幾個，因為兩兩相消，可以異或 hash，也可用一些奇怪 hash。

   但是千萬千萬不要直接用 \(\sum a^n\)，這個東西竟然是可以穩定被卡的！

2. 跳躍

   發現其一定是在一個最大子段中反復橫跳，然后在到下一個。

   數據比較水，錯解輕松過（于是加了 hack）。

   hack 思路：

   首先是 \(k\) 取 \(min\) 的亂搞，這個輕松卡，就是 \(1,-100000,-100000,100000,100000\) 之類的用長段的負數讓你一直在最前面跳，但其是可以到后面。

   這個在大數據隨機下效果一般，不到 \(100\) 組就會出錯，欽定第一個是 \(1\) 以后十幾組就卡掉了。

   然后是一些假了的貪心，就是每次直接向最后一個可以跳到的地方跳，這個原理就是構造前后和的差距不大，但是從前面跳到后面會有較大代價導致不優，像 \(99999,100000,-100000,-100000,-100000,-99998,100000,100000\) 在 \(k\) 比較小的時候。

   這個在小數據隨機下效果一般，\(n,k\le 20\) 時十幾組就卡了（值域開大點），但是有人數據點分治但 \(n,k\le 20\) 的 dfs T 了沒繃住。

   然后有一些逆天的 \(0\)，比如 \(k=0\)，有的要寫特判。

   還有一些暴力會在恰好整除時錯，懶得卡了，暴力一般也過不去。

   給一下數據生成器，多生成幾組就有了

   #include<bits/stdc++.h>
   using namespace std;
   using llt=long long;
   using llf=long double;
   using ull=unsigned long long;
   #ifdef LOCAL
       FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/in.in","w",stdout);
   #else
       FILE *InFile=stdin,*OutFile=stdout;
   #endif
   
   mt19937 rnd(ull(new char)*ull(new char));
   
   int main(){
       ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
       cout<<10<<endl;
       for(int t=1;t<=10;++t){
           int k=rnd()%10+1;
           if(k<=2){
               int n=901+rnd()%100,k=999999901+rnd()%100; cout<<n<<' '<<k<<endl;
               for(int i=1;i<=n;++i){
                   if(rnd()%5==0) cout<<0<<' '; 
                   else cout<<int(rnd()%200000)-100000<<' '; 
               }cout<<endl;
           }else if(k<=4){
               int n=901+rnd()%100,k=999999901+rnd()%100; cout<<n<<' '<<k<<endl;
               cout<<1<<' '; for(int i=2;i<=n;++i) cout<<int(rnd()%200000)-100000<<' '; cout<<endl;
           }else if(k<=6){
               int n=10+rnd()%10,k=10+rnd()%10; cout<<n<<' '<<k<<endl;
               for(int i=1;i<=n;++i) cout<<int(rnd()%200000)-100000<<' '; cout<<endl;
           }else if(k<=8){
               int n=rnd()%1000+1,k=rnd()%1000000000+1; cout<<n<<' '<<k<<endl;
               for(int i=1;i<=n;++i) cout<<int(rnd()%200000)-100000<<' '; cout<<endl;
           }else{
               int n=rnd()%1000+1; cout<<n<<' '<<0<<endl;
               for(int i=1;i<=n;++i) cout<<int(rnd()%200000)-100000<<' '; cout<<endl;
           }
       }
   }
   

3. 大陸

   水題，建議改名：樹分塊前置。

   就是考慮維護子樹中沒有被選的，合并到父親上，如果 \(\ge B\) 就單開一個，以父節點為省會。

   最后的根直接歸到最后一個即可，可以證明其不超過 \(3B-1\)。

4. 排列

   逆天題。

   其實思路很簡單，就是直接維護 \(min\)，\(max\)，在子樹是否存在三元組，二元組中最大的最小和最小的最大。

   因為只有在不存在三元組時要維護二元組，直接子樹二分即可。

   代碼長，但還算好寫。