首页 > 其他分享 >CF2014H Robin Hood Archery(异或哈希)

CF2014H Robin Hood Archery(异或哈希)

时间:2024-09-28 17:34:31浏览次数:6  
标签:std Archery int pref CF2014H cin i64 ++ 异或

题目链接

题意

AliceBob 将进行一场射击比赛

题解

点击查看代码
#include <bits/stdc++.h>

using i64 = long long;

i64 seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937_64 rng(seed ^ std::random_device{}());

constexpr int M = 1E6 + 5;

i64 hash[M];

void solve() {
  int n, q;
  std::cin >> n >> q;

  std::vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }

  std::vector<i64> pref(n + 1);
  for (int i = 0; i < n; ++i) {
    pref[i + 1] = pref[i] ^ hash[a[i]];
  }

  for (int i = 0; i < q; ++i) {
    int l, r;
    std::cin >> l >> r;

    if ((r - l + 1) % 2) {
      std::cout << "NO\n";
      continue;
    }

    --l;
    std::cout << ((pref[r] ^ pref[l]) == 0 ? "YES\n" : "NO\n");
  }
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

  for (int i = 1; i < M; ++i) {
    hash[i] = rng() % i64(1e18);
  }

  int T;
  std::cin >> T;

  while (T--) {
    solve();
  }
  return 0;
}

标签:std,Archery,int,pref,CF2014H,cin,i64,++,异或
From: https://www.cnblogs.com/LDUyanhy/p/18438196

相关文章

  • [CL-22] 异或和之和
    CL-22二进制拆分。对于枚举到的每一个二进制位\(i\),注意到其对答案的贡献只有\(0\)和\(2^{i}\)两种情况考虑什么时候贡献是\(2^i\),可以发现,当选入奇数个该位为\(1\)的数之后,对答案的贡献是\(2^{i}\)因此变成求选出奇数个为\(1\)的数的方案数设该位为\(1\)的数有......
  • 题解:P10104 [GDKOI2023 提高组] 异或图
    \(\text{Link}\)本题属于集合划分容斥,更多关于集合划分容斥的信息可观看详细揭秘:集合划分容斥的容斥系数。题意给定一个\(n\)个点\(m\)条边的图以及一个长为\(n\)的序列\(a_{1\dotsn}\),有一常数\(C\),你需要求出有多少序列\(b_{1\dotsn}\)满足\(0\leb_i\lea_i\)......
  • 关于异或哈希
    Re:疑惑异或哈希异或哈希是个很神奇的算法,利用了异或操作的特殊性和哈希降低冲突的原理,可以用于快速找到一个组合是否出现、序列中的数是否出现了\(k\)次算法如其名,异或+哈希。想起某首歌叫PPAP?Ihavea\(\oplus\),Ihavean\(hash\).(Uhh~)\(\oplushash\)!......
  • 异或线性基
    问题给定一个数组\(A=[a_1,a_2,...a_n]\),其中\(a_i≤2d\),在A中选择元素的某个子集,并将它们XOR。求你能得到的不同元素的个数。思路显然可以得到一个效率非常劣的做法x[0].insert(0);for(inti=1;i<=n;i++){x[i]=x[i-1];for(autocur:x[i-......
  • 异或线性基
    我们考虑这样一个问题:给定\(N\)个整数\(A_1,A_2,\dots,A_N\)。求能异或出多少种不同的值。我们考虑用一个集合\(S\)记录目前能凑出来的数字。当我们要加入\(A_i\)时,如果\(A_i\not\inS\),则\(x\oplusA_i(x\inS)\)一定都不在\(S\)中,否则可以通过\((x\oplusA_i)\o......
  • 使用docker-compose搭建数Archery据库审核平台并简单测试
    Archery是一个开源的数据库审核平台,在日常数据库操作中,可以对操作进行审核。官网:https://archerydms.com/https://gitee.com/rtttte/Archery目前有业务使用需求,先用docker-compose部署,后期考虑配置到k8s上。目前最新版本是v1.11.3参考文档 https://archerydms.com/installation/do......
  • P4551 最长异或路径(树上前缀异或01-trie)
    #include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefvector<int>......
  • P10471 最大异或对 The XOR Largest Pair(01trie)
    #include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefvector<int>......
  • 信息学奥赛初赛天天练-88-CSP-S2023阅读程序1-数据类型、unsigned 关键字、二进制、位
    信息学奥赛初赛天天练-88-CSP-S2023阅读程序1-数据类型、unsigned关键字、二进制、位运算、左移、右移、异或运算PDF文档公众号回复关键字:202409132023CSP-S阅读程序1判断题正确填√,错误填⨉;除特殊说明外,判断题1.5分,选择题3分,共计40分)01#include<iostream>......
  • 异或的一些性质
    1.异或:相同为0不同为1\[0\oplusn=n\]\[n\oplusn=0\]2.异或定理\[4i\oplus(4i+1)\oplus(4i+2)\oplus(4i+3)=0\]证明:由于异或按位进行操作,将\(4i\)、\(4i+1\)、\(4i+2\)、\(4i+3\)二进制右移两位之后,得到\(4\)个偶数,其数值都为\(i\),因此,右移之后的异......