时间限制：1000MS 内存限制：524288KB
出题人：zzx 难度：6.0
给定字符串 s 。你需要回答 n 个询问，第 i 个询问给出一个正整数 k_i 和一个字符串 m_i，请求出 s 的所有子串 t 中，满足 m_i 在 t 中出现至少 k_i 次的字符串 t 的长度的最小值。
一个字符串的子串是该字符串中的连续一段字符。
保证任意两个询问的 m_i 不相同。
第一行包含一个字符串 s（1 \leq \left|s\right| \leq 10^5）。
第二行包含一个正整数 n（1 \leq n \leq 10^5）。
接下来 n 行，每行一个正整数 k_i（1 \leq k_i \leq \left|s\right|）和一个非空字符串 m_i，表示第 i 个询问。
所有字符串仅包含小写英文字母，且所有询问字符串的总长度不超过 10^5 。
对于每个字符串输出一行表示答案。
如果 m_i 在 s 中出现次数小于 k_i，输出 -1 。…
时间限制：1000MS 内存限制：262144KB
出题人：E.Space 难度：6.1
在这个游戏中一共有 n 个角色。你需要编写一些关于这些角色的对话内容。
你打算用角色名字的一个非空子序列来作为它的简称。
当然，不同的角色要用不同的字符串作为简称，否则你就变量重名了。
你想确定一个简称的分配方案使得所有角色中最长的简称尽量短。
第一行一个正整数 n。
接下来 n 行，每行一个由小写字母组成的字符串，代表一个角色的名字。
不同的角色可能会有相同的名字。
如果不存在一种分配简称的方案满足条件，输出 -1。
否则第一行输出一个正整数，表示最长的简称的最小长度。
接下来 n 行每行一个字符串，按顺序表示每个角色的简称。
若有多种方案满足条件，那么你可以输出任意一种。
保证 n \leq 300 ，每个名字的长度不超过 300。
时间限制：2000MS 内存限制：131072KB
出题人：Night 难度：6.0
有一个序列 x_1,x_2,\cdots,x_n 。
求有多少个从 1,2,\cdots,n 中取三个元素的排列 (a,b,c) 满足 x_a=x_b-x_c 。
由于是排列，所以 (a,b,c) 与 (c,b,a) 视为两组解。
第一行一个整数 n 表示序列长度。
第二行为 n 个整数表示序列里的 n 个数。
一行一个正整数，表示答案。
对于 20\% 的数据，1 \leq n \leq 500；
对于 45\% 的数据，1 \leq n \leq 5000；
对于 100\% 的数据，1 \leq n \leq 1000000，0 \leq \left|x_i\right| \leq 100000 。
Time Limit：1000MS Memory Limit：131072KB
Difficulty: 6.0
The city executive board in Lund wants to construct a sightseeing tour by bus in Lund, so that tourists can see every corner of the beautiful city. They want to construct the tour so that every street in the city is visited exactly once. The bus should also start and end at the same junction. As in any city, the streets are either one-way or two-way, traffic rules that must be obeyed by the tour bus. Help the executive board and determine if it’s possible to construct a sightseeing tour under these constraints.
On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario begins with a line containing two positive integers m and s, …
时间限制：1000MS 内存限制：65536KB
难度：6.0
给定一个序列 t_1,t_2,\cdots,t_n，求一个递增序列 z_1<z_2<\cdots<z_n，使得 R=\sum\limits_{i=1}^{n}{\left|t_i-z_i\right|} 的值最小。
本题中，我们只需要求出这个最小的 R 值。
第一行为一个正整数 n
第二行到第 n+1 行，每行一个整数，第 k+1 行为 t_k
一个整数 R
所求的 z 序列为 6,7,8,13,14,15,18，R=13
对于 100\% 的数据，1 \leq n \leq 10^6，1 \leq t_i \leq 2\times 10^9 。
时间限制：1000MS 内存限制：131072KB
出题人：zzx 难度：6.5
本题中，我们需要计算一些“Bomb表达式”的结果。比如， “1-2+3” 的结果为 2 。和普通表达式不同的是，Bomb表达式中可能包含一些 “#” 号，会展开一些普通表达式。比如 “(1-2+3)#(3)” 表示 “1-2+3 ”出现了 3 次，将会被展开为 “1-2+31-2+31-2+3”，其结果为 60 。
为了方便理解，下面给出了Bomb表达式（bomb expression）和普通表达式（normal expression）的BNF表示。…
时间限制：1000MS 内存限制：262144KB
难度：6.0
有一个 n 个点，m 条边的无向图，每次可以对这张图进行操作：对于一条边 (u,v)，可以把图中除了这条边以外的边，每一条的权值都减少 1。
对于某一条编号为 e 的边，至少需要多少次操作，才能保证其能出现在最小生成树中？
第一行输入三个整数 n、m、e。
接下来输入 m 行，每行输入三个整数，其中第 i+1 行输入的整数分别为 u_i、v_i、w_i，表示无向图的边的两个端点和边权。
输出一个整数表示答案。
对于 50\% 的数据，n \leq 300，m \leq 1000 。
对于 100\% 的数据，n \leq 2 \times 10^4，m \leq 2 \times 10^5，0 \leq w_i \leq 2\times 10^4 。
时间限制：3000MS 内存限制：131072KB
难度：6.0
已知密匙与一个长度为 n 的字符串有关，字符串中的字符都来自于字符集 \{\text{‘a’..}\text{‘z’}, \text{‘?’}\}，每个 \text{‘?’} 的位置都要被填上一个小写字母，我们定义一个填好的串是合法的当且仅当它满足如下条件：
在输入的 m 次操作后与这个串操作之前的样子相比没有改变。
一次操作是翻转这个串的第 l_i 个字符到第 r_i 个字符。
求出字典序第 K 小的合法的能被填出的串，因为密码就是它。
第一行三个数 n,m,k 。
第二行一个长度为 n 的串。
接下来 m 行每行两个数 l_i 和 r_i 。
一个串，表示字典序第 K 小的合法的能被填出的串。
对于 100\% 的数据，保证 n,m \leq 5 \times 10^5, k \leq 1 \times 10^{18} 。
时间限制：2000MS 内存限制：262144KB
出题人：zzx 难度：6.0
k 维空间内有两个点集 A=\{X_1,X_2,\ldots,X_m\}，B=\{Y_1,Y_2,\ldots,Y_n\}，每个点的坐标是一个 k 元组 (x_1,x_2,\ldots,x_k)。我们称点 X(x_1,x_2,\ldots,x_k) 控制点 Y(y_1,y_2,\ldots,y_k) 当且仅当 \forall 1\le i\le k,x_i>y_i，记为 X>Y。数点问题是要求计算点 X_i 能控制 B 中的点数 c_i，即 c_i=\left| \{Y \in B\ |\ X_i > Y\} \right|。
对于给定的点集 A 和 B，求出对于所有 1\le i\le m 的 c_i 的值。
第一行有三个正整数m、n 和 k，分别表示集合 A 和 B 的基数及维数。接下来的 m+n 行依次给出点 X_1 , X_2 ,\ldots, X_m ,Y_1 ,Y_2 ,\ldots,Y_n，每个点的坐标用一行 k 个整数 x_1 , x_2 ,\ldots, x_k 描述，所有坐标在 int 范围内。
将计算出的 c_1 ,c_2 ,\ldots,c_m 依次输出到文件中，每个 c_i 输出 1 行。
时间限制：2000MS 内存限制：524288KB
难度：6.0
在一条东西向的街道上有 n 个餐馆，从西向东编号为 1 至 n，第 i 个餐馆和第 i+1 个餐馆的距离为 a_i 。
吃货小W喜欢到这条街道的餐馆里吃饭。现在，小W得到了 m 张餐票，每张餐票可以用于在街道上的任一餐馆里吃一餐。在第 i 个餐馆中，使用第 j 张餐票吃饭，可以获得的美味度为 b_{i,j} 。注意，每张餐票最多用一次，但在同一餐馆内可以使用任意多张餐票。
小W打算用完这 m 张餐票。他可以选择任一餐馆作为起点，每次吃饭时，可以选择一个餐馆，然后从当前位置（上次吃饭的地点，如果不存在则为起点）出发前往该餐馆并用任意一张未用过的餐票吃一餐，直到吃完 m 餐为止。小W希望最大化每次吃饭的美味度之和减去路上经过的总路程的值。
输入第一行包含两个正整数 n,m 。
第二行包含 n-1 个正整数 a_1,a_2,\cdots,a_{n-1} 。
接下来 n 行，每行包含 m 个正整数，其中第 i 行第 j 个数为 b_{i,j} 。
输出一行一个整数，表示所求的最大值。
最优方案如下：以餐馆 1 为起点，在餐馆 1 使用第 1 张餐票、第 3 张餐票，然后前往餐馆 2 使用第 2 张餐票、第 4 张餐票。
对于所有数据，nm \leq 10^6，n \geq 2，a_i, b_{i, j} \leq 10^9 。
Source：ARC067 F – Yakiniku …