牛客练习赛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;
} 
全部评论

相关推荐

07-02 18:09
门头沟学院 Java
苍穹外卖和谷粒商城这俩是不是烂大街了,还能做吗?
想去重庆的鸽子在吐槽:你不如把这俩做完自己搞明白再优化点再来问 何必贩卖焦虑
点赞 评论 收藏
分享
身边有人上海、深圳&nbsp;6、7k&nbsp;都去了,真就带薪上班了。
程序员小白条:木的办法, 以后越来越差,还是家附近宅着吧,毕业的人越来越多,岗位都提供不出来,经济又过了人口红利期
点赞 评论 收藏
分享
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
评论
4
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务