首页 > 其他分享 >Round 945 B

Round 945 B

时间:2024-10-31 23:41:50浏览次数:3  
标签:... expectedNum return int 945 vector 按位 Round

https://codeforces.com/contest/1973/problem/B

题目大意:

给定长度位n的数组a,找出符合以下条件的最小k:
任意连续的k个元素,他们按位或的结果相同

输入:
t 组数据,每组数据第一行 n (1 ≤ n ≤ 1e5)和 第二行数组a(0 ≤ai <2`20) 
输出:
最小的 k

思路:

  1. 假设一个小于 n 的 k 满足条件,则 (k + 1) 也满足条件

    证明:
    假设当前 k = 3, 则 a[1] | a[2] | a[3] = a[2] | a[3] | a[4] = ...
    => (a[1] | a[2] | a[3]) | (a[2] | a[3] | a[4]) = (a[2] | a[3] | a[4]) | (a[3] | a[4] | a[5]) = ...
    以此类推, (a[1] | ... | a[k]) | (a[2] | ... | a[k + 1]) = (a[2] | ... | a[k + 1]) | (a[3] | ... | a[k + 2]) = ...
    注意到,已经 or 过的数再 or 多少遍都不会改变结果,故上式可以化简为:
    a[1] | .. a[k + 1] = a[2] | ... | a[k + 2] = ...

    接下来,可以在 [1, n] 上二分确定最小的k

  2. 怎么判断每个k是否符合条件?
    前 k 位按位或的结果设为 expectedNum ,后面每段连续的 k 个数字按位或的结果与 expectedNum 进行比较,看是否相同

check函数代码实现:

将每个 a[i] 转换成二进制,用s_a表示,每 k 个数字按位或的结果为s_res,则每一位s_res[i]取决于这 k 个 s_a[i] 中有没有'1',如果有,则s_res[1] = '1',否则 s_res[1] = '0'
=>一堆数字按位或,如果有一个 1 则结果为 1,否则为 0

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, n;
/* 十进制转二进制 */
string DtoB(int x){
    if(x == 0){
        return "0";
    }
    string s = "";
    while(x > 0){
        s += x % 2 + '0';
        x /= 2;
    }
    int len = s.length();
    for(int i = 0; i < len - 1 - i; i++){
        swap(s[i], s[len - 1 - i]);
    }
    return s;
}
/* check当前k是否可行 */
bool check(int k, vector<string> &a, vector<vector<int>> &b){
    /* 计算前k个数字按位或的结果 */
    char expectedNum[21]; //expected[j]表示结果的倒数第j位
    for(int j = 1; j <= 20; j++){
        if(b[k][j] > 0){
            expectedNum[j] = '1';
        }
        else{
            expectedNum[j] = '0';
        }
    }

    for(int i = k + 1; i <= n; i++){
        for(int j = 1; j <= 20; j++){
            if(!(expectedNum[j] == '1' && b[i][j] - b[i - k][j] >= 1 || expectedNum[j] == '0' && b[i][j] - b[i - k][j] == 0)){
                return false;
            }
        }
    }
    return true;
}
signed main(){
    std::iostream::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while(t--){
        /* 初始输入 */
        cin >> n;
        vector<int> a(n + 1);
        vector<string> A_inBinary(n + 1);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            A_inBinary[i] = DtoB(a[i]);
        }

        vector<vector<int>> b(n + 1, vector<int>(21)); //b[i][j]表示前i行,倒数第j位上1的个数,前缀和的思想
        for(int i = 1; i <= n; i++){
            string s = A_inBinary[i];
            int len = s.length();
            for(int j = 1; j <= 20; j++){
                b[i][j] = b[i - 1][j] + (s[len - j] == '1');
            }
        }

        /* 二分 */
        int l = 1, r = n, mid = (l + r) / 2, ans = mid;
        while(l <= r){
            mid = (l + r) / 2;
            if(check(mid, A_inBinary, b)){
                ans = mid;
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

注意点:
类似需要转换成二进制的题目,出现转换后长度不统一时,若有需要,可以将数组的长度开到最大(如a_max = 2`32,就将数组长度设为32),前面多余没用到的设为0(例如本段代码中的 expected 和 b 就将长度均设为21)

标签:...,expectedNum,return,int,945,vector,按位,Round
From: https://www.cnblogs.com/eric13/p/18519172

相关文章

  • Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round)
    Preface这场其实是上周四VP的,因为当时马上要出发打济南站了,但因为挺久没写代码了所以打算临阵磨枪一下好家伙结果Div.2D不会做直接给人整麻了,不过好在看了眼榜把E2写了,后面发现这个D想到了就不难A.MeaningMean容易发现从小到大操作一定最优#include<cstdio>#inc......
  • FirstRound-博客中文翻译-五-
    FirstRound博客中文翻译(五)原文:FirstRoundBlog协议:CCBY-NC-SA4.0为什么这位工程领导者认为你不应该以零遗憾减员为目标原文:https://review.firstround.com/why-this-engineering-leader-thinks-you-shouldnt-aim-for-zero-regrettable-attrition作为【温室】****的首......
  • Educational Codeforces Round 171 (Rated for Div. 2)B-D
    B.BlackCells题目:思路:首先我们发现要分奇偶讨论。偶数:很简单,取a[2]-a[1],a[4]-a[3],.........a[n]-[n-1]的最大值。奇数:我只需要知道假如删除当前的这个数剩下的数最大的间隔值,注意只能删除1,3,等奇数位,因为要保证删除后左右的数为偶数。(我的代码里面是偶数位因......
  • Codeforces Round 978(div.2) D1
    #感觉挺有意思的一道题题目:思路:观察发现对于两个人a,b如果两个人里面没有Impostor那么,你得到的回答是一样的,如果有impostor那么结果不同,那么我们就可以两个两个的询问,先找到2个人里面有impostor然后在找另外一个人来询问就行了。代码:#include<bits/stdc++.h>usin......
  • Codeforces Global Round 27,D. Yet Another Real Number Problem 题解
    单调栈+贪心题意:给定一个序列从左往右对于每个索引iii,求出其前缀的数组可以进行任意次以下操作的条件下:选择......
  • Codeforces Round 981 (Div. 3) ABCDE
    CodeforcesRound981(Div.3)ABCDEA.SakurakoandKosuke藕是看样例直接猜了结论......
  • Codeforces Round 982 (Div. 2)
    CodeforcesRound982(Div.2)总结A猜结论,最后的图形的周长都能移成一个长方形的周长,这个长方形就是\(w\)和\(h\)的最大值。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<q......
  • # [Educational Codeforces Round 171](https://codeforces.com/contest/2026)
    EducationalCodeforcesRound171D.SumsofSegments定义四个前缀和:\(s_i=a_1+a_2+\dots+a_i\)\(u_i=s_1+s_2+\dots+s_i\)\(t_i=s(i,i)+s(i,i+1)+\dots+s(i,n)\)\(ts_i=t_1+t_2+\dots+t_i\)\(s_i\)为\(a_i\)的前缀和,\(u_i\)为\(s_i\)的前缀和,\(t_i\)为分块之后第......
  • Educational Codeforces Round 171 (Rated for Div. 2) 10.28 ABCD题解
    EducationalCodeforcesRound171(RatedforDiv.2)10.28(ABCD)题解A.PerpendicularSegments数学(math)计算几何(geometry)题意:给定一个\(X,Y,K\)。需要求解出二维坐标系中的四个点\(A,B,C,D\),满足:\(0\leqA_x,B_x,C_x,D_x\leqX\),\(0\leqA_y,B_y,C_y,D_y\leqY\)。并......
  • Educational Codeforces Round 171 (Div. 2)
    EducationalCodeforcesRound171(Div.2)A猜结论,两条边的最小值最大时,两条边相等。所以取\(min(x,y)\)为边长的正方形,对角线就是所求。#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>usingnamespacestd;intx,y,k;voidsolve(){......