牛客小白月赛40
牛客小白月赛
A
这一题其实直接暴力就可以了。推荐一个函数：
__builtin_popcount(x) //返回x在二进制表示1的个数
__builtin_clz (unsigned int x) //返回前导的0的个数。
代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
scanf("%d",&T);
while (T--) {
int x, ans = 0;
scanf("%d",&x);
while (x) {
if (__builtin_popcount(x) & 1)
x ^= 1;
else {
int bit = 31 - __builtin_clz(x);
x ^= 1 << bit;
}
ans++;
}
printf("%d\n", ans);
}
return 0;
}
D
签到题，判断有多少个两两相同连在一起的字符就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
ll n,m,k;
void solve(){
string s;
cin>>s;
int n=s.size();
int tt=n;
for(int i=0;i<tt-1;i++){
if(s[i]==s[i+1]) n++;
}
cout<<n<<endl;
}
int main(){
int T=1;
cin>>T;
while(T--) solve();
}
E
二分答案，二分最多的小组的人数
那么check函数，数据范围挺小的，直接可以桶 计数。判断最多可以分成多少组，组数是不是小于 m就可以了。
代码：
#include<bits/stdc++.h>
using namespace std;
int a[1000010],t[1000010];
int n,m;
bool chk(int mid){
if(mid==0) return true;//其实根本不会有这种情况
int ans=0,mx=0;
for(int i=1;i<=100000;i++){
if(t[i]){
ans=ans+(t[i]+mid-1)/mid;
}
}
return ans<=m;//判断能不能分那么多组
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i];
t[a[i]]++;
}
int l=0,r=n;
int ans=100000;
while(l<=r){
int mid=(l+r)/2;
if(chk(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
if(ans==100000) cout<<-1<<endl;
else cout<<ans<<endl;
}
F
题意
有n个 方块，每一个方块都一个数 ,为正数可以往前跳，跳到 到 ，负数可以往回跳 可以跳到到 。
思路
这个题目有很明显的转移，且数据范围较小，可以采用动态规划。 假设 表示到达第 i 个方块的最短用时。由于负数相当于往回走，用时肯定更长，负数肯定可以直接跳过，有负数可能导致不能遍历到第 n 个 方块，如果可以遍历到第 n 个方块直接输出 ,如果不能输出 -1 ；
- 转移方程：
dp[i+a[i]]=min(dp[i]+1,dp[i+a[i]);
负数直接跳过
- code
#include<bits/stdc++.h>
using namespace std;
int dp[30000],a[20000];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],dp[i]=INT_MAX;
dp[1]=0;
for(int i=1;i<=n;i++){
if(a[i]>0){
for(int j=i+1;j<=i+a[i];j++){
dp[j]=min(dp[i]+1,dp[j]);
}
}
}
if(dp[n]==INT_MAX) cout<<-1<<endl;
else cout<<dp[n]<<endl;
}
G
差分、前缀和
枚举每一个K，去一个最大值
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int sum[6000010]={0};
int main(){
int n,m,p;
cin>>n>>p;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++){
sum[a[i]-p+1000000]++;
sum[a[i]+p+1000000+1]--;
}
int ans=0;
for(int i=0;i<=2000000;i++){
sum[i]+=sum[i-1];
ans=max(sum[i],ans);
}
cout<<ans<<endl;
}
H
要使得选的数的gcd等于x,那么选的数一定是 x的倍数，所以我们枚举 x，2x，3x，4x，如果在数组中出现过，我们就对他 取一个gcd，如果最后这些数的gcd等于 x，那么输出YES，否则输出NO
时间卡的有点紧，用快一点的输入输出
代码：
#include<bits/stdc++.h>
using namespace std;
int n,a[1000010],m,h[1000010];
void solve(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++) h[i]=0;//注意不要用memset，会超时
for(int i=1;i<=n;i++) scanf("%d",&a[i]),h[a[i]]++;
int x;
while(m--){
scanf("%d",&x);
bool ok=true;
int p=x,tt=0;
for(int i=x;i<=n&&tt!=x;i+=x){
if(h[i]) tt=__gcd(i,tt);
}
if(tt==x) printf("YES\n");
else printf("NO\n");
}
}
int main(){
int t;
cin>>t;
while(t--) solve();
}
I
范围只有到10，直接STL，全排列函数，next_permutation(a.begin(),a.end()),返回下一个比他大的全排列。判断每一个排列是否符合条件。
DFS搜全排列也是一样的。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define endl '\n'
typedef long long ll;
const int N=5e5+10;
const int M=1e6+7;
const int mod=1e9+7;
ll n,m,k;
ll a[N],b[N];
void solve(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) b[i]=i+1;
int ans=0;
do{
bool ok=true;
for(int i=0;i<n;i++){
int pos=0;
if(a[i]==i+1) continue;
for(int j=0;j<n;j++){//找到他的位置，
if(b[j]==i+1) {
pos=j+1;
break;
}
}
for(int j=0;j<pos;j++){//判断是不是在他的前面
if(b[j]==a[i]){
ok=false;
break;
}
}
}
if(ok) ans++;
}while(next_permutation(b, b+n));
cout<<ans<<endl;
}
int main(){
solve();
}
