二维前缀矩阵

1.大衣的观光

2. #include<bits/stdc++.h>
3. #define int long long
4. using namespace std;
5. int t;
6. int n,m,k;
7. bool check(int mid,vector<vector<int>>pre,vector<vector<int>>a)
8. {
9.         for(int i=1; i<=n; i++)
10.         {
11.                 for(int j=1; j<=m; j++)
12.                 {
13.                         //枚举以老师房间为中心 距离mid的矩形区域边界
14.                         int up=max(i-mid,(int)1),down=max(i+mid,n);
15.                         int left=max(j-mid,(int)1),right=max(j+mid,m);
16.                         int sum1=pre[down][right]-pre[down][left-1]-pre[up-1][right]+pre[up-1][left-1];
17.                         //如果区域房间容量大于k+1 并且老师房间至少有一个容量 证明还能收缩
18.                         if (sum1 >= k + 1 && a[i][j]) return true;
19.                 }
20.         }
21.         return false;
22. }
23. signed main()
24. {
25.         cin>>t;
26.         while(t--)
27.         {
28.                 cin>>n>>m>>k;
29.                 vector<vector<int>>a(m+1);
30.                 vector<vector<int>>pre(m+1);
31.                 int sum=0;
32.                 for(int i=1; i<=n; i++)
33.                 {
34.                         for(int j=1; j<=m; j++)
35.                         {
36.                                 cin>>a[i][j];
37.                                 sum+=a[i][j];
38.                         }
39.                 }
40.                 if(sum<k+1)
41.                 {
42.                         cout<<-1<<endl;
43.                         continue;
44.                 }
45.                 for(int i=1; i<=n; i++)
46.                 {
47.                         for(int j=1; j<=m; j++)
48.                         {
49.                                 pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
50.                         }
51.                 }
52.                 int l=0,r=max(n,m),mid=0;
53.                 int ans=-1;
54.                 while(l<=r) //二分遍历所有情况，找到老师的房间和距离他最远的学生的房间距离最小
55.                 {
56.                         mid=(l+r)/2;
57.                         if(check(mid,pre,a))
58.                         {
59.                                 r=mid-1; //存在符合继续缩减范围
60.                                 ans=mid;
61.                         }
62.                         else
63.                         {
64.                                 l=mid+1;
65.                         }
66.                 }
67.                 cout<<ans<<endl;
68.         }
69.         return 0;
70. }

复制代码

2.小秋的矩阵

2. #include<bits/stdc++.h>
3. #define int long long
4. using namespace std;
5. int n,m,k;
6. int a[10010][10010],sum[10010][10010];
7. signed main()
8. {
9.         cin>>n>>m>>k;
10.         for(int i=1; i<=n; i++)
11.         {
12.                 for(int j=1; j<=m; j++)
13.                 {
14.                         cin>>a[i][j];
15.                         if(a[i][j]==1) a[i][j]=0;
16.                         else a[i][j]=1;
17.                         sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];
18.                 }
19.         }
20.         int sum1=0;
21.         // 遍历所有可能的方阵，方阵大小为 l x l
22.         for (int l = 1; l <= min(n, m); l++)
23.         {
24.                 // 遍历每个方阵的左上角位置 (i, j)
25.                 for (int i = 1; i <= n - l + 1; i++)
26.                 {
27.                         for (int j = 1; j <= m - l + 1; j++)
28.                         {
29.                                 // 获取左上角为 (i, j) 的 l x l 方阵的和
30.                                 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];
31.                                 if(total==k)
32.                                 {
33.                                         sum1++;
34.                                 }
35.                         }
36.                 }
37.         }
38.         cout<<sum1<<endl;
39.         return 0;
40. }

复制代码

二维矩阵前缀盘算时绘图明白 
3.错误票据

2. #include<bits/stdc++.h>
3. #define int long long
4. using namespace std;
5. int n;
6. vector<int>a;
7. signed main()
8. {
9.         cin>>n;
10.         getchar();
11.         string line;
12.         while(n--)
13.         {
14.                 getline(cin,line);
15.                 stringstream ss(line);
16.                 int num;
17.                 while(ss>>num)
18.                 {
19.                         a.push_back(num);
20.                 }
21.         }
22.         sort(a.begin(),a.end());
23.         int m,n;
24.         for(int i=0;i<a.size()-1;i++)
25.         {
26.                 if((a[i]+1)!=a[i+1] && a[i]!=a[i+1]) //断号且非重号情况
27.                 {
28.                         m=a[i]+1;
29.                 }
30.                 if(a[i]==a[i+1]) //重号
31.                 {
32.                         n=a[i];
33.                 }
34.         }
35.         cout<<m<<" "<<n<<endl;
36.         return 0;
37. }

复制代码

对于空格字符串的处置惩罚 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。