AOE还是单体？ #include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include <string> using namespace std; const int N = 2e5 + 10; typedef long long ll; ll n,x; ll a[N],mx; int main(){ scanf("%lld%lld",&n,&x); for(int i = 1...

思路： #include <cstdio> #include <iostream> using namespace std; const int N = 1010; int n,m,k,a[N][N]; int check(int x1,int y1,int x2,int y2){ return a[x2][y2] - a[x1-1][y2] - a[x2][y1-1] + a[x1-1][y1-1]; } int main(){ scanf("%d%d%d",&n,&m,&k); for(int i = 1;i &l...

思路： #include <cstdio> #include <algorithm> using namespace std; const int N = 15; double a[N],b[N],c[N],p[N]; double f[N][N]; int main(){ for(int i = 1;i <= 12;i++){ scanf("%lf",a+i); } for(int i = 1;i <= 12;i++){ scanf("%lf",b+i); } for(int i =...

题意： 有n个点，然后有m条边，且你只能从权值高的点走到权值低的点；且你可以回到之前你曾经走过的点，然后问从1出发，最多可以遍历多少个点，且遍历最多点时最小距离是多少？ 思路： 首先需要保证遍历的点最多，应该希望新加入的点高度越高越好，因为这样就不会漏掉一些本来可以遍历的点，然后再希望距离越小越好；做一遍prim，将点加入生成树时以高度降序，到生成树距离升序来取，且每到一个点的代价就是这个点到生成树中所有点集中的最短路 #include <cstdio> #include <cstring> #include <algorithm> #include &lt...

题意： 求符合题目要求的子序列的个数 思路： 首先若把那个条件变成ai < aj，即严格上升子序列的个数的问题，只需要用dp[j]表示以j结尾的符合条件的序列的个数，每次更新时，看所有小于j的i是否符合ai < aj，若符合就加上dp[j];回到原题，那个东西最大可能要算,不太好比较，可以两边取个对数变成: #include <cstdio> #include <cmath> #include <iostream> using namespace std; typedef long long ll; const ll mod = 1e9+7; ...

题意： 把原数组Ai内所有长度大于等于k的子段的第k大的数拿出组成一个新的数组 Bi，然后询问Bi中第 m 大的数是多少？ 思路： 暴力地求出每个区间的第 k 大值，因为n最大1e5，最坏情况下有n*n的区间，所有显然是不可取的；可以知道答案Bi中的第m大的数一定是原数组Ai中任意一个元素，先对原数组Ai排序后，二分答案 怎么二分，哪里满足单调性？假设答案为x，那么说明至少有m个子区间的第k大值大于等于x，那么对于比x小的数同样有大于等于m个子区间的第k大值大于等于x 然后到了怎么去求第k大值大于等于x的子区间有多少个？用尺取法枚举每个一个区间左键，对于一个固定了左键的区间，找到第一个满足nu...

只有长度大于等于x的木棍才能切出长度为x的木棍，而可以切出木棍长为x的木棍k条，那么长为x-1的木棍也至少能切除k条，具有单调性，二分找最大值，二分起点为1，终点为原本木棍中的mx；ans初始为-1只能过90%，我的理解是会存在无解的情况，但题目输出要求是一个非负整数，所有应该将ans初始为0 #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const ll inf = 1e12; const int N = 2e5+10; int n; ll k,a[N...

对于树上的点，只有深度为奇数的点走到深度为奇数的点和深度为偶数的点走到深度为偶数的点经过的边才会是偶数，dfs一边记录每个点的深度，统计深度为奇数的点的个数n和深度为偶数的点的个数m ans = #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N = 1e5+10; struct Node{ int to,nex; }e[N<<1]; int n,head[N],...

首先只有两个相同的数异或结果才可能为0即两个非重叠区间异或和应该相同而求一个区间[l,r]的异或和可以用前缀异或和求得即sum[r]^sum[l-1]然后枚举一个区间[x,y]，规定这个区间[x,y]为右区间，固定右区间的左键为i，那么区间右键可以为i+1，i+2......，n，那么只要左区间的异或和等于右区间且左区间的右键小于x就可以了，每次循环更新以i-1位右键的所有异或和出现次数，因此计算[x,y]为右区间时的有几个左区间满足就是[x,y]这个区间的异或和之前出现的次数 #include <cstdio> #include <map> using names...

1. 算出前几项然后OEIS 2. 组合数学 从低位到高位选择0或者1填数，当填到第i位的时候，如果第i位为0对答案是没有贡献的，如果是1就要算前面已经填好的长度为i-1的串中有多少个0，因此计算每一个位置为1时的贡献的和就是答案； 当字符串的第i位为1时，它对答案的贡献就是长度为i-1的串的0的个数，所有长度为i-1的串一共有(i-1) * 2^(i-1)个数字，0的个数和1的个数应该一样，0应该有(i-1) * 2^(i-2)个；而填好第i位后，后面还有n-i个位置没填完，还有2^(n-i)种方式填好整个长度为n字符串，当字符串第i为1时的贡献是(i-1) * 2^(i-2) * 2^...

题意：动态地输入输出，如果输入的数个数为奇数就输出当前的中位数 对顶堆的经典题，附上大佬的关于对顶堆的博客一篇：https://www.cnblogs.com/SGCollin/p/9673252.html 这题需要动态地维护中位数，用一个大根堆和小根堆；构造对顶堆应满足以下性质：1.上面的堆是小根堆，下面的堆是大根堆；2.上面的堆内的所有元素都不小于下面的堆的对顶元素；3.下面的堆的元素个数最多只比上面的个数多1个；然后对于一个新读入的元素x，如果 x 不大于下面的大根堆的对顶元素，就把x放到下面的大根堆，否则放到上面的小根堆，这样可以维护上述的第二条性质；但是这样不一定也能满足第三条性质，...

题目要求对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。相当于切掉树上的 x 条边（0<= x <= min(n-1,k-1)），让原树变成x+1个连通块，每个连通块涂成一个颜色，问有多少种方案；ans = C(n-1,i)是从n-1条边选i条边切，分成i+1个连通块，再在k种颜色内选i+1种给i+1个连通块上***r>预处理求下组合数，P(n,m)用C(n,m)*m!求得 #include <cstdio> #include <algorithm> using namespace std; typedef long l...