hnsdfz-4.md

title	create	modified	tags
HNSDFZ2016	2016.8.15	2016.8.15	HNSDFZ 互测 2016

[TOC]

HNSDFZ2016 #4

A. 24点加强版 (ruanxingzhi)

题目描述

这是一道提交答案的防AK水题。

给定$n$个正整数,以四则运算、小括号拼出$k$。 自然,每个数都要用且仅用一次。

输入格式

第一行,两个正整数,表示$n$和$k$。
第二行,$n$个正整数,意义如题目所述。

输出格式

一行,一个四则运算的表达式。注意所有括号都是小括号,可以括号嵌套。

样例输入1

4 24
6 6 6 6

样例输出1

()6+(6+(6)+6)

样例输入2

4 24
2 7 1 7

样例输出2

(7*7-1)/2

数据范围及提示

对于每个输入文件k_.in,你需要提交一个输出文件k_.out.
共有$7$个测试点。前$4$个测试点每个$10$分,后$3$个测试点每个$20$分。

$k$-SBK变换 (riteme)

题目描述

数学家Lunk最近发现了一种逗逼的SBK变换。在Lunk眼里，SBK变换是这样的：

给你一个$1$至$n$的排列$A$和一个$1$至$n$的排列$P$，$P$对$A$做一次SBK变换后将得到一个新的排列$B$，其中： $$ B_{P_i} = A_i \tag{SBK Transformation}$$

然而做一次SBK变换太过无聊，于是Lunk决定连续做多次SBK变换。即将每次变换后的结果$B$变为$A$，然后继续用$P$对$A$做SBK变换。Lunk想知道连续对$A$做$k$次SBK变换后的结果。

输入格式

第一行输入两个整数$n$和$k$，表示排列的长度和连续做SBK变换的次数。 第二行输入$n$个整数表示排列$A$。 第三行输入$n$个整数表示排列$P$。

输出格式

一行输出$n$个整数，表示$k$次SBK变换后的结果。

样例输入

5 2
1 2 3 4 5
2 3 4 5 1

样例输出

4 5 1 2 3

样例解释

做完第一次SBK变换后： 5 1 2 3 4 做完第二次SBK变换后： 4 5 1 2 3

数据范围及约定

共$10$个测试点，每个测试点的数据范围如下表所示：

数据点	$n$的规模	$k$的规模
1	$\le10^3$	$\le10^3$
2	$\le10^3$	$\le10^3$
3	$\le10^4$	$\le10^5$
4	$\le10^4$	$\le2\times10^5$
5	$\le4\times10^5$	$\le2^{30}$
6	$\le4\times10^5$	$\le2^{33}$
7	$\le6\times10^5$	$\le2^{63}$
8	$\le6\times10^5$	$\le2^{63}$
9	$\le10^6$	$\le2^{63}$
10	$\le2.3\times10^6$	$\le2^{63}$

C. 稀奇古怪的根 (Link)

题目描述

DYX是一个很ZY的ZY,但是他不想ZY一样ZY。
他特别喜欢捣鼓一些无与伦比的树。
他也特别喜欢逆序对这种东西,因此他想把逆序对拓展到树上来。
DYX对于树上的逆序对的定义是这样的:
树上的某个点到根节点的路径上权值比他大的节点和他构成逆序对
换句话来说,就是指,树上某个节点能和他构成逆序对的节点是他的子树中
权值比他小的或者是他到根节点的路径上权值比他大的
聪明的DYX很快就把他推广到树上了。
最近DYX学会了LCT,里面的换根操作打动了他。
因此他在想能不能把LCT的换根拓展到他的树上

定义树上两个节点$X$和$Y$,且$X$是$Y$到根节点的路径上面的一个节点
定义$X$和$Y$构成逆序对当且仅当$X$的权值比$Y$的大
给你一棵树,询问以某个节点为根的时候这棵树总共有多少组逆序对

输入格式

第一行$n$和$m$表示树的节点个数和询问个数
第二行$n$个数表示每个节点的权值
然后$n-1$行两个数$X$,$Y$.表示点$X$和$Y$有一条边连接
然后$m$行每行$1$个数$X$,表示以$X$为根的时候树中有多少组逆序对

输出格式

输出$m$行,每行一个整数,表示以$X$为根的树中有多少组逆序对

样例输入

10 5
1 2 3 4 5 6 7 8 9 10
1 2
1 3
3 4
3 5
3 7
2 9
2 10
2 6
2 8
3
2
1
7
10

样例输出

2
1
0
8
10

数据范围及提示

$30%$ $n,;m \le 1000$ $50%$ $n,;m \le20000$, 且权值不大于$20000$ $100%$ $n,;m \le 100000$, 保证所有数据在int范围内

提供两个类:
LCT和主席树,要的请找出题人。
要了的话就­1分

D. 最长公共子序列 (Haogram)

题目描述

给定两个正整数序列,每个序列中元素两两不同,且范围都在$[1,;n^2]$。求其最长公共子序列。

输入格式

第一行一个正整数$t$, 表示数据组数。对于每组数据:
第一行三个数$n$, $p$, $q$, $n$, 含义如题, $p$, $q$分别为两个序列的长度。
接下来两行描述两个序列。

输出格式

共$t$行$t$个整数,表示答案。

样例输入

1
3 7 8
1 7 5 4 8 3 9
1 4 3 5 6 2 8 9

样例输出

4

数据范围及提示

对于$30%$的数据，$n \le 30$ 对于$100%$的数据，$2 \le n \le 250,;1 \lt p,;q \le n^2,;t\le10$

E. ZY的金坷垃 (HJWJBSR)

题目描述

Zy:金坷垃好处都有啥,谁说对了就给他
zy:肥料掺了金坷垃,不流失,不蒸发,零浪费
zY:肥料掺了金坷垃,能吸收两米下的氮磷钾
zy:世界肥料都涨价,肥料掺了金坷垃,一袋能顶两袋撒
zY:用了金坷垃,小麦亩产一千八。日本的粮食再也不向美国进口了!hhhhhhhh
Zy:小鬼子,真不傻!金坷垃给了他对美国农业危害大,决不能给了他!
Zy:非洲农业不发达,我们都要支援他。金坷垃,你们日本别想了!
zY:狡猾,狡猾。没有金坷垃,怎么种庄稼!金坷垃!金坷垃!(残念脸

zy最近从小鬼子手中抢到了金坷垃。开始考虑怎么撒。他家的地可以看做一个$n\times m$的方阵。
由于非洲农业不发达,zy家的地有些地方并不能够播撒。
并且金坷垃是全球瞩目的焦点是农业科技的前沿,所以播撒的方式也比较不一样:每次需要选择一个没被选择过的矩形 并均匀撒上金坷垃,且必须将所有矩形都播撒一次。
每次播撒的花费的金坷垃袋数是矩形包含的格子个数的平方。
zy想知道他要买多少金坷垃才够用。

输入格式

第一行给出两个正整数$n$和$m$代表zy家的地的长和宽。
下面$n$行每行一个长度$m$的01串描述了zy家地的状态。$0$代表这个地不能撒,$1$代表能撒。

输出格式

一个非负整数代表金坷垃至少要多少袋。

样例输入

5 5
01001
11000
00010
00000
10001

样例输出

15

数据范围及提示

对于$30%$的数据, 保证$n,;m \le 10$。 对于$50%$的数据,保证$n,;m \le 100$。 对于所有数据,保证$n,;m \le 1000$。

题解

A

这道题首先需要你有1个小时。 然后就可以A掉了。 防AK什么鬼......

B

1. 20分: 模拟 ($\Theta(nk)$)
2. 80分:
   1. 排列矩阵快速幂 ($\Theta(n \log k)$，排列矩阵的乘法可以在$\Theta(n)$的时间内计算)
   2. 寻找循环节，倍增找到每个值 ($O(n\log k)$)
3. 100分: 寻找循环节，取模找到每个值 ($\Theta(n)$)

C

首先需要计算DFS序。 然后用可持久化平衡树来维护它上面的值。 首先以$1$为根，计算每棵子树中比树根小的值有多少个，加起来就是$1$的答案。 然后从$1$开始DFS一遍，考虑在知道当前节点的答案的情况下，换根到自己的一个儿子处，答案的变化，可以在$\Theta(\log n)$的时间内计算出来。 然后就可以愉快的$\Theta(1)$回答啦~~~

D

将其中一个序列的值依次重新编号，然后将另外一个序列也同步修改一下。 然后就转成了求另外一个序列的最长上升子序列问题。 这个可以在$\Theta(n\log n)$的时间内计算。

E

引用一段话：

题解： 本来打算出了另外一道题，后来才发现正确性不太好。又不想变成只能出数据结构题的选手，就临时换了这个比较裸的题。 （出题好难 很明显如果矩形代价都是1那么肯定就是直接悬线法。 否则他要算这个的代价就在悬线法里面加特技：每次相当于要从一个长宽分别为n*m的矩形里面算满足特定条件的子矩形的答案。这样就不会重复。 相当于$\sum_{i=y_0}^{y_1} i^2 \times \text{横着的答案}$。 横着的答案：$\sum_{i=1}^m i^2 \cdot (n-i+1)$。 然后就没了。