咕了一周，終于寫出來了。

部分暴力代碼為自己的賽時代碼（因此可能十分丑陋），正解為官方代碼。

t1 前導(dǎo)零與回文

題意簡述：給出一個整數(shù)n，判斷能否在n前面添加多個0，使得n成為回文數(shù)。

數(shù)據(jù)范圍：0<n<

從數(shù)據(jù)范圍來看我們?nèi)菀紫氲接米址甇()暴力，作為長度僅僅只有10，遠(yuǎn)低于string類255的最高長度，于是我們?nèi)サ鬾末尾的0，判斷余下字符是否回文即可。

正解運(yùn)用了字符串自帶函數(shù)，這里不再贅述，思想和暴力算法一致。

暴力AC（熱愛壓行的我硬是把搞得看起來像n一樣）：

正解：

t2 矛盾的不等式

題意簡述：給出n個關(guān)于變量x的不等式，要求確定x的值，使得滿足條件的不等式最多，輸出最少的矛盾數(shù)量。

不等式中，Lv等價于xv，Gv等價于xv.

數(shù)據(jù)范圍：1<n<1000，1<vi<

輸入：第一行包含n。

以下n行每行包含字符L或G，之后是整數(shù)vi

從不等式的性質(zhì)判斷，如果所有可以滿足G的數(shù)字存在于集合G，所有可以滿足L的數(shù)字存在于集合L，那么最優(yōu)解一定存在于G或L的子集中。

枚舉這些數(shù)字，判斷最優(yōu)解即可，復(fù)雜度為O()，可得30分。

進(jìn)一步思考，預(yù)處理G和L，將其分別排序后二分出答案，復(fù)雜度降為O(nlog(n))，滿分。

40分算法（暴力+預(yù)處理，無二分）：

正解：

t3 獨(dú)特的顏色

題意簡述：給定一棵樹，其節(jié)點(diǎn)編號為1-N，第i條邊連接節(jié)點(diǎn)A[i]與B[i]，結(jié)點(diǎn)i的顏色為C[i]。如果根節(jié)點(diǎn)到節(jié)點(diǎn)x的最短路徑上不包含與節(jié)點(diǎn)x顏色相同的節(jié)點(diǎn)，我們就稱節(jié)點(diǎn)x為好點(diǎn)。按照升序輸出所有好點(diǎn)的編號。

輸入：第一行一個正整數(shù)N，表示節(jié)點(diǎn)數(shù)。

第二行N個正整數(shù)C[i]，表示每個節(jié)點(diǎn)的顏色。

下面N-1行，每行輸入兩個正整數(shù)A[i],B[i]，表示一條邊。

輸出：每行輸出一個好點(diǎn)的編號。

數(shù)據(jù)范圍：2N,1C[i]

一道放t3但是很水的題。雖然這是個最短路問題，但由于它在樹上，且數(shù)據(jù)范圍只有，我們可以直接用DFS搜索，然后開個較大的數(shù)組（用vector也行）暴力維護(hù)最短路上節(jié)點(diǎn)的顏色，對拍后發(fā)現(xiàn)這是可行的。

接下來的思路就很好想到了，從根節(jié)點(diǎn)開始DFS，同時開一個數(shù)組記錄路徑上所有點(diǎn)的顏色，遞歸就相加，回溯就相減。得到最短路后查找當(dāng)前點(diǎn)的顏色是否出現(xiàn)在路徑中，是則標(biāo)記為好點(diǎn)，否則標(biāo)記為非好點(diǎn)。

（說著容易寫起來難，我賽時這題從100掛到40，果然碼力還不足）

這題沒寫暴力，直接上正解：

注意，在使用這份代碼時，必須在Dev-c++編譯器的編譯選項中加入-std=c++11這行指令，否則會造成CE（auto變量的支持在c++11才出現(xiàn)）

（三中比賽開c++20，所以賽時不會有問題）

t4 集合相等

題意簡述：對于2個給出的只包含小寫字母a到r的字符串s,t進(jìn)行Q次詢問，每次詢問給出一個a到r的子字符集l。你需要按照順序取出s與t中所有由l包含字符組成的子序列s'與t'，并判斷得到的s'與t'是否相同。

輸入：第一行為s，第二行為t，第三行為Q。接下來Q行每行包含一個詢問字符串l。在一個詢問字符串里，所有字母均不相同。此外，所有詢問字符串均已排序。保證每個詢問字符串只出現(xiàn)一次。

輸出：對于每個詢問，輸出一個字符表示答案，s'和t'相同則輸出‘Y’，反之輸出‘N’，所有輸出在一行內(nèi)完成。

數(shù)據(jù)范圍：1<=Q,,<=

一開始對于這題我們可能毫無頭緒，但總之先寫個暴力再說。暴力思路非常容易，兩個字符串各自取出子集，然后比對即可。但這份代碼的時間復(fù)雜度達(dá)到了驚人的O(Q)，顯然對于的數(shù)據(jù)范圍是不可行的，于是我們看到了一大片紫荊花喜提20分。

接著我們觀察題面，發(fā)現(xiàn)了一個很奇怪的點(diǎn)：s與t都只包含了a到r的小寫字母。那么是不是可以猜想正解的時間復(fù)雜度與字符集大小有關(guān)呢？用萬能的計算器算一下，結(jié)果顯然驗證了我們的猜想，也就是說，正解的復(fù)雜度必然是O(n*k)（k為字符集大?。┑?，基于這個復(fù)雜度去考慮算法，思路就會開闊許多。

首先我們預(yù)處理單個字符的情況，顯然當(dāng)我們查詢某單個字符a時，只需要滿足s,t中這個字符的數(shù)量相等，結(jié)果就必然一致。

接著來看兩個字符的情況，這里我們就不能用到上述結(jié)論了，因為子集是否一致還受到這兩個字符的順序影響。這里沒有別的辦法，暴力比對即可。

而多個字符呢？能否用到上一個結(jié)論？答案是肯定的。通過記錄每個字符串中的字符數(shù)量我們可以得到以下結(jié)論：假使要查詢的字串為abc，我們枚舉它任意兩個字符的組合ab,ac,bc，如果查詢這些組合所得到的子串都一致，那么查詢字符串a(chǎn)bc所得到的子串也必然一致。

有了這個結(jié)論之后，對于任意查詢序列，我們都可以通過查詢它任意兩個字符的組合進(jìn)行判斷，時間復(fù)雜度為O(n*k)

我不認(rèn)為你們想看但還是放上來的20分暴力：

正解：

完結(jié)，慶賀我的第一篇題解，讓我們?nèi)鲆话衙袔烀赘ダ敔査_耶努巴希爾特國特產(chǎn)的名叫路絲忒可杜雷姆松利森弗諾維坦的花！

有問題可發(fā)在評論區(qū)，會盡可能解答。