题目: 题解 题意： 把一段数列分成 M 段，并且满足各段所有数的和的最大值是所有分段方法中最小的 做法： 用二分枚举答案，易证：每段和的最大值一定在 l\~r 范围内（ l 是数组中的最大值，r 是数组里所有数的和） 定义一个变量 mid 如果每段和的最大值最小为 mid 看能否分成 M 段，如果可以，在 l\~mid 里继续搜索，否则在 mid+1\~r 里 直到 l\=\=r 就是答案 #include<iostream> #include<cstdio> using namespac…

C++ 模板 1. 差分模板 #include <bits/stdc++.h> using namespace std; int n,k,data[1000010],diff[1000010],a[1000010]; int main() { int a,b,v=0; int x; cin>>n>>k; for(int i=1;i<=n;i++) { cin>>a[i]; if(i==1) diff[i]=a[i]; else diff[i]=a[i]-a[i-…

题目 #include<bits/stdc++.h> #define reint register int #define ll long long using namespace std; struct nod{ //存雷达区间 double l,r; }f[1005]; int x[1005],y[1005],ans; bool cmp(nod a,nod b){ //按右边缘排序 return a.r<b.r; } int main(){ int n,d; scanf("%d%d",&…

#include<bits/stdc++.h> #define reint register int using namespace std; int n,m; inline void read(int &a) { //快读 int x(0),y(1); char c=getchar(); while(c<'0'||c>'9') { if(c=='-')y=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<…

P类问题： 可以用一个时间复杂度为多项式级别^*的的算法来解决的问题，就是P类问题 NP类问题： 可以在时间复杂度为多项式级别的方法来判断有无解的问题，就是NP类问题 另外：NP类问题包含P类问题 * ：多项式级别就是例如O(1), O(n^a), 这类的时间复杂度

一些简单的STL用法 主要是给作者当备忘录 string 字符串，相当于一个字符数组，同时还有各种函数支持。 1. 几种特殊赋值方法： string str1="wssb"; char c[]="wssb"; string ss; ss=str1; //直接赋值 ss=string(10,'s') //ss=ssssssssss ss=string(str1,2) //ss=从第2个字符开始一直到结束，即ss=sb（这里下标从0开始） ss=string(str1,0,2)//ss=从0个字符开始一直到2结束，即s…

Kruskal算法简介： Kruskal 算法是一种用来求最小生成树的算法，在稀疏图中比 Prim 有更高的效率，且方便实现，所以本文重点讲解 Kruskal 算法的用途和使用方法 Kruskal算法原理： Kruskal 算法主要利用贪心的思想使得边权和最小 Kruskal 算法步骤： 1. 把 m 条边按边权从小到大排序 2. 把图中的 n 个顶点看成独立的 n 棵树组成的森林； 3. 先从边权小的边开始循环，通过并查集判断添加这条边后是否会形成环（也就是能否连接两个不同祖先的点），如果可以，则添加这条边。 4…

举个例子，有一个数组 a[]={ 1,5,3,7,2,8 } ，他的差分数组就是 b[]={ 1,4,-2,4,-5,6 } a 1 5 3 7 2 8 b 1 4 -2 4 -5 6 想必你也很快发现了他们之间的联系，b_i=a_i-a_{ i-1 } ，因此可以推出 a_i=b_1+b_2+b_3+...+b_i 。 当我们把 a_{2} 到 a_5 都加上 2 后，数组 a 就变成了 a[]={ 1,7,5,9,4,8 } a 1 7 5 9 4 8 然后我们在重新计算一下 b 数组，计算结果是这样的： b[…

1. 读入优化（快读） 原理：利用getchar读入更快的原理，读入字符后转换成数字 代码： int qread() { int x(0),y(1);char c=getchar(); while(c<'0'||c>'9') { if(c=='-')y=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*y; } 2. 输出…

笔记： 对数log： 如果 a 的 x 次方等于 N（ a>0，且 a≠1 ），那么数 x 叫做以 a 为底 N 的对数，记作 x=log_a N。其中，a 叫做对数的底数，N 叫做真数， \log_xn = y 就说明 x^y=n (x就是底数，在信奥中如果不写默认为2，数学中默认10) \log_2 n = y , 那么 2^y = n ，当 n/2 后，2 ^{( y - 1 )} = n /2 了 线性结构与非线性结构 线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双…