A - mod M
題目鏈接
這道題我們可以首先對于所有的數 $%2$ ，可以證明出答案最多不超過 $2$ ，此時我們就可以把問題轉化為：是否存在一個數使得序列 $a$ 中所有元素減去這個數之后的最大公因數大于$1$，就是一道妥妥的同余了，
A題代碼
B - dp
題目鏈接
這道題我們可不難想出$O(n^3)$的做法，即列舉左端點和右端點，檢查這段區間的答案變換過后是否比當前答案更小，如果是，則更新當前答案，
然后就是優化了，我們可以發現，從開頭開始，我們遇到的第一個 $p$，是一定得被修改成 $d$ ，這樣肯定是最優選擇，那么我們就可以省略了列舉左端點的步驟，此時時間復雜度為$O(n^2)$，足以通過此題，
B題代碼
C - Lights Out on Tree
題目鏈接
這道題我們首先有一些性質:
1.每個節點最多按一次
2.節點按下的先后順序沒有影響
依據這個性質，我們可以得到：當一個硬幣頭朝上時，要按下這個節點按鈕的最佳選擇是：
1.這個節點的父親是尾朝上
2.這個節點的子樹全是頭朝上
對于第一點，我們可以由性質1證明出來，如果這個節點的父親是頭朝上，那我們就再等到他父親再繼續，
然后對于第二點，依據性質2，我們可以假設如果一個節點在一開始表明頭朝上了，我們遍歷到他的父親時，這個節點里的所有子樹都已經頭朝上了(有點類似于 動態dp 的思路?)，反之，這個節點里所有子樹都已經尾朝上，我們就需要按下這個節點的按鈕，
C題代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/510986.html
標籤：其他