Even Degrees  给定一个无向图,构造一个有向图使得每个点的出度为偶数.  对这个图生成的树,从叶子结点往上分配,如果该节点的出度为偶数了那么指向根的边当做根的出度,如果是奇数那么指向根的那条边当作该节点的出度.在子节点满足条件后,判断根结点指向的那个结点是否遍历过如果遍历过那么说明子节点已经满足了,这时这条边当作根的出度.   #include<bits/stdc++.h> using namespace std; const int N=1e5+5; template<typename T>int o(T x){cout<<x<<e...

gcd查询  给定一个序列 有三种操作:   :在区间 加上 .   : 查询区间 中的 .   :查询 .    根据 的性质, ,设 是 的差分数组,对于任意一个区间  由于 的性质,在区间 加上一个数其实只对 有用所以只需要维护 数组就可以单点更新即可,求询问2刚好在差分数组上单点更新就可以.   #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=1e6; const lo...

最长子段  给定一个序列,找出最长的子段使得子段和大于 .  处理一个前缀和数组 ,假设合法区间为 ,即 ,题目就转化为求 .  解法一：线段树,将数组 从小到大排序, 相同按下标从大到小排序,每次维护一个最大值下标数组,将出现过的值删除,每次取出最大值即为所求的 . 解法二：单调栈,从头开始构造一个单调递减的数组,从后面往前扫,即答案中所求的 一定会在这个单调栈中.     线段树#include<bits/stdc++.h> using namespace std; const int N=2e6+5; template<typename T>int o(T x){...

Hopscotch Addict  给定一个有向图,一次只能走 步,问最少需要几次才能从 走到 .  从 走到 需要的步数一定是 的倍数,用一个 表示从 到 的步数 除 余 ,即 到 有 三种状态,当 存在时,说明从 到 状态为 的最短路径已找到,不必要再找一次.   #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=1e6; const long long mod=1e9+7;...

迫真小游戏  给定一棵树,每个结点有值 ,确定一个字典序最小的排列,保证在 号结点之前每个 的深度要小于等于 .  以最小的 开始找,查找深度小于等于 且结点标号最小的值,用线段树维护即可.   #include<bits/stdc++.h> #define sc scanf using namespace std; const int N=6e5+5; const int mod=1e9+7; const int oo=1e9+7; typedef unsigned long long ull; typedef long long ll; template <typenam...

1181 C.Flag  给定一个矩阵图案,找到有几种图形满足上面不等于中面,中面不等于下面.  处理高度数组 ,宽度数组 即可.对答案贡献就是 .   #include<bits/stdc++.h> #define sc scanf using namespace std; const int N=3e5+5; const int mod=1e9+7; typedef unsigned long long ull; typedef long long ll; template <typename it>int o(it a){cout<<a<<...

1182 E. Product Oriented Recurrence   . .   . .   #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=1e6; const long long mod=1e9+7; const long long M=1e9+6; const int oo=0x7fffffff; const int sup=0x80000000; typedef ...

Sum Equals Xor  You are given a positive integer in base two.How many pairs of non-negative integers satisfy the following conditions?     Since there can be extremely many such pairs, print the count modulo .  首先假设 全是 的时候,按相同长度来考虑,根据题意,如果 的第 位是 则 的第 位必须是 .所以答案就是 .算一般情况时,统计 的前 位有 个 ,后面 位答案就是 ,前 位的有 ...

K 个不同整数的子数组  给定一个数组 ,如果 中的子数组不同数的个数为 ,则称为一个好数组,统计 中有多少个好数组.  考虑尺取.首先定义一个函数 ,表示 数组中有多少个子数组 ,满足 中不同数的个数小于等于 ,然后答案就是 .算 时,定义一个 数组记录每个数出现的次数,当 这个区间不同数的个数大于 时,左指针 右移.每一次得到合法的区间 时,对答案的贡献为 .   class Solution { public: int subarraysWithKDistinct(vector<int>& A, int K) { return f(A,K)-f(A,K-1); } i...

K 连续位的最小翻转次数  在仅包含 和 的数组 中，一次 位翻转包括选择一个长度为 的（连续）子数组，同时将子数组中的每个 更改为 ，而每个 更改为 。返回所需的 位翻转的次数，以便数组没有值为 的元素。如果不可能，返回 。  如果最左边的元素是 ，那么我们一定要翻转从位置 开始的子数组。类似的，如果最左边的元素是 ，我们不应该翻转从位置 开始的子数组。这证明了我们可以贪心地执行这一过程：在明确是否要反转第一个子数组之后（位置 至 ），我们可以考虑将数组中第一个元素（值为 ）移除，然后重复这个过程。我们还可以做得更好。每次翻转一个子数组 ，我们可以考虑这样的两种事件：第一种是 “开始事件”，...

1175 E. Minimal Segment Cover 给你 个区间 ,有 个询问 ,问要覆盖 中所有的点至少需要几个区间.(覆盖的点包括实数点,比如3.5) 倍增写法.首先更新每个区间中左端点 能扩展到的最远 ,然后 ,倍增更新.查找时如果 ,则 ,因为 中 一共有 个点,无解的时候只要判断 是否大于 即可.  #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=1e6; c...

1173C - Nauuo and Cards 有 张牌,其中有 张时空牌,标号为 ,剩下的 张牌标号在 中。首先给你一个序列 表示手上的牌的标号为 ,一个序列 表示桌上的牌的标号 .每一轮从 中抽出一张牌放在 的尾部,然后 弹出,放在手中,求最小的操作次数使得 序列为 . 先把牌 的在 中的位置标记为 ,不在标记为 .只有2种情况：  当 中的序列为 这种形式时，看看能不能一次性打完,只有满足 才能打完. 当第一种不满足时,说明所有的牌必须从末尾进去在到达该指定位置,牌 从 中打出去要花费 步,再次从末尾进入到 要花费 步,所以找到 即可.    #include<bits/stdc+...

1. Lucas ll fac[N]; void N_() { fac[0]=1; for(ll i=1;i<N;i++) fac[i]=fac[i-1]*i%mod; } ll quick_mod(ll a,ll b,ll mo){ll ans=1;for(;b;b>>=1,a=a*a%mo)if(b&1)ans=ans*a%mo;return ans; } ll C(ll n, ll m) { if(m > n) return 0; return fac[n]*quick_mod(fac[m]*fac[n-m],mod-2)%mod; } ll Lucas(...

//杜教BM #include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typed...