题号:1856A~E2
A
题面:
给定一个正整数 \(n\) 和一个长度为 \(n\) 的序列 \(a\),重复执行以下操作直至 \(a\) 序列单调不减:
- \(\forall 1 \le i \le n\),\(a_i = \max(a_i - 1, 0)\)。
求一共需要执行多少次操作。
多测,共 \(t\) 组数据。
对于所有数据,保证 \(1 \le t \le 500\),\(2 \le n \le 50\),\(1 \le a_i \le 10 ^ 9\)。
B
题面:
给定一个正整数 \(n\) 和一个长度为 \(n\) 的序列 \(a\),问是否存在正整数序列 \(b\) 满足以下条件:
\(\forall 1 \le i \le n\),\(a_i \ne b_i\)。
\(\sum \limits_{i = 1} ^ {n} a_i = \sum \limits_{i = 1} ^ {n} b_i\)。
若存在,输出
YES
,否则输出NO
。多测,共 \(t\) 组数据。
对于所有数据,保证 \(1 \le t \le 10 ^ 4\),\(1 \le n, \sum n \le 10 ^ 5\),\(1 \le a_i \le 10 ^ 9\)。
C
给定两个正整数 \(n\) 和 \(k\),以及一个长度为 \(n\) 的序列 \(a\),你可以进行不超过 \(k\) 次如下操作(以下两个步骤合称一次操作):
选择一个 \(i\) 满足 \(1 \le i < n\),且 \(a_i \le a_{i + 1}\)。
将 \(a_i\) 增加 \(1\)。
求操作完成后,\(\max \limits_{i = 1} ^ {n} a_i\) 的最大可以是多少。
多测,共 \(t\) 组数据。
对于所有数据,保证 \(1 \le t \le 100\),\(1 \le n, \sum n \le 1000\),\(1 \le k, a_i \le 10 ^ 8\)。
D
本题交互。
有一个长为 \(n\) 的序列 \(a\),最初不知道 \(a\) 的任何一个值。
一次询问区间 \([l,r]\) 的逆序对个数,代价为 \((r-l)^2\)。
你需要进行若干次询问,求出 \(a\) 的最大值所在的位置,并使得询问总代价 \(w\le 5n^2\)。
多测,\(1\le t\le 100,1\le n\le 2000\)。所有数据中 \(n\) 的总和不超过 \(2000\)。
E2
标签:890,10,le,正整数,多测,sum,Codeforces,序列,Div.2 From: https://www.cnblogs.com/oierpyt/p/17611034.html这是问题的困难版本,两个版本之间的唯一区别是 \(n\) 的范围和时间限制的不同。
给定一棵以 \(1\) 为根的有根树,你需要给出一个 \(1\) 到 \(n\) 的排列 \(a\),最大化二元组 \((u,v)\) 的数量,满足 \(a_u < a_{\rm{lca(a_u,a_v)}} < a_v\),输出这个最大值。
\(2 \leq n \leq 10^6\)。