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

首先是C题：

咱们先看题目：

链接：https://ac.nowcoder.com/acm/contest/133790/C
来源：牛客网。

这道题其实特别简单，我们只需要按顺序遍历数组，统计能依次被 1、2、3... 整除的元素数量，即可，但不知为什么比赛时做对的人没有特别多。

代码示例

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ll t; ll n; ll j; ll sum; cin>>t; while(t--){ cin>>n; vector<ll>a(1000001); j=1; sum=0; for(int i=0;i<n;i++){ cin>>a[i]; if(a[i]%j==0){ sum++; j++; } } cout<<sum<<endl; } return 0; }

再说D题，这个题稍微有点难度

先看题目：

要写这道题我们首先要搞懂题目意思其实就是一道简单的枚举，第一个人向右传 0 或 1 颗糖，然后递推验证整圈是否能合法均分糖果，能的话输出 “YES”，不能的话就输出 “NO”。

解题过程：

1.我们先计算总糖果数，如果不能均分的话直接输出NO

2.由题意可知最后每个小朋友的糖书应该都相等，所以都为平均值avg，所以我们也要先计算出平均值。

3.每个小朋友递出去的糖数应该为从上一个小朋友手里拿到的糖数减去平均糖数。

4.如果小朋友递出去的糖果数目小于0或大于1都违反了题目规则，直接就可以返回false.

5.因为每个人只能传0 或 1，所以第一个人只有两种可能：传 0 或传 1

6.分别尝试first=0和first=1两种情况.

7.只要有一个返回true,我们就可以输出YES，否则输出NO。

代码示例

#include<bits/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 i=1;i<n;i++){ x[i]=x[i-1]+a[i]-avg; if(x[i]<0||x[i]>1) return false; if(x[i]==1&&a[i]==0) return false; } if(x[0]!=x[n-1]+a[0]-avg)return false; return true; } int main(){ int t; cin>>t; ll sum; while(t--){ sum=0; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; sum+=a[i]; } ll avg=sum/n; if(sum%n!=0){ cout<<"NO"<<endl; } else{ if(check(0,avg)||check(1,avg)){ cout<<"YES"<<endl; } else cout<<"NO"<<endl; } } return 0; }