HNSDFZ2016 #2

这是一场痞题大战。

A. 二十四点 (blue)

时间限制: 0.4s / 内存限制: 128MB

题目描述

给定四个数，判断能否构成二十四点。仅允许：+ - * / () [] {}这几种符号。

输入格式

第一行，一个正整数$n$，表示有$n$组数据。 接下来$n$行，每行四个正整数，表示给你的牌。 保证：这些正整数$\in[1,13]$。

输出格式

$n$行，每行一个整数，描述是否能构成二十四点。 能则输出$Yes$，不能则输出$No$。

样例输入

1
2
3

2
5 5 5 1
9 9 9 9

样例输出

1
2

Yes
No

数据范围及提示

最多5000组。

B. BST厂长 (riteme)

时间限制: 1 s / 内存限制: 128 MB

题目描述

二叉树真是迷人......

随着时代的进步，二叉搜索树(Binary Search Tree)发挥着越来越大的作用。作为HNSDFZ上机部长XL，担负着为学校制造各种BST的任务。它们会用于各种用途：成绩排名、薪水发放、PY**......
本来学校对BST的需求并不是很大，但是自从ZY加入了上机组后，BST的需求越来越大......
作为XL，早已按捺不住。于是XL利用通用技术教学楼建立了一个厂房，专门制造各种BST。
这个厂子会收到各种各样的订单。每个订单都会是一个很长的数列，其中没有两个数是相同的。而XL要做的就是将这些数字依次插入到一棵空的BST中，然后将BST发送出去。
然而人工干这件事实在是太麻烦了，因此XL将ZY抓过来造BST。然而ZY更懒，把Link抓过来要它帮
ZY写个程序来构建BST。然而Link并不屑于写这个程序，于是这个任务莫名其妙地传到了你手上......
当然XL不会就这样放手不管，XL会随时来检查这棵BST是否是正确的，以防你在乱造BST。

输入格式

第一行输入一个正整数$n$，表示订单中数列的长度。
接下来$n$行，每行输入两个正整数$x$和$k$。表示将$x$插入到当前的BST中。初始时是空树。$k$则表示XL的检查。他会问你根节点到新插入的节点$x$的链上第$k$个节点是谁。默认从$1$开始数。

输出格式

对于每一次XL的检查，输出对应的答案。

样例输入

1
2
3
4

3
2 1
1 1
3 2

样例输出

1
2
3

2
2
3

数据范围及提示

对于第一次插入$2$，树的根节点为$2$，故答案为$2$。
对于第二次插入$1$，因为$1 \lt 2$，所以$1$是$2$的左儿子。$2$到$1$的链上的第一个节点为$2$
对于最后一次插入$3$，因为$3 \gt 2$，所以$3$是$2$的右儿子。$2$到$3$的链上的第二个节点是$3$。

对于$10\%$的数据，$n \le 20,000$。
对于$10\%$的数据，$n \le 90,000$。
对于$20\%$的数据，$n \le 100,000$。
对于另外$10\%$的数据，数列完全随机。
对于$100\%$的数据，$n \le 200,000$，$1 \le x \le n$，保证每次检查的节点存在。

C. 鱼的记忆 (Link)

时间限制: 3s / 内存限制: 100MB

题目描述

对于只有7秒记忆的鱼来说，他能够记住的东西太少了。
但是鱼对于美的追求却不会因为他的记忆而放弃。
他想知道在他的记忆中，对于每个事物有多少个事物没有这个事物美丽。
每一件事物都有三个维度的评价，鱼能够很快的知道评价是多少。
但是他并没有办法知道每个事物有多少个事物没有这个事物美丽。
如果一个事物的三个维度都>=另外一个事物的三个维度并且这个事物被鱼看到的时间不能比其先。

输入格式

第一行一个n，表示鱼见到的事物个数 第2到n+1行分别为4个整数。 分别是前3维和时间

输出格式

输出n行，分别是有多少个事物没这个事物美丽

样例输入

1
2
3
4

3  
1 2 3 5  
2 1 1 6  
1 1 1 5  

样例输出

1
2
3

1  
1  
0  

数据范围及提示

10% N<=1000
10% N<=30000
80% N<=100000
没错，就是4维的。
前面3维小于100000
第4维<=7 鱼的记忆只有7秒

D. ZY的铁套装 (Haogram)

时间限制: 1s / 内存限制: 250MB

题目描述

在附中内网MC伊始之时，RLB(排名不分先后)三侠努力地挖矿造家打脏比，每天幸福充实的生活着，MC着。
然而ZY突然出现，夺走了RLB所有的铁块，打造了一身时尚时尚最时尚的铁套装。
RLB决心攻击ZY，收回铁套装。毕竟挖矿很难。
于是RLB三侠拿起了武器背包，向ZY发起进攻，并决心事后封ZY的id。
由于ZY的铁套装十分时(qiang)尚(da)，所以必须要连击$L$次才能打败ZY。
RLB三侠有$N$个武器，每个武器本可以在两个时刻发动攻击，然而ZY的铁套装太强，每个武器使用一次就报废了。
每次攻击要从1时刻开始向ZY攻击，显然，如果RLB没有可以在1时刻攻击的武器，那就一次也不能打到ZY了。

输入格式

第一行有两个数，$N$和$L$。 接下来的$N$行，每一行有两个数$a$,$b$，表示该武器可以在$a$或$b$时刻攻击ZY。

输出格式

输出一行，如果 RLB 能攻击 ZY 至少$L$次，输出”Yes”,否则”No”。(区分大小写)。

样例输入

1
2
3
4

3 2
1 2
2 3
4 5

样例输出

1

Yes

数据范围及提示

输出样例1 解释：
1时刻，RLB用1号武器攻击, 1号武器报废
2时刻，RLB用2号武器攻击, 2号武器报废
3时刻，RLB没有可以在3时刻攻击ZY的武器，攻击结束。
一共攻击2次，正好打败ZY！

数据范围：
对于30%的数据，保证N <= 1000
对于100%的数据，保证N <= 1000000
攻击ZY的时刻 0 < a,b <= 10000

题解

A

暴力暴力暴力......

B

用平衡树维护当前二叉树中能够被插入的节点，每次插入节点时在平衡树上二分找出新节点的范围，然后利用倍增法计算LCA来确定父亲，最后更新倍增数组的值。
查询时利用倍增上跳即可。

C

对于同一时间内，利用CDQ分治就可以解决(像Mokia或陌上花开一样)
由于有个时间轴，当时却只有7，因此进行7次CDQ分治......
因该要注意下细节，我并没有写......
Link真是脑洞大开......

D

将原问题转换为一个二分图匹配的问题，然后匈牙利算法直接跑。
即第$i$件武器与对应的天相连来构建二分图。
一群贪心100分......