清晰的繽紛的都可以
臟兮兮的甜的也都有轉機
不想太小心
錯過第一百零一場美麗

CF思維小訓練（二）

書接上回CF思維小訓練-CSDN博客

雖然代碼很短，都是每一道題的背后都思維滿滿；

---

Arboris Contractio

Problem - 2131D - Codeforces

一開始看到題目的思路是先找到鏈接最多的點然后用spfa找一遍最遠的點，然后再從這個點出發找一遍里這個點的最遠點，這樣就找到了這個樹的直徑，然后看直徑上有幾個分支就再操作幾次；_{（學算法學魔怔了）}與題意有較大的偏差；

其實只用找子葉節點的個數即可，因為分析這個操作的本質，每次操作只能減少一個子葉那條路徑的情況，因為操作都會連到第一個點上；所以根本不需要那么麻煩，直接統計子葉節點的個數就好了；

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=2e5+5;
const int inf=0x3f3f3f3f;
vector<int> e[N];
void slove(){int n;cin>>n;for(int i=1;i<=n;i++)e[i].clear();for(int i=1;i<n;i++){int u,v;cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}if(n==2){cout<<0<<endl;return ;}int an=0;for(int i=1;i<=n;i++)if(e[i].size()==1) an++;int mx=0;for(int i=1;i<=n;i++){int c=0;for(auto v:e[i]){if(e[v].size()==1)c++;}mx=max(mx,c);}cout<<an-mx<<endl;
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;cin>>_;while(_--)slove();return 0;
} 

---

Adjacent XOR

Problem - 2131E - Codeforces

這道題不算難，我們要判斷能否通過$a_i=a_i\oplus a_{i+1}$的操作將數組$a$變成數組$b$；也就是看$b_i$是佛滿足$b_i=a_i\oplus a_{i+1}$或者$b_i=a_i$；

利用異或的性質推出，如果$b_i=a_i\oplus a_{i+1}$那么$a_{i+1}=a_i\oplus b_i$；所以我們每個位置上判斷一下是佛符合條件即可；

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int inf=0x3f3f3f3f;
const int N=2e5+5;
int a[N],b[N];
void slove(){int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];if(a[n]!=b[n]){cout<<"NO"<<endl;return ;}for(int i=1;i<n;i++){int x=a[i]^b[i];if(x!=0&&a[i+1]!=x&&b[i+1]!=x){cout<<"NO"<<endl;return ;}}cout<<"YES"<<endl;
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;cin>>_;while(_--)slove();return 0;
}

---

Scammy Game Ad

Problem - D - Codeforces

一開始看到題目的反應是貪心；但是貪心只能保證是局部最優解；我們需要的是全局最優解，所以不難想到利用動態規劃的思路；但是問題又來了，動態規劃要求無后效性，但是題目中的每次選擇都會對后面的狀態產生影響，所以可以換個思路，從后往前進行dp；

觀察題目可以發現加法操作時的更新量是唯一的，不管原來是多少，增加的量都是固定的，所以可以先把加法門存起來再原位置變成×1門，相當于在這個門后又加入了新的人；等到最后在判斷增加的人的最優情況；剩下的就是對乘法門的處理了，此時倒序遍歷就可以保證無后效性利用貪心的思想求解即可；（dp數組有點類似后綴和，將后面的最優倍率存起來）

最后累加結果，不要忘記最開始的兩個人；

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int inf=0x3f3f3f3f;
const int N=1e5+5;
int b[N][3],dp[N][3];
int a[N];
void slove(){memset(a,0,sizeof a);memset(b,0,sizeof b);memset(dp,0,sizeof dp);int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=2;j++){char op;int x;cin>>op>>x;if(op=='+') a[i]+=x;else b[i][j]=x-1;}}dp[n][1]=1,dp[n][2]=1;for(int i=n;i>=1;i--){for(int j=1;j<=2;j++){dp[i-1][j]=dp[i][j]+b[i][j]*max(dp[i][1],dp[i][2]);}}int an=dp[0][1]+dp[0][2];for(int i=1;i<=n;i++){an+=a[i]*max(dp[i][1],dp[i][2]);}cout<<an<<endl;
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;cin>>_;while(_--)slove();return 0;
}

---

Rudolf and 121

Problem - 1941B - Codeforces

讓我們考慮最小的 i 使得 ai > 0；將這個元素變為零的唯一方法是選擇第 (i+1) 個元素進行操作（對更左側的元素進行操作要么不可能，要么會導致某些元素變為負數）我們將以這種方式進行操作，直到到達數組末尾；如果在應用這些操作后仍有非零元素剩余，則答案為 “NO”；

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int inf=0x3f3f3f3f;
const int N=2e5+5;
int a[N];
void slove(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<n-1;i++){if(a[i]<0){cout<<"NO"<<endl;return ;}int x=a[i];a[i]-=x;a[i+1]-=2*x;a[i+2]-=x;}if(a[n]||a[n-1])cout<<"NO"<<endl;else cout<<"YES"<<endl;
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;cin>>_;while(_--)slove();return 0;
}

---

Deadly Laser

Problem - 1721B - Codeforces

首先，我們需要判斷是否有可能到達終點。如果激光的覆蓋范圍沒有觸及任何墻壁，那么顯然可以到達——只需沿著墻壁行走即可。

如果激光最多只觸及一面墻，仍然可以到達。如果激光覆蓋的是下墻或左墻，則選擇靠近上墻和右墻的路徑；反之，如果激光覆蓋的是上墻或右墻，則選擇靠近下墻和左墻的路徑。

但如果這兩條路徑都被封鎖了呢？這意味著激光同時覆蓋至少兩面墻：上墻和左墻，或者下墻和右墻。事實證明，在這兩種情況下，完全無法到達終點。你可以畫個圖自己驗證一下。

因此，我們總是可以選擇至少一條沿墻壁的路徑。從起點到終點的距離是 ∣n?1∣+∣m?1∣，而這兩條路徑的長度恰好等于這個值。所以答案要么是 ?1，要么是 n+m?2。

要檢查激光的覆蓋范圍是否觸及墻壁，可以使用公式計算，或者檢查靠近墻壁的每個單元格。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int inf=0x3f3f3f3f;
const int N=1e5+5;
void slove(){int n,m,sx,sy,d;cin>>n>>m>>sx>>sy>>d;int x=min(sx-1,m-sy);int y=min(n-sx,sy-1);if(x<=d&&y<=d)cout<<-1<<endl;else cout<<n+m-2<<endl;
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;cin>>_;while(_--)slove();return 0;
}

---