P3552 [POI2013]SPA-Walk

    • 3通过
    • 11提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 哈希,HASH 数论,数学 POI 2013 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    The names of towns in Byteotia are unique sequences of exactly $n$ bits.

    There are $2^n-k$ towns in Byteotia, and thus,only $k$ sequences of $n$ bits do not correspond to any town.

    Some pairs of towns are connected with roads.

    Specifically, two towns are directly linked by a road if and only if their names differ in a single bit.

    The roads do not cross outside of towns.

    Byteasar intends to take a stroll - he intends to walk from the town $x$ to the town $y$, taking the existing roads.

    Your task is to write a program that will determine if such a walk is possible.

    有2^n个长度为n的01串,两个01串之间有边当且仅当这两个01串只有一位不同,现在从这2n个串中拿掉k个,问指定两个串之间能否到达

    输入输出格式

    输入格式:

    In the first line of the standard input, there are two integers,$n$ and $k$($1\le n\le 60$, $0\le k\le 1\ 000\ 000$, $k\le 2^n-1$, $n\times k\le 5\ 000\ 000$), separated by a single space.

    These are the length of town names in bits and the the number of $n$-bit sequences that do not correspond to any town, respectively.

    In the second line, there are two strings, separated by a single space, each consisting of $n$ characters 0 and/or 1.

    These are the names of the towns $x$ and $y$.

    In the $k$ lines that follow, all the sequences of $n$ bits that do not correspond to any town are given, one sequence per line.In the $k$ lines that follow, all the sequences of $n$ bits that do not correspond to any town are given, one sequence per line.Each such sequence is a string of $n$ characters 0 and/or 1.You may assume that $x$ and $y$ are not among those $k$ sequences.

    输出格式:

    Your program should print to the standard output the word TAK (Polish for yes) if walking from the town x to the town y is possible, and the word NIE (Polish for no) otherwise.

    输入输出样例

    输入样例#1: 复制
    4 6
    0000 1011
    0110
    0111
    0011
    1101
    1010
    1001
    
    输出样例#1: 复制
    TAK
    

    说明

    有2^n个长度为n的01串,两个01串之间有边当且仅当这两个01串只有一位不同,现在从这2n个串中拿掉k个,问指定两个串之间能否到达

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