首页 > 其他分享 >洛谷题单指南-字符串-P6824 「EZEC-4」可乐

洛谷题单指南-字符串-P6824 「EZEC-4」可乐

时间:2024-11-04 16:59:11浏览次数:3  
标签:洛谷题 位是 之后 异或 P6824 EZEC 如果 范围

原题链接:https://www.luogu.com.cn/problem/P6824

题意解读:已知整数序列a[i],i在1~n,有整数k,求一个整数x,要求a[i] ^ x <= k,使得符合要求的a[i]数量最多,求这个数量。

解题思路:

1、确定x的范围

由于a[i] ^ x <= k,因此,x的有效二进制位不可能超过a[i],而a的取值范围<=1000000,因此x差不多最多20位,取值范围是0~2^20 - 1

2、分情况讨论

对于每一个a[i],枚举a[i]和k的每一个二进制第j位(第一位是0),设定初始x = 0

如果k的第j位是1:

  当a[i]的第j位是1:  

    x的第j位如果取1,异或之后得0,j之后随便取都能保证结果比k小,因此得到一个有效的x的范围 [x + (1 << j), x + (1 << j + 1) - 1]

    x的第j位如果取0,还需要继续处理j之后的二进制位,此时x的值依然是x 

  当a[i]的第j位是0:

    x的第j位如果取0:异或之后得0,j之后随便取都能保证结果比k小,因此得到一个有效的x的范围[x, x + (1 << j) - 1]

    x的第j位如果取1:还需要继续处理j之后的二进制位,此时x的值更新为x + (1 << j)

如果k的第j位是0:

  x的第j位必须和a[i]的第j位一致,异或之后才得0,才能保证结果不超过k,此时x根据a[i]第j位的情况来更新

    如果a[i]第j位是1,x更新为x + (1 << j),否则x值还是x

最后得到的x也是一个有效的x

3、差分统计

对于以上分情况讨论中,得到的有效x的区间,最后统计一个覆盖最多的x的即可,可以借助于哈希数组

定义数组s[1 << 20],s[i]表示满足a ^ i <= k的a的数量

当找到一个有效的x的范围,对范围内每一个元素加1即可,如何快速实现区间加1?可以借助于差分数组,定义c[1 << 20]来进行区间加1操作,最后再还原s数组,找到s中最大值即是答案。

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005, X = (1 << 20); //X取值范围,是a[i]对应值的有效二进制位的最大值
int n, k, a[N], c[X], s[X], ans;

//利用差分数组c[]将l~r区间每个数加上1
void update(int l, int r)
{
    c[l]++;
    c[r + 1]--;
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for(int i = 1; i <= n; i++) //对每一个a[i]按位与k进行比较
    {
        int x = 0; //x初始值
        for(int j = 20; j >= 0; j--) //枚举a[i]和k的每一位
        {
            if(k >> j & 1) //k的第j位是1
            {
                if(a[i] >> j & 1) //a[i]的第j位也是1
                {
                    //x的第j位如果是1,后面是多少都可以满足
                    //对应到x的取值范围是x + (1 << j) ~ x + (1 << j + 1) - 1
                    update(x + (1 << j), x + (1 << j + 1) - 1);

                    //x的第j位如果是0,还要继续看后面的,此时第j位的0对x没有贡献
                }
                else  //a[i]的第j位是0
                {
                     //x的第j位如果是0,后面是多少都可以满足
                     //对应到x的取值范围是x ~ x + (1 << j) - 1
                     update(x, x + (1 << j) - 1);

                     //x的第j位如果是1,还要继续看后面的,此时第j位的1对x有贡献
                     x += (1 << j);
                }
            }
            else //k的第j位是0
            {
                //x的第j位必须与a[i]的第j位相同,然后继续看后面的
                if(a[i] >> j & 1)
                {
                    x += (1 << j);
                }
            }
        }
        //最终得到的x是符合要求的
        update(x, x);
    }

    ans = c[0];
    s[0] = c[0];
    for(int i = 1; i < X; i++)
    {
        s[i] = s[i - 1] + c[i]; //还原前缀和
        ans = max(ans, s[i]); //取最大值即得到x能满足的最多的a[]的数量
    }
    printf("%d", ans);

    return 0;
}

 

标签:洛谷题,位是,之后,异或,P6824,EZEC,如果,范围
From: https://www.cnblogs.com/jcwy/p/18520267

相关文章

  • 洛谷题单指南-字符串-P3369 【模板】普通平衡树
    原题链接:https://www.luogu.com.cn/problem/P3369题意解读:平衡树的基本操作,模版题。解题思路:1、二叉搜索树-BST二叉搜索树满足这样的性质:每一个节点的权值大于它的左儿子,小于它的右儿子。对BST进行中序遍历,将得到一个从小到大的有序序列,因此BST是为了维护一个有序序列的动态......
  • 洛谷题单指南-字符串-P4735 最大异或和
    原题链接:https://www.luogu.com.cn/problem/P4735题意解读:已知长度为n的数组a[],要在l~r范围找到一个p,使得a[p]^a[p+1]^...^a[n]^x最大,求这个最大的异或值。解题思路:1、利用前缀和将问题转化设s[]是a[]的前缀异或数组,要计算a中一段范围l~r的异或,可以借助于s由于s[r]=a[0]^a[......
  • 洛谷题单指南-字符串-P2922 [USACO08DEC] Secret Message G
    原题链接:https://www.luogu.com.cn/problem/P2922题意解读:已知M个01串,给出N个01串,对于N个串的每一个,求在M个串中有多少与其有公共前缀,且前缀长度是两个串中较小者。解题思路:用Trie树存储M个01串,用cnt1[]记录某个节点结束的01串个数,cnt2[]记录经过某个节点的01串的数量对于N个0......
  • 洛谷题单指南-字符串-P2375 [NOI2014] 动物园
    原题链接:https://www.luogu.com.cn/problem/P2375题意解读:计算字符串所有子串的不重叠相同前后缀数量。解题思路:1、KMP+暴力通过Next数组,可以计算所有子串相同前后缀的数量然后枚举Next数组,通过回跳Next[j]、Next[Next[j]-1]、Next[Next[Next[j]-1]-1]......来统计长度小于......
  • 洛谷题单指南-字符串-P3435 [POI2006] OKR-Periods of Words
    原题链接:https://www.luogu.com.cn/problem/P3435题意解读:定义字符串a是b的周期,当a是b的真前缀,且b是aa的前缀。给定字符串s,求s每一个前缀的最大周期长度之和。解题思路:针对字符串babababa进行样例模拟:前缀子串  最大周期  周期长度b空0ba空0babba2......
  • 洛谷题单指南-字符串-Test
    原题链接:https://www.luogu.com.cn/problem/CF25E https://codeforces.com/contest/25/problem/E题意解读:给定a,b,c三个字符串,求包含a、b、c的最短字符串长度。解题思路:要得到包含a、b、c的字符串,可以通过a、b、c连接形成,而要使得连接后的字符串最短,可以尽可能的利用重叠部分......
  • 洛谷题单指南-字符串-P1470 [USACO2.3] 最长前缀 Longest Prefix
    原题链接:https://www.luogu.com.cn/problem/P1470题意解读:求s最长前缀长度,使得可以拆解成p集合中的字符串解题思路:动态规划:设s字符串下标从1开始,p集合用set<string>保存所有的元素状态表示:设f[i]表示前i个字符s[0~i-1]是否能拆解成p中的元素状态计算:对于j=i-1开始往后倒......
  • 洛谷题单指南-字符串-P5283 [十二省联考 2019] 异或粽子
    原题链接:https://www.luogu.com.cn/problem/P5283题意解读:n个整数,每次从从取l~r的数进行异或得到美味值,一共取k次,并计算这k个美味值之和的最大值。解题思路:1、如何O(1)的计算l~r数的异或,得到美味值可以借助前缀和思想,a[i]为第i个数,s[i]表示a[1]~a[i]每个数的异或值,要计算l~r的......
  • 洛谷题单指南-字符串-P2580 于是他错误的点名开始了
    原题链接:https://www.luogu.com.cn/problem/P2580题意解读:给n个字符串,再依次处理m个字符串,对于每个字符串,如果在前面n个字符串中输出OK,如果不在n个字符串中输出WRONG,如果在n个字符串中且不止一次查询过输出REPEAT。解题思路:1、set/map方法很简单直接,用set存下前n个字符串,map......
  • 洛谷题单指南-字符串-P1481 魔族密码
    原题链接:https://www.luogu.com.cn/problem/P1481题意解读:在n个字符串中找到最长的词链长度,定义字符串a、b、c可以形成词链,即a是b的前缀、b是c的前缀。解题思路:1、Trie树定义Trie树,也称前缀树、字典树,核心思想是将字符串拆解为单个字符,每个字符是树的一条边,节点是字符添加到树......