淘宝客的api怎么做网站,wordpress 全站不刷新,重庆网站seo排名,怎么下载文件清晰的缤纷的都可以 脏兮兮的甜的也都有转机 不想太小心 错过第一百零一场美丽 CF思维小训练#xff08;二#xff09;
书接上回CF思维小训练-CSDN博客
虽然代码很短#xff0c;都是每一道题的背后都思维满满#xff1b; 目录CF思维小训练#xff08;二#xff09;Arbo… 清晰的缤纷的都可以 脏兮兮的甜的也都有转机 不想太小心 错过第一百零一场美丽 CF思维小训练二
书接上回CF思维小训练-CSDN博客
虽然代码很短都是每一道题的背后都思维满满 目录CF思维小训练二Arboris ContractioAdjacent XORScammy Game AdRudolf and 121Deadly LaserArboris Contractio
Problem - 2131D - Codeforces
一开始看到题目的思路是先找到链接最多的点然后用spfa找一遍最远的点然后再从这个点出发找一遍里这个点的最远点这样就找到了这个树的直径然后看直径上有几个分支就再操作几次学算法学魔怔了与题意有较大的偏差
其实只用找子叶节点的个数即可因为分析这个操作的本质每次操作只能减少一个子叶那条路径的情况因为操作都会连到第一个点上所以根本不需要那么麻烦直接统计子叶节点的个数就好了
#includebits/stdc.h
using namespace std;
#define int long long
#define pii pairint,int
#define fi first
#define se second
#define endl \n
const int N2e55;
const int inf0x3f3f3f3f;
vectorint e[N];
void slove(){int n;cinn;for(int i1;in;i)e[i].clear();for(int i1;in;i){int u,v;cinuv;e[u].push_back(v);e[v].push_back(u);}if(n2){cout0endl;return ;}int an0;for(int i1;in;i)if(e[i].size()1) an;int mx0;for(int i1;in;i){int c0;for(auto v:e[i]){if(e[v].size()1)c;}mxmax(mx,c);}coutan-mxendl;
}
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
这道题不算难我们要判断能否通过aiai⊕ai1a_ia_i⊕a_{i1}aiai⊕ai1的操作将数组aaa变成数组bbb也就是看bib_ibi是佛满足biai⊕ai1b_ia_i⊕a_{i1}biai⊕ai1或者biaib_ia_ibiai
利用异或的性质推出如果biai⊕ai1b_ia_i⊕a_{i1}biai⊕ai1那么ai1ai⊕bia_{i1}a_i⊕b_iai1ai⊕bi所以我们每个位置上判断一下是佛符合条件即可
#includebits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define pii pairint,int
#define fi first
#define se second
const int inf0x3f3f3f3f;
const int N2e55;
int a[N],b[N];
void slove(){int n;cinn;for(int i1;in;i) cina[i];for(int i1;in;i) cinb[i];if(a[n]!b[n]){coutNOendl;return ;}for(int i1;in;i){int xa[i]^b[i];if(x!0a[i1]!xb[i1]!x){coutNOendl;return ;}}coutYESendl;
}
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数组有点类似后缀和将后面的最优倍率存起来
最后累加结果不要忘记最开始的两个人
#includebits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define pii pairint,int
#define fi first
#define se second
const int inf0x3f3f3f3f;
const int N1e55;
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;cinn;for(int i1;in;i){for(int j1;j2;j){char op;int x;cinopx;if(op) a[i]x;else b[i][j]x-1;}}dp[n][1]1,dp[n][2]1;for(int in;i1;i--){for(int j1;j2;j){dp[i-1][j]dp[i][j]b[i][j]*max(dp[i][1],dp[i][2]);}}int andp[0][1]dp[0][2];for(int i1;in;i){ana[i]*max(dp[i][1],dp[i][2]);}coutanendl;
}
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将这个元素变为零的唯一方法是选择第 (i1) 个元素进行操作对更左侧的元素进行操作要么不可能要么会导致某些元素变为负数我们将以这种方式进行操作直到到达数组末尾如果在应用这些操作后仍有非零元素剩余则答案为 “NO”
#includebits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define pii pairint,int
#define fi first
#define se second
const int inf0x3f3f3f3f;
const int N2e55;
int a[N];
void slove(){int n;cinn;for(int i1;in;i)cina[i];for(int i1;in-1;i){if(a[i]0){coutNOendl;return ;}int xa[i];a[i]-x;a[i1]-2*x;a[i2]-x;}if(a[n]||a[n-1])coutNOendl;else coutYESendl;
}
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要么是 nm−2。
要检查激光的覆盖范围是否触及墙壁可以使用公式计算或者检查靠近墙壁的每个单元格。
#includebits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define pii pairint,int
#define fi first
#define se second
const int inf0x3f3f3f3f;
const int N1e55;
void slove(){int n,m,sx,sy,d;cinnmsxsyd;int xmin(sx-1,m-sy);int ymin(n-sx,sy-1);if(xdyd)cout-1endl;else coutnm-2endl;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _1;cin_;while(_--)slove();return 0;
}
