牛客周赛 Round 142 C题及D题题解

首先是C题咱们先看题目链接https://ac.nowcoder.com/acm/contest/133790/C来源牛客网。这道题其实特别简单我们只需要按顺序遍历数组统计能依次被 1、2、3... 整除的元素数量即可但不知为什么比赛时做对的人没有特别多。代码示例#includebits/stdc.h using namespace std; typedef long long ll; int main(){ ll t; ll n; ll j; ll sum; cint; while(t--){ cinn; vectorlla(1000001); j1; sum0; for(int i0;in;i){ cina[i]; if(a[i]%j0){ sum; j; } } coutsumendl; } return 0; }再说D题这个题稍微有点难度先看题目要写这道题我们首先要搞懂题目意思其实就是一道简单的枚举第一个人向右传 0 或 1 颗糖然后递推验证整圈是否能合法均分糖果能的话输出 “YES”不能的话就输出 “NO”。解题过程1.我们先计算总糖果数如果不能均分的话直接输出NO2.由题意可知最后每个小朋友的糖书应该都相等所以都为平均值avg所以我们也要先计算出平均值。3.每个小朋友递出去的糖数应该为从上一个小朋友手里拿到的糖数减去平均糖数。4.如果小朋友递出去的糖果数目小于0或大于1都违反了题目规则直接就可以返回false.5.因为每个人只能传0 或 1所以第一个人只有两种可能传 0 或传 16.分别尝试first0和first1两种情况.7.只要有一个返回true,我们就可以输出YES否则输出NO。代码示例#includebits/stdc.h using namespace std; typedef long long ll; int n; ll a[10000001]; int x[10000001]; bool check(int first,ll avg){ x[0]first; for(int i1;in;i){ x[i]x[i-1]a[i]-avg; if(x[i]0||x[i]1) return false; if(x[i]1a[i]0) return false; } if(x[0]!x[n-1]a[0]-avg)return false; return true; } int main(){ int t; cint; ll sum; while(t--){ sum0; cinn; for(int i0;in;i){ cina[i]; suma[i]; } ll avgsum/n; if(sum%n!0){ coutNOendl; } else{ if(check(0,avg)||check(1,avg)){ coutYESendl; } else coutNOendl; } } return 0; }