二维前缀矩阵

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 l
	for (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;
}

对于空格字符串的处理