A - mod M

題目鏈接

10年積累的網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶(hù)對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶(hù)得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站設(shè)計(jì)后付款的網(wǎng)站建設(shè)流程，更有石家莊免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

這道題我們可以首先對(duì)于所有的數(shù) \(\mod 2\) ，可以證明出答案最多不超過(guò) \(2\) ，此時(shí)我們就可以把問(wèn)題轉(zhuǎn)化為：是否存在一個(gè)數(shù)使得序列 \(a\) 中所有元素減去這個(gè)數(shù)之后的最大公因數(shù)大于\(1\)，就是一道妥妥的同余了。

A題代碼

B - dp

題目鏈接

這道題我們可不難想出\(O(n^3)\)的做法，即枚舉左端點(diǎn)和右端點(diǎn)，檢查這段區(qū)間的答案變換過(guò)后是否比當(dāng)前答案更小，如果是，則更新當(dāng)前答案。

然后就是優(yōu)化了，我們可以發(fā)現(xiàn)，從開(kāi)頭開(kāi)始，我們遇到的第一個(gè) \(p\)，是一定得被修改成 \(d\) ，這樣肯定是最優(yōu)選擇，那么我們就可以省略了枚舉左端點(diǎn)的步驟，此時(shí)時(shí)間復(fù)雜度為\(O(n^2)\)，足以通過(guò)此題。

B題代碼

C - Lights Out on Tree

題目鏈接

這道題我們首先有一些性質(zhì):

1.每個(gè)節(jié)點(diǎn)最多按一次

2.節(jié)點(diǎn)按下的先后順序沒(méi)有影響

依據(jù)這個(gè)性質(zhì)，我們可以得到：當(dāng)一個(gè)硬幣頭朝上時(shí)，要按下這個(gè)節(jié)點(diǎn)按鈕的最佳選擇是：

1.這個(gè)節(jié)點(diǎn)的父親是尾朝上

2.這個(gè)節(jié)點(diǎn)的子樹(shù)全是頭朝上

對(duì)于第一點(diǎn)，我們可以由性質(zhì)1證明出來(lái)，如果這個(gè)節(jié)點(diǎn)的父親是頭朝上，那我們就再等到他父親再繼續(xù)。

然后對(duì)于第二點(diǎn)，依據(jù)性質(zhì)2，我們可以假設(shè)如果一個(gè)節(jié)點(diǎn)在一開(kāi)始表明頭朝上了，我們遍歷到他的父親時(shí)，這個(gè)節(jié)點(diǎn)里的所有子樹(shù)都已經(jīng)頭朝上了(有點(diǎn)類(lèi)似于 動(dòng)態(tài)dp 的思路?)，反之，這個(gè)節(jié)點(diǎn)里所有子樹(shù)都已經(jīng)尾朝上，我們就需要按下這個(gè)節(jié)點(diǎn)的按鈕。

C題代碼