基礎算法
前綴和
一維前綴和
[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;
}二維差分
模板題
活動 - AcWing
#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;
}
