Gym103371(XXII Open Cup. Grand Prix of Korea)

​

A. Automatic Sprayer 2

隻能膜拜孔外公，換我肯定找不全方程。

設每一行的和為 \(R_i\)，每一列的和為 \(C_i\)，那麼有：

\[E_{x,y} = \sum_{i=1}^{n}|x-i|R_i+ \sum_{j=1}^{n} |y-j|C_j \]

考慮二次差分，會發現：

\[C_j=((E_{i,j+1}-E_{i,j})-(E_{i,j}-E_{i,j-1}))/2\]

\(R_i\) 同理，那麼我們隻差 \(R_1,R_n,C_1,C_n\)，沒有求出來。

然後再通過 \(E_{x,y}\) 的定義列方程：

\[R_1+C_1=(E_{n,n}-\sum_{x=2}^{n-1}(n-x)R_x-\sum_{y=2}^{n-1}(n-y)C_y)/(n-1)\]

可以繼續列出 \(R_1,C_n\)，\(R_n,C_1\)，然後發現第四個其實可以通過前三個推出來 (是否等價其實就看未知數，第四個方程的未知數完全可以用前三個組合出來，是以是線性相關的)，是以我們還缺一個方程。然後加上很容易被忽略的 “行之和等于列之和” 即可搞出新的未知數組合。

構造出行之和與列之和以後直接貪心即可。

for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) 
a[i][j]=min(r[i],c[j]),r[i]-=a[i][j],c[j]-=a[i][j];
      

隻要行之和=列之和這樣的構造就是合法的，因為如果有在某一行填完的時候這一行的 \(r_i\) 還有剩餘，那麼說明前 \(i\) 行的和大于列總和，沖突。

C. Equivalent Pipelines

兩個樹相同，當且僅當從大到小加邊（邊權相同的一起加），每次合并的點集都相同。

可以用哈希，每次合并的權值就是兩邊點集權值和的乘積再乘上邊權。每次合并權值都相等就行。

E. Goose Coins

先講一下我場上的 \(dp\)：

考慮 \(p\) 的貪心分解：即記 \(a_i=(p \% c_{i+1})/c_i\)，如果有解一定有 \(\sum a \leq k\)

設 \(f_{i,j}\) 表示搞出一個 \(c_i\) 用 \(j\) 個硬币的最大/最小代價，可以做一個背包，最壞複雜度為 \(O(k^3log_{1000}V)\)

然後直接用貪心分解再跑一個背包，複雜度 \(O(k^3)\)，可以通過。

下面是 \(nk^2\) 的做法：

\(f_{i,j,k}\) 表示從後往前到 \(i\)，填了 \(j\) 個，目前剩餘 \(rest/c_i=k\) 。這樣是 \(nk^3\) 的，但是發現 \(i,j,k\) 和 \(i,j-c_i/c_{i-1},k+1\) 往下貢獻的位置都是相同的，是以處理一個字尾 \(min/max\) 即可。

F. Hedgehog Graph

有點難，隻講一下 \(2 \sqrt V + logV\) 的做法吧：對于所有 \(i \in [1,\sqrt V]\)，詢問 \((s,i)\) 和 \((s,\sqrt V i)\)，發現任意一個 \([1,V]\) 的數都可以表示成兩個數之差，是以一定能找到相同點。

找到環長的倍數以後試除每個因子即可。

G. Lamb's Respite

拆成三段，即使初始血量不等于 \(H\) 也可以看成 \(H\) 然後加上一個 \(-x\) 。

直接維護區間的最小子段和，最小字尾和，最小字尾和是最後一個頂到 \(H\) 的位置，最小子段和是最容易觸底的地方。

如果不是鎖血的話，那麼處理出最小子段和的終止節點，後面任意字首和一定 \(>0\) ，隻要考慮上界即可。

H. Or Machine

簽到題。對于每一個二進制位考慮，其實就是一個對于操作時間跑最短路。

J. Periodic Ruler

簽到題。首先把每一對的因子幹掉，然後再對于 \(1 \sim n\) 把不同餘數拍到一起看看是否必然有更小周期。

K. Three Competitions

孔外公的做法：

對于每個點求出它的直接出邊的度數。

很顯然這是一個競賽圖，對于競賽圖有一個性質就是可以通過出度得到 \(scc\) 。

具體地，對于度數排序，在縮點後的圖中後面點的出度一定大于前面的出度，是以 \(scc\) 一定是一個區間。

從後往前搞，去掉最後一個環必須要滿足剩下的點滿足總出度 = \(\frac{n(n-1)}{2}\)。從後往前掃一遍即可。

複雜度 \(O(nlog^2n)\) 或 \(O(nlogn)\) ，取決于三維偏序的實作複雜度。

MYY 的做法：

有一種非常神仙的 \(scc\) 求法，即直接暴力 \(dfs\)，然後記下出棧序列。

然後對于出棧序列從後往前掃，在反圖上再暴力 \(dfs\)，找到的點就同屬于一個 \(scc\)。

問題在于怎麼找出邊，相當于分成 3 個圖，每個圖就是一個平面每次要找到一個在這個點左下的點。

對于第一維建立線段樹，維護在第一維 \([l,r]\) 區間中第二維的最小值，然後就可以删了（為啥我隻能想到樹套樹。。）