上面就是我的丑图hh，一般主席树开40倍空间就可以了，每次插入的时候只需要比较前一个版本和这一个版本就行了，然后每个版本是区间可减的，比如询问l到r之间的第k大，只需要处理r-(l-1）版本的数量即可。 #include<bits/stdc++.h> using namespace std; const int N=200010; struct node{ int l; int r; int sum; }tr[N*40]; int cnt; int a[N]; int root[N]; vector<int>v; int getid(int x) { ...

要保证数据随机化 操作1 ：区间加 操作2 ：区间赋值 操作3 ：区间和 操作4 ： 区间幂次和 #include<stdio.h> #include<string.h> #include<algorithm> #include<map> #include<string> #include<math.h> #include<vector> #include<queue> #include<stack> #include<iostream> #include<sstre...

#include<bits/stdc++.h> using namespace std; #define x first #define y second #define int long long typedef long long ll; const int N=100010; struct node{ int l; int r; int sum; int maxv; }tr[N*20]; int n; int w[N],col[N],dfn[N],h[N],ne[N*2],idx,e[N*2],top[N],son[N],sz[N],fa[N]; int ...

题意 ： 给定一个带权有向图 问从1到n的路径中恰好为w的方案数。 思路： 拆点 由于边权<=9 那么我们拆成9个点， 记得将每相邻的两个点从前面一个点连向后一个点，都边权为k的时候 将第k个点连向对应的点，然后矩阵快速幂。 ac代码： #include<bits/stdc++.h> using namespace std; const int N=110; const int mod=2009; int g[N][N]; int e[N][N]; int n,m; void mul(int a[][N],int b[][N],int c[][N]) { int tem...

题意：有m对好朋友关系 每个人有不同的想法， 每个人可以改变自己的想法，如果改变的话会让答案值+1 问好朋友之间冲突的个数最小值。 思路： 把不同的想法的点，分别与S和T连边，如果两个人之间是好朋友就代表可能会有冲突，那么就连双向边。 #include<bits/stdc++.h> using namespace std; const int N=5510,M=N*100*2; int h[N],ne[M],e[M],idx,d[N],cur[N],q[N],f[M]; void add(int a,int b,int c) { e[idx]=b,ne[idx]=h[a...

给定n个变量 给定m对关系 例如 aVb !aVb 让你构造出一组布尔值解满足题目要求 就是2sat的模板 把拓扑序后面的点当做可行解 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define debug printf("---\n"); const int N=2000010,M=2000010; int h[N],ne[M],e[M],idx,top,id[N],dfn[N],low[N],stk[N]; bool instk[N]; void add(int a,...

给定一棵完美二叉树的后序遍历，求完美二叉树的层次遍历。 只需要求出该树的左右儿子的数量即可 #include<bits/stdc++.h> using namespace std; typedef long long ll; int n; struct node{ int lnum; int rnum; int sz; int val; }tr[N]; int a[N]; vector<int>dep[N]; void build(int u) { tr[u].sz=1; if((u*2)<=n) build(u<<1...

给定 n 个长度不超过 50 的由小写英文字母组成的单词，以及一篇长为 m 的文章。 请问，有多少个单词在文章中出现了。 #include<bits/stdc++.h> using namespace std; const int N=10010,S=55,M=1000010; char str[M]; int tr[N*S][26],q[N*S],idx; int cnt[N*S]; int ne[N*S]; void add() { int p=0; for(int i=0;str[i];i++) { int t=...

思路：其实就是求每个单词的前缀中有多少后缀出现过某个单词，如果正向通过单词来枚举每个后缀，复杂度过高，那么我们反着枚举，然后惊奇的发现，这不就是next数组吗！那么就是把原题转化成了一个dag图，只需要把某个后继点的值累加到每个前缀就可以了，最后在插入的时候记录下每个单词的的位置，由于是dag图，我们将bfs的序列反着遍历，把f数组的当前值累加到前驱即可，这样就等价于把他的值给了所有前驱节点。最后查询f[位置]即可。 #include<bits/stdc++.h> using namespace std; const int M=1000010; char str[M]; int...

题意：去除一个数让所有前缀的最后一个数最大的个数最多。 思路：对于 任意j<i 如果去除j能让i成为最大值，那么 在a[j]是1~i的最大值且a[i]是次大值，那么启发我们从前往后扫描的时候维护最大和次大这两个变量，如果当前的x比最大值大，那么去除x对答案贡献为-1，如果x比次大值大，去除最大值对答案贡献为1,因为x是除去最大值的最大值。 #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; #define int long long int a[100010]; signed main() {...

题目类型 取石子 取到最后一粒石子就算输 Anti-SG游戏 决策集合为空的操作者胜 其余规则与SG游戏一致 这种游戏有一个特殊的解决工具：SJ定理 我们先来看一下SJ定理的内容 SJ定理 对于任意一个Anti-SG游戏，如果定义所有子游戏的SG值为0时游戏结束，先手必胜的条件： 游戏的SG值为0且所有子游戏SG值均不超过1 游戏的SG值不为0且至少一个子游戏SG值超过1 游戏的sg值就是nim的sg值。

题目链接 题意：给定一个01串，操作有区间取反 区间赋1 区间赋0 查询区间1的个数 和连续1的个数。 思路：维护双lazy，注意当置成全0或者全1的时候清空懒标记，如果区间取反那就不要清空懒标记，因为区间取反和前面01序列的取值是有关的。 #include<iostream> #include<cstring> using namespace std; const int N=100010; struct node{ int l; int r; int lnum0; int lnum; int rnum0; int rnum; int max...

题目链接 题意：连接n个单词使得前后两个单词 公共后缀与前缀去掉重复的。 思路：一开始 想的哈希 ，想不到 kmp 结果看了题解 原来这么简单，直接从后缀开始匹配 最后匹配的j就是结尾匹配的长度。注意哈希要双模数，防止北卡。 h a s h hash hash #include<bits/stdc++.h> using namespace std; //typedef long long ll; #define debug printf("---\n"); const int N=210,M=10010; #define debug(a) cout<&...

题目链接 题意 ： 给你一棵树，每个点有一个零食 ，某个人从1号根节点出发，每次尽量走最近的点，最后走完回到1号点，问最小的k。 思路：本来想的是二分+check 发现不可做啊，然后看了别人的题解，原来是有规律的，这道题确实和ccpc秦皇岛的蛮像，也是用的树形dp和贪心的结合，假设我们以u为根（u不是根节点的情况），那么对于每个儿子v所要满足 k > = f [ v ] + 2 k>=f[v]+2 k>=f[v]+2 其中k是能走的最大的范围 f[v]是子节点最浅的位置，由于这个题的特殊性，每次遍历完子树，必然会停在某个叶子节点上，然后再从叶子节点转向另外一个子树，那么走的...