背了重展的锅 de了两个小时，说实话stl真心救命这道题主要就是优先选择贪心，同时比较s把s从大到小排列 每次让其按顺序入队 下一个入队时考虑新加入的a[i].s因为每一次s递减所以维护起来十分方便 #include <bits/stdc++.h> using namespace std; #define int long long const int maxn=2e5+7; priority_queue<int , vector<int >, greater<int > > pa; struct node { int v,s; }a[m...

看清题目很重要 以i为界限，他的左右最大的长度为k的连续子段为状态，转移方程很容易推出 m[i]=max(m[i+1],sum[i+k]-sum[i])///i右边M[i]=max(M[i-1],sum[i]-sum[i-k]);///i左边就是一个经典的dp注意数据范围a[i]可以小于0还有边界位置处理 请在这里输入引用内容输入描述:第一行一个整数T（T<=10）,代表有T组数据接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <= n)接下来一行n个整数a1,a2,...,an，（-100,000<=ai<=100,...

如果用一般的思路每次查找O(k)的复杂度，总时间复杂度达到O(k(n-k)) 数据范围显然需要优化算法所以选用易理解的单调队列，和普通队列不同的是，要进行两端删除和插入需要双指针，当然stl的deque（双端队列）就可以实现。 具体实现：比如说[2,1]这个序列，当1一直存在时，2在出窗口之前永远不可能成为最小的那个值，所以这个元素就是无用值，所以每次移动窗口删除队首元素，从右到左寻找单调队列中比刚入队元素大的值（因为刚入队那个元素值始终比他们小，所以最小值就不是这些值） 最大值反之亦然例如有序列5，2，6，8，10k = 3滑动窗口 [5,2,6],8,3 --> ...

可能是对于小木棍这种题目过于熟悉，把我以前在洛谷P2440上的代码搬来了，ac了讲讲思路：二分的基础题目二分最重要的就是check函数 （这仅仅只是可行解）当然可行解并不一定是最优解所以我们还需要往最优解靠继续二分 #include <bits/stdc++.h> using namespace std; #define int long long const signed maxn=1e6+7; int a[maxn]; int n,m; bool check(int x) { int cnt=0; for (int i=1;i<=n;++i) ...

又来写题解了没学过组合数学不过垫着高中的本还是够的 前 0 在后 典型的组合n中选两个 顺序确定 就是n*(n-1)/2 剩下的来个排列n-2 个数每一个数都有0或1两种选择 所以就是2^n-2种选择当然提醒一下为了保证除数的模可以用逆元我的c++程序de了半天始终只能过13%额 放弃了 上pythonn = int(input()) if n<=1 : print("0") else : mod = int(1e9+7) ans = (pow(2,n-2,mod)*n*(n-1)//2%mod)%mod print(int (ans)) ```

突然发现这道题似曾相识 额luoguP1168中位数(被树状数组坑进去的） 这里只需要用两个优先队列来写（一个大根堆和一个小根堆）一个存取中位数和比他小的数（小根堆） 另外一个存取比它大的 （大根堆） 中位数肯定在两个堆其中一个的顶部具体看代码做解释 #include <bits/stdc++.h> using namespace std; struct cmp_a{ bool operator() (const int a,const int b) const { return a<b; } }; struct cmp_b{ bool operator...

这道题开始写的时候让我想起了子段异或这道题https://ac.nowcoder.com/acm/contest/3005/D思路：首先你需要知道 0^x=x ; x^x=0数据比较小(枚举啦）（我太菜了orz）所以接下来我们枚举一个区间（求出他的异或和）然后找到其他区间（不重叠）是否存在和此前区间一样的异或和值（ x^x=0嘛） 枚举一条线将总区间分成两个区间 例如{a1,a2,a3,a4,a5}从a1开始分成{a1}{a2，a3，a4，a5}{a2} {a2,a3} {a2,a3,a4} {a2,a3,a4,a5}{a3} {a3,a4} {a3,a4,a5}这是下面代码里面的枚举法...

先来看看（a/b)%c 这个问题                    不妨引入一个新的概念来让其等于1/b  切入正题：     若  ，gcd（a,b)=1 则称x为a模p的乘法逆元  记x为inv(a)或者a^-1       （a p互质）  (概念性的东西讲完了，那么他有什么存在的意义呢？） 先看看下面这个符号 “≡ ”   简单说明一下 ....a≡ b(mod c)等价于a(mod c)=b(mod c)   例如：4关于1模7的乘法逆元为多少？ 4X≡1 mod 7 这个方程等价于求一个X和K，满足 4X=7K+1 其中X...

迅哥讲解（说实话没有认真听，不过关系不大） RMQ：Range Minimum Maximum Query 给定一个序列A[1…N]，问A[i…j]之间的极值 如果只问一次， 显然是O(N) 标准RMQ问题是：不停的查询同一个序列上的不同区间内的极值 序列A的长度N，一共Q次查询 纯暴力法：O(NQ) 带预处理的暴力法： 矩阵B[N][N]， 令B[i][j]是A[i…j]的极值 求B需要一个双重循环，O(N2) 对每一次查询只需O(1)即可 所以总时间复杂度O(N2+Q) 空间复杂度则为O(N2)   Sparse Table算法 矩阵M[N][logN+1] M[i][j...

这是我的第一篇随笔（其实是为了防止我忘记而做的笔记） 问题引入： 孙子定理是中国古代求解一次同余式组（见 同余）的方法。是 数论中一个重要定理。又称 中国余数定理。一元线性同余方程组问题最早可见于中国 南北朝时期（公元5世纪）的数学著作《 孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下： 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。 好像还是不太懂 来个百度上的例题 当然一般的做法就是除三...