zhangxyhp

摘要： A B C D Sum Rank 100 100 15 25 240 6/21 A. flandre 數據過弱放過一批錯解。包括我的 正解：一個結論是選擇的序列一定是原數組排序后的一段后綴。具體的證明是，如果 \(a_i\) 互不相同那么可以將區間一直往右移，如果相同那么一定可以不斷插入進去，答案一 閱讀全文

摘要： A. The Bakery 設 \(dp_{i,j}\) 表示 \(i\) 為第 \(j\) 段的中點的最大價值，容易寫出轉移式：\(dp_{i,j}=\max_{k=0}^{i-1}\{dp_{k,j-1}+cost[k+1,i]\}\)。看到 \(\max\) 可以考慮線段樹優化 DP，因此我們 閱讀全文

摘要： A B C D Sum Rank 100 20 20 10 150 5/21 A. zzy 的金牌 設 \(f_{i,j,k}\) 表示考慮了前 \(i\) 個盒子，總共放了 \(j\) 塊金牌，其中在第 \(i\) 個盒子放了 \(k\) 塊金牌的方案數。考慮怎樣保證可重集數量的不重不漏，限定最后 閱讀全文

摘要： 考場唯一成果→ 閱讀全文

摘要： A B C D Sum Rank 50 20 60 8 138 10/21 A. 萬花筒 對于一條邊，假設 \(u<v\)，則會連出 \(\gcd(n,v-u)\) 個環。于是按照 kruskal 的思路，每一個環留一條邊不取即可。 Code #include<bits/stdc++.h> #def 閱讀全文

摘要： A B C D Sum Rank 50 17 - 20 87 5/21 A. 魔力屏障 區間 DP，設 \(f_{l,r,x}\) 表示擊破 \([l,r]\)，向右傳遞 \(x\) 的最小花費。轉移分為先擊破右區間再擊破左區間、用左區間的剩余擊破右區間兩種。（第二個轉移可以簡化為用 \([l,r- 閱讀全文

摘要： A B C D Sum Rank 100 - 30 10 140 6/20 今天使用了表格😜 A. 馬 新題的數據很水，可能有許多正確率較高的貪心能夠通過。 正解是 \(O(m^3)\) 的 DP，然而我寫的是 \(O(nm^3)\) 的（ 設 \(f_{i,x,y,z}\) 表示前 \(i\) 閱讀全文

摘要： 倒序放題嗎，有點意思🤪🤪💀💀😋😋💩💩 A. 環游(tour) 注意到我們最多可以跳 \(O(\log V)\) 次。考慮對于每一次的容量，求出若干連續的區間，于是我們要在每一層選一個區間來使這些區間的并為全集。 對除了最上面那一層之外的層進行狀壓 DP，維護 \(f_S\) 表示在 閱讀全文

摘要： A. 異或 \(r+l=n+1\) 的特殊性質提示一個做法：修改時只在頂點標記，用兩個矩陣分別記錄向下傳遞的數和向右下傳遞的數。于是一個小三角就等于一個大三角減掉一個小三角再減掉一個矩形。這兩個三角也都是到底的，可以用如上方法計算；矩形直接做差分即可。 Code #include<bits/stdc 閱讀全文

摘要： A. 返鄉 當所有 \(a+b+c\) 都相等時，顯然沒有偏序。使這個和為 \(\lfloor\frac{3\times n}{2}\rfloor\) 時，顯然是數量最多的。 然后實際上這就是最優構造，因為它顯然無法再往里加東西了。 Code #include<bits/stdc++.h> #def 閱讀全文