列表

详情

NC218831. 集训队长魂牵梦绕的题目

描述

（现任zafu集训队队长wzc在他初学ACM时写到一道经典好题，一直想着什么时候个人赛拉过来让大家写一写。可惜当时的他没有整理代码记录题目题号的习惯，导致一直找不到那道题在哪。
现在他借由这次出题机会依靠回忆出了这道题，来了却这桩萦绕了许久的心事。）

因为Lucifer糟糕的脾气和行事风格，他的挚友Sariel再也无法忍受他，躲进了堕天使花园的最深处。
堕天使花园是一个2行n列的方格矩阵，Sariel躲在了最深处，右下角的[2][n]处。
Lucifer从左上角[1][1]出发，试图走到Sariel所在的位置向他道歉。
Lucifer每次移动只能移动到当前位置上下左右四个相邻的格子上，且不能走出矩阵外。
可是堕天使花园里不是所有的格子都是安全的，有一部分格子踩上去会使Lucifer失去对自己灵魂的控制，因此他决不能踩到这些格子上。
也就是说，很有可能Lucifer无法走到Sariel面前道歉。

可是由于Sariel有时候会由于心软，会将某个不安全的格子变成安全的，有时候也会由于不想见Lucifer，会把某个安全的格子变成不安全的。(每次修改的结果都会对后续造成影响）
你需要告诉Lucifer，初始的时候以及Sariel每次对堕天使花园修改后，Lucifer能否能否走到Sariel面前道歉。
（题目保证，任意时刻[1][1]和[2][n]位置都是安全的，即Lucifer所在的初始位置和Sariel所在的位置都是安全的）

输入描述

第一行为一个正整数n，代表堕天使花园矩阵有几列。（1<=n<=1e6）
接下来第二行为n个空格隔开的整数a1,a2,...,an。（ai只可能为0或1，代表矩阵[1][i]位置是安全还是不安全，0代表安全，1代表不安全）
接下来第三行为n个空格隔开的整数b1,b2,...,bn。（bi只可能为0或1，代表矩阵[2][i]位置是安全还是不安全，0代表安全，1代表不安全）
第四行为一个整数m，代表Sariel会对堕天使花园做几次修改。（0<=m<=1e6）
接下来m行，每行为两个被空格隔开的整数x和y，代表位置[x][y]的格子被修改，如果该格子是安全的则被修改为不安全的，如果该格子是不安全的则被修改为安全的。
（1<=x<=2，1<=y<=n）

输出描述

输出m+1行，第一行对应初始情况，2到m+1行对应m次修改后的情况。
每种情况，如果Lucifer能成功走到Sariel面前道歉，输出"I'm the worst friend.Please forgive me."
如果Lucifer无法走到Sariel面前道歉，输出"You are the worst friend."

示例1

输入: 

4
0 0 0 0
0 0 0 0
7
1 2
2 2
1 3
2 3
2 3
1 2
1 3

输出: 

I'm the worst friend.Please forgive me.
I'm the worst friend.Please forgive me.
You are the worst friend.
You are the worst friend.
You are the worst friend.
You are the worst friend.
You are the worst friend.
I'm the worst friend.Please forgive me.

说明:

初始地图为
0 0 0 0
0 0 0 0
第一次修改后变为
0 1 0 0
0 0 0 0
第二次修改后变为
0 1 0 0
0 1 0 0
第三次修改后变为
0 1 1 0
0 1 0 0
第四次修改后变为
0 1 1 0
0 1 1 0
第五次修改后变为
0 1 1 0
0 1 0 0
第六次修改后变为
0 0 1 0
0 1 0 0
第七次修改后变为
0 0 0 0
0 1 0 0

示例2

输入: 

4
0 1 0 0
0 0 1 0
6
2 2
1 3
2 3
2 3
1 2
1 3

输出: 

You are the worst friend.
You are the worst friend.
You are the worst friend.
You are the worst friend.
You are the worst friend.
You are the worst friend.
I'm the worst friend.Please forgive me.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C(clang11) 解法, 执行用时: 417ms, 内存消耗: 33528K, 提交时间: 2021-03-07 16:26:35 

#include <stdio.h>
const int max = 1e6;

int map[2][max];
int flag;
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < 2; i++)
	{
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &map[i][j]);
		}
	}
	for (int i = 1; i < n-1; i++)
	{
		if (map[0][i] == 1)
		{
			if (map[1][i - 1] == 1)
				flag++;
			if (map[1][i] == 1)
				flag++;
			if (map[1][i + 1] == 1)
				flag++;
		}
	}
	int m;
	scanf("%d", &m);
	while (m--)
	{
		if (!flag)
			printf("I'm the worst friend.Please forgive me.\n");
		else
			printf("You are the worst friend.\n");
		//printf("%5d\n", flag);
		int x, y;
		scanf("%d%d", &x, &y);
		x--; y--;
		int chang = map[x][y];
		if (chang==0)
		{
			map[x][y] = 1;
			if (map[!x][y - 1] == 1)
				flag++;
			if (map[!x][y] == 1)
				flag++;
			if (map[!x][y + 1] == 1)
				flag++;
		}
		else
		{
			map[x][y] = 0;
			if (map[!x][y - 1] == 1)
				flag--;
			if (map[!x][y] == 1)
				flag--;
			if (map[!x][y + 1] == 1)
				flag--;
		}
	}
	if (!flag)
		printf("I'm the worst friend.Please forgive me.\n");
	else
		printf("You are the worst friend.\n");
	return 0;
}

C++(clang++11) 解法, 执行用时: 459ms, 内存消耗: 46320K, 提交时间: 2021-03-12 19:49:28 

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

int a[3][1000007],n,m,x,y;

int check(int i,int j){	//1表示有危险，0表示没危险 
	int res=0;
	if(a[3-i][j]) res++;
	if(a[3-i][j-1]&&j!=1) res++;
	if(a[3-i][j+1]&&j!=n) res++; 
	return res;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=2;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	int cnt=0;
	for(int j=1;j<=n;j++)
		if(a[1][j])
			cnt+=check(1,j);
		
	scanf("%d",&m);
	if(!cnt) printf("I'm the worst friend.Please forgive me.\n");
	else printf("You are the worst friend.\n");
	while(m--){
		scanf("%d %d",&x,&y);
		if(a[x][y]){
			a[x][y]=0;
			cnt-=check(x,y);
			if(cnt<0) cnt=0;	
		}
		else{
			a[x][y]=1;
			cnt+=check(x,y);	
		}
		if(!cnt) printf("I'm the worst friend.Please forgive me.\n");
		else printf("You are the worst friend.\n");
	}
}

上一题

© 2024 nowcoder.com