牛客练习赛76 ACE 题解

A. 校园活动

Solution

考虑到要分成几组，可以先求出总的数量
最终的分组情况肯定是 的因子数
随后从大往小枚举分组数即可
时间复杂度

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n; cin >> n;
  string s; cin >> s;
  int sum = 0, ans = 1;
  for(auto &x : s) {
    sum += x - '0';
  }
  for(int i = n; i >= 1; i--) {
    if(sum % i) continue;
    int se = 0, ok = 1;
    for(auto &x : s) {
      se += x - '0';
      if(se == sum / i) se = 0;
      else if(se > sum / i) {
        ok = 0; break;
      }
    }
    if(ok) {
      ans = i;
      break;
    }
  }
  if(ans == 1) cout << -1 << '\n';
  else cout << ans << '\n';
  return 0;
} 

C. CG的通关秘籍

Solution

对于一个数字 , 他的后面要放比他小的数字会形成逆序, 一共有 种可能, 如果放比他大的数字, 一共有 种可能
根据题意给的贡献统计规则, 总的贡献为
那么对于每个数字都有上述的情况， 即
一共有 个位置可以在他后面形成贡献即
至于其他数字可以随意摆放，都会产生上述的贡献，摆放方案为
所以总的答案是

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
ll qpow(ll a, ll b) {
  ll res = 1;
  while(b) {
    if(b & 1) {
      res = res * a % mod;
    }
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int T; cin >> T;
  while(T--) {
    ll n, m; cin >> n >> m;
    ll ans = m * m % mod;
    ans += m * (m + 1) / 2;
    ans %= mod;
    ans -= 2 * m;
    ans %= mod, ans += mod, ans %= mod;
    ans *= (n - 1), ans %= mod;
    ans *= qpow(m, n - 2);
    ans %= mod;
    cout << ans << '\n';
  }
  return 0;
} 

E. 牛牛数数

Solution

现场学线性基，这是一种能够求给定序列异或第 小的东西，想学的同学移步洛谷
那么不妨二分答案 , 将线性基里面第 小的元素与给定 作比较，大于则符合条件，由此二分出最小的符合条件的
那么答案就是 , 是线性基的集合大小。
模板是从洛谷抄的....毕竟是现学现卖

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
ll a[65], tmp[65];
const int MN = 63;
bool flag;
void ins(ll x){
  for(int i=MN;~i;i--)
    if(x&(1ll<<i))
        if(!a[i]){a[i]=x;return;}
        else x^=a[i];
  flag=true;
}
bool check(ll x){
  for(int i=MN;~i;i--)
    if(x&(1ll<<i))
      if(!a[i])return false;
      else x^=a[i];
  return true;
}
ll query(ll k){
  ll res=0;  
  int cnt=0;
  k-=flag;if(!k)return 0;
  for(int i=0;i<=MN;i++){
      for(int j=i-1;~j;j--)
          if(a[i]&(1ll<<j))a[i]^=a[j];
      if(a[i])tmp[cnt++]=a[i];
  }
  if(k>=(1ll<<cnt))return -1;
  for(int i=0;i<cnt;i++)
      if(k&(1ll<<i))res^=tmp[i];
  return res;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n; ll x; cin >> n >> x;
  ll p;
  for(int i = 1; i <= n; i++) cin >> p, ins(p);
  ll left = 1, right = 2e18, ans = 0;
  while(left <= right) {
    ll mid = left + right >> 1;
    if(query(mid) != -1) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  left = 1, right = ans;
  ll res = 0;
  while(left <= right) {
    ll mid = left + right >> 1;
    if(query(mid) > x) {
      res = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  cout << ans - res + 1 << '\n';

  return 0;
}