C2025 基础进阶——模拟与枚举

(10月来了，CSP也来了，教练布置了一堆基础巩固)

(也许zzb没有解释清楚，所以可以评论区@)

(共有10道题，但zzb不想更哩，就三道题吧awa)

「ABC176E」Bomber

【题目描述】

有一个 N*M 的二维矩阵，其中有 M 个目标。第 i 个目标的位置是 (，) 。

你现在有一个炸弹，可以选定一个位置投放炸弹，与炸弹位于同一行或同一列中的爆炸目标将被炸毁。求最多能摧毁多少个目标。

思路

思路有手就行（我没手？）

枚举炸弹放置的位置，判断能够摧毁的目标数量，找出最大值。

时间复杂度为O(HW(H+W))。（TLE自动机）

考虑优化

炸弹肯定放在行目标最多和列目标最多的交点处，统计出行最多的目标数x，列最多的目标数 y。

那答案就是x+y吗？

当然不是

如果x、y的交点上没有数，那肯定就是x+y

反之，就是x+y-1

但怎么判断交点上有没有数呢？（总不能O(HW)TLE来求吧）

我们就可以求有多少个最大行，多少个最大列

若一个目标处在交点处，那么这个交点就是x+y-1

如果交点都是x+y-1，答案就是x+y-1，反之就是x+y

代码如下

无注释代码

#include
using namespace std;
 
int h,w,m,mx,my,xx,yy,l,r,cnt,x[300005],y[300005],i;
pair<int,int>q[300005];
 
int main()
{
	scanf("%d%d%d",&h,&w,&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d%d",&l,&r);
		++x[l],++y[r];
		q[i]=make_pair(l,r);
	}
	for(i=1;i<=h;++i)
		if(mx
	for(i=1;i<=w;++i)
		if(my
	for(i=1;i<=h;++i)
		if(x[i]==mx) ++xx;
	for(i=1;i<=w;++i)
		if(y[i]==my) ++yy;
	for(i=1;i<=m;++i)
		if(x[q[i].first]==mx&&y[q[i].second]==my) ++cnt;
	printf("%d",mx+my-(cnt==xx*yy));
	return 0;
}

有注释代码

#include
using namespace std;
 
int h,w,m,mx,my,xx,yy,l,r,cnt,x[300005],y[300005],i;
pair<int,int>q[300005];
 
int main()
{
	scanf("%d%d%d",&h,&w,&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d%d",&l,&r);
		++x[l],++y[r];//记录行上的数量和列上的数量 
		q[i]=make_pair(l,r);//STL优化码量 
	}
	for(i=1;i<=h;++i)
		if(mx//行上最大值 
	for(i=1;i<=w;++i)
		if(my//列上最大值 
	for(i=1;i<=h;++i)
		if(x[i]==mx) ++xx;//有多少行为最大值 
	for(i=1;i<=w;++i)
		if(y[i]==my) ++yy;//有多少列为最大值 
	for(i=1;i<=m;++i)
		if(x[q[i].first]==mx&&y[q[i].second]==my) ++cnt;//有多少个目标处于最大行和最大列的交点上 
	printf("%d",mx+my-(cnt==xx*yy));//如果满足条件的目标与交点总数相等，就-1，反之不减 
	return 0;
}

「ABC129D」Lamp

【题目描述】

有一个 H 行 W 列的字符矩阵。

.表示空地，#表示障碍物。现在可以在.上放一盏灯，光线沿着上下左右传播，遇障碍物停止。问光线最多照亮几个空地。

 思路

第一思路：模拟plus（其实这道题与上一道题有点像有木有）

直接TLE自动机

枚举放的位置，O(HW(H+W))

然后又来想优化

枚举肯定没法，只能在计算空地时加大优化

可以想到（我没想到）用四个数组存储（X，Y）向四个方向的最大连续空地数量

易证：up[x,y]=up[x-1,y]+1

同理，别的也可以求出来

O(HW+HW)

直接AC

无注释代码

#include
using namespace std;
 
int ans,h,w,i,j,f[2001][2001][5];
char s[2001][2001];
 
int main()
{
	scanf("%d%d",&h,&w);
	for(i=1;i<=h;i++)
		for(j=1;j<=w;j++) cin>>s[i][j];
	for(i=1;i<=h;i++)
		for(j=1;j<=w;j++)
		{
			if(s[i][j-1]=='.') f[i][j][1]=f[i][j-1][1]+1;
			if(s[i-1][j]=='.') f[i][j][2]=f[i-1][j][2]+1;
		}
	for(i=h;i>=1;i--)
		for(j=w;j>=1;j--)
		{
			if(s[i][j+1]=='.') f[i][j][3]=f[i][j+1][3]+1;
			if(s[i+1][j]=='.') f[i][j][4]=f[i+1][j][4]+1;
			if(s[i][j]=='#') continue;
			ans=max(f[i][j][1]+f[i][j][2]+f[i][j][3]+f[i][j][4]+1,ans);
		}
	printf("%d",ans); 
	return 0;
}

有注释代码

#include//(感觉其实很像DP)
using namespace std;
 
int ans,h,w,i,j,f[2001][2001][5];
char s[2001][2001];
 
int main()
{
	scanf("%d%d",&h,&w);
	for(i=1;i<=h;i++)
		for(j=1;j<=w;j++) cin>>s[i][j];
	for(i=1;i<=h;i++)
		for(j=1;j<=w;j++)
		{
			if(s[i][j-1]=='.') f[i][j][1]=f[i][j-1][1]+1;//up
			if(s[i-1][j]=='.') f[i][j][2]=f[i-1][j][2]+1;//left
		}
	for(i=h;i>=1;i--)
		for(j=w;j>=1;j--)
		{
			if(s[i][j+1]=='.') f[i][j][3]=f[i][j+1][3]+1;//down
			if(s[i+1][j]=='.') f[i][j][4]=f[i+1][j][4]+1;//right
			if(s[i][j]=='#') continue;
			ans=max(f[i][j][1]+f[i][j][2]+f[i][j][3]+f[i][j][4]+1,ans);//max
		}
	printf("%d",ans); 
	return 0;
}

「ABC182E」Akari

【题目描述】

有一个 H 行 W 列的网格，定义 ( i，j ) 是第 i 行 j 列的方格。

这个网格上有 N 个灯泡和 M 个障碍物，第 i 个灯泡在 (,) 处，第 i 个障碍物在 (,) 处。每个方格保证最多只有一个灯泡或障碍物。

每一个灯泡都会将光照向上下左右四个方向延伸，直至遇到障碍物或到达边界。灯泡所在的方格也会有光照。

请你计算，被光照照到且没有障碍物的方格有多少。

 思路

（是不是与上一道题叕很像？）

这道题码量还大一点

首先，最容易想到的就是TLE思路：

暴力枚举每一个灯

比如:

(画得好丑呀awa)

但当枚举是，其实是会有重复浪费的部分的，比如（2，3）与（3，2）

把它拆开看

其实可以这样遍历（更丑了QWQ）

实际就是把他拆成四个方向

对于每一行，从左往右遍历。考虑灯泡往右照射到的空地。

 如果遇到一个灯泡，那么说明此时有光线，标记 flag=1。如果遇到障碍，说明往右的光线被挡住了，flag=0。如果遇到空地，flag 为 1 表示这个空地能够被灯泡照到，进行记录；flag 为 0 表示这个空地不能够被灯泡照到。

这样，对于每一行，从左往右遍历，可以找出灯泡往右照射到的所有空地。• 按照同样的方式，找出灯泡往左，往上，往下照射到的所有空地。

时间复杂度为 O(4HW)。

是不是很绕？

看代码

无注释代码

#include
using namespace std;
 
int n,m,N,M,x,y,f,C,a[1501][1501],i,j;
 
int main()
{
    scanf("%d%d%d%d",&n,&m,&N,&M);
    for(i=1;i<=N;i++) scanf("%d%d",&x,&y),a[x][y]=2;
    for(i=1;i<=M;i++) scanf("%d%d",&x,&y),a[x][y]=3;
    for(i=1;i<=n;i++)
	{
		f=0;
		for(j=1;j<=m;j++)
		{
			if(a[i][j]==2) f=1;
			else if(a[i][j]==3) f=0;
			else if(f==1) a[i][j]=1;
		}
	}
    for(i=1;i<=n;i++)
	{
		f=0;
		for(j=m;j>=1;j--)
		{
			if(a[i][j]==2) f=1;
			else if(a[i][j]==3) f=0;
			else if(f==1) a[i][j]=1;
		}
	}
    for(i=1;i<=m;i++)
	{
		f=0;
		for(j=1;j<=n;j++)
		{
			if(a[j][i]==2) f=1;
			else if(a[j][i]==3) f=0;
			else if(f==1) a[j][i]=1;
		}
	}
    for(i=1;i<=m;i++)
	{
		f=0;	
		for(j=n;j>=1;j--)
		{
			if(a[j][i]==2) f=1;
			else if(a[j][i]==3) f=0;
			else if(f==1) a[j][i]=1;
		}
	}
    for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(a[i][j]==1) C++;
    printf("%d",C+N);
}

有注释代码

#include
using namespace std;
 
int n,m,N,M,x,y,f,C,a[1501][1501],i,j;
 
int main()
{
    scanf("%d%d%d%d",&n,&m,&N,&M);
    for(i=1;i<=N;i++) scanf("%d%d",&x,&y),a[x][y]=2;
    for(i=1;i<=M;i++) scanf("%d%d",&x,&y),a[x][y]=3;
    //枚举四个方向 
	for(i=1;i<=n;i++)
	{
		f=0;
		for(j=1;j<=m;j++)
		{
			if(a[i][j]==2) f=1;//是灯 
			else if(a[i][j]==3) f=0;//照不到了 
			else if(f==1) a[i][j]=1;//照得到 
		}
	}
    for(i=1;i<=n;i++)
	{
		f=0;
		for(j=m;j>=1;j--)
		{
			if(a[i][j]==2) f=1;//同上 
			else if(a[i][j]==3) f=0;
			else if(f==1) a[i][j]=1;
		}
	}
    for(i=1;i<=m;i++)
	{
		f=0;
		for(j=1;j<=n;j++)
		{
			if(a[j][i]==2) f=1;///同上 
			else if(a[j][i]==3) f=0;
			else if(f==1) a[j][i]=1;
		}
	}
    for(i=1;i<=m;i++)
	{
		f=0;	
		for(j=n;j>=1;j--)
		{
			if(a[j][i]==2) f=1;//同上 
			else if(a[j][i]==3) f=0;
			else if(f==1) a[j][i]=1;
		}
	}
    for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(a[i][j]==1) C++;//有C个空地被照到了 
    printf("%d",C+N);//+N个灯 
    return 0;
}