基础算法
前缀和
一维前缀和
[USACO16JAN] Subsequences Summing to Sevens S - 洛谷
这一题主要是需要结合数学知识来求解，
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 50010;
int n;
int s[N], l[7], r[7];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++) {
int cur;
scanf("%d", &cur);
// 初始化前缀和矩阵
s[i] = (s[i - 1] + cur) % 7;
}
// 从右往左，记录7的每个余数的最左边的坐标值
for (int i = n; i ; i --) l[s[i]] = i;
// 从左往右，记录7的每个余数的最右边的坐标值
for (int i = 1; i <= n; i ++) r[s[i]] = i;
l[0] = 0;
int res = 0;
for (int i = 0; i <= 6; i ++) {
if (r[i]) res = max(res, r[i] - l[i]);
}
printf("%d\n", res);
return 0;
}
二维前缀和
核心的原理
模板题
活动 - AcWing
例题
这个题的N是100，比较小，可以用三重循环通过；故枚举正方形的边长，记作len
这个题的(x1,y1)等于(i,j) 这个题的(x2,y2)相当于(i+len,j+len)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 510;
int a[N][N],s[N][N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
//判断正方形 这个正方形里面的和是变长的平方
// 枚举最大长度
int res = 0;
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= m; j ++) {
for (int len = 0; i + len <= n && j + len <= m; len ++) {
if (s[i + len][j + len] - s[i - 1][j + len] - s[i + len][j - 1] + s[i - 1][j - 1] == (len + 1) * (len + 1)){
res = max(len + 1, res);
}
}
}
}
cout<<res<<endl;
return 0;
}
二维前缀和之固定边长的正方形
[HNOI2003] 激光炸弹 - 洛谷
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
int s[5050][5050];
int res = 0;
int main()
{
cin >> n >> m;
while (n--)
{
int x, y, v;
cin >> x >> y >> v;
s[x + 1][y + 1] += v;
}
for (int i = 1; i <= 5001; i++)
{
for (int j = 1; j <= 5001; j++)
{
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
for (int i = m; i <= 5001; i++)
for (int j = m; j <= 5001; j++)
{
//标准
int value = s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m];
res = max(res, value);
}
printf("%d", res);
return 0;
}差分
一维差分
[Poetize6] IncDec Sequence - 洛谷
这个题里面的数学推理我现在都还没看明白
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long ll;
ll a[N];
ll b[N];
ll n;
int main()
{
cin>>n;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
}
ll x,y;
x=y=0;
for(ll i=1;i<n;i++)
{
b[i]=a[i+1]-a[i];
if(b[i]<0)x-=b[i];
else y+=b[i];
}
cout<<max(x,y)<<endl;
cout<<abs(x-y)+1<<endl;
return 0;
}二维差分
模板题
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
//差分矩阵为什么是这个
void insert(int x1,int y1,int x2,int y2,int c)
{
b[x1][y1]+=c;
b[x2+1][y1]-=c;
b[x1][y2+1]-=c;
b[x2+1][y2+1]+=c;
}
// void insert(int x1, int y1, int x2, int y2, int c)
// {
// b[x1][y1] += c;
// b[x2 + 1][y1] -= c;
// b[x1][y2 + 1] -= c;
// b[x2 + 1][y2 + 1] += c;
// }
int main()
{
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
//初始化差分数组
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
insert(i, j, i, j, a[i][j]); //构建差分数组
}
}
while (q--)
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1, y1, x2, y2, c);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; //二维前缀和
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
printf("%d ", b[i][j]);
}
printf("\n");
}
return 0;
}
洛谷地毯 - 洛谷
在模版的基础上稍微变一下形即可
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
//差分矩阵为什么是这个
void insert(int x1,int y1,int x2,int y2,int c)
{
b[x1][y1]+=c;
b[x2+1][y1]-=c;
b[x1][y2+1]-=c;
b[x2+1][y2+1]+=c;
}
// void insert(int x1, int y1, int x2, int y2, int c)
// {
// b[x1][y1] += c;
// b[x2 + 1][y1] -= c;
// b[x1][y2 + 1] -= c;
// b[x2 + 1][y2 + 1] += c;
// }
int main()
{
int n, m, q;
cin >> n >> m;
//初始化差分数组
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
insert(i, j, i, j, 0); //构建差分数组
}
}
while (m--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
insert(x1, y1, x2, y2, 1);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; //二维前缀和
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
printf("%d ", b[i][j]);
}
printf("\n");
}
return 0;
}
贪心
与排序有关的贪心（注意排序的写法）
结构体排序（记忆一下）
[USACO1.3] 混合牛奶 Mixing Milk - 洛谷
bool cmp(cow farmer1,cow farmer2)
{
return farmer1.p<farmer2.p;
}
也就是bool cmp(结构体名称 实例1，结构体名称 实例2)
{
return 实例1的某个成员<实例2的某个成员;
}
#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
struct cow {
int p;
int maxnum;
}farmer[N];
bool cmp(cow farmer1,cow farmer2)
{
return farmer1.p<farmer2.p;
}
int main()
{
int m,n;
int sum = 0;
cin >> m>> n;
for (int i = 0; i < n; i++)
{
cin >> farmer[i].p>>farmer[i].maxnum;
}
sort(farmer,farmer+n,cmp);
//需要m牛奶
int mark=0;
while(farmer[mark].maxnum<m)
{
m-=farmer[mark].maxnum;
sum+=farmer[mark].p*farmer[mark].maxnum;
mark++;
}
sum+=farmer[mark].p*m;
cout<<sum<<endl;
return 0;
}双指针算法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int a[N],cnt[N];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int res=0;
for(int i=0,j=0;i<n;i++)
{
cnt[a[i]]++;
while(cnt[a[i]]>1)
{
cnt[a[j]]--;//左边
j++;
}
res=max(res,i-j+1);
}
cout<<res<<endl;
return 0;
}两个指针都要有更新的操作！
数据结构
链表
算法题中一般使用数组来模拟链表（链式前向星），带头结点
单链表
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
int head;
int e[N], ne[N], idx;
void init() {
head = -1;
idx = 0;
}
void add_to_head(int x) { // 在头部加一个结点
e[idx] = x;
ne[idx] = head;
head = idx++;
}
void add(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}
void remove(int k) {
ne[k] = ne[ne[k]];
}
int main() {
int m;
scanf("%d", &m); // 使用scanf加快输入
init(); // 初始化链表
while (m--) {
char op;
scanf(" %c", &op); // 读取操作
if (op == 'H') {
int x;
scanf("%d", &x); // 读取插入的数据
add_to_head(x);
} else if (op == 'I') {
int k, x;
scanf("%d%d", &k, &x); // 读取插入的位置和数据
add(k - 1, x);
} else if (op == 'D') {
int k;
scanf("%d", &k); // 读取删除的位置
if (k == 0) head = ne[head]; // 删除头结点
else remove(k - 1);
}
}
for (int i = head; i != -1; i = ne[i]) {
printf("%d ", e[i]); // 使用printf加快输出
}
printf("\n");
return 0;
}双链表
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int e[N],l[N],r[N],idx;
//初始化
void init()
{
r[0]=1;
l[1]=0;
idx=2;
}
//在结点k的右边插入一个数x
void insert(int k,int x)
{
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx++;
}
void remove(int k)
{
l[r[k]]=l[k];
r[l[k]]=r[k];
}
int main()
{
int m;cin>>m;
init();
while (m -- ){
string op;cin>>op;
int k,x;
if(op=="L"){
cin>>x;
insert(0,x);
}
else if(op=="R"){
cin>>x;insert(l[1],x);
}
else if(op=="D"){
cin>>k;remove(k+1);
}
else if(op=="IL")//在第k个位置的左侧插入一个数
{
cin>>k>>x;
insert(l[k+1],x);
}
else if(op=="IR")
{
cin>>k>>x;
insert(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i]){
cout<<e[i]<<" ";
}
cout<<endl;
return 0;
}栈和队列
单调栈
#include <iostream>
using namespace std;
const int N = 100010;
int stk[N], tt;
int main()
{
int n;cin>>n;
while (n -- ){
int x;cin>>x;
while(tt&&stk[tt]>=x)tt--;
if(tt!=0)cout<<stk[tt]<<" ";
else cout << "-1"<<" ";
stk[++tt]=x;
}
return 0;
}逆序处理但是下标不变
#include <iostream>
using namespace std;
const int N = 3e6+10;
int stk[N], tt;
int a[N],b[N];
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n;i>0;i--)
{
while(tt&&a[stk[tt]]<=a[i])tt--;
b[i]=stk[tt];
stk[++tt]=i;
}
for(int i=1;i<=n;i++)cout<<b[i]<<" ";
return 0;
}
单调队列（滑动窗口）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int a[N];
int hh=1,tt=0;
int n,k;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
int q1[N];
for(int i=1;i<=n;i++){
while(hh<=tt&&a[q1[tt]]>a[i])tt--;
q1[++tt]=i;
if(q1[hh]<i-k+1)hh++;
if(i>=k)printf("%d ",a[q1[hh]]);
}
cout<<endl;
//清空q
int q2[N];
for(int i=1;i<=n;i++){
while(hh<=tt&&a[q2[tt]]<a[i])tt--;
q2[++tt]=i;
if(q2[hh]<i-k+1)hh++;
if(i>=k)printf("%d ",a[q2[hh]]);
}
return 0;
}
int hh=1,tt=0;
for(int i=1;i<=n;i++){
while(hh<=tt&&a[q[tt]]>=a[i])tt--;//队尾出队（队列不为空且新元素更优）
q[++tt]=i;//队尾入队
if(q[hh]<i-k+1)hh++;
if(i>=k)printf("%d ",a[q[hh]]);//输出最值（队头）并查集
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n,m;
int p[N];
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)p[i]=i;
while(m--)
{
char op;
int a,b;
cin>>op>>a>>b;
if(op=='M')
{
//find找这个东西所在的编号
p[find(a)]=find(p[b]);
}
if(op=='Q')
{
if(find(a)==find(b))
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
}
return 0;
}
