2023青岛市程序设计竞赛小学组题解

1.付钱

题目链接：https://www.luogu.com.cn/problem/U303904

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	ll n;cin>>n;
	cout<<n/100<<' '<<(n%100)/50<<' '<<(n%50)/20<<' '<<(n%50%20)/10<<' '<<(n%10)/5<<' '<<n%5;
	return 0;
}

解题思路：

最简单的贪心，签到题

2.开关灯

题目链接：https://www.luogu.com.cn/problem/U303899

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	int T;cin>>T;
	while(T--){
		int n,m,k;
		bool flag=0;
		cin>>n>>m>>k;
		for(int x=0;x<=n;x++){
			for(int y=0;y<=m;y++){
				if(x*m+y*n-2*x*y==k){
					cout<<"Yes\n";
					flag=1;
					break;
				}
			}
			if(flag)break;
		}
		if(!flag)cout<<"No\n";
	}
	return 0;
}

解题思路：

枚举点亮行数和列数，计算量的灯数，判断是否为k即可

错误原因：

考虑不周全，条件只有1条

3.正方形

题目链接：https://www.luogu.com.cn/problem/U303907

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3+39+7;
int a[N][N];
ll ans=1e15,n,sum[N][3];bool flag=0;
void dfs(int pre,int tr,ll xsum){
	if(tr>n&&pre<2)return;
	else if(tr>n&&pre==2){
		ans=min(ans,xsum);
		return;
	}
	dfs(pre,tr+1,xsum+sum[tr][pre]);
	if(pre+1<=2)dfs(pre+1,tr+1,xsum+sum[tr][pre+1]);
}
int main(){
//	freopen("square.in","r",stdin);
//	freopen("square.out","w",stdout);
	memset(sum,0,sizeof(sum));
	cin>>n;int t=2*n-1;
	for(int i=1;i<=t;i++){
		for(int j=1;j<=t;j++){
			cin>>a[i][j];
		}
	}
	if(a[n][n]!=0)flag=1,a[n][n]=0;
	for(int quan=2;quan<=n;quan++){
		for(int color=0;color<3;color++){
			for(int i=n-quan+1;i<=n+quan-1;i++){
				if(i==n-quan+1||i==n+quan-1){
					for(int j=n-quan+1;j<=n+quan-1;j++)
						sum[quan][color]+=(a[i][j]==color?0:1);
				}else{
					sum[quan][color]+=(a[i][n-quan+1]==color?0:1);
					sum[quan][color]+=(a[i][n+quan-1]==color?0:1);
				}
			}
		}
	}
	dfs(0,1,0);
	cout<<ans+(flag);
	return 0;
}

#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ll long long
using namespace std;
const int N = 5e2+39+7;
const ll INF = 0x7fffffffffff;
ll n,a[N*2][N*2],cnt[N][3],ans=INF;
inline int Hash(int x,int y){return n-max(max(n-x,x-n),max(n-y,y-n));}
int main(){
	cin>>n;
	for(int i=1;i<=2*n-1;i++){
		for(int j=1;j<=2*n-1;j++){
			cin>>a[i][j];
			cnt[Hash(i,j)][a[i][j]]++;
		}
	}
	for(int i=2;i<n;i++){
		for(int j=i+1,sum=0;j<=n;j++,sum=0){
			for(int k=1;k<=n;k++){
				ll all=8*n-8*k;
				if(!all)all=1;
				if(k<i)sum+=all-cnt[k][2];
				else if(k<j)sum+=all-cnt[k][1];
				else sum+=all-cnt[k][0];
			}
			ans=min(ans,sum);
		}
	}
	cout<<ans;
	return 0;
}

解题思路：

方法1：统计每一层同时改变成同一种颜色需要多少次，使用深搜，求最小和即可

方法2：统计每一层每一种颜色各有多少个，枚举颜色区间，取最小和即可