OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【CTSC2013】组合子逻辑

【题目描述】

组合子逻辑是Moses Schönfinkel 和Haskell Curry 发明的一种符号系统,用于消除数理逻辑中对于变量的需要。本题考察一种与真实世界的组合子演算略有差别的组合子系统。

一个组合子项是下列形式之一:

P

(E1 E2)

其中P 表示一个基本函数,E1以及E2表示一个组合子项(可以相同)。不满足以上形式的表达式均非组合子项。

我们将一个组合子项E 的参数个数np(E)如下:

np(P) = 基本函数P 的参数个数;

np((E1 E2))=np(E1)-1。

本题中,我们用一个正整数同时表示一个基本函数,以及该基本函数的参数个数。

对于一个组合子项E,如果它和它包含的所有组合子项的参数个数np 均为正整数,那么我们称这个E为范式。

我们经常组合子项简化表示:如果一个组合子项E含有连续子序列(… ((E1 E2) E3) …En) (其中n ≥ 3),其中Ek表示组合子项(可以是简化表示的),那么将该部分替换为(E1 E2 E3 … En),其他部分不变,得到表达式E 的一个简化表示。一个组合子项可以被简化表示多次。

给定一个基本函数序列,问至少需要添加多少对括号,才能使得该表达式成为一个范式的简化表示(即满足范式的性质);如果无论如何怎样添加括号,均不能得到范式的简化表示,输出-1。

【输入】

第一行包含一个正整数T,表示有T 次询问。

接下来2T 行。

第2k 行有一个正整数nk,表示第k 次询问的序列中基本函数的个数。

第2k + 1 行有nk个正整数,其中第i 个整数表示序列中第i 个基本函数。

【输出】

输出T 行,每行一个整数,表示对应询问的输出结果。

【输入样例】

2

5

3 2 1 3 2

5

1 1 1 1 1

【输出样例】

3

-1

【数据范围】

令TN 表示输入中所有nk的和,TN≤2000000

【题解】

CTSC第一题,先撒花儿O(∩_∩)O~~

这题主要是要理解题意,题目要求给原序列添加尽可能少的括号,使得序列变为一个数,规则大致如下:

①(E1,E2,E3,...,Ek)=E1-k+1;

②要求序列中的数始终大于0。

这样来考虑,我们在为x的数左边添加括号,那么右括号最多与之间隔为x-1,所以可以用贪心。先在最左边加上括号,然后每读入一个数,就将括号右移一位,直到超出限制。超出限制后可以在已读入的序列中找一个最大的数x',x'能将限制增加x'-1。那就用一个堆来维护,把读入的数都放入堆中,当超出限制时取出堆顶,假如堆为空或堆中最大值为1,则代表无解。从堆中取的次数+1即为答案(因为还要加上最开始的括号)。

注意处理n=1的情况,此时答案为0,因为连最开始的括号都不需要了。

【代码】

时间复杂度为O(T*nlogn),由于Σn<=2000000,即使只有一组数据,也能在2s内得出答案~

http://paste.ubuntu.com/8138430/

评论
热度(1)
  1. 1319861573OI技术宅 转载了此文字

© OI技术宅 | Powered by LOFTER