- https://atcoder.jp/contests/arc128/tasks
- https://www.bilibili.com/read/cv13612020
- https://www.cnblogs.com/stinger/p/15416806.html
arc 好難。。。（雖然題面都很簡單）
A Gold and Silver
著名的套利系列問題，但是這個題應該是裡面最簡單的一類，可以貪心，
掃一遍就行了。
B Balls of Three Colors
討論一下最後保留哪個，然後就很容易了。
C Max Dot
先不考慮 𝑚 的限制。。。
考慮 n=2 的情況，如果 a1 < a2 的情況，顯然資源全部都給 a2，否則只能對半分。
考慮 n 個數的情況，一定是 0 0 x x x x 這種 pattern，均分給一個後綴。
題解用的是調整法，也不難用歸納法證明，我們可以把後面的後綴合併起來看成是一個數，權值用平均值代替，
然後沿用 n=2 的方法即可。
我們枚舉後綴，得到的 x 有可能不滿足 m 的限制。
這個時候我們只要先把這些後綴填上 m，然後就可以遞歸到更短且 s 更小的問題。
這樣直接做是 O(n2) 的，可以構造一個 a 遞增的序列就可以弄出最壞複雜度。。
不過已經足夠通過本題。。。然後題解最後還說仔細觀察這個過程可以用凸包優化到 O(n)，
（。。我猜是斜率 DP？。。。沒能寫出來。。）
const int N = int(5e3) + 9;
int n,m,s;
int a[N];
DB gao(int n, DB m, DB s) {
vector<pair<DB,int>> avg; DB ss = 0;
DWN(i, n, 0) {
ss += a[i];
avg.PB({ss / (n-i), i});
}
int t = max_element(ALL(avg))->se;
DB x = s / (n-t);
if (x <= m) {
DB z = 0;
FOR(i, t, n) z += x * a[i];
return z;
} else {
DB z = 0;
FOR(i, t, n) z += m * a[i];
return z + gao(t, m, s-(n-t)*m);
}
}
int main(){
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n,m,s); REP(i,n)RD(a[i]);
OT(gao(n,m,s));
}
D Neq Neq
看起來有點像 spoj zuma 那個題。。。不過轉移感覺不是很好想。。
首先如果是 x,y,x,y,x … 這樣的交錯序列，答案就是斐波那契數列，一旦合併之後狀態就會被分割。
那麼用類似 上次那個題 的方法，可以用 x,x 將狀態分割成獨立的子問題，最後答案用乘法原理乘起來即可。
考慮不存在相鄰元素相等的子問題，考察某個區間能否把中間的元素全部合併掉，
判定的條件是，長度 <= 3 或者這個區間有 3 種不同的元素，因為相鄰的元素不同，總是可以用第三種元素作為支點反覆消，不難用歸納法證明。
設 f[i] 表示以 i 元素結尾的方案數，有了上面的結論，就可以得到轉移方程，大概就是斐波那契關係之上再加點東西，
f[i] = f[i-1] + f[i-2] + pre，其中 pre 是所有符合上述判定的前綴和，注意別和長度 <= 3 的算重複了。
用類似 小z的襪子 里的方法維護區間不同元素的數目即可。
實現的時候，可以設置哨兵 f[0] = f[1], f[n+1] = f[n] 以簡化代碼。
const int N = int(2e5) + 9;
Int f[N]; int a[N], c[N], cn;
int n;
void add(int x) {
x = a[x];
if (!c[x]) ++cn;
c[x] += 1;
}
void dec(int x) {
x = a[x];
c[x] -= 1;
if (!c[x]) --cn;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n); REP_1(i, n) RD(a[i]);
f[0] = 1; f[1] = 1; a[0] = a[1]; a[n+1] = a[n]; ++n;
Int z = 1, pre = 0;
int l = 1; REP_1(i, n) {
if (a[i] == a[i-1]) {
z *= f[i-1]; f[i-1] = 0; f[i] = 1;
while (l < i) dec(l++); add(i); pre = 0;
} else {
add(i); while (cn > 2 && l < i-2) pre += f[l], dec(l++);
f[i] = f[i-1] + f[i-2] + pre;
}
}
cout << z << endl;
}
E K Different Values
直接 dfs 顯然不行，考慮構造。。。
(1 hour later … )
呃。。。好吧，我覺得這個題還是挺難的。囧。。完全沒看懂 題解。。。
但是 標程 到是挺容易麗潔的。。。
我們先考慮 k|n 的情況，那麼可以分成 n/k 組，我們嘗試貪心構造，每次儘可能放最小的，但是放到後面有可能需要回溯。。。
看來我們需要想一種貪心構造，使得問題的規模不斷減小，並且最好不會出現回溯。。
設 n = dk + r，(r > 0)，首先如果存在 Ai > (d+1) 或者有超過 r 組 == (d+1) 那麼顯然無解 (a)，
否則，如果恰好有超過 r 組 == d+1，那麼從這 r 組裡選最小的 (1)，否則選全局最小的 (2)，添加到隊首，
當然選出的數要保證與上次出現的距離至少為 k，然後遞歸到 n-1 即可。
上面的過程顯然保證字典序最小，我們只要證明這個演算法一定能終止即可。。
考慮反證法 + 歸納法。。
首先如果第一輪沒有出現無解的情況，那麼後面的輪次也都不會出現。。否則前面輪次的 (1) 就已經取走了。
再考慮如果某個輪次沒有取到數，那麼前 k 輪次時也一定沒有取到數，但是 <= k 輪次時一定可以取到數，
因此取不到數的情況也不存在。
F Game against Robot
非常贊的組合計數題。有早年 SRM Div1 1000 的感覺了。。。。
首先考慮靜態的問題，然後類似 linearity of expectation，我們設法求出每個 Ai 在結果中出現的次數。
我們只關注排列中每個元素和 Ai 的大小關係，這樣只需要考察 01 序列，最後對貢獻乘以 i!(n-i)! 即可。
進一步考察靜態過程，我們可以計數得到所有大於等於 Ai 的數在答案中的出現次數，類似那個證明 Catalan 數等於 \binom{2n,n} – \binom{2n, n+1} 的過程，最後預處理二項式係數的和即可。
具體得看 lyric 的代碼。
