首页 > 其他分享 >CF979D Kuro and GCD and XOR and SUM

CF979D Kuro and GCD and XOR and SUM

时间:2023-08-27 09:13:50浏览次数:37  
标签:Kuro XOR cout int Max CF979D 异或 ans 集合

题目大意

初始有一个空的集合,和 \(Q\) 个操作。对于每个操作,有两种类型,分别用如下的两种形式表示:

1 u:加入 \(u\) 到集合
2 x k s:求一个最大的 \(v\),使得:

  1. \(v+x \leq s\)
  2. \(k \mid \gcd(v,x)\)
  3. \(x \oplus v\) 最大(其中 \(\oplus\) 表示按位异或,对应 C++ 中的 ^ 运算符)

如果找不到满足条件的 \(v\),输出 \(-1\)。

思路

考虑第二个限制,我们可以转化为 \(k \mid x \land k \mid v\),那么 \(x\) 和 \(v\) 都是 \(k\) 的倍数,我们可以预处理加入集合的数 \(u\),把它加入所有它因数的集合里。

这样在后面查找 \(v\) 就直接在 \(k\) 的集合中查找就能够保证满足第二个条件。

对于查询操作,直接找到小于等于 \(s-x\) 的数,然后在集合中从大到小遍历。

知道,两个数异或值最大就是两个数的值相加,如果当前记录的最大异或值 Max 已经大于遍历到的 x + v,后面的部分肯定不会再对答案产生贡献了,可以直接退出循环。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 100500;

int n;
int opt,u,x,k,s;

set<int> S[N];
// S[i] 中的任意数 x 满足 i | x 
// 即存的是 i 的倍数 
// 用于第二个条件 

long long ans,Max;

int main() {
    cin >> n;

    for(int i = 1;i <= n; i++) {
        cin >> opt;
        if(opt == 1) {
            cin >> u;
            for(int i = 1;i <= floor(sqrt(u)); i++) {
                if(u % i == 0) {
                    S[i].insert(u);
                    S[u / i].insert(u);
                }// 记录的是其倍数 
            }
        }
        else {
            cin >> x >> k >> s;
            
            ans = -1;
            Max = -1;

            if(x % k != 0) {
                cout << "-1\n";
                continue;
            }

            set<int>::iterator it = S[k].upper_bound(s - x);
            // 找到大于 v 的最小的数 
            if(it == S[k].begin() || S[k].empty()) {
                cout << "-1\n";
                continue;
            }

            it --;
            // 现在的 it 指向的是满足第一个条件和第二个条件的最大的数

            while(it != S[k].begin()) {
                int v = *it;

                if(Max > x + v) 
                    break;
                // 异或最大值就是 x + v 
                // Max 已经超过 x + v 肯定不能更新答案 
                
                if(Max < (v ^ x)) {
                    Max = v ^ x;
                    ans = v;
                }

                it --;
            }

            if((*it ^ x) > Max)
                ans = *it;
            
            cout << ans << "\n";
        }
    }
    return 0;
}

标签:Kuro,XOR,cout,int,Max,CF979D,异或,ans,集合
From: https://www.cnblogs.com/baijian0212/p/CF979D.html

相关文章

  • [ABC098D] Xor Sum 2 题解
    题解传送门题目大意给出一个序列\(A\),求\(A_l\oplusA_{l+1}\oplus\dots\oplusA_r=A_l+A_{l+1}+\dots+A_r\)(\(\oplus\)即为\(xor\)异或)解析众所周知,异或是位运算中的一种不进位加法,即为如果两个\(bit\)相等返回\(0\),反之返回\(1\)。为什么说是不......
  • CF1787E The Harmonization of XOR 题解
    CF1787ETheHarmonizationofXOR题目大意给定\(n\)个数\([1,2,3,\cdots,n]\)和两个正整数\(k\)和\(x\)。将这些数分成恰好\(k\)组使得每组的异或和都是\(x\)。(\(1\lek\len\le2\cdot10^5,1\lex\le10^9\))。题解首先,我们知道,如果我们无法从\(n\)......
  • CF1787E The Harmonization of XOR 题解
    题面将集合\(\left\{1,2,\cdots,n\right\}\)划分为\(k\)个非空不交子集,使得每个子集的异或和均为\(x\)。(\(1\len,k\le2\times10^5\))。题解首先显而易见的判断一下无解的情况,记\(sum=\bigoplus\limits_{i=1}^{n}i\),如果\(k\)为奇数但\(sum\neqx\)或......
  • ARC137D Prefix XORs 题解
    这里的所有下标从\(\bm0\)开始。我们考察一下每次操作后的数列\(a\)会是什么样的。这里用\(a_i\)前面的系数\(x\)表示\(a_i\)贡献了\(x\)次,\(+\)表示异或。\[\begin{matrix}k=0&a_0&a_1&a_2&\cdots&a_{n-1}\\k=1&a_0&a_0+a_1&a_0+a_1+a_2&\cdots&......
  • 【XOR-HASHING】CF1175F
    XOR-HASHING一眼典。考虑对于每个数随一个longlong的权值。那么就可以有\(prx_r\oplusprv_{l-1}=base_{r-l+1}\)。这个很难直接计数,考虑增强条件。那么就是这个段一定包含1。那么就是很典的问题了,问多少个包含1的段满足上面那个柿子。然后考虑前驱后驱间形......
  • 汇编-xor异或
     XOR指令在两个操作数的对应位之间进行(按位)逻辑异或(XOR)操作如果两个位值相同(同为0或同为1),则结果位等于0;否则结果位等于1【相同为0,不同为1】      ......
  • 关于 x11 xorg wayland 的区别
           ......
  • XorDistances
    [ABC202E]CountDescendants考虑一个判断某个点\(v\)是否为另一个点\(u\)后代的方法:令\(dfn_v\)表示\(v\)的\(dfs\)序,令\(out_u\)表示离开\(u\)的子树时的最新的\(dfs\)序,由于一个子树内的\(dfs\)序是连续的,所以只要\(dfn_u\ledfn_v\leout_u\)。考虑将深......
  • XorDistances
    [ABC201E]XorDistances首先,根据\(a\oplusa=0\),一条路径\(dis(u,v)=(dis(1,\text{LCA})\oplusdis(1,u))\oplus(dis(1,\text{LCA})\oplusdis(1,v))\),消去相同的,得\(dis(1,u)\oplusdis(1,v)\)。预处理从\(1\)到每个点的前缀异或,问题被转换成从\(n\)个数中选两个两两异......
  • [CF1849F] XOR Partition
    XORPartition题目描述Forasetofintegers$S$,let'sdefineitscostastheminimumvalueof$x\oplusy$amongallpairsofdifferentintegersfromtheset(here,$\oplus$denotesbitwiseXOR).Iftherearelessthantwoelementsintheset,......