清晰的缤纷的都可以
脏兮兮的甜的也都有转机
不想太小心
错过第一百零一场美丽

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⊕a_{i+1}$ 的操作将数组 $a$ 变成数组 $b$ ；也就是看 $b_i$ 是佛满足 $b_i=a_i⊕a_{i+1}$ 或者 $b_i=a_i$ ；

利用异或的性质推出，如果 $b_i=a_i⊕a_{i+1}$ 那么 $a_{i+1}=a_i⊕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;
}