2019牛客暑期多校訓練營（第七場)

A. String

做法 比賽時預處理哪些子串是最小表示，然後 BFS 最短路。複雜度不是很合理，本地測試了下 300 組長度為 200 的 010101.... 串，嚴重 TLE，題目中資料範圍的描述可能存在不嚴謹之處。

B. Irreducible Polynomial

題意 判斷一個多項式能否分解成若幹個實系多項式。

做法 實系數多項式因式分解定理。多項式的非是根一定是共轭負數。

• 比賽時想了半天，發現這個東西不會做啊。
• RDC: 我們先求出所有根，再把這些根劃分成很多個集合。
• F0_0H: 大膽猜結論，雖然猜的沒一個對的。

C. Governing sand

做法 按高度分類，從小到大枚舉最大高度，比目前枚舉的高度 h 要高的，一定删，比它小的，如果删前 ? 小的。

E.Find the median

solved by F0_0H 194min -1

題意 每次插入\([l[i], r[i]]\),詢問中位數

做法

• 很奇怪，資料為什麼要這麼搞，很容易讓人想歪或者認為這是個強制線上題
• 離散化後權值線段樹上二分即可，比賽時因為沒考慮好邊界條件，智障了很久...

F.Energy stones

upsolved

題意 吃能量

做法 比賽中對着一個假做法自閉了很久，一直堅信其優美性和正确性

正解：

• 查詢離線，依次計算每個石頭對答案的貢獻
• \(set\)維護包含目前石頭的區間的\(ti\)
• 每次插入删除至多修改三個區間差，用樹狀數組維護即可
• 這種套路上次是在維護樹上聯通塊大小上

I. Chessboard

很精彩的一道題！

做法

• 設 \(A_i\) 為第 \(i\) 行全為 1，其它位置全為 0 的方陣。
• 設 \(B_j\) 為第 \(j\) 列全為 1，其它位置全為 0 的方陣。
• 一個 \(k\) 行 \(k\) 列，任取 \(k\) 個元素，每個元素不同行不同列的方陣，一定可以由 \(\{A_1,A_2,....,B_1,B_2.....\}\) 的生成的線性空間中。也就是 \(\sum_{i=1}^{k}a_iA_i+\sum_{j=1}^{k}b_jB_k\)
• 于是有 \(\sum_{i=1}^{k}a_i+\sum_{j=1}^{k}b_j \leq n\)
• 但很可惜，如上線性空間的基中隻有 \(2k-1\) 個向量，是以表出方式不唯一。
• 對于不同的表出方式，令 \(d=min_{i=1}^{k} a_i\) 做變換 \(a_i:=a_i-d\), \(b_i:=b_i+d\)，于是我們識破了本質相同的矩陣的不同表出方式。
• 對于一個确定的 \(k\)，答案為 \(\sum_{i=1}^{k}a_i+\sum_{j=1}^{k}b_j \leq n(存在 a_i=0)\)
• 枚舉 \(k\)，用 \(\sum_{i=1}^{k}a_i + \sum_{j=1}^{k}b_j\leq n, (a_i,b_j\geq0)\) 的解數，減去 \(\sum_{i=1}^{k}a_i + \sum_{j=1}^{k}b_j\leq n, (b_j\geq0, a_i\geq1)\) 的解數。即可，複雜度 \(O(n)\)

複盤

• 比賽時第一眼的想法：任選 \(k\) 個元素，之和相等，等價于任意子矩陣對角之和相等。建立線性方程組，第一行第一列的是主元，其它是自由元。
• 然後就沒有然後了。
• 把矩陣中的元素當成變量，不失為一種合理的想法，但隻有這個想法，就是視野狹窄了。
• 題解中的做法，把行和列當成了變量。
• 從行和列的角度考慮一個矩陣，這是常見的思路。

轉載于:https://www.cnblogs.com/FST-stay-night/p/11322585.html