自动搬运

查看原文

来自洛谷，原作者为

	ShanCreeperPro DILL QQTeam：746219450

搬运于2025-08-24 22:37:22，当前版本为作者最后更新于2022-04-01 18:49:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P8254 [NOI Online 2022 入门组] 王国比赛

update：

2022.4.5 更新了大家好奇的 TLE 做法和突然心血来潮的 Go 语言做法。

---

这道题有一个坑：

• 题目中为 $n$ 题 $m$ 人，可是输入数据是 $m$ 行 $n$ 列。

还不理解？看看这个样例就知道了：

3 3
1 0 1
0 1 1
0 1 0
1 1 1

以正常的想法，应该是 1 0 1，0 1 1，0 1 0 这三个数据为一题大臣的判断，可是由于是 $n$ 行 $m$ 列，导致了你需要“竖”着看，即 1 0 0，0 1 1，1 1 0 为三道题的判断。

新手容易上当（包括我都蒙了一会）。

---

TLE 做法：

inline void part2(){
	fore(i,1,m){
		fore(j,1,n){
			if(a[i][j]==0) b[j].x++;
			else if(a[i][j]==1) b[j].y++;
		}	
	}
	fore(i,1,m){
		if(b[i].x>z) pd[i]=0;
		else pd[i]=1;	
	}
	fore(i,1,n){
		if(pd[i]==ans[i]) sum++;
    }
	write(sum);	
}

这个 TLE 的原因非常明显。

所以我们要尽可能把他们放在一起处理。

---

接着讲正解。

• 我们可以定义一个二维数组 $a$ 来存每道题大臣的答案，用 $b$ 存正确的答案，并读入，读入时记得外层循环终止条件为 $m$，内层为 $n$：

（C++）：

#define fore(i,x,n) for(int i=x;i<=n;i++)
int n,m,a[MAXX][MAXX],b[MAXX];
fore(i,1,m)
	fore(j,1,n)
    	a[i][j]=read();
fore(i,1,n) b[i]=read();

（Go）：

var i,j int
fmt.Scan(&n,&m)
for i=1;i<=m;i++{
	for j=1;j<=n;j++{
		fmt.Scan(&a[i][j])
	}
}
for i=1;i<=n;i++{
	fmt.Scan(b[i])
}

• 定义 $x$ 为单个问题猜测正确的人数，$y$ 为猜测错误的人数，如果 $x>y$ 则猜测为对，否则为错：

（C++）：

fore(j,1,n){
	x=0; y=0;
	fore(i,1,m){
		if(a[i][j]==1) x++;
		else y++;
	}
	if(x>y) sum=1;
	else sum=0;

（Go）：

for j=1;j<=n;j++{
	x=0
	y=0
	for i=1;i<=m;i++{
		if a[i][j]==1{
			x++
		} else {
			y++
		}
		if x>y{
			sum=1
		} else {
			sum=0
		}

（这里记得将外层循环设为 $n$，内层为 $m$。）

• 最后进行判断，如果判断对了 ans 增加 1，最后输出：

（C++）：

	if(sum==b[j]) ans++;
}
write(ans);

（Go）：

		if sum==b[j]{
			ans++
		}
	}
}
fmt.Println(ans);

时间复杂度 $O(mn)$，可以通过本题。

AC 代码：

（C++）：

#include<bits/stdc++.h>
#define int long long
#define fore(i,x,n) for(int i=x;i<=n;i++)
using namespace std;
const int MAXX=1005;
int n,m,a[MAXX][MAXX],b[MAXX];
int x,y,c=1,sum,ans;
const int mod=1;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
signed main(){
	n=read();
	m=read();
	fore(i,1,m)
		fore(j,1,n)
			a[i][j]=read();
	fore(i,1,n) b[i]=read();
	fore(j,1,n){
		x=0; y=0;
		fore(i,1,m){
			if(a[i][j]==1) x++;
			else y++;
		}
		if(x>y) sum=1;
		else sum=0;
		if(sum==b[j]) ans++;
	}
	write(ans);
}

（Go）：

package main
import "fmt"
var n,m,x,y,sum,ans int
var a[1005][1005] int
var b[1005] int
var c=1
func main(){
	var i,j int
	fmt.Scan(&n,&m)
	for i=1;i<=m;i++{
		for j=1;j<=n;j++{
			fmt.Scan(&a[i][j])
		}
	}
	for i=1;i<=n;i++{
		fmt.Scan(b[i])
	}
	for j=1;j<=n;j++{
		x=0
		y=0
		for i=1;i<=m;i++{
			if a[i][j]==1{
				x++
			} else {
				y++
			}
			if x>y{
				sum=1
			} else {
				sum=0
			}
			if sum==b[j]{
				ans++
			}
		}
	}
	fmt.Println(ans);
}

后记：

比赛时脑抽写了个 TLE 的代码气死我了呜呜呜。