课时训练06

T638487 打扫卫⽣

当我一看到这个题目时，首先想到了枚举抹布所擦区域左上角的位置，如果是脏的，就遍历抹布所擦区域，看是不是全脏，如果是就把它全部变干净，最后再看地板是不是全部都变成干净的了；但因为没有考虑清楚什么时候应该输出-1，终止循环加上代码中的一些小问题导致只得了二十分，代码如下

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k,num;
map<int,string> v;
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for (int i=0;i<n;i++) cin>>v[i];
	for (int i=0;i<=n-k;i++)
		for (int j=0;j<=m-k;j++){
			if (v[i][j]=='*'){
				bool t=true;
				for (int l=i;l<=i+k-1&&t;l++)
					for (int p=i;p<=j+k-1&&t;p++)
						if (v[l][p]!='*')
							t=false;
				if (t){
					num++;
					for (int l=i;l<=i+k-1&&t;l++)
						for (int p=j;p<=j+k-1&&t;p++)
							v[l][p]='.';				
				}
			}
		}
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			if (v[i][j]!='.'){
				printf("-1");
				return 0;
			}
	printf("%d",num);
}

后来听完老师的讲解后,发现只要找到一个左上角不是全脏，就可以输出-1，终止程序，正解如下

代码

#include<bits/stdc++.h> 
using namespace std;
int n,m,k;
vector<vector<char>> a; //当作二维char数组使用
long long ans; //统计最后答案
int main(){
	scanf("%d%d%d",&n,&m,&k);
	a.resize(n+5,vector<char>(m+5)); 
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			cin>>a[i][j];
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){ //枚举左上角位置
			if (a[i][j]=='*'){
				long long num=0;
				for (int l=i;l<=min(n,i+k-1);l++)
					for (int p=j;p<=min(m,j+k-1);p++)//遍历抹布所擦的区域
						if (a[l][p]=='*')
							num++,a[l][p]='.';
				if (num==1LL*k*k) ans++;//判断是否全脏	
				else {
					printf("-1");
					return 0;
				}			
			}
		}
	printf("%lld",ans);
}

T640726 落落的去的围栏

等我写完前四道题以后，留给这道题的时间已经只剩十分钟了，准备只拿部分分，但因为代码中的一些问题得了零 分

后来听完老师的讲解后，知道这道题应该枚举第一种颜色占了栅栏的几块木板k,然后二分出大于等于k和大于等于n减k块木板的颜色种类数x,y，让最后的答案加上x乘y减重复的数量，正解如下

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,m,a[200001];
int main(){
	scanf("%d",&t);
	while (t--){
		scanf("%d%d",&n,&m);
		for (int i=1;i<=m;i++){ 
			scanf("%d",&a[i]),a[i]=min(a[i],n-1);
		}
		sort(a+1,a+m+1);
		long long num=0;
		for (int i=1;i<n;i++){
			int l=lower_bound(a+1,a+m+1,i)-a;
			int p=lower_bound(a+1,a+m+1,n-i)-a;
			int o=m-l+1,b=m-p+1;
			num+=1LL*o*b-min(o,b);
		}
		printf("%lld\n",num);
	}
}

本次总结就到这里，感谢观看！