「比賽題解」AtCoder Regular Contest 126

比賽連結

開了把vp，C降智導緻浪費大量時間/dk/dk

A

貪心，幾種湊 \(10\) 的方案的優先度是：\((3,3,4),(3,3,2,2),(4,4,2),(2,2,2,2,2),(4,2,2,2)\)

ll a, b, c, ans;
void solve() {
	read(a); read(b); read(c);
	ll sum = 0;
	ll t1 = Min(b/2, c+a/2);
	sum = t1;
	if(t1 > c) t1 -= c, c = 0, a -= 2 * t1;
	else c -= t1;
	ll t2 = Min(c/2, a);
	a -= t2;
	printf("%lld\n", sum + t2 + a/5 + (a % 5 >= 3 && c % 2 == 1));
}
           

B

設 \(f_i\) 為 \(([i,n],1)\) 一條線段也沒挂的最大挂繩子數。

按順序枚舉每一個繩子，然後用線段樹快速轉移這個 dp 即可。

Code

C

把 \(k\) 能夠把所有的 \(A\) 都添到 \(\max A\) 的情況特判掉，這樣答案隻可能 \(\leq \max A\)．

開個桶，用字首和維護值域上的 \(A\) 的個數，\(A\) 的和，枚舉每一個可能的答案 \(x\)，然後枚舉 \(x\) 的倍數，可以快速統計所需的最小代價。複雜度是調和級數的。

D

狀壓dp + 費用提前計算。

從前往後枚舉 \(i\)，設 \(f_S\) 為考慮集合 \(S\) 已經連在一起且排好序的代價，并且包括提前計算的費用，這裡提前計算的費用是使得有一個數想加進來的時候之間按照插排的規則插入進來，走到這個段之前的代價已經在 \(f\) 裡面算進去了。

這個提前計算的費用為多少？對于一個位置 \(i\) 如果不是最終的遞增段，而是一個路人，那麼遞增段要經過它并且湊齊的最小代價是遞增段在它左邊多少和在它右邊多少取個 \(\min\)，也就是 \(\min(pop\_count(S),k-pop\_count(S))\)。

形象地：

\(o...o...o..\Delta..o...o...o..o\)

假如 \(\Delta\) 是目前枚舉到的 \(i\)，而 \(o\) 是最終要拼成連續段的位置，那麼要不然左邊所有的 \(o\) 越過 \(\Delta\)，要不然右邊所有的 \(o\) 越過 \(\Delta\)，那麼 \(\Delta\) 處需要提前計算的費用就是兩邊 \(o\) 的個數取 \(\min\)．

E

F