由于題面還沒出來,現在先口胡一下思路
填空題直接打表找規律或者亂搞一下就能出,從大題開始說。
1,題意:
給你一個數組,這個數組里有幾個數可以被一個連續遞增的數字區間求和得出
思路:詐騙題,顯然用[-(n-1),n]能構造出任何數。特判1。
2,題意:
給定,a,b,c,k,定義一次變換是同時進行a->(b+c)/2,b->(a+c)/2,c->(a+b)/2,問執行K次后a,b,c的值
打表發現執行次數一多三個數后面必然會不變,直接判如果三個數在一次操作后不變就輸出。
3,題意:
給定一個數組,從中取m個數并重新排列,使得這些數組成的新數組 a a a的| a i 2 ? a i ? 1 2 {a_i}^2-{a_{i-1}}^2 ai?2?ai?1?2|之和最小。
直接排序后雙指針掃一遍
4,有個2*n的網格,里面已經有一些網格是"#“,其它的是”.“,最少要把多少個”.“替換成”.“才能讓所有”#“聯通。
經典DP,首先找到一個最大的區間,使得區間的最左邊和最右邊都有”#“。定義DP數組:dp[1][i]:表示第i列第1行有”#“,dp[2][i]表示第i列第2行有”#“,dp[3][i]表示第i列第1,2行都有”#",直接根據這些狀態轉移即可
5,給定一棵樹,需要你去掉一些葉子節點,使得每個非葉子節點下面的葉子節點權值之和不大于它的權值,問最后節點1的葉子節點權值和為多少?
bitset優化樹上背包板子題,直接暴力的基礎上用bitset優化,本地測試跑滿大概200ms.
6,給定一個數組讓你在這些數中間填入加減和異或符號,所有可能的情況的計算值之和是多少。
觀察發現答案只和前綴異或和有關,預處理表示 3 n 3^n 3n的數組后直接算即可。
題目正式出來了再寫正式題解