CF 979D Kuro and GCD and XOR and SUM(异或 Trie)
2024-09-07 19:01:36
CF 979D Kuro and GCD and XOR and SUM(异或 Trie)
给出q(<=1e5)个操作。操作分两种,一种是插入一个数u(<=1e5),另一种是给出三个数x,k,s(<=1e5),求当前所有u中满足,k|u,x+u<=s,且\(x\oplus u\)最大的u。
做法好神啊。关于异或的问题有一种常见做法,就是利用01trie来查找在一堆数里面,哪个数与x的异或值最大。这道题就是这个思路。如果去掉k必须整除v这个条件,那么就转化成了上一个问题(只不过有最大值的限制,怎么解决具体看代码)。
这道题的做法非常神奇。我们建1e5个Trie,第i个Trie中插入值为i的倍数的数。这样,查询x,k,s时,只要查询第k个Trie即可,因为里面的数一定满足k|v。插入时要遍历u的所有因数si,然后将u插入第si个Trie。
注意,异或运算是在尾部对齐的,但是要在Trie上贪心,所以必须在插入和查询的数前补零,使他们长度相同。
分析一波复杂度:
- 预处理:我们需要预处理出u的因数。u的最大值为Max=1e5。用类似筛法的方法,时间复杂度是\(O(Max(1+\frac{1}{2}+\frac{1}{3}...+\frac{1}{Max}))=O(MaxInMax)\)。
- 查询:就是Trie上的查询,总时间复杂度为\(O(qlog_2Max)\)。
- 插入:一个数最多只有\(log_2(Max)\)个因数(\(2*10^9\)内因数最多的数之一是1837836000,有1536个因数),所以总的时间复杂度为\(O(qlog^2_2(Max))\)。
- 空间复杂度:最多插入\(qlog_2(Max)\)个数,因此空间复杂度为\(qlog_2^2(Max)\)。
果然只能膜拜膜拜。
#include <cstdio>
#include <vector>
using namespace std;
const int maxnum=1e5+5, maxq=1e5+5, maxn=maxq*17*17, INF=1e9;
//maxnum指插入的数的最大值 maxq指查询的最多数目
//maxn指结点的最多数目(=maxq*插入几个trie*插入数的二进制长度)
int s[maxn][2], minm[maxn], v[maxn], tot;
int q, root[maxnum], use[maxnum];
vector<int> div[maxnum];
void init(){
for (int i=1; i<maxnum; ++i)
for (int j=i; j<maxnum; j+=i)
div[j].push_back(i);
}
//把x插到对应的trie里,注意维护子树中的最小数 l:处理到从左到右第几位
void insert(int &now, int x, int l){
if (!now){ now=++tot; minm[now]=INF; }
minm[now]=min(minm[now], x);
if (l==-1){ v[now]+=x; return; }
if ((x>>l)&1) insert(s[now][1], x, l-1);
else insert(s[now][0], x, l-1);
}
//要找到v<=lim,并且x^v尽量大(贪心)。函数返回v
//注意由于没有删除操作,路径底下一定有点。
int query(int now, int x, int lim, int l){ //l:第几位
if (l==-1) return v[now];
int s0=s[now][0], s1=s[now][1];
if (!s0||minm[s0]>lim) return query(s[now][1], x, lim, l-1);
if (!s1||minm[s1]>lim) return query(s[now][0], x, lim, l-1);
if ((x>>l)&1) return query(s[now][0], x, lim, l-1);
else return query(s[now][1], x, lim, l-1);
}
int main(){
init();
scanf("%d", &q); int op, x, k, s;
for (int i=0; i<q; ++i){
scanf("%d", &op);
if (op==1){
scanf("%d", &x);
if (use[x]) continue; use[x]=1;
for (int j=0; j<div[x].size(); ++j)
insert(root[div[x][j]], x, 18);
} else {
scanf("%d%d%d", &x, &k, &s);
if (x%k||!minm[root[k]]||minm[root[k]]+x>s) puts("-1"); //注意可能没有一个数
else printf("%d\n", query(root[k], x, s-x, 18)); //保证一定有解
}
}
return 0;
}
最新文章
- viewgager
- IIS 7.0 部署MVC
- 查看SSIS Package 部署的历史记录
- BZOJ1579 [Usaco2009 Feb]Revamping Trails 道路升级
- python_Day1_基础知识开篇
- HashSet与HashMap、Hashtable
- 【转】发布python的包至pypi服务器
- PDO操作mysql数据库(一)
- JavaScript 应用开发 #4:切换任务的完成状态
- Java学习----接口
- 素数判定 AC 杭电
- C#Equal的使用
- jquery-1.10.2.min.js之Multiple markers at this line
- MYSQL中取当前年份的第一天和当前周,月,季度的第一天/最后一天
- Cocos2d-x 2.2.3 Android配置
- python学习笔记(一)元组tuple
- ThinkPHP中处理Layout模板的问题
- Windows Server 2016-部署RODC只读域控制器
- IO流的种类
- Linux常用命令4(grep、df、du、awk、su、ll)
热门文章
- 分享知识-快乐自己:Spring切入点的表达式和通知类型
- node.js+express+jade系列二:rotue路由的配置
- http接口测试框架-构想图
- Netty组件理解(转载)
- 关于自动化与vTable两种暴露接口的区别-1未完......
- SPOJ375Query on a tree I(树剖+线段树)(询问边)
- bzoj 4103: 异或运算 可持久化Trie
- [转]关于新一轮QQ Tencent://Message 在线联系
- 【转】 Pro Android学习笔记(七四):HTTP服务(8):使用后台线程AsyncTask
- Python-通过socket实现一个小型的端口检测工具