链接 题意：平面上有n个点（互不相同）现要把所有点分成两部分A，B 并对两点P，Q之间 Euclidean distance 染***r> 当点p，q属于同一部分时 染成黄色 否则染整 蓝***r> 输出满足使 所有相同距离的颜色不同的 集合A Euclidean distance：（xi-xj）（xi-xj）+ (yi-yj) (yi-yj) 两种颜色 坐标距离 两个部分 考虑将坐标分成4个部分 00 ，01 ，10 ，11 代表坐标奇偶性 后可以构造这样两个集合 A：00,11 B：01,10 发现相同集合内的颜色全为Y 不同集合 为B 特殊情况 ： 当只有00,11； 0...

传送门 题意： 现在有一棵树 每个点有一个ci和ai ai为点权，ci代表i的子树中点权aj <ai 的个数 现在给你这棵树的形状和每个点的ci 构造所有点的ai n<2000 思路： ci大于子节点个数时显然不能构造出解； 假设当前节点有m个子节点 该点的Ci为k； 那么 就相当于将该节点的 子节点分为两部分 k个节点的权值小于ai的 m-k个节点的权值大于ai dfs即可 #include<bits/stdc++.h> using namespace std; typedef long long L; vector<int>vec[2010]; vec...

链接 题意 ： 给n个数 求x与a[i]异或的最大值最小 思路：每个数拆成2进制数建立一个trie树，在trie树上dp即可 难点主要是实现方面 对trie树建边的思想没有理解很到位 #include<bits/stdc++.h> #define warn printf("!*!!*\n") #define debug(x,c) cout<<string(c)<<":"<<x<<endl using namespace std; typedef long long L; const int...

D. Minimax Problem 二分答案，由于m<=8，所以可以把每行对于一个mid的状态存储下来， 然后枚举所有状态即可 利用二进制存储信息的思想，并分析题目的特点 ，可以很清晰的想到解法 A. Deadline n，d<1e9 求方程 x+ceil（d/(x+1)）<=n是否有解 可以看出x（0，n-1），暴力x即可（可惜并不行） 分析当n>1e5时 可以构造出这样一种解x+1=2e4，那么不等式左边一定小于7e4 不等式恒成立。 n<1e5暴力✔ E. Messenger Simulator

HDU6704 补 2019山东省赛 E 补 // 区间操作 灵活应用 静态区间第k小 普通权值线段树可以查询整体的第k小问题 而主席树就是利用这一点保存每个时刻的权值线段树，这样当查询区间第k值时就能通过相减得到这个区间的权值线段树 就相当于这个区间求整体第k值 故主席树能查询区间第k值(__) 利用重复信息保存插入每个数时的 权值线段树 那么当求l~r的区间 时 只需要 将插入第r个数时的权值线段树T【root【r】】 减去T【root【l-1】】（其中的细节要好好理解）那么我们得到的其实就是L ~ R的权值线段树了 直接按步即可 主席树要注意内存 一般开正常大小25倍 代码参考q...

传送门 区间加和区间查询 分块实现(是真慢。。。) #include<cstdio> #include<cmath> #include<iostream> #define ls rt<<1 #define rs rt<<1|1 #define warn printf("!!**!!\n") using namespace std; typedef long long LL; typedef pair<int,int>pii; const int maxn=1e6; const int mod=1e9...

莫队入门 小z的袜子 题意：n个数记ai，ai<=n m次询问：l~r区间内任意选两个数 求其相同的概率 稍微化简为 求区间内每个数出现次数的平方和 #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int>pii; typedef pair<LL,LL>pll; const int maxn=1e5; const int oo=1e9; LL a[maxn+5],cnt[maxn+5],pos[maxn+5],n,m,L=1,R=0...

bzoj2038莫队入门题目目前没有理解的几点就是 当前区间L R的初始化问题，为什么要L=1，R=0? 还有在 更新过程中出现了cnt《0的情况？ hdu6483莫队求区间不同数字种类数 当题目要求的区间操作满足以下条件时可以应用莫队 1）已知L，R区间答案可以O1求出【L-1，R】【L，R-1】【L+1，R】【L，R+1】 2）支持离线 3）数据范围最多最多不能超过1e6 ，1e5为合理数据范围 对于莫队的时间优化方面主要在于如何对离散区间进行排序 推荐使用第二种 1）分块排序 bool cmp(node a,node b) { if(pos[a.l]==pos[b.l]) re...

A Sequence Game 大意：求区间内的最大值与最小值中的数是否都出现过 看max-min+1是否等于区间数字种类数即可 前者预处理ST表 后者可用两种方法求出 1）莫队 #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int>pii; typedef pair<LL,LL>pll; const int maxn=1e5; const int mod=1e9+7; const int oo=1e9; int n,m,a[maxn+...

题目链接 求L,R内所有数字第一次出现的下标的中位数 区间第一次出现 即倒着的最后一次出现 所以我们倒着更新一个主席树 如果位置 I 的数字第一次出现 那么直接在第I颗树上的第I个位置加一即可 否则在加完1后 再在该数字的原位置减一 找BUG真的好难啊 ✔ #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int>pii; typedef pair<LL,LL>pll; const int maxn=2e5; const int mod...

P5357 对应输出n个模式串在文本串中出现的次数 AC自动机😳 坑点：可能出现重复模板串，所以标记结尾时做相应的修改即可 这里的写法是把fail树对应的图建出来了， 其实不需要建也可以求出(这不重要) void getans(void){ for(int i=1;i<=tot;i++) in[fail[i]]++; for(int i=1;i<=tot;i++) if(!in[i]) q.push(i); while(!q.empty()){ int x=q.front(); q.pop(); ...

洛谷P5357模板题 CodeForces 727E Games on a CD补 HDU – 2243 poj2778 nefuoj2027 在写AC自动机相关题目时要注意一下几点 避免浪费时间 1）使用邻接矩阵建图时要注意 将head 清空为-1 2）解决计数问题时mod运算比较费时，少用 3）搞清楚题目要求，在遍历fail树时 ，每个节点 是对他的后缀有影响，还是将它作为后缀的几点有影响，选择bfs还是dfs 4）建边时记得建反向边 即：fail→i 5）必要时通过建立new node函数减少时间复杂度 6）注意内存 7）注意所给串的 符号范围 8）其实有关题目都是相对模板化些，如果在...

想不出来啊 想不出来😟（全局变量数组开大还会RE。。。。。） 官方题解:**多模式串匹配的问题用 AC 自动机来解决。**首先用输入的这些串构建出 AC 自动机，然后用状压在 AC 自动机上对答案进行搜索。设 res[now][S][l]，表示的意思是在自动机上当前节点为 now，状态是 S，已经匹配的长度为 l，有多少种方案数。用记忆化搜索将答案统计出来，就可以了。 问题 1） 为什么可以用状压dp解决呢 当此问题没有任何限制时，本题求的即为26的n次幂。对应代码 LL dfs(int l) { if(l==n){return 1;} if(dp[l]) return d...