CF2052F.Fix Flooded Floor

普及+/提高

通过率:0%

AC君温馨提醒

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

题目描述

阿基米德曾进行过著名的浮力实验。然而,少有人知道,在他一次洗澡时,因过于专注,未能及时注意水溢出了浴缸,淹没了靠墙的地板,导致他昂贵的木地板受到不可修复的损坏。

细心的阿基米德发现,并不是所有的地板都受损了。靠近墙的一部分完好的木地板呈现出 2×n2 \times n 的窄长条状。阿基米德手头有无限数量的 1×21 \times 2 的木板块,这些板块可以顺着或垂直于墙壁放置。他不想对这些木板进行切割。作为一名伟大的科学家,他算出了填补受损区域只有一种方法能成功。

请协助历史学家核实阿基米德的计算。对于给定的 2×n2 \times n 木地板布局,确定是否确实仅有一种方法可以用 1×21 \times 2 的木板块填补受损区域。如果阿基米德的计算有误,请判断是否有多种填补方式,或者说根本没有办法完成修复。

输入格式

第一行为一个整数 TT(1≤T≤1041 \le T \le 10^4),表示需要处理的测试用例数量。

接下来的每个测试用例描述如下:

  • 第一行包含一个整数 nn(1≤n≤2×1051 \le n \le 2 \times 10^5),表示木地板的长度。
  • 接下来的两行每行包含 nn 个字符,描述了木地板的状态,其中 . 表示受损的单元格,# 表示未受损的单元格。

所有测试用例中,nn 的总和不超过 2×1052 \times 10^5。

输出格式

对于每个测试用例,输出 Unique,如果只有一种方法可以修复;输出 Multiple,如果有多种修复方案;输出 None,如果没有可行的修复方案。

本翻译由 AI 自动生成

输入输出样例

  • 输入#1

    4
    10
    #.......##
    ##..#.##..
    6
    ...#..
    ..#...
    8
    ........
    ........
    3
    ###
    ###

    输出#1

    Unique
    None
    Multiple
    Unique

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

首页