题目链接 大意：给你一个目标点，让你从(0,0)出发走k步到(n,m)，（8个方向），问你最多能走几次斜着的，或者不能到 思路：我们思考一下我们该怎么走，显然我们上来先斜着走到一个坐标为0，（从(n,m)到(0,0) ），然后我们看剩余的步数last和剩下的k，的奇偶关系。（首先要满足能走到的条件） 如果两个都是偶数的话，我们显然可以直接走完k步 如果last是偶数但是k是奇数的话，我们显然要把之前斜着走的一次给换成直着走的，然后奇数k走一次直的就成偶数了，然后剩下的再斜着走就行。 last是奇数的情况直接输出K-1就行了。。因为我们可以走到目标点的相邻点然后直着走一次就到了 #inclu...

题目链接 大意：给你一棵树，问你树上距离等于x的无序点对个数 点分治模板题，直接做 #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mp make_pair #define LL long long #define SZ(X) X.size() #define pii pair<int,int> #define ALL(X) X.begin(),X.end() using namespace std; LL gcd(LL a, L...

题目链接 大意：给你一个数组，询问一个区间仅出现一次的数。 思路：我们记录每个位置x左边的第一个相同数的位置y，记为这个x的值为y，如果左边没数的话就是0，然后询问的区间必然是满足存在一个 t , t ∈ [ l , ...

题目链接 树套树模板 #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define LL long long #define pii pair<int,int> #define SZ(x) (int)x.size() #define all(x) x.begin(),x.end() using namespace std; LL gcd(LL a, LL b) {return b ? gcd(b, a % ...

题目链接 大意：m个城市，给你前n年的举办城市，之后的每一年都会让举办次数最少且标号最小的城市举办一次，给你q组询问让你求出第k年的举办城市。 思路：首先，对m个城市按举办次数从小到达排序，建一颗主席树，然后每次举办的城市显然是在一些举办次数相同且最小的城市中轮换，那我们就预处理出每种等级的城市升级到下一个等级一共需要多少次（按举办次数分等级），然后每次询问就二分一下是从哪个等级升过来的，然后在主席树上查一下区间第x小就行了。 细节有一些需要注意： #include<bits/stdc++.h> #define fi first #define se second #defin...

题目链接 题意：给以 一个数组，给你一些询问，每次询问给出 p , k p,k p,k，可以执行一些操作，每次操作会使得 p − > ...

题目链接 大意：有n个人，每个人有两个参数 a , b a,b a,b，表示第 i − t h ...

题目链接 大意：有两个数组a，b，你可以把任何一个数组的任何一个位置的元素复制到任何一个数组的任何一个位置，你需要使得两个数组中的任意两个位置（分别来自两个数组）都存在于一个相同的位置，复制的代价是元素值，问最小代价？ 思路：显然我们有两种策略： 1.把一些位置都复制到一个位置上，那么这些位置就都满足 2.对于一个数组的一个位置来说，每次选择把自己复制到另一个数组的某个位置，或者把另一个数组的某个位置复制到当前位置上（根据大小来定）。 先对两个数组按元素值从小到大排序。 那么我们枚举这两种操作的分界点来统计最小答案即可。 细节见代码： #include<bits/stdc++.h&gt...

题目链接 思路：把题目中的绝对值式子拆开 那么答案就是 m a x { <mtext>    </mtext> <munderover> ∑ ...

题目链接 题意：给你两个长度为n,m的排列a,b，然后让你支持两个操作： 1.询问a排列上[l1,r1]区间和b排列上[l2,r2]区间相同元素的个数。 2.交换b排列上c,d位置的元素 思路 ：我们可以建立一个长度m的数组c，其中第 i i i个元素表示b[i]在a中的位置，那么显然答案就是c数组[l2,r2]中值在[l1,r1]的个数了。 直接上树状数组套主席树即可在线解决这个问题，注意要回收空间。 #include<bi...

题目链接 大意：给你一个n*n的矩阵和k，让你往每个单元格填1-k的数，使得每行每列的最小值都是1.问有多少种构造方法。 思路：考虑 d p [ i ] [ j ] ...

题目链接 大意：给你一个无向带权图，给你一些询问点， s , t s,t s,t，你从s出发有 l l l升的油，走 ...

题意：给你两个矩阵让你求出最大相同的子矩阵的面积。 两个矩阵中的元素是两个1到n*m的排列 思路：广告牌问题 先预处理出每个元素向上最远到达的地方。 然后枚举底边，对每个底遍历右边界，维护一个单调递增的单调队列，中间在维护一下每个元素最左到达的地方。 每次出队的时候更新一下答案，出队的时候因为是新值小于队尾的值，所以是以自己为基准，所以更新答案是： a n s = ...

给你一个式子 ∑ a = 2 n ( a ...