题目详情题解（0）讨论（0）提交记录（0）

AT_agc059_e.[AGC059E] Grid 3-coloring

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个 N×NN \times N 的方格棋盘。你需要用三种颜色给所有格子染色，要求任意相邻（共享边）的两个格子颜色不同。

棋盘最外层的格子已经被染色。请判断是否可以按照要求给剩下的格子染色。

更准确地说，给定一个由字符 1、2、3 组成的长度为 4N−44N-4 的字符串 SS，该字符串表示从 (1,1)(1, 1) 开始，按顺时针顺序记录的最外层格子的颜色。具体地，第 ii 个字符表示如下格子的颜色：

  • 当 1≤i≤N−11 \leq i \leq N-1 时，对应 (1,i)(1, i)；
  • 当 N≤i≤2N−2N \leq i \leq 2N-2 时，对应 (i−(N−1),N)(i - (N-1), N)；
  • 当 2N−1≤i≤3N−32N-1 \leq i \leq 3N-3 时，对应 (N,3N−1−i)(N, 3N-1-i)；
  • 当 3N−2≤i≤4N−43N-2 \leq i \leq 4N-4 时，对应 (4N−2−i,1)(4N-2-i, 1)。

其中，(r,c)(r, c) 表示第 rr 行第 cc 列的格子。

保证最外层格子中，任意相邻的两个格子颜色不同。

对于每个输入文件，请判断是否存在一种方案，可以用三种颜色给剩下的格子染色，使得任意相邻格子颜色不同。

输入格式

输入从标准输入读入，格式如下：

TT
case1case_1
case2case_2
⋮\vdots
caseTcase_T

每个测试用例格式如下：

NN SS

输出格式

对于每个测试用例，如果存在一种方案可以按照要求用三种颜色染色，则输出 YES，否则输出 NO。输出时不区分大小写。

输入输出样例

  • 输入#1

    4
3
12312312
4
121212121212
7
321312312312121212121321
7
321312312312121312121321

    输出#1

    NO
YES
NO
YES

说明/提示

限制

  • 1≤T≤5⋅1041 \leq T \leq 5 \cdot 10^4
  • 3≤N≤2⋅1053 \leq N \leq 2 \cdot 10^5
  • SS 是由字符 1、2、3 组成的长度为 4N−44N-4 的字符串。
  • 对于 1≤i≤4N−51 \leq i \leq 4N-5，有 Si≠Si+1S_i \neq S_{i+1}，且 S4N−4≠S1S_{4N-4} \neq S_1。
  • 每个输入文件中所有 NN 的总和不超过 2⋅1052 \cdot 10^5。
  • 输入中的所有数字均为整数。

样例解释 1

对于第一个和第三个测试用例，可以证明无法按照要求染色。对于第二个和第四个测试用例，下面给出了可以按照要求染色的方案。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页