牛客练习赛76部分题题解

本场实力爆炸了，由于时间和能力关系，这里只订正了3题。

A 校园活动

算是签到题，还是Wa了好多发。
题目是要我们对给出的数字序列进行分组，要求每组的和相同，而且每组是连续的。由于数据比较小,n<=1000，我们可以直接暴力枚举组数然后check一下就好了。注意特判全0的时候。

#include<bits/stdc++.h>
using namespace std;
int n,sum[1004],tot,a[1004];
string s;
bool check(int x,int z){
  int tmp=0;
  int k=0;
  for(int i=1;i<=n;){
      while(tmp<z&&i<=n)tmp+=a[i++];
      if(tmp==z)k++,tmp=0;
      if(tmp>z) return false;
      if(k>x)return false;
  }
  return true;
}
int main()
{
  cin>>n;
  cin>>s;
  for(int i=0;i<n;i++){
      a[i+1]=s[i]-'0';
      tot+=s[i]-'0';
  }
  int i;
 // cout<<tot<<endl;
  for( i=n;i>=2;i--){
      int ea=tot/i;
      if(check(i,ea)){
          cout<<i<<endl;
          break;
      }
  }
  if(tot==0)cout<<n<<endl;
  else if(i==1)cout<<-1<<endl;
  return 0;
}

C CG的通关秘籍
比赛的时候开了这题，结果推了半天，一直错，结束以后发现推错了。。
首先可以发现，兴奋度的增加只存在于相邻的两个数中，通过推算可以知道，对于相邻的两个数ai和a(i+1)
假设能取的范围为[1,m]，我们可以计算出任意的取法的兴奋度之和为,
这个式子合并简化一下为。
接着我们考虑在占用了两个位置的情况下，剩下的n-2个位置上数字是随便放的，因此一共有种情况，在n个格子中选2个位置的情况一共有n-1种，那么我们可以得到最后的贡献和：
```
#include<bits/stdc++.h>
#define Mod 1000000007
using namespace std;
typedef long long ll;
ll qpow1(ll a,ll b){
  ll ans=1;
  while(b){
      if(b%2)ans=ans*a%Mod;
      a=a*a%Mod;
      b=b/2;
  }
  return ans%Mod;
}
ll feima(ll a){
  return qpow1(a,Mod-2)%Mod;
}
int t;
ll n,m;
int main(){
  scanf("%d",&t);
  while(t--){
      scanf("%lld%lld",&n,&m);
    //  ll ans=m*m-(m+1)*m/2+(m-1)*m;
      ll ans=3*m*(m-1)%Mod*feima(2)%Mod;
     // cout<<ans<<endl;
      ll tot=qpow1(m,n-2)%Mod;
      tot=tot*(n-1)%Mod;
      tot=tot*ans%Mod;
      printf("%lld\n",tot%Mod);
  }
}
```
E 牛牛数数
本题是参考题解写的，解法是二分+线性基。
由于之前并不了解线性基，所以去百度了一下。

这里贴一个讲解线性基的博客：https://blog.csdn.net/a_forever_dream/article/details/83654397

首先本题题意很简单，从n个数中任意选择进行异或，得到异或和x，求满足x>K的x的个数。
n<=100000,显然暴力是不可能的了。
这里感性理解一下线性基，线性基可以认为是从原集合中构造出一个新的集合，这个新集合的异或结果和原集合的异或结果一样。然后这个新集合有以下几个主要特点：
1.原序列任何的一个数都可以由线性基中的数异或得到
2.线性基中的数异或不能得到0
3.线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的
因此原问题中的数字集合的异或结果，我们可以通过构造的线性基来求解。
由于我们要获得满足x>K的x的个数。所以可以联想到二分查找第k小的数，与K进行判断。这样可以找到最小的大于K的数字，而我们构造的线性基可以得到总的数量，最差就可以了。
注意线性基中特判0的情况

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll d[100],n,K,p[100],cnt;
int flag;
void ins(ll x){
    for(int i=63;i>=0;i--){
        if( x&(1ll<<i)){
            if(!d[i]){
                d[i]=x;
                return;
            }
            else x^=d[i];
        }
    }
    flag=1;
}
void rebuild(){
    for(int i=63;i>=0;i--){
        for(int j=i-1;j>=0;j--){
            if(d[i]&(1ll<<j))d[i]^=d[j];
        }
    }
    for(int i=0;i<=63;i++){
        if(d[i])p[cnt++]=d[i];
    }
}
ll kth(ll k){
    if(k>=(1ll<<cnt))return -1;
    if(flag)k--;
    if(k==0)return 0;
    ll ans=0;
    for(int i=0;i<=63;i++){
            if(k&(1ll<<i))ans^=p[i];
    }
    return ans;
}
bool query(ll x){
    ll ans=kth(x);
    if(ans>K)return true;
    else return false;
}
int main()
{
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        ll x;
        cin>>x;
        ins(x);
    }
    rebuild();
    ll l,r;
    l=0;r=(1ll<<cnt)-flag;
    while(l<r){
        ll mid=l+r>>1;
        if(query(mid))r=mid;
        else l=mid+1;
    }
    if(l==(1ll<<cnt)-flag&&query(l)<=K)l++;
    cout<<(1ll<<cnt)-1+flag-l+1<<endl;
    return 0;
}

牛客练习赛76部分题题解

A 校园活动

C CG的通关秘籍

E 牛牛数数