自动搬运

查看原文

来自洛谷，原作者为

	CaoXian 这是我初一的成就，也是我最后的成就，几年学习终究是证明了自己的上限

搬运于2025-08-24 22:32:45，当前版本为作者最后更新于2021-09-18 14:42:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P7749 [COCI2013-2014#2] MISA 题解

思路：先求出 Mirko 没入座时人们的握手次数，再枚举 Mirko 入座的位置，若这个座位为空，那么计算 Mirko 在这个位置入座的握手次数，求出最大值。否则跳过。最后输出 Mirko 可以握手的最大次数加上 Mirko 没入座的所有人的握手次数。

对于刚开始 Mirko 没入座时所有人的握手次数，可以把每个人的的握手次数相加，最后除以 2 。因为握手时双向的，计算过程中，每一次握手都被计算了两次，所以最后要除以 2 。

还有两个小优化：

1. 若会场坐满了，可以直接输出，不用枚举 Mirko 入座的位置，因为他无处可坐了。
2. 如果枚举到某一时刻， Mirko 可以握手的人数为 8 ，可直接输出答案，因为一个人最多与周围八个人握手。

Code：

#include <stdio.h>
#define clac(r, c) (flag[r - 1][c - 1] + flag[r - 1][c] + flag[r - 1][c + 1] + flag[r][c - 1] + flag[r][c + 1] + flag[r + 1][c - 1] + flag[r + 1][c] + flag[r + 1][c + 1])//计算握手的人数 
#define max(a, b) ((a) > (b) ? (a) : (b))//手写max函数 
bool bol = true, flag[64][64];
int n, m, sum, ans;
char ch[64][64];
int main() {
	scanf("%d%d", &n, &m);
	getchar();
	for(int i = 1; i <= n; ++i) scanf("%s", ch[i] + 1);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			bol &= flag[i][j] = (ch[i][j] == 'o');//其实这里这样写是为了偷懒，可以写成flag[i][j] = (ch[i][j] == 'o'); if(!flag[i][j]) bol = false;
	//计算Mirko没入座时人们的握手情况
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			if(flag[i][j]) sum += clac(i, j);
	sum /= 2;
	if(bol) return 0 * printf("%d", sum);//第一种优化 
	//枚举Mirko的位置
   for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j) {
			if(!flag[i][j]) ans = max(ans, clac(i, j));//i行j列位置Mirko的握手次数
			if(ans == 8) return 0 * printf("%d", sum + ans);//第二种优化 
		}
	printf("%d", sum + ans);
	return 0;
}