\(\mathcal{Preface}\)

分數 \(90+100+100+30=320\)。

掛完了，嗚。

\(\mathcal{Problem \space{} A}\)

Tag：詐騙，循環。

減法可以出負數，我們希望最后的值最大，可以一開始用最小的值去減其他所有值，但是保留任意一個非最小值，最后用這任意一個非最小值去減最小值就可以了，一定是最大解。具體的，和是 \(a_2 + a_3 + \dots + a_{n-1} + a_n - a_1\)，其中 \(a_1\) 是最小的數。

取余考慮保留，由于數組中的數各不相同，所以必定存在一個唯一的最小值，拿這個最小值不斷去和其他值取余，最后也能保留下這個最小值，這一定是最大解。

因此兩個都只需要算 \(sum\) 總和以及 \(mn\) 最小值就可以解決了。

注意特判 \(n=1\) 的情況啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！賽時沒注意掛了 \(10\)pts。之后一定要注意看邊界的一些特殊情況！！！！！！1111

\(\mathcal{Problem \space{} B}\)

Tag：分討，貪心。

由于題目保證肯定可以在兩次以內搞定，因此不滿足回文串的位置最多也只有兩處，記為 \((d_1,n-d_1+1)\) 和 \((d_2,n-d_2+1)\) 兩對。如果只有一處，那么 \(d_2 = 0\)，\(d_1\) 存數；而一處都沒有的情況，即一開始就是回文串的話，\(d_1\) 和 \(d_2\) 當然就都不會存數了。

首先考慮一開始就是回文串的情況。顯然我們手里還有兩次操作，可以考慮將一些位置改成 a，優化字典序。從前往后找到這個位置對即可，至于為什么要去找，因為存在一開始就是 a 的，沒必要再浪費次數修改重復的。

接著考慮只有一個位置需要修改的情況。如果 \(d_1\) 和 \(n-d_1+1\) 這兩個位置中存在一個為 a 的，那么這里就只消耗了一個次數，還剩下一個次數怎么使用呢？只有當 \(n\) 是奇數的時候，我們可以考慮把最中間的那個，自己對自己的回文字符，改成 a；否則，這個次數就只能閑著啦。不過如果 \(d_1\) 和 \(n-d_1+1\) 兩個位置中不存在任何一個為 a 的，那么兩次就消耗完了，直接都改成 a 即可。

最后考慮有兩個位置需要修改的情況，這種很簡單，兩個對子中都要分別選擇一個字典序大的一端，把它的值改成那個較小字典序的字母，最后輸出就 OK 啦。

\(\mathcal{Problem \space{} C}\)

Tag：判斷質數，質數篩。

并不需要 DFS，雖然結構是棵樹。

只要對讀入的每條邊，判斷一下，如果這條邊連接的兩個點的點權加起來的值是質數，就讓 \(ans \to ans+1\)。考慮順序？不不不，只要定某個點為根，然后從葉子往上改就好了。

為了更快判斷質數，一開始寫個埃氏篩就行了，沒必要寫線性篩哦。

\(\mathcal{Problem \space{} D}\)

Tag：前綴和，枚舉，簡單思維。

考慮用 \(p_x\) 記錄 \(c\) 中最多可以有多少個數字 \(x\)，\(x\) 的范圍是 \(1 \sim 5 \times 10^6\)。\(x\) 是 \(0\) 的可以一開始算一下，就是 \(a\) 中 \(< 10^6\) 的數字的個數。

重點在于如何計算具體 \(p\) 值。

考慮枚舉 \(i\) 表示 \(b\) 中的值，然后枚舉 \(j\) 為 \(i\) 的倍數并記 \(x = \frac{j}{i}\)。在這里，\(i \le 10^6\) 且 \(j \le 5 \times 10^6\)。

那么這里就有一個區間 \([j,j+i-1]\)，表示在 \(b\) 值為 \(i\) 的情況下 \(a\) 中取哪個范圍才能得到 \(c\) 值為 \(x\)。將原 \(a\) 值塞進桶里求前綴和，維護在區間 \([j,j+i-1]\) 中有多少個滿足條件的 \(a\)，加進 \(p_x\) 里。

問題在于這種方法會重復計算，一個數可能除以多個數都等于某個數，這樣是行不通的，重復計算會導致數值錯誤。怎么辦呢？只要對于每個 \(x\) 都記錄一下上次 \(p_x\) 計算答案的時候的這個區間是多少，然后這次計算 \([j,j+i-1]\) 的時候判斷一下，不要累加重復部分就好啦。

代碼是很好寫的。

n=read();
for(int i=1;i<=n;i++)a[i]=read(),s[a[i]]++;
for(int i=1;i<=5000000;i++)s[i]+=s[i-1];
for(int i=1;i<=n;i++)Ans+=(a[i]<1000000);
for(int i=1;i<=1000000;i++){
    for(int j=i,x=1;j<=5000000;j+=i,x++){
        LL oL=h[x].fr,oR=h[x].se;
        LL nL=j,nR=min(j+i-1,5000000);
        if(oR<nL)p[x]+=s[nR]-s[nL-1];
        else if(oR<nR)p[x]+=s[nR]-s[oR];else;
        h[x]={nL,nR};
    }
}
for(int i=1;i<=5000000;i++)Ans=max(Ans,p[i]);
cout<<Ans<<"\n";

有一個 Hack，疑似能 Hack 死某些人的代碼，我這里貼出來。

Input：

10
7 14 28 4000001 4000002 4000003 4000004 4000005 4000006 4000007

Answer：

10

Possible output：

9

解釋一下，構造 \(b = \{ 1,2,4,571428,571428,571428,571428,571428,571428,571428\}\)，可以讓所有 \(c\) 值都為 \(7\)。

似乎可以 Hack 死某兩位大神的賽時代碼。

\(\mathcal{Summary}\)

T1 沒有考慮邊界情況，之后一定要注意了！！！！！！11111

T4 沒有想到正解，之后要多推導一下。思維要跳出來，不要卡在一個死胡同里。

希望今天下午成績可以好一點，嗚。