NOIP2025模拟赛21总结

ǒεγδφψωζ

2025-08-14 17:57:59

发布于：陕西

20阅读

0回复

0点赞

T1	T2	T3	T4
${\color{#52C41A} 普及+/提高}$	${\color{#3498DB} 提高+/省选− }$	${\color{purple} 省选/NOI−}$	${\color{black} NOI/NOI+/CTSC }$

参赛网址：https://oj.33dai.cn/d/TYOI/contest/6899b750c5d9c2f14c1fd4cb

T1 小明与魔法【NOIP2025模拟赛T1】

题目传送门

题目难度： ${\color{#52C41A} 普及+/提高}$

算法标签：贪心

思路

特殊性质 $A$ ：存在 $1\le i\le n$ ，使得对任意 $1\le j\le n$ ，均有 $c_{i,j}=1$ 。

子问题 $\alpha$ ：当特殊性质 $A$ 的约束下，即至少有 $1$ 行全是 $1$ ，所以可以直接用这一行去补全不是全 $1$ 的列。

然后，在一般情况，我们考虑构造全 $1$ 行。

对于任意一行，每一个 $0$ 都需要 $1$ 次代价修改为 $1$ 。如上图。

可能有点难，就是让所有的0都通过转换制度变为1。

所以枚举每一行，然后判断每一行的 $0$ 的个数，取最小值后转化成了子问题 $\alpha$ 。我们就做完了

95 Wrong Answer

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=3005;
const int inf=1e18+7;
int n;
int ans=inf;
int vis[maxn];
char a[maxn][maxn];

signed main(){
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			cin>>a[i][j];
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (a[i][j]=='1')	vis[i]=1;
	for (int i=1;i<=n;i++){
		int f=0;
		for (int j=1;j<=n;j++){
			if (a[i][j]=='1')	continue;
			f++;
		}
		ans=min(ans,f);
	}
	for (int i=1;i<=n;i++){
		int f=0;
		for (int j=1;j<=n;j++){
			if (a[j][i]=='0')	f=1;
		}
		ans+=f;
	}
	cout<<ans;
	return 0;
}

吗？

我们发现，当这一行全是 $0$ 时，答案 $++$ 。

AC Code

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=3005;
int n,qw,minn=inf;
char ch[maxn][maxn];
bool l[maxn];
signed main(){
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>ch[i][j];
	for(int j=1;j<=n;j++){
		qw++;
		for(int i=1;i<=n;i++){
			if(ch[i][j]=='0'){
				qw--;
				break;
			}
		}
		for(int i=1;i<=n;i++){
			if(ch[i][j]=='1'){
				l[j]=1;
				break;
			}
		}
	}
	for(int i=1;i<=n;i++){
		int cnt=0;
		if(!l[i])cnt++;
		for(int j=1;j<=n;j++)if(ch[i][j]=='0')cnt++;
		minn=min(minn,cnt);
	}
	cout<<minn+n-qw;
	return 0;
}