題目簡(jiǎn)述

? ? ? ? Problem A1 / A2：給定一個(gè)長(zhǎng)度為的只含字母'a'和字母'b'的字符串，判斷能否按順序劃分成非空的三個(gè)子串，使得的在字典序意義下，要么同時(shí)不比大，要么同時(shí)不比小。

????????Problem B：給定一個(gè)長(zhǎng)度為的序列。判斷能否將劃分成兩個(gè)不同（指所取的下標(biāo)不同）的非空子序列和，使得子序列中元素按位或的結(jié)果相等。

????????Problem C：給定，解方程

????????其中。如果解存在，要求給出最小的解。

????????Problem D：給定一個(gè)長(zhǎng)度為的數(shù)組。如果與不互質(zhì)，則在之間連一條邊。給定起點(diǎn)和終點(diǎn)，求最短路徑，要求輸出其中一種行走方案。

????????原題目地址：https://codeforces.com/contest/1775

思路

????????Problem A1 / A2：一個(gè)小小的分類(lèi)討論題目，不想多說(shuō)，詳見(jiàn)代碼。

????????Problem B：按位或操作相當(dāng)于集合取并集。要想兩個(gè)子序列不同，最簡(jiǎn)單的制造不一致的方法是選擇一個(gè)被和公共部分代表的集合包含的元素，使得不含但包含。如果連這種最簡(jiǎn)單的情形都無(wú)法成立，則無(wú)解。

????????因此只需要依次判斷每個(gè)元素的各個(gè)二進(jìn)制位是否獨(dú)自瀟灑（我是指是不是只有它在這一位上為）。對(duì)于元素，一旦存在這么一個(gè)瀟灑的二進(jìn)制位，意味著它不可能被其它任何元素組代表的集合組的并集所包含。反之，把其它元素全選上，再利用就可以按前述策略制造不一致。用一個(gè)桶記錄一下各個(gè)位上出現(xiàn)的個(gè)數(shù)，可以輕松完成判斷，復(fù)雜度為，其中表示的二進(jìn)制位中的數(shù)目。

????????后話(huà)：雖然非常淺顯，但是可以硬來(lái)證明一下最開(kāi)始提到的情形確實(shí)是“最簡(jiǎn)單的情形”，我將直接使用用集合的語(yǔ)言來(lái)說(shuō)明。這個(gè)“最簡(jiǎn)單”是指所有可行的集合序列，均存在對(duì)應(yīng)的集合和某個(gè)下標(biāo)序列，使得：

????????開(kāi)證。因?yàn)榧闲蛄?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=c" alt="c">可行，因此存在下標(biāo)序列：

????????由于，因此存在，使得：

????? ? 令，這就完成了證明。

????????Problem C：按位與操作相當(dāng)于集合取交集，所以伴隨，左式會(huì)越來(lái)越小。在這一長(zhǎng)串連續(xù)按位之中，左式是以何種方式變小呢？例如：

????????我們驚訝的發(fā)現(xiàn)，和按位與一下并不會(huì)影響結(jié)果，因?yàn)槌俗畹臀?，二者完全一致，而最低位已?jīng)是了，無(wú)法被按位與改變。而：

????????一旦它參與進(jìn)來(lái)，連續(xù)的三個(gè)將無(wú)一幸免永遠(yuǎn)變成。事實(shí)上，這一規(guī)律具有普適性。即對(duì)于任意位置的連續(xù)，當(dāng)且僅當(dāng)在達(dá)到在這些連續(xù)的位置恰好變成了，且連續(xù)的最高位再高一位由變成時(shí)，才會(huì)將這一段連續(xù)一并永久變?yōu)?/strong>。

????????于是，可能的關(guān)鍵節(jié)點(diǎn)不超過(guò)個(gè)（當(dāng)然，其實(shí)只有這個(gè)數(shù)的一半左右）。因此我們可以枚舉的二進(jìn)制表示中所有連續(xù)片段，計(jì)算其對(duì)應(yīng)的節(jié)點(diǎn)，以及按位與的最終結(jié)果。這里不詳述計(jì)算方案，最后的復(fù)雜度是。

????????Problem D：原始的圖太大了，沒(méi)有辦法直接建圖再跑BFS。但是節(jié)點(diǎn)是以互質(zhì)關(guān)系來(lái)確定連接的，因此我們可以考慮從質(zhì)因子出發(fā)做文章。和如果不直接相連，說(shuō)明它們沒(méi)用公共質(zhì)因子（也就是互質(zhì)了）。如何讓它們連起來(lái)呢？需要找到一些中介?？紤]一階的情形，比如和有公共質(zhì)因子，和有公共質(zhì)因子，這就把和連上了。有了這一思考的基礎(chǔ)，我們?yōu)槭裁匆詳?shù)組元素為節(jié)點(diǎn)建圖呢？

????????直接以質(zhì)因子為節(jié)點(diǎn)建圖，這樣每一個(gè)數(shù)組元素意味著若干個(gè)質(zhì)因子之間的連接關(guān)系。這樣邊就表示“從包含某個(gè)質(zhì)因子的數(shù)出發(fā)，經(jīng)過(guò)邊所代表的數(shù)組元素，可以與另一個(gè)包含質(zhì)因子的數(shù)相連”。每個(gè)數(shù)組元素至多產(chǎn)生條邊（雙向邊存成兩條有向邊），這樣新圖僅包含約個(gè)節(jié)點(diǎn)和條邊，直接使用BFS求最短路，復(fù)雜度為。當(dāng)然，需要一些瑣碎的操作記錄一條最短路徑。

后記

????????代碼的github地址：https://github.com/cnzzx/AlgorithmCompetitions。