首页 > 其他 > 详细

7.4 热身训练

时间:2020-07-06 11:19:07      阅读:48      评论:0      收藏:0      [点我收藏+]

Table of Contents

  1. 2020.7.4 热身训练赛(四)
    1. A - Zeros and Ones
      1. solution
      2. code

2020.7.4 热身训练赛(四)

A - Zeros and Ones

solution

折半搜索。

  1. __builtin_popcount() 比我手打的函数要快,以后就用它了。
  2. 折半搜索计算答案的一半长度不能为零,要取(x+y)-(x+y)/2,要不然无法计算答案。
  3. lower_bound返回的是第一个大于等于这个数的地址,upper_bound返回第一个大于这个数的地址。
  4. 二维vector的写法,多组数据,用后要清零。

code

#include <bits/stdc++.h>

using namespace std;
#define lbrg p[c].begin(), p[c].end() //lower_bound range
int x, y,mo, k;
vector<vector<int> > p(50);
int main() {
    freopen("zeros.in", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d%d", &x, &y, &mo, &k);

        int rm = (x + y) >> 1; //二进制下右边的长度
        int lm = x + y - rm; //左边的长度
        for (int i = 0; i < (1 << rm); ++i) {
            int c1 = __builtin_popcount(i);
            p[c1].push_back(i % mo);
        }
        for (int i = 0; i < 50; ++i)
            sort(p[i].begin(), p[i].end());
        ll ans = 0;
        for (ll i = 0; i < (1 << lm); ++i) {
            if (((i >> (lm - 1)) & 1) == 0) continue;
            int c1 = __builtin_popcount(i);
            int c = x - c1;
            if (c < 0) continue;
            int lk = (i << rm) % mo;
            if (lk <= k) {
                ans += lower_bound(lbrg, mo - lk) - lower_bound(lbrg, k - lk);
            } else {
                ans += lower_bound(lbrg,mo - lk) - p[c].begin();
                ans += lower_bound(lbrg, mo) - lower_bound(lbrg, mo + k - lk);

            }
        }
        printf("%lld\n", ans);
        for (int i = 0; i < 50; ++i)
            p[i].clear();
    }
    return 0;
}

7.4 热身训练

原文:https://www.cnblogs.com/huihao/p/13253543.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!