T1.
就是個隨機題目
告訴我們烤柿要大膽
所有點都是偶度數，直接構造歐拉回路，三個截一段輸出
然后有奇數點呢？
這里構出一種正確性很高的 trick
度數越小要求越嚴格，于是我們每次選出一個度數奇數中度數最小的點 \(a\)，先隨機找出一個與 \(a\) 有邊的點 \(b\)，再隨機找出一個與 \(b\) 有邊的點 \(c\)，之后找出一個與 \(c\) 有邊的點 \(d\)，這里要求點 \(d\) 度數最好為奇數，最后刪除邊 \(\{a,b\},\{b,c\},\{c,d\}\)。
找奇點直接暴力就行
T2
原 P13231 [GCJ 2015 #3] Log Set
發現 \(A\) 長度 log
這題先考慮都是正數
最小的一定是其中一個元素，然后掃一遍刪掉其貢獻
像這樣寫
for(int i = 1;i <= n;i++) {
a[i].y -= mp[a[i].x];
mp[a[i].x + c[k]] = a[i].y;
}
然后一直做就行
考慮有負數，我們自然還是想像這樣每次確定一個元素
我剛開始想從 \(0\) 向兩邊擴，發現找不到確定的值
然后這題有結論曰最大值減去次大值一定是某個元素的絕對值
自己想想就能明白
所以我們每次可以確定一個數的絕對值
由于加不加這個元素的集合兩兩對應，所以不管是正是負，都可以看做是兩個相同的集合刪去其中一個
我們直接當做正數
就算刪錯了，其內部的結構也不會變化，相當于是整體平移
這樣找到所有數的絕對值之后
我們再拋出一個結論
當所有正數的和等于初始冪集的最大值時，這個 A 集合就合法
證明我覺得也很簡單
根據找絕對值的過程，我們同樣可以逆序構造出他的冪集
自己畫幾個圖可以發現，不管是正是負，其內部的結構也不會變化，頂多是整體平移
而我們只需要固定其一個位置的數相同整個集合就是相同的
然后直接基于這個結論，我們就能 \(dp\) 出方案數，以及最小解
然后這個題就沒了，代碼超級好寫，我這個菜雞發現考場上打的部分分包括暴力和特殊性質幾乎包含所有正解的部分
拼一拼就過了
唯一卡了一個多小時的東西是這個( 招笑
"你猜我為什么 MLE"
sum = len = q = 0;
for(int i = 1;i <= q;i ++) f[i].clear();
T3
其實他們是一個題
先看前置
直接給出做法，分塊每個塊維護大根堆和小跟堆
大根堆維護內部元素，用于跳整塊
小跟堆維護標記，用于重構塊
發現如果操作覆蓋整塊，一定變成其最大值
散塊考慮第一個位置一定留下最小值，然后往后掃即可
復雜度 \(O(n \sqrt{n} \log n)\)
看區間 LIS
掃描線右端點
維護所有左端點的答案
有結論 \(f[l + 1][r]\subseteq f[l][r]\)
然后每個數貢獻的是一個前綴
考慮 LIS 經典貪心二分的過程，替換第一個大于她的數
我們維護值域序列，每個位置存她的貢獻區間
答案即為 \(num_{v \ge q_l}\)
加入一個數
所以我們依次考慮大于其的數，如果他的貢獻區間大于上一個的區間，就替換掉多出來的部分
操作等價于在值域 \([v , n]\) AT_joisc2016_h 回転壽司
然后將 \(v\) 修改為 i
用樹狀數組維護前綴加，單點查
復雜度 \(O(n \sqrt{n} \log n + q \log n)\)
卡常
-
每次加優先隊列，先判會不會操作，不進行無效操作
-
由于 \(t = n\) 所以不需要重構最后一段
-
不是環，不用取模
浙公網安備 33010602011771號