https://codeforces.com/contest/1304/problem/E 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxbit = 20; 5 const int maxn = 1e5+5; 6 vector<int> G[maxn]; 7 int depth[maxn]; 8 int fa[maxn][maxbit]; 9 int Log[ma…

A. Two Rabbits （手速题） 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int main(){ 5 int t; 6 cin>>t; 7 while(t--){ 8 ll x,y,a,b; 9 cin>>x>>y>>a>>b; 10 ll sum = a+b; 11 if((y-x)%sum == 0){ 12 cout<…

1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod = 1e9+7; 5 struct Matrix { 6 int a[3][3]; 7 Matrix() { memset(a, 0, sizeof a); } 8 Matrix operator*(const Matrix &b) const {//重载矩阵乘法 9 Matrix res; 10 for (int i …

链接：https://codeforces.com/contest/1288/problem/D D. Minimax Problem 题意：给定n个数组，长度为m，从n中数组挑选两个数组，两个数组中的每一位取两者的最大值组成一个新的数组，新数组中的最小值记为c，所有组合中c的最大值   思路：题目中m的范围只有8，数组中元素的范围是1e9，显然m的范围非常特殊，似乎可以把数组用二进制的形式进行状态压缩，这里采用二分答案的方法。二分范围是数组元素最小值到最大值，每次check(mid)一遍，check的时候对于每个…

链接 https://codeforces.com/problemset/problem/1284/E 题意：平面上有ｎ个点，问你存在多少组四个点围成的四边形 严格包围某个点P的情况。不存在三点共线。 思路：首先看数据范围是2500，可以做n^2的枚举，我们可以枚举两遍n。正面求解有些困难，反面求解可以考虑有多少组子集不满足题目要求，拿总的子集数量减去不满足的就是答案。 那么考虑不满足题意的点集。 首先如果对于一对点P和P1，让它们连线，以P为基准，相对度数为0度，枚举P和P1这个条线以上的所有点，假设枚举出n个点…

  使用逆康托展开打阶乘表快速求解   逆康拖展开是从自然数到序列的映射 例如： 在（1，2，3，4，5)  给出61可以算出起排列组合为34152 具体过程如下： 用 61 / 4! = 2余13，说明  ,说明比首位小的数有2个，所以首位为3。 用 13 / 3! = 2余1，说明  ，说明在第二位之后小于第二位的数有2个，所以第二位为4。 用 1 / 2! = 0余1，说明  ，说明在第三位之后没有小于第三位的数，所以第三位为1。 用 1 / 1! = 1余0，说明  ，说明在第二位之后小于第四位的数有1个，…

https://nanti.jisuanke.com/t/42387 x的数据范围只有2~10，也就是说x只可能含2、3、5、7这四个因子，那么就可以用等价于4棵线段树的数据结构去维护区间4个素因子的信息了。 用线段树维护区间Pot(ai)的最大值，每次区间修改，只需使区间修改2、3、5、7这四个素因子个数，最大值查询也只需查询2、3、5、7四个素因子的max值。 注意用scanf和printf输入输出，否则cin、cout T到自闭。 1 #include<bits/stdc++.h> 2 using…

例题洛谷 P4017：https://www.luogu.com.cn/problem/P4017   求最大食物链的数量，题中已给出最大食物链的定义，可以转化定义一条链的起点就是入度为0的点，出度为0的点可以作为终点。注意食物网抽象出的有向图可能有多个。 思路：只需一遍拓朴排序，动态累计记录一下答案即可，最终累加输出到终点的最大食物链数量即可。 模板: 1 bool toposort() { 2 q = new queue(); 3 for (i = 0; i < n; i++) 4 if (in_deg[…

https://codeforces.com/contest/1328/problem/E 题目所描述的是一棵树，题中已明示1为root结点。 题目可以转化为，是否存在一条路径，满足集合中的k个点到路径的距离小于等于1？ 思路： 1.首先倍增离线预处理出结点深度，便于后续在线询问LCA 2.对于每次的询问，依次扫描k个点。对于集合中的u和v两点，每次我们求出u和v的LCA，计算u和v到LCA的距离，如果u和v到LCA的距离同时大于1，那么说明无法找到一条路径，使得u和v到该路径链的距离小于等于1。 3.对于k个点如…

https://codeforces.com/contest/1328/problem/F   首先把a数组处理成pair对（num,cnt），表示数字num有cnt个，然后按num升序排序离散化一下。 对于一个数x，若想使得小于x的数字都变成x，必须先把所有小于x的数变成x-1，然后再+1变成x。 同理，要使得大于x的数变成x，必须把所有大于x的数字变成x+1，然后再-1变成x。 以上是题意所要求的必须操作。 思路： 1. 用f[i]数组记录离散化后前i大的数字的总数，那么对于任意第i大数字，可以靠f[i]数组轻…