P3481 [POI2009]PRZ-Algorithm Speedup

    • 1通过
    • 13提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 POI 2009 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    As a punishment for misbehaving, Byteasar is to calculate a certain mysterious and nasty Boolean-valued function , which is defined for a pair of positive integer sequences , as follows:

    boolean if then return else if then return else return .

    Where: denotes the set of members of the sequence (order and repetitions of elements are insignificant), denotes the longest prefix (initial part of any length) of the sequence , such that , denotes the longest suffix (final part of any length) of the sequence , such that , denotes the logical conjunction, - true, - false, and - cardinality of set .

    For example, for the sequence we have:

    For very large data a programme calculating values of the function directly from definition is too slow by any standards.

    Therefore you are to make these calculations as fast as possible.

    Write a programme that reads several pairs of sequences from the standard input and prints out the values on the standard output for every input pair.

    你的任务是计算一个函数F(x, y),其中x和y是两个正整数序列。F的定义如下:

    boolean F(x, y)
    if W(x) ≠ W(y) then return 0
    else if |W(x)| = |W(y)| = 1 then return 1
    else return F(p(x), p(y)) AND F(s(x), s(y)).
    W(x)表示序列x中元素的集合。(元素的顺序和出现次数将被无视)
    p(x)表示序列x的最长前缀,满足:W(x) ≠ W(p(x))
    s(x)表示序列x的最长后缀。满足:W(x) ≠ W(s(x))
    |Z|表示集合Z中元素个数

    输入输出格式

    输入格式:

    The first line of the standard input contains one integer () denoting the number of sequence pairs to analyse.

    Next line hold descriptions of test cases.

    The first line of each description contains two integers and () separated by a single space and denoting the lengths of the first and second sequence, respectively.

    The second line holds integers () that form the sequence , separated by single spaces.

    The third line holds integers (), that form the sequence , separated by single spaces.

    输出格式:

    The output should consist of exactly lines; the -th line (for ) should contain a single integer - 0 or 1 - the value of for -th test case.

    输入输出样例

    输入样例#1: 复制
    2
    4 5
    3 1 2 1
    1 3 1 2 1
    7 7
    1 1 2 1 2 1 3
    1 1 2 1 3 1 3
    
    输出样例#1: 复制
    0
    1
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。