牛客小白月赛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个方块，每一个方块都一个数 $a_{i}$ ,为正数可以往前跳，跳到 $i$ 到 $i + a [i]$ ，负数可以往回跳可以跳到 $1$ 到 $i + a [i]$ 。

思路

这个题目有很明显的转移，且数据范围较小，可以采用动态规划。假设 $d p [i]$ 表示到达第 i 个方块的最短用时。由于负数相当于往回走，用时肯定更长，负数肯定可以直接跳过，有负数可能导致不能遍历到第 n 个方块，如果可以遍历到第 n 个方块直接输出 $d p [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();
}