P5292 [HNOI2019]校园旅行

    • 193通过
    • 637提交
  • 题目提供者 「QQ红包」 发红包了
  • 评测方式 云端评测
  • 标签 各省省选 2019 湖南
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    HNOI2019 day2t1

    题目描述

    某学校的每个建筑都有一个独特的编号。一天你在校园里无聊,决定在校园内随意地漫步。

    你已经在校园里呆过一段时间,对校园内每个建筑的编号非常熟悉,于是你情不自禁的把周围每个建筑的编号都记了下来——但其实你没有真的记下来,而是把每个建筑的编号除以 2 取余数得到 0 或 1,作为该建筑的标记,多个建筑物的标记连在一起形成一个 01 串。

    你对这个串很感兴趣,尤其是对于这个串是回文串的情况,于是你决定研究这个问题。

    学校可以看成一张图,建筑是图中的顶点,而某些顶点之间存在无向边。对于每个顶点我们有一个标记(0 或者 1)。每次你会选择图中两个顶点,你想知道这两个顶点之间是否存在一条路径使得路上经过的点的标记形成一个回文串。

    一个回文串是一个字符串使得它逆序之后形成的字符串和它自己相同,比如“010”,“1001”都是回文串,而“01”,“110”不是。注意长度为 1 的串总是回文串,因此如果询问的两个顶点相同,这样的路径总是存在。此外注意,经过的路径不一定为简单路径,也就是说每条边每个顶点都可以经过任 意多次。

    输入输出格式

    输入格式:

    输入文件名为 tour.in。

    第一行三个整数 $n,m,q$ ,表示图中的顶点数和边数,以及询问数。

    第二行为一个长度为$n$的 01 串,其中第$i$个字符表示第 $i$ 个顶点(即顶点 $i$)的标记,点从 1 开始编号。

    接下来$m$行,每一行是两个整数$u_i$,$v_i$,表示顶点$u_i$ 和顶点 $v_i$ 之间有一条无向边,不存在自环或者重边。

    接下来$q$行,每一行存在两个整数 $x_i,y_i$,表示询问顶点$x_i$和顶点$y_i$的点之间是否有一条满足条件的路径。

    输出格式:

    输出文件名为 tour.out。

    输出$q$行,每行一个字符串“YES”,或者“NO”(引号不输出)。输出“YES”表示满足条件的路径存在,输出“NO”表示不存在。

    输入输出样例

    输入样例#1: 复制
    5 4 2
    00010
    4 5
    1 3
    4 2
    2 5
    3 5
    1 3
    
    输出样例#1: 复制
    NO
    YES
    输入样例#2: 复制
    10 11 10
    0011011111
    4 6
    10 6
    5 9
    4 7
    10 7
    5 8
    1 9
    5 7
    1 10
    5 1
    5 6
    10 3
    7 4
    8 10
    9 4
    8 9
    6 6
    2 2
    9 9
    10 9
    3 4
    输出样例#2: 复制
    NO
    YES
    YES
    NO
    YES
    YES
    YES
    YES
    YES
    NO

    说明

    【样例解释 1】 对于第一个询问,3 号点和 2 号点不连通, 因此答案为“NO”。

    对于第二个询问,一条合法的路径是1 → 3,路径上的标号形成的字符串为“00”。注意合法路径 不唯一。

    【数据范围】

    对于 30%的数据,$1 ≤ m ≤ 10000$;

    对于 70%的数据,$1 \leq n \leq 3000$ , $1 ≤ m ≤ 50000$;

    对于 100%的数据,$1 ≤ n ≤ 5000$ , $1 ≤ m ≤ 500000$ , $1 ≤ q ≤ 100000$。

    【编译命令】

    对于 c++语言: g++ -o tour tour.cpp –lm -O2

    对于 c 语言: gcc -o tour tour.c –lm -O2

    对于 pascal 语言: fpc tour.pas -O2

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。