Educational Codeforces Round 158 (Rated for Div. 2)（A~E）（貪心，樹形DP）

A - Line Trip?

??????? 題意：有一條路，可以用一條數線來表示。你位于數線上的點 0 ，你想從點 0 到點 x ，再回到點 0。你乘汽車旅行，每行駛 1個單位的距離要花費 1 升汽油。當您從點 0出發時，汽車已加滿油(油箱中的油量已達到最大值)。在 a1,a2,…,an點有 n 個加油站。到達加油站后，為汽車加滿油。注意只能在加油站加油， 0 和 x點沒有加油站。你必須計算出你的汽車油箱的最小容積(以升為單位)，這樣你才能從點 0行駛到點 x 并返回到點 0 。

??????? 思路：求一下相鄰加油站的距離最大值即可，注意最后一個加油站要先到點x再回來。

????????

// Problem: A. Line Trip
// Contest: Codeforces - Educational Codeforces Round 158 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1901/problem/0
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=1e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{cin >> n >> m;for(int i = 1 ; i <= n ; i ++){cin >> a[i];}	int maxx = (m - a[n]) * 2;for(int i = 1 ; i <= n ;i ++){maxx = max(maxx , a[i] - a[i - 1]);}cout << maxx << endl;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

B - Chip and Ribbon?

??????? 題意：有一條帶子被分成 n 個單元格，從左到右編號為 1 到 n 。最初，每個單元格中都寫有一個整數 0。Monocarp在玩芯片游戲。游戲由幾個回合組成。在第一輪中，Monocarp 將芯片放入色帶的第一單元格。除了第一輪之外，在每一輪中，魔卡都會做以下兩個動作中的恰好一個：

將芯片移動到下一個單元格(例如，如果芯片在 i 單元格，則將其移動到 i+1單元格)。如果芯片在上一格，則無法進行此操作；

選擇任意一個 x單元格，將芯片傳送到該單元格。可以選擇芯片當前所在的單元格。

每回合結束時，寫入芯片所在單元格的整數會增加 1。

Monocarp的目標是在某些回合中使第一個單元格中等于整數 c1 ，第二個單元格中等于整數 c2 ....第n個單元格中等于整數 cn。他希望盡可能少地傳送芯片。

請幫助 Monocarp 計算他傳送芯片的最少次數。

??????? 思路:對于一個連續的序列來說，無需傳送就能全部+1，因此此題變成了每輪操作能將[l ,r]單元格內的數加一，求最小操作數。此題類似于Problem - C - Codeforces

可以發現，所有左側標紅的即為選擇的區間，因此最小操作數就是統計標紅的數量，即 $\sum _{i = 1}^{n}max(0 , a[i] - a[i - 1])$ 。具體解析可以看該題題解。

????????

// Problem: B. Chip and Ribbon
// Contest: Codeforces - Educational Codeforces Round 158 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1901/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=2e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{int n;cin >> n;for(int i = 1 ; i <= n ; i ++){cin >> a[i];}	LL ans = 0;for(int i = 1 ; i <= n ; i ++){if(a[i] > a[i - 1]){ans += a[i] - a[i - 1];}}cout << ans - 1<< endl;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

C - Add, Divide and Floor?

??????? 題意：給你一個整數數組 a1,a2,…,an (? $0\leq a_{i}\leq 10^9$ )。在一次操作中，你可以選擇一個整數 x (? $0\leq x\leq 10^{18}$ )，并用 ? $(a_{i} + x ) / 2$ ? 替換 ai ( ?y? 表示將 y 舍入為最接近的整數)。 ?y? 表示將 y 舍入為最接近的整數）來替換從 1 到 n 的所有 i。請注意，每次操作都會影響數組中的所有元素。打印使數組中所有元素相等所需的最小操作數。如果操作次數小于或等于 n，則打印每次操作所選擇的 x 。如果有多個答案，則打印任意一個。

??????? 思路：若最小的數通過操作等于最大的數，那么其他數必然也相等。因此只需要看最小的和最大的即可。再考慮如何去操作：觀察可以發現其實x的大小沒有用，x的奇偶性可能會改變答案，因此我們x的取值只設為（0 ， 1）。如果最大值是偶數，那么+1不會使得結果更大，否則可能會使得結果更大。

????????

// Problem: C. Add, Divide and Floor
// Contest: Codeforces - Educational Codeforces Round 158 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1901/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=2e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{cin >> n;int maxx = -1 , minn = 1.5e9;for(int i = 0 ; i < n ; i ++){cin >> a[i];maxx = max(a[i] , maxx);minn = min(minn , a[i]);}vector<int> ans;while (minn != maxx) {if (minn % 2 == maxx % 2) {ans.push_back(0);} else if (maxx % 2 == 0) {ans.push_back(1);++minn;++maxx;} else {ans.push_back(0);}minn /= 2;maxx /= 2;}cout << ans.size() << "\n";if ((int)ans.size() <= n) {for (int x : ans) {cout << x << " ";}cout << "\n";}
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

D - Yet Another Monster Fight?

??????? 題意：現有n頭怪獸，每個怪獸有 $a_{i}$ 的血量，你需要發動一次魔法將所有怪獸打敗。魔法規則如下：第一輪將打中你選擇的那頭怪獸，并扣除x的血量，接下來每一輪魔法的傷害值減一，并且打中那些未被打中的，處于已被打中的怪獸的相鄰怪獸。要求你可以選擇任意第一輪打中的怪獸的情況下，魔法的初始傷害的最小值。

??????? 思路：首先考慮已知第一輪打中第 $i$ 只怪獸的情況下，魔法初始傷害的最小值。對于 $[1 , i - 1]$ 的第 $x$ 只怪獸而言，其最晚被打中的輪次為右邊所有怪獸的數量（ $n - x$ ），所以初始傷害值需要 $a_{i} + n - x$ ,我們將其定義為 $r[x]$ 。而對于 $[i + 1 , n]$ 的第 $j$ 只怪獸而言則相反，其最晚被打中的輪次為 $j - 1$ ，初始傷害值需要 $a_{i} + j - 1$ ? ，我們將其定義為 $l[j]$ 。因此魔法初始傷害的最小值為： $max(max(r[1]...r[i - 1]) , a[i] , max(l[i + 1] ...l[n]))$ 。考慮完這個以后我們可以通過前綴最大值和后綴最大值來維護 $r , l$ 數組。然后再遍歷每只怪獸，假設其為第一輪攻擊的怪獸，求魔法初始傷害的最小值即可。

????????

// Problem: D. Yet Another Monster Fight
// Contest: Codeforces - Educational Codeforces Round 158 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1901/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=3e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
LL a[N];
LL r[N] , l[N];
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{int n;cin >> n;for(int i = 1 ; i <= n ; i ++)cin >> a[i];for(int i = 1 ; i <= n ; i ++){l[i] = a[i] + (i - 1);r[i] = a[i] + (n - i);}for(int i = 1 ; i <= n ; i++){r[i] = max(r[i - 1] , r[i]);}for(int i = n; i >= 1 ; i --){l[i] = max(l[i + 1] , l[i]);}LL ans = 1e18;for(int i = 1 ; i <= n ; i ++){ans = min(ans , max(a[i] , max(r[i - 1] ,l[i + 1])));}cout << ans ;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;
//	cin>>t;while(t--){solve();}return 0;
}

E - Compressed Tree （樹形DP）

??????? 題意：給你一棵由 n 個頂點組成的樹。每個頂點上都寫有一個數字；頂點 i 上的數字等于 ai 。

????????您可以執行以下任意次數的操作(可能為零)：選擇一個最多有1條邊的頂點，并將該頂點從樹中刪除。請注意，您可以刪除所有頂點。

????????完成所有操作后，就可以壓縮樹了。壓縮過程如下。當樹中有一個頂點恰好有2條邊時，執行以下操作：刪除該頂點，用一條邊連接其鄰居。

????????可以看出，如果在壓縮過程中有多種選擇刪除頂點的方法，那么得到的樹還是一樣的。

????????你們的任務是計算在任意次數的上述操作后，求出壓縮完樹以后的所有頂點的權值之和最大。

??????? 思路：對于一個頂點來說，最終壓縮完樹以后有4種情況：

1、只保留了自己一個頂點。

2、保留了自己和自己鄰邊上一個頂點。

3、保留了鄰邊上的兩個頂點。

4、保留了自己和鄰邊上面2個以上的頂點。（這樣在壓縮的時候就不會把自己刪了）

因此用dp[n][4]來分別表示這四種狀態。接下來考慮如何從子頂點上轉移，若頂點只有一個子頂點，那么就只有1、2兩種情況。如果頂點有兩個子頂點，那么就會出現1、2、3三種情況。如果子頂點大于2個的話，那么就需要對子頂點的值進行排序了，肯定是越大的越好。對于情況4，并不是所有的子頂點都需要選擇，若子頂點的值小于0，那么就代表這子頂點是無需保留的，刪除即可。

??????? 接下來考慮子樹的值如何選擇：對于情況1和情況4，直接繼承。對于情況2，在壓縮的過程中會把子樹結點給壓縮掉，所以需要減去子頂點的值。對于情況3，原本是不保留子頂點的，但是由于需要連到父親上，所以子頂點需要保留，因此需要增加子頂點的值。因此一個子頂點的值即為： $max(dp[ch][1] , dp[ch][2] - a[ch] , dp[ch][3] + a[ch] , dp[ch][4])$ 。

??????? 接下來走任意一點開始走一遍DFS，時刻記錄最大值。（只有一條鏈或者兩個點的情況下特殊處理一下即可）

// Problem: E. Compressed Tree
// Contest: Codeforces - Educational Codeforces Round 158 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1901/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=5e05+10;
const LL mod=1e09+7;
const LL inf = 1e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
LL a[N];
int deg[N];
vector<int>e[N];
LL dp[N][4];
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0 , deg[i] = 0 , e[i].clear();}
}
LL cmp(LL a , LL b){return a > b;
}
LL ans = 0;
void dfs(int cur , int fa){dp[cur][0] = a[cur] , dp[cur][1] = -inf , dp[cur][2] = -inf , dp[cur][3] = -inf;vector<LL>ch;for(auto v : e[cur]){if(v == fa)continue;dfs(v , cur);ch.pb(max(dp[v][0], max(dp[v][1] - a[v], max(dp[v][2] + a[v], dp[v][3]))));}sort(ch.begin() , ch.end() , cmp);if(ch.size() >= 1){dp[cur][1] = a[cur] + ch[0];}if(ch.size() >= 2){dp[cur][2] = ch[0] + ch[1];}if(ch.size() >= 3){dp[cur][3] = a[cur] + ch[0] + ch[1] + ch[2];for(int i = 3 ; i < (int)ch.size() ; i ++){if(ch[i] < 0){break;}dp[cur][3] += ch[i];}}ans = max(ans , max(dp[cur][0], max(dp[cur][1], max(dp[cur][2], dp[cur][3]))));
}
void solve() 
{cin >> n;for(int i = 1 ; i <= n ; i ++)cin >> a[i];int max_deg = 1;for(int i = 1 ; i < n ; i ++){int x , y;cin >> x >> y;e[x].pb(y);e[y].pb(x);deg[x] ++;deg[y] ++;max_deg = max(max_deg , max(deg[x] , deg[y]));}if(max_deg == 1){if(a[1] < 0){cout << max(1LL * 0 , a[2]) << endl;}else{cout << max(a[1] , a[1] + a[2]) << endl;}}else if(max_deg == 2){sort(a + 1, a + 1 + n , cmp);if(a[1] < 0){cout << max(1LL * 0 , a[2]) << endl;}else{cout << max(a[1] , a[1] + a[2]) << endl;}}else{ans = 0;dfs(1 , 0);cout << ans << endl;}init(n);
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

????????