-
算法竞赛（差分）（上午）
初始化
#include <algorithm>
int arr[100];
std::fill(arr, arr + 100, 0);
//比memset更高效
int arr[100] = {}; // 所有元素都初始化为 0
栈溢出
为局部变量每次运行时都在运行栈中分配，如果数组很大，结果会造成运行栈溢出，自然就运行不了
另外，使用全局变量只是在静态区内分配，同样也有溢出的问题，显然你的数组需要的空间还没有到这么多
//作为全局变量，能运行
int a[1010][1010];
//作为局部变量，能运行，不能输入也不能输出
最大字段和（分治）
p1115
1e-9 表示科学记数法中的 10 的负九次方，即 0.000000001
不是-10^9；
#include<bits/stdc++.h>
using namespace std;
int n;
int a,b;
int ans=1e-9;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a;
if(i==0)b=a;
else
{
b=max(a,b+a);
}
ans=max(ans,b);
}
cout<<ans;
return 0;
}
-
比赛团队赛3+算法竞赛（差分和前缀和）
借教室 差分＋二分
https://www.luogu.com.cn/problem/solution/P1083
int 大概在2.15e9
所以本题我们要开longlong
比较难想的是我们要而二分订单数量，这有一个性质，订单数量数轴，如果前面的点不符合，后面一定不符合。
质检员
https://www.luogu.com.cn/problem/P1314
#include<bits/stdc++.h>
#define ll long long
#define R register int
#pragma GCC optimize(3)//O3优化
using namespace std;
ll n,m,s,l,r,mid,ans;//朴素定义，
ll w[200010],v[200010],le[200010],ri[200010],ss;
ll Min=1e15; //记录结果
ll q[200010],p[200010]; //前缀和记录
//q记录从0~i有几个符合题意的源石，p记录从0~i符合题意的石头的价值之和
int main()
{
scanf("%lld%lld%lld",&n,&m,&s);
for(R i=1;i<=n;i++)
{
scanf("%lld%lld",&w[i],&v[i]);
r=max(r,w[i]);//右边界设为最大的w[i]，应该是显然对的……当然如果不放心开到1<<30也没问题
}
for(R i=1;i<=m;i++) //读入m个区间
scanf("%lld%lld",&le[i],&ri[i]);
while(l<=r)
//这里取等了
{
ans=0,mid=(l+r)>>1;
for(R i=1;i<=n;i++) //循环更新前缀和数组
{
if(w[i]>mid)
q[i]=q[i-1]+1,p[i]=p[i-1]+v[i];
//q存前i个数量和，p存前i个价值和。二分W（所求）
//我们在求区间和所以用前缀和优化
else
q[i]=q[i-1],p[i]=p[i-1];
}
for(R i=1;i<=m;i++) //计算一下Y，也就是Y1+Y2+……+Yn
ans+=(q[ri[i]]-q[le[i]-1])*(p[ri[i]]-p[le[i]-1]);
//每个区间的数量和×价值和即yi
ss=s-ans; //这里先不要绝对值，要利用原数决定怎么改l和r的值
//ans y大于s时，增大w减小y，使y-s绝对值减小
//ans y小于s时，减小w增大y，使y-s绝对值增大
if(ss<0)l=mid+1; //小于0说明假定的W小了，扩大l的值
else r=mid-1; //否则缩小r的值
Min=min(Min,abs(ss)); //更新求得的最小值
}
printf("%lld",Min);
}
算法竞赛 排序和排列
结构体
//这个相当于定义结构体同时，定义了结构体变量s1,s2;
//补充）sort左闭右开
https://blog.csdn.net/m0_51064412/article/details/130352792
排列 next_permutation（s.begin(），s.end(),cmp)
prev.permutation求前一个排列组合
string s="abc";
do{
cout<<s<<endl;
}while(next_permutation(s.begin(),s.end()));
//输出第n个排列，n=1654
do{
if(n==1654){
for(int i=0;i<7;i++)
cout<<a[i];
cout<<endl;
break;
}
n++;
}while(next_permutation(a,a+7));
//序列中有重复元素会去重
//结构体需要定义如何比较
struct test{//结构体test
int val;
};
bool cmp(test t1,test t2){//自定义的排列
return t1.val<t2.val;
}
int main(){
test t[4];//结构体数组
t[0].val=1;
t[1].val=2;
t[2].val=3;
t[3].val=4;
do{
for(int i=0;i<4;i++){//打印排列
cout<<t[i].val<<' ';
}
cout<<endl;
//vector
#include<iostream>
#include<vector> //使用vector需要导入的头文件
#include<algorithm>//使用 next_permutation()和sort()需要导入的头文件
using namespace std;
int main(){
vector<int> v;//定义一个int型的vector
v.push_back(1);//在尾部插入数据1
v.push_back(2);
v.push_back(3);
v.push_back(4);
do{
for(int i=0;i<v.size();i++){//打印排列
cout<<v[i]<<' ';
}
cout<<endl;
}while(next_permutation(v.begin(),v.end()));//获取下一个排列
}