莫队：O() 算法：算法核心是分块与排序。分块是将数组分成大小为的几块，然后对左端点所在块的编号进行排序，如果相等则按照右端点进行排序。 大佬博客：https://www.cnblogs.com/WAMonster/p/10118934.html 题目：https://www.luogu.com.cn/problem/P2709 #include <bits/stdc++.h> #include <iostream> #include <cstdio> #define ll long...

数论小知识： x|y 表示y能被x整数 1-n中的数的因子个数最大为n的二进制位数。看题：https://ac.nowcoder.com/acm/contest/8282/A n内既是2的倍数又是3的倍数的个数有： n/lcm(2,3)个 阶乘 https://ac.nowcoder.com/acm/problem/22942 #include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <algorithm> #include &...

1：数列极限 https://ac.nowcoder.com/acm/problem/50166 思路： 考虑3个数a,b,c. a < b < c,有三种取法： m1 = (ab+1)c = abc + c m2 = (ac+1)b = abc + b m3 = (bc+1)a = abc + a m1 > m2 > m3 可以看出来要最后值最大的话优先取两个小的数，值最小的话优先取两个最大的数。 #include <bits/stdc++.h> #include <iostream> #include <cstdio> ...

https://leetcode-cn.com/problems/minimum-swaps-to-arrange-a-binary-grid/ 排布二进制网格的最少交换次数：贪心+后缀 注意：题目只能交互相邻的两行 大佬题解：https://leetcode-cn.com/problems/minimum-swaps-to-arrange-a-binary-grid/solution/c-tan-xin-hou-zhui-0-by-spacex-1/ class Solution { public: int minSwaps(vector<vector&...

储物点的距离 https://ac.nowcoder.com/acm/problem/14683 思路： 1：首先预处理三个前缀和，a--前i个储物点的距离和，x_sum--前i个储物点的东西搬到第一个储物点的和，n_sum前i个储物点的东西和. 2：判断x与l和r的大小，如果x>=r,那么就先把[l,r]的东西全部搬到储物点1去，然后在全部搬到x点去，我们可以发现对于每个在[l,r]里面的j，[1,j]是重复搬了的，那么我们要减去，也就是减去x_sum[r]+x_sum[l-1]。 3：如果x<=l,也是先把[l,r]的东西全部搬到储物点1去，然后在全部搬到x点去，...

第226场周赛 https://leetcode-cn.com/contest/weekly-contest-226/ 3：前缀和 https://leetcode-cn.com/problems/can-you-eat-your-favorite-candy-on-your-favorite-day/ class Solution { public:     typedef long long ll;     long long&...

https://ac.nowcoder.com/acm/problem/14247 思路：1：首先要知道异或前缀和sum[i]^sum[j-1] = a[j]^a[j+1]^...^a[i],所有这样我们就可以求出每个区间的异或和。2：异或和为零则说明两个区间的异或和相等。3：因为这题要求的区间不能覆盖，所有我们每次以i为基点去查找以i为右端点的区间的异或和有多少个，然后再查找以i为左端点的区间异或和有多少个，再看其中相等的区间异或和有多少个。4：用map去查找相等的有多少个。 #include <bits/stdc++.h> #include <iostream> #...

https://ac.nowcoder.com/acm/contest/5667/F 思路：先把最小公倍数的素组求出来，利用单调队列求出每一行的最大值保存起来，然后再利用一次单调队列依次求出每一列的最大值加起来就是k阶子矩阵的最大值和。单调队列（滑动窗口求最值）：比如有一个素组a，里面有几个数2，6，7，3，1，9.现在有一个长度为3的窗口从i=1的位置往右边移动，求每次移动时候窗口内数的最大值。我们队列里面保存的是入队元素的下标，可以认为队首保存的是当前窗口所在位置最大值的下标，入队时，判断入队元素与队尾元素值的大小，如果队尾元素比入队元素小，那么当前以及在有当前入队元素的位置，队尾元素的值...

https://ac.nowcoder.com/acm/problem/16563 扩展欧几里得 方程ax+by=n,当n能够被gcd(a,b)整除时，那么就可以用扩展欧几里得来求改方程的特解。 同余方程 同余方程ax≡m(mod b)，意思是ax模b的值等于m模b的值，做下变换有(ax-m)%b≡0,说明(ax-m)是b的整数倍，设该整数为k，那么(ax-m)=kb,即ax-kb=m,因为k可以为正数或负数，所以ax+kb=m,接下来可以用扩展欧几里得来求一个解。 #include <bits/stdc++.h> #include <iostream> #includ...

Music Problme https://ac.nowcoder.com/acm/problem/13885 bitset可以用于那些选举个别元素进行组合进行求和，积等问题，以求和为例如下题所示，我们可以用bitset去求出素组中元素的所有组合的和存放在bitste里面，求得的值是多少，我们就让这个位置的上的值设为1，比如有3个数1，2，3，任意两个数的和有3，4，5，假设有定义bitset<7500>p,那么p[3] = 1,p[4] = 1,p[5] = 1,三个数也是类似，然后又可以发现我们可以用移位来完成这个加法操作，比如有1，p[1] = 1,那么2的话可以是1左移了两...

二分答案 分析：和雨巨讲的牛棚放牛类似，这题可以把要移走的石头看成空牛棚，留下的石头看成要跳的石头，然后开始二分答案，假设最短距离中的最长距离是x，那么枚举每块石头的距离，小于这个x的话则这块石头要去掉，然后记录下要去掉的石头数cnt，如果超过了m，说明距离大了，让r=mid - 1，否则距离小了，让l = mid + 1。一直这样下去可以得到最终答案ans。 #include <bits/stdc++.h> #include <iostream> const int Max = 100 * 100 * 100 + 5; #define LL long long con...

拦截导弹 https://ac.nowcoder.com/acm/problem/16810 涉及算法：最长递增子序列(LIS)。dp[i]表示以第i个元素结尾的最长递增子序列的长度。数组中每个元素对于本身可以构成一个递增序列，所有初始化dp为1，然后循环取判断每个元素与在它之前的元素比较，前面的元素小于它，则说明可以放在该元素后面，然后再判断dp[i]与dp[j] + 1的大小，如果小于他没必要放在这个元素后面，这样也就可以求出最大值来。最长不递增子序列也是同样的道理。 分析：最长不递增的序列个数等于最长递增序列，先用一个dp算出最长不递增序列的长度，类似的可以算出最长递增序列的...

https://ac.nowcoder.com/acm/problem/201613 ##三维bfs #include <bits/stdc++.h> #include <iostream> const int Max = 100 * 100 * 100 + 5; #define LL long long const int mod = 1e9+7; //const int inx = INT_MAX; using namespace std; // srand(time(NULL)); // m = rand() % 1000 + 1; //...

可以看看https://blog.csdn.net/qq_34494458/article/details/53589878 优先队列默认容器时vector，默认算子时less，小的往前排，大的往后排，输出时从后往前依次输出。即大的优先级高。   empty() 如果队列为空返回真        pop() 删除对顶元素 push() 加入一个元素 size() 返回优先队列中拥有的元素个数 top() 返回优先队列对顶元素  &nb...