CSP-S模擬35
什么逆天題。
唉呀呀
卸載簽免：
話
r摘要，什么**題啊都是， \(T1\) 一點都不顯然， \(T2\) 也是一點都不顯然，賽時想到了一些但是不會寫， \(T3\) 更是不顯然的本質不同的 \(border\) 數量， \(T4\) 也是逆天柿子們，反正就是偏離 \(CSP\) 就是了。
還有就是今天下午的歌也是非常之不好聽也，像我爸喝多了唱的。
圖
另一組圖（不是斗羅大陸?。。。?/summary>
駭
T1 集合——"春風若有憐花意，可否許我再少年。"
喂喂，誰來可憐可憐我?。。?/s>
題目描述：
不粘了自己想象。
樣例一：
輸入：
5 5
1 2
2 3
1 4
4 5
2
3
2
2
4
輸出：
3 2 2 3 2
樣例二：
輸入：
10 10
1 2
2 3
1 4
2 5
2 6
6 7
6 8
2 9
1 10
6
3
6
9
8
4
6
3
8
7
輸出：
3 3 1 3 3 3 3 2 3 3
Solve：
首先根據題目文件名，可以想到使用 \(set\) 維護，但是正常的維護是平凡的，只有 \(20pts\) ，于是我們手腕陽歷，下圖每個節點上的數字們表示按順序合并后每個節點的“盟友集合”中的元素：
然后我們反著玩一下樣例（這里的“第一次”實際上是輸入樣例的第五次，以此類推）：
我們驚奇地發現這下面的數字對應著前面那張圖每個元素屬于的集合編號，比如節點 \(①\) 是屬于集合 \(1,4,5\) 的，然后就可以使用 \(bitset\) 反著創優化，如果人聰明常數小，就可以 \(AC\)。
但是為什么？這一點都不顯然，我沒有那么神秘的注意力，我也不是萬能遙控器，對不上腦電波………
于是我們想辦法使結論顯然化：
·最初，每個元素都只會存在于與其編號相同的集合；
·第一次合并時，元素 \(2\) 會存在于集合二和集合三中，元素 \(3\) 會存在于集合三和集合二中，我們直接無腦加上就好；
·第二次合并時，元素 \(1\) 會存在于集合一和集合四中，元素 \(4\) 會存在于集合四和集合一中，我們還是直接無腦加上就好；
·第三次合并時，駭，跟第一次一樣，于是什么影響都不會有，跳過；
·第四次合并時， \(How~~old~~are~~you~?\) （怎么老是你？），同上；
·第五次合并時，如果平凡地無腦加，那么元素 \(4\) 會存在于集合四、集合一和集合五中，元素 \(5\) 會存在于集合五、集合四和集合一中（?）我腦子壞了罷，很顯然元素 \(5\) 不會出現在集合一中，并且元素 \(1\) 在此時應該被更新為也存在于集合五中口牙，這樣的話就很難搞了，我們曾經的操作對后面的操作可能產生影響，可能會亂七八糟判一堆然后假假假假假假假，但是后面的操作不會改變曾經的操作，我們直接反著來就會發現沒有這個逆天后效性（肝硬化自己發明的說法）了。
這可能就是 \(OI\) 神犇 \(0.1~ms\) （沒那么久!）就能發現的顯然了，嚴謹的證明可能要看魚魚的博客（update at 25.10.20 21:34：我*了啊 \(TA\) 博客里啥也沒證）。
我們有了從后往前的思路，還需要考慮一件事情：不同時刻對同一條邊進行操作時，我們肯定不能直接無腦加（萬一這次的操作與上次操作的集合有交那不是壞了嗎），于是我們高一選手（高二也是不能忘記了的吧）通過 \(whk\) 數學可得： \(|S\cup T| = |S| + |T| - |S\cap T|\) ，且對于同一條邊的兩次操作，前一次操作的集合并恰好是后一次操作前的集合交，于是單開個數組記錄一下就好，代碼比暴力還好寫qwq。
Code：
#include <bits/stdc++.h>
using namespace std;
const int _ = 400010;
int n, m, a[_], b[_], x[_], ans[_], h, bfr[_];
bool lian[_];
inline int r(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}return x*f;}
inline void w(int x){if(x<0)x*=-1,putchar('-');if(x>9)w(x/10);putchar(x%10+'0');return;}
int main(){
freopen("set.in", "r", stdin);
freopen("set.out", "w", stdout);
n = r(), m = r();
for(int i = 1; i < n; i ++){
a[i] = r(), b[i] = r();
ans[i] = 1;
}
ans[n] = 1;
for(int i = 1; i <= m; i ++){
x[i] = r();
}
for(int i = m; i; i --){
h = x[i];
if(! lian[h]){
ans[a[h]] += ans[b[h]];
ans[b[h]] = ans[a[h]];
bfr[h] = ans[a[h]];
lian[h] = 1;
}
else{
ans[a[h]] += ans[b[h]] - bfr[h];
ans[b[h]] = ans[a[h]];
bfr[h] = ans[a[h]];
}
}
for(int i = 1; i <= n; i ++){
w(ans[i]);
putchar(' ');
}
return 0;
}
死
T2 存錢
我也想環游世界。
題目描述：
依舊自己 \(yy\) 。
樣例：
輸入：
2
3 5 2
2 3 4
6 10 4
2 3 4 5 6 7
輸出：
8
16
Solve：
先說賽時罷：
花了 \(inf~~minutes\) 發現樣例第二組數據投放·方案的不唯一性，（這其實啟發我們可以把最小的隨便給扔到邊上但是它沒注意到）；
·又花了 \(1~ms\) 發現當 \(k = n - 1\) 時，兩種錢拼成的長度為 \(m + 1\) 顯然更優,并且肝硬化一通亂搞發現當 \(k\) 為 \(n - 2\) 的時候相當于跑兩遍 \(n - 1\) ；
但是它什么沒想到其他的有助于 \(AC\) 題目的東西；
然后觀察樣例想到一個逆天假做法就是給輸入的東西排個序，每次放當前最短的和最長的，一直放放放放到厭倦，然后自己不相信（幸好沒信）給自己又造了一組小樣例發現比瞎放還劣，同時意識到當一種錢的數目 \(>m\) 時可以完全不管，并且答案與其取 \(max\) ，然后意識到答案很有可能是不知道幾倍的 \((m + 1)\) 減一堆不知道什么的東西 ，之后有想到每次取與前一次錢數量的和最接近 \(m + 1\) 的顯然更優，然后就不會實現了（因為柿子只推出一半），罰坐后遺憾離場。
正解：
首先扔掉大于 \(m\) 的 \(a_i\) ，先考慮 \(k = n - 1\) ，如果我們上一個放置的區間的起點在 \(x\) ，現在要放一個長度為 \(y\) 的區間。顯然，這個區間的起點應該至少為 \((x + m ? 1) ? y + 1 + 1 = x + m + 1 ? y\) 。我們肯定每次會盡可能往前放置區間。所以總長度應該是 \(∑^n_{i=2}(m + 1 ? a_i) + a_n\) ，也
就是 \(m + 1 +∑^{n?1}_{i=2}(m + 1 ? a_i)\)，可以將最小的兩個數放在 \(1\) 和 \(n\) 。排序一下就可以算出最小答案了（別忘了與最大的 \(a_i\) 取 \(max\)）。
然后考慮 \(k = n ? 2\) 。我們將它拆成兩個 \(k = n ? 1\) ，即將 \(a\) 劃分為兩個部分，分別跑一遍，最后將兩個答案取 \(max\) 。這樣做一定是正確的，因為兩部分每個部分都最多只完全包含一種錢幣。
首先扔掉長度最小的四個區間，它們一定會被放在首尾無貢獻。那我們假設全集是 \(U\) ，將區間劃分為集合 \(S\) 和集合 \(U ? S\)，令 \(cha_i = m + 1 ? a_i\) ，那么答案就是 \(m+1+max(∑_{x∈S}cha_x,∑_{x∈U/S}cha_x)\) 。
于是我們可以使用 \(bitset\) 優化 \(0/1\) 背包 \(+\) 隨機化大法創過去。
沸羊羊你太粗魯了?。?！
考慮將 \(cha\) 從小到大排序，找到最后一個位置 \(p\) 使得 \(∑^p_{i=1}cha_i ≤ \frac{sum}{2}\) 。
先選上所有 \(p\) 之前的元素，此時的總和與 \(\frac{sum}{2}\) 差值不超過 \(m\)。
如果我們此時進行調整，在總和比 \(\frac{sum}{2}\) 大時去掉 \(p\) 之前選的某個值，在總和比
\(\frac{sum}{2}\) 小的時候加入 \(p\) 之后的某個值，那么我們調整過程中出現的值與 \(\frac{sum}{2}\) 差值都不會超過 \(m\)。
我們從 \(p\) 到 \(n\) 進行調整，加入當前的值或者刪除 \(p\) 之前的值。
考慮一個 \(DP\)，設 \(f_{i,j}\) 表示調整到 \(i\) ，要想湊出來 \(j +\frac{sum}{2}\) ，左端點位置的最小值（也就是刪除的數都在 \(f_i,j\) 右邊）。沒有就是 \(0\) 。因為 \(?m ≤ j ≤ m\) 。轉移枚舉當前值是否加入，在考慮 \(p\) 左側
新增的能刪值是否刪除?？梢詽L動數組。由于每個數在每個 \(j\) 下只會被考慮一次是否加入刪除，所以時間復雜度 \(O(nm)\)，人聰明常數小。
實現上，下標肯定不能是負的（大蛇愛用用 \(map\) 當我沒說），需要將數組下標整體加上 \(10000\) （數據范圍是一萬）。
code：
#include<bits/stdc++.h>
using namespace std;
const int _ = 20010;
int t, n, m, tot, k, x, y, mx, a[_], b[_], cha[_], f[_], g[_], as, ans, all;
signed main(){
freopen("money.in", "r", stdin);
freopen("money.out", "w", stdout);
scanf("%d", & t);
while(t --){
all = as = ans = 0;
for(int i = 0; i <= 20000; i ++){
f[i] = g[i] = 0;
}
scanf("%d%d%d", & n, & m, & k);
tot = 0;
bool yes = (k == n - 1);
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
sort(a + 1, a + 1 + n);
mx = a[n];
if(a[1] > m){
printf("%d\n", mx);
continue;
}
n = lower_bound(a + 1, a + n + 1, m + 1) - a - 1;
if(yes){
ans = m + 1;
for(int i = 3; i <= n; i ++){
ans += m + 1 - a[i];
}
printf("%d\n", max(ans, mx));
continue;
}
if(n <= 2){
printf("%d\n", mx);
continue;
}
if(n <= 4){
printf("%d\n", max(mx, m + 1));
continue;
}
for(int i = 5; i <= n; i ++){
cha[++ tot] = m + 1 - a[i];
}
n = tot;
sort(cha + 1, cha + 1 + n);
for(int i = 1; i <= n; i ++){
all += cha[i];
}
int p = 1, sum = 0;
for(; p <= n && sum + cha[p] <= (all >> 1); p ++){
sum += cha[p];
}
g[sum - (all >> 1) + 10000] = p;
for(int i = p; i <= n; i ++){
for(int j = 0; j <= 20000; j ++){
f[j] = g[j];
}
for(int j = 0; j <= 9999; j ++){
f[j + cha[i]] = max(f[j + cha[i]],g[j]);
}
for(int j = (10000 << 1); j >= 10001; j --){
for(int tot = g[j]; tot < f[j]; tot ++){
f[j - cha[tot]] = max(f[j - cha[tot]], tot);
}
}
for(int j = 0; j <= 20000; j ++){
g[j] = f[j];
}
}
for(int i = 10000; i >= 0; i --){
if(f[i]){
as = (all >> 1) - 10000 + i;
break;
}
}
printf("%d\n", max(mx, m + 1 + all - as));
}
}
我
T3 串串
說道手機，我前兩天剛把舊手機………不對好像串臺了那是轉轉【大霧】。
力
T4 游走
神級游走NPC。
浙公網安備 33010602011771號