洛谷 P3481 [POI2009]PRZ-Algorithm Speedup

题目描述

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.

输入样例:                                                              输出样例:

2                                                                               0
4 5                                                                            1
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

翻译:

作为对行为不端的惩罚,Byteasar将计算一个神秘而讨厌的布尔值函数,该函数是为一对正整数序列定义的,如下所示:

布尔if-then返回else if-then返回else-return。

其中:表示序列的成员集(元素的顺序和重复不重要),表示序列的最长前缀(任何长度的起始部分),表示序列的最长后缀(任何长度的最后部分),表示逻辑连接,-true,-false,和-集的基数。

例如,对于序列,我们有:

对于非常大的数据,直接从定义计算函数值的程序按任何标准都太慢。

因此,您必须尽可能快地进行这些计算。

编写一个程序,从标准输入读取多对序列,并打印出每个输入对的标准输出值

标准输入的第一行包含一个整数(),表示要分析的序列对的数量。

下一行保存测试用例的描述。

每个描述的第一行包含两个整数和(),由单个空格分隔,分别表示第一个和第二个序列的长度。

第二行包含构成序列的整数(),由单个空格分隔。

第三行保存整数(),它们构成序列,由单个空格分隔。

输出应完全由行组成;第-行(for)应该包含一个整数-0或1-第-个测试用例的值。

题解网址:https://www.luogu.com.cn/problem/solution/P3481

热门文章

暂无图片
编程学习 ·

C语言二分查找详解

二分查找是一种知名度很高的查找算法,在对有序数列进行查找时效率远高于传统的顺序查找。 下面这张动图对比了二者的效率差距。 二分查找的基本思想就是通过把目标数和当前数列的中间数进行比较,从而确定目标数是在中间数的左边还是右边,将查…
暂无图片
编程学习 ·

GMX 命令分类列表

建模和计算操作命令: 1.1 . 创建拓扑与坐标文件 gmx editconf - 编辑模拟盒子以及写入子组(subgroups) gmx protonate - 结构质子化 gmx x2top - 根据坐标生成原始拓扑文件 gmx solvate - 体系溶剂化 gmx insert-molecules - 将分子插入已有空位 gmx genconf - 增加…
暂无图片
编程学习 ·

一文高效回顾研究生课程《数值分析》重点

数值分析这门课的本质就是用离散的已知点去估计整体,就是由黑盒子产生的结果去估计这个黑盒子。在数学里这个黑盒子就是一个函数嘛,这门课会介绍许多方法去利用离散点最大化地逼近这个函数,甚至它的导数、积分,甚至微分方程的解。…
暂无图片
编程学习 ·

在职阿里5年,一个28岁女软测工程师的心声

简单的先说一下,坐标杭州,14届本科毕业,算上年前在阿里巴巴的面试,一共有面试了有6家公司(因为不想请假,因此只是每个晚上去其他公司面试,所以面试的公司比较少) ​ 编辑切换为居中…
暂无图片
编程学习 ·

字符串左旋c语言

目录 题目: 解题思路: 第一步: 第二步: 第三步: 总代码: 题目: 实现一个函数,可以左旋字符串中的k个字符。 例如: ABCD左旋一个字符得到BCDA ABCD左旋两个字符…
暂无图片
编程学习 ·

设计模式--观察者模式笔记

模式的定义与特点 观察者(Observer)模式的定义:指多个对象间存在一对多的依赖关系,当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并被自动更新。这种模式有时又称作发布-订阅模式、模型-视图模式&#xf…
暂无图片
编程学习 ·

睡觉突然身体动不了,什么是睡眠痽痪症

很多朋友可能有这样的体验,睡觉过程中突然意识清醒,身体却动弹不了。这时候感觉非常恐怖,希望旁边有一个人推自己一下。阳光以前也经常会碰到这样的情况,一年有一百多次,那时候很害怕晚上到来,睡觉了就会出…
暂无图片
编程学习 ·

深入理解C++智能指针——浅析MSVC源码

文章目录unique_ptrshared_ptr 与 weak_ptrstd::bad_weak_ptr 异常std::enable_shared_from_thisunique_ptr unique_ptr 是一个只移型别(move-only type,只移型别还有std::mutex等)。 结合一下工厂模式,看看其基本用法&#xff…
暂无图片
编程学习 ·

@TableField(exist = false)

TableField(exist false) //申明此字段不在数据库存在,但代码中需要用到它,通知Mybatis-plus在做写库操作是忽略它。,.
暂无图片
编程学习 ·

Java Web day15

第十二章文件上传和下载 一、如何实现文件上传 要实现Web开发中的文件上传功能,通常需要完成两步操作:一.是在Web页面中添加上传输入项;二是在Servlet中读取上传文件的数据,并保存到本地硬盘中。 需要使用一个Apache组织提供一个…
暂无图片
编程学习 ·

【51nod 2478】【单调栈】【前缀和】小b接水

小b接水题目解题思路Code51nod 2478 小b接水 题目 输入样例 12 0 1 0 2 1 0 1 3 2 1 2 1输出样例 6解题思路 可以发现最后能拦住水的都是向两边递减高度(?) 不管两个高积木之间的的积木是怎样乱七八糟的高度,最后能用来装水的…
暂无图片
编程学习 ·

花了大半天写了一个UVC扩展单元调试工具

基于DIRECTSHOW 实现的,用的是MFC VS2019. 详见:http://www.usbzh.com/article/detail-761.html 获取方法 加QQ群:952873936,然后在群文件\USB调试工具&测试软件\UVCXU-V1.0(UVC扩展单元调试工具-USB中文网官方版).exe USB中文网 USB中文…
暂无图片
编程学习 ·

贪心(一):区间问题、Huffman树

区间问题 例题一:区间选点 给定 N 个闭区间 [ai,bi]请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。 位于区间端点上的点也算作区间内。 输入格式 第一行包含整数 N,表示区间数。 接下来 …
暂无图片
编程学习 ·

C语言练习实例——费氏数列

目录 题目 解法 输出结果 题目 Fibonacci为1200年代的欧洲数学家,在他的着作中曾经提到:「若有一只免子每个月生一只小免子,一个月后小免子也开始生产。起初只有一只免子,一个月后就有两只免子,二个月后有三只免子…
暂无图片
编程学习 ·

Android开发(2): Android 资源

个人笔记整理 Android 资源 Android中的资源,一般分为两类: 系统内置资源:Android SDK中所提供的已经定义好的资源,用户可以直接拿来使用。 用户自定义资源:用户自己定义或引入的,只适用于当前应用的资源…
暂无图片
编程学习 ·

零基础如何在短时间内拿到算法offer

​算法工程师是利用算法处理事物的职业 算法(Algorithm)是一系列解决问题的清晰指令,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。 如果一个算法有缺陷,或不适合于某个问题,执…
暂无图片
编程学习 ·

人工智能:知识图谱实战总结

人工智能python,NLP,知识图谱,机器学习,深度学习人工智能:知识图谱实战前言一、实体建模工具Protegepython,NLP,知识图谱,机器学习,深度学习 人工智能:知识图…
暂无图片
编程学习 ·

【无标题】

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注…