AC. 梦想

frank_c1

2016多校联合训练3

发布于2016年07月27日 | 暂无评论 | 853阅读 | 比赛经历

mjymjy?mjymjy! mjy太强啦!

昨天下午我们总共有6道题,5道题是mjy贡献的,跪跪跪~

另外,绍兴一中的题目太强啦,跪。

那么来补题吧。

1001. Sqrt Bo

定义f(n) = \lfloor \sqrt{n} \rfloor, f^1(n) = f(n), f^y(n) = f(f^{y-1}(n))

给定n,求最小的y满足f^y(n) = 1。如果y \gt 5,输出"TAT"。

1 \le T \le 120, 1 \le n \le 10 ^ {100}

1002. Permutation Bo

有两个长度为n的数列c,h,已知h_1, h_2, ..., h_n1 - n的一个排列,h_0 = h_{n+1} = 0。定义

f(h) = \sum_{i=1} ^ {n} {c_i [h_i \gt h_{i-1} \; and \; h_i \gt h_{i+1}]}

给定数列c,求f(h)的期望。

1 \le T \le 12, 1 \le n \le 1000, 0 \le c_i \le 1000

1003. Life Winner Bo

在一个n \times m的棋盘上,棋子开始在(1,1)

现在两人轮流操作。玩家可以以一定的走法移动这枚棋子。设当前棋子在(x,y),则到达的位置(x',y')需满足x' \ge xy' \ge y。如果轮到某一名玩家时,棋子在(n,m),则这名玩家判负。如果轮到某一名玩家时,棋子不在(n,m),但无路可走,则判平局。假设双方都采取最优策略。

走法有四种,分别是国际象棋中王、车、马、后的走法。

每次询问type \; n \; m,即在n \times m的棋盘上,采用type走法时,先手是必胜/平局/必败?

1 \le T \le 1000, 1 \le type \le 4, 1 \le n,m \le 1000

1004. Gambler Bo

给定一个n \times m的矩阵。每个格子中有一个0,1,2中的整数。

现在可以对矩形做若干操作。每一次操作选定一个格子,将其值加上2,其四连通格子分别加上1。注意,加法均在模3域下进行。求一种方案可以将矩阵清零,输出任意一种即可。操作次数不应超过2nm

数据随机生成,保证存在至少一组解。

1 \le T \le 10, 1 \le n,m \le 30

1005. Boss Bo

给定n个点的有根树,根为1

给出q个询问。每次询问给出一个点集A_1, A_2,..., A_k

定义点x是好点当且仅当不存在一个A中的点是x的祖先。

对于每个询问,求出好点之间距离的最大值,好点之间距离的最小值,好点之间的距离之和。

如果不存在一个好点,输出-1。

强制在线。

T = 30, 1 \le n, k \le 50000, 1 \le q \le 10 ^ 5, \sum {k} \le 2 \cdot 10 ^ 5,大数据占20 \%

1006. Product Bo

给定长度为n的实数数列a

选取一个长度为m的子序列s,定义其乘积为

f(s) = \prod_{i=1} ^ {m} {a_{s_i}}

{n \choose m}个选取方案中,第k大的乘积。

由于实数和乘积表示的不便,实数以符号和绝对值的对数(opt,b)的形式给出,其中b[-10 ^ 9,10 ^ 9]中的整数。答案也以这种形式输出。

1 \le m \le n \le 2 \cdot 10 ^ 5, 1 \le k \le \min(2 \cdot 10 ^ 5, {n \choose m})

1007. Explorer Bo

给定一棵n个点的树。

你可以任意选取一个起点,每次可以经过一条边走到一个相邻的结点,也可以使用一次传送到任意一个结点。要求一条边不能连续经过两次。结束条件是经过树上每条边至少一次。

求在最小化传送次数的情况下,最少需要经过的边数。

1 \le T \le 20, 1 \le n \le 10 ^ 5

1008. Gardener Bo

给定n个点的带权有根树,第i个点权值为w_i

定义

f(u) = \sum_{i=1} ^ {n} \sum_{j=1} ^ {n} {(w_i + w_j)[LCA(i,j) = u]}

维护两种操作:

1 \; u \; x: 将所有满足v = ufa(v) = ufa(fa(v)) = uv的权值加上x

2 \; u:询问f(u) \mod 2 ^ {32}

1 \le n \le 3 \cdot 10 ^ 5, |w_i|,|x| \lt 10 ^ 9

1009. Palindrome Bo

给定长度为n的数列a

定义一个数列是BoBo数列当且仅当数列中存在一个位置,数列自这个位置分别向两端单调递增。

a的最长BoBo子序列及其个数。答案对10 ^ 9 + 7取模。

1 \le n \le 5000, 1 \le a_i \le 20000

1010. Rower Bo

平面直角坐标系上,有一艘小船在(0,a)。河流带着小船朝x轴正方向运动,速度v_2。小船船速v_1,航向始终指向(0,0)。求需要多少时间小船能到达(0,0)。如果永远无法到达,输出"Infinity"。

1 \le T \le 1000, 0 \le a \le 100, 0 \le v_1,v_2 \le 100

1011. Teacher Bo

给定平面直角坐标系上n个点,第i个点在(x_i,y_i),且0 \le x_i, y_i \le m

求是否存在一个四边形(A,B,C,D),满足AB的曼哈顿距离与CD的曼哈顿距离相等。

输出"YES"或"NO"。

1 \le T \le 50, 1 \le n, m \le 10 ^ 5