Codeforces Round #306 Div.2 題解 (A/B/C/E)

A. Two Substrings

判斷字符串是否包含不重疊的 "AB" 和 "BA"。暴力掃描四次：先找 AB 再找 BA，先找 BA 再找 AB，找到即標記為 '*' 防止重疊。O(n)。

B. Preparing Olympiad

n≤15 道題，選若干題使總難度 ∈ [l,r]，且最大最小難度差 ≥ x。DFS 枚舉選/不選，剪枝。2^15=32768 狀態，極快。

C. Divisibility by Eight

給數字串，刪除若干位使剩餘數能被 8 整除。性質：被 8 整除 ⇔ 最後三位被 8 整除。枚舉所有 1~3 位子序列（保持相對順序），檢查是否為 8 的倍數。預計算所有 1~3 位 8 的倍數（共 125 個），掃描匹配。

E. Brackets in Implications

邏輯蕴含 →：0→0=1, 0→1=1, 1→0=0, 1→1=1。給 0/1 序列，加括號使整式為 0。分析：結果為 0 ⇔ 最後一項為 0 且前綴能構造 1。不可能情況：序列為全 1 後接單 0，或倒數第二為 0 且前面全 1。構造輸出：(((a1→a2)→...→a_{n-2})→(a_{n-1}→0))。

代碼片段 (E)

if (a[n]==1) { puts("NO"); continue; }
bool allOne=true;
for (int i=1;i<=n-2;i++) if (a[i]!=1) { allOne=false; break; }
if (allOne && a[n-1]==0) { puts("NO"); continue; }
puts("YES");
for (int i=1;i<=n-2;i++) printf("(%d->", a[i]);
printf("%d", a[n-1]);
for (int i=1;i<=n-2;i++) printf(")");
printf("->0\n");

總結

CF #306 Div.2 題目涵蓋字符串、DFS枚舉、數論、邏輯構造。關鍵在於快速識別問題本質：A 為貪心掃描，B 為小規模 DFS，C 為 8 的倍數性質，E 為邏輯表達式括號化構造。D 題為構造題未補全。