写在前面：(2020-2-12)
发现之前学习的一些算法忘了很多，准备最近在洛谷上找一些基础的题目做一做，熟悉一下这些基础算法，仅仅是Ac(暴力)的，
洛谷P1387最大的正方形
题目描述
在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。
输入格式
输入文件第一行为两个整数n,m（1<=n,m<=100），接下来n行，每行m个数字，用空格隔开，0或1.
输出格式
一个整数，最大正方形的边长
分析：二维前缀和的裸题，对于每个点，我们依次枚举边长从1到min(n,m)的正方形，因为矩阵的元素不是0就是1，所以我们利用二维前缀和计算出正方形中1的个数是否等于该正方形的面积，ans维护答案即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010;
int n,m;
int a[N][N];
int s[N][N];
bool check(int x1,int y1,int x2,int y2)
{
int res = (x2-x1+1) * (y2-y1+1);
int t = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
if(t == res) return true;
return false;
}
int main()
{
cin>>n>>m;
for(int i = 1; i<=n; i++)
for(int j = 1; j<=m; j++)
scanf("%d",&a[i][j]);
for(int i = 1; i<=n; i++)
for(int j = 1; j<=m; j++)
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
int len = min(n,m); //正方形的边长不可能超过n和m中小的那一个
int ans = 0;
for(int i = 1; i<=n; i++)
for(int j = 1; j<=m; j++)
for(int k = 1; k<=len; k++)
{
if(i+k-1 >n || j+k-1 >m) continue;
if(check(i,j,i+k-1,j+k-1))
{
ans = max(ans,k);
//cout<<ans<<endl;
}
}
cout<<ans<<endl;
return 0;
}
洛谷P2280激光炸弹
题目
很容易看出，此题和上题一样，是个二维前缀和的题目，但是由于处于正方形的边上的目标不会被摧毁，我们可以做一个转化，对二维前缀和来说，我们认为每个元素代表一个格子，所以，这题我们可以认为这些目标处于格子的中心，这样格子的左上角坐标是(Xi-0.5，Yi-0.5)，右下角坐标是(Xi+0.5，Yi+0.5)，而右下角处于格子交线上，所以我们依次枚举边长为R的正方形，利用二维前缀和维护答案即可。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 5050;
int a[N][N];
int u,r;
int main()
{
cin>>u>>r;
r = min(r,5001);
for(int i = 0; i<u; i++)
{
int x,y,w;
cin>>x>>y>>w;
a[x+1][y+1] = w;
}
//预处理前缀和
int n = 5001,m = 5001;
for(int i = 1; i<=n; i++)
for(int j = 1; j<=m; j++)
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
int ans = 0;
for(int i = r; i<=n; i++)
for(int j = r; j<=m; j++)
{
ans = max(ans,a[i][j] - a[i-r][j] - a[i][j-r] + a[i-r][j-r]);
//cout<<ans<<" "<<i<<" "<<j<<endl;
}
cout<<ans<<endl;
return 0;
}
洛谷P1114非常男女计划
题目描述
近来，初一年的XXX小朋友致力于研究班上同学的配对问题（别想太多，仅是舞伴），通过各种推理和实验，他掌握了大量的实战经验。例如，据他观察，身高相近的人似乎比较合得来。
万圣节来临之际，XXX准备在学校策划一次大型的“非常男女”配对活动。对于这次活动的参与者，XXX有自己独特的选择方式。他希望能选择男女人数相等且身高都很接近的一些人。这种选择方式实现起来很简单。他让学校的所有人按照身高排成一排，然后从中选出连续的若干个人，使得这些人中男女人数相等。为了使活动更热闹，XXX当然希望他能选出的人越多越好。请编写程序告诉他，他最多可以选出多少人来。
输入格式
第一行有一个正整数n，代表学校的人数。
第二行有n个用空格隔开的数，这些数只能是0或1，其中，0代表一个女生，1代表一个男生
输出格式
输出一个非负整数。这个数表示在输入数据中最长的一段男女人数相等的子序列长度。
如果不存在男女人数相等的子序列，请输出0。
先想一想暴力的方法，枚举左右端点，前缀和计算区间的和(把女生的值设为-1)，用ans来维护答案，这样暴力的复杂度是，显然是通过不了的，其实在第二层循环那里可以优化一下，第二层循环从后向前枚举，如果当前枚举区间的长度小于ans，直接break，效率将大大提升。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 101000;
int n;
int a[N];
int s[N];
int main()
{
scanf("%d",&n);
for(int i = 1; i<=n; i++)
{
scanf("%d",&a[i]);
if(!a[i]) a[i] = -1;
s[i] = s[i-1] + a[i];
}
int ans = 0;
for(int i = 1; i<=n; i++)
{
for(int j = n; j>=i+1; j--)
{
if(j-i+1 <ans) break; //如果当前枚举的长度小于ans，不需要再往后遍历了
if(s[j] - s[i-1] == 0)
ans = max(ans,j-i+1);
}
}
cout<<ans<<endl;
return 0;
}
(更新-2020-3-25)
Codeforces#Round624C题-Perform the combo
我们可以使用前缀和解决这道题目：先记录每个字母出现的次数，然后求一遍前缀和，累加到答案中即可。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e5+100;
int t,n,m;
int p[N], a[N][26],ans[26];
char s[N];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
scanf("%s",s+1);
for(int i = 1; i<=m; i++) scanf("%d",&p[i]);
//这里如果使用memset清空数组会超时
for(int i = 1; i<=n; i++)
for(int j = 0; j<26; j++)
a[i][j] = 0;
for(int i = 0; i<26; i++) ans[i] = 0;
//记录每个字符出现的次数
for(int i = 1; i<=n; i++) a[i][s[i]-'a'] ++;
//求一遍前缀和，ans[i][j]即表示前i个字符中，字母j一共出现了多少次
for(int i = 1; i<=n; i++)
for(int j = 0; j<26; j++)
a[i][j] += a[i-1][j];
for(int i = 1; i<=m; i++)
for(int j = 0; j<26; j++)
ans[j] += a[p[i]][j];
for(int i = 0; i<26; i++) ans[i] += a[n][i];
for(int i = 0; i<26; i++) printf("%d ",ans[i]);
puts("");
}
return 0;
}
网友评论