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…
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 题意:平面上有n个点,问你存在多少组四个点围成的四边形 严格包围某个点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]数组轻…
COPYRIGHT © 2022 zhizhesoft. ALL RIGHTS RESERVED.