二维前缀矩阵

1.大衣的旅行

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n,m,k;
bool check(int mid,vector<vector<int>>pre,vector<vector<int>>a)
{for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){//枚举以老师房间为中心 距离mid的矩形区域边界int up=max(i-mid,(int)1),down=max(i+mid,n);int left=max(j-mid,(int)1),right=max(j+mid,m);int sum1=pre[down][right]-pre[down][left-1]-pre[up-1][right]+pre[up-1][left-1];//如果区域房间容量大于k+1 并且老师房间至少有一个容量 证明还能收缩if (sum1 >= k + 1 && a[i][j]) return true;}}return false;
}
signed main()
{cin>>t;while(t--){cin>>n>>m>>k;vector<vector<int>>a(m+1);vector<vector<int>>pre(m+1);int sum=0;for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){cin>>a[i][j];sum+=a[i][j];}}if(sum<k+1){cout<<-1<<endl;continue;}for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];}}int l=0,r=max(n,m),mid=0;int ans=-1;while(l<=r) //二分遍历所有情况，找到老师的房间和距离他最远的学生的房间距离最小{mid=(l+r)/2;if(check(mid,pre,a)){r=mid-1; //存在符合继续缩减范围ans=mid;}else{l=mid+1;}}cout<<ans<<endl;}return 0;
}

2.小秋的矩阵

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
int a[10010][10010],sum[10010][10010];
signed main()
{cin>>n>>m>>k;for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){cin>>a[i][j];if(a[i][j]==1) a[i][j]=0;else a[i][j]=1;sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];}}int sum1=0;// 遍历所有可能的方阵，方阵大小为 l x lfor (int l = 1; l <= min(n, m); l++){// 遍历每个方阵的左上角位置 (i, j)for (int i = 1; i <= n - l + 1; i++){for (int j = 1; j <= m - l + 1; j++){// 获取左上角为 (i, j) 的 l x l 方阵的和int total = sum[i + l - 1][j + l - 1] - sum[i - 1][j + l - 1] - sum[i + l - 1][j - 1] + sum[i - 1][j - 1];if(total==k){sum1++;}}}}cout<<sum1<<endl;return 0;
}

二维矩阵前缀计算时画图理解

3.错误票据

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
vector<int>a;
signed main()
{cin>>n;getchar();string line;while(n--){getline(cin,line);stringstream ss(line);int num;while(ss>>num){a.push_back(num);}}sort(a.begin(),a.end());int m,n; for(int i=0;i<a.size()-1;i++){if((a[i]+1)!=a[i+1] && a[i]!=a[i+1]) //断号且非重号情况 {m=a[i]+1;}if(a[i]==a[i+1]) //重号 {n=a[i];}}cout<<m<<" "<<n<<endl;return 0;
}