时间限制：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 内存限制：131072KB
难度：\(5.1\)
在 \(Y\) 国有 \(N\) 座城市，并且有 \(M\) 条双向公路将这些城市连接起来，并且任意两个城市至少有一条路径可以互达。\(Y\) 国的国王去世之后，他的两个儿子 \(A\) 和 \(B\) 都想成为新的国王，但他们都想让这个国家更加安定，不会用武力解决问题。于是他们想将这个国家分成两个小国家 \(A\) 国和 \(B\) 国。现在，\(A\) 拥有 \(1\) 号城市，\(B\) 拥有 \(N\) 号城市，其他的城市还尚未确定归属哪边。
由于大家都想让国家变得更好，而某些城市的人民愿意国王的 \(A\) 儿子作为他们的领袖，而某些城市更看好 \(B\)，而为了交通的便捷，如果划分后的公路连接两个同一个国家的城市，那么更利于城市之间的交流。于是大臣们设计了一种对土地划分的评分机制，具体如下：
1，对于城市 \(i\) ，如果它划分给 \(A\) 国，将得到 \(VA[i]\) 的得分；划分给 \(B\) 国，将得到 \(VB[i]\) 的得分。
2，对于一条公路 \(i\) ，如果它连接两个 \(A\) 国的城市，将得到 \(EA[i]\) 的得分；连接两个 \(B\) 国的城市，将得到 \(EB[i]\) 的得分；否则，这条公路将失去意义，将扣除 \(EC[i]\) 的得分。
现请你找到最优的土地划分，使得这种它的评分最高。
第一行包含两个整数 \(N\)，\(M\)，含义如问题描述所示。
接下来一行 \(N-2\) 个非负整数，表示 \(VA[2..N-1]\) 。
接下来一行 \(N-2\) 个非负整数，表示 \(VB[2..N-1]\) 。
接下来 \(M\) 行，每行五个非负整数描述一条公路：\(X, Y, EA[i], EB[i], EC[i]\)，含义如问题描述所示。
输出一个整数，表示最高评分。
|
1 2 3 4 5 6 |
3 3 8 9 1 2 2 6 2 2 3 8 5 7 1 3 9 4 1 |
|
1 |
11 |
\(100\%\) 的数据 \(N \leq 10000, M \leq 40000\)；
时间限制：1000MS 内存限制：262144KB
难度：\(6.0\)
有一个 \(n\) 个点，\(m\) 条边的无向图，每次可以对这张图进行操作：对于一条边 \((u,v)\)，可以把图中除了这条边以外的边，每一条的权值都减少 \(1\)。
对于某一条编号为 \(e\) 的边，至少需要多少次操作，才能保证其能出现在最小生成树中？
第一行输入三个整数 \(n\)、\(m\)、\(e\)。
接下来输入 \(m\) 行，每行输入三个整数，其中第 \(i+1\) 行输入的整数分别为 \(u_i\)、\(v_i\)、\(w_i\)，表示无向图的边的两个端点和边权。
输出一个整数表示答案。
|
1 2 3 4 5 6 7 8 9 |
5 8 8 5 1 1 5 2 2 5 3 5 5 4 7 1 2 0 2 3 15 2 4 25 1 4 100 |
|
1 |
170 |
对于 \(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\) 。
时间限制：2000MS 内存限制：1048576KB
难度：\(7.0\)
在工程的开发中，我们常常用 \(Git\) 进行版本的管理。这个方式具体来说是这样的：刚开始只有一个版本 \(0\)，表示最初始的情况，也就是空的项目；接下来一个用户可以对某一个版本 \(p\) 的项目进行修改，得到一个新的版本 \(i\)。这样，一个工程就产生了许多不同的版本，而管理员可以选择一些优秀的，将其合并到主版本中。
\(F\) 公司有一个项目 \(U\)，这个项目由一个字符串构成。版本 \(0\) 为空串。有 \(n\) 个开发者按顺序对这个项目进行了修改，其中第 \(i\) 个开发者将第 \(p_i ( 0 \le p_i < i)\) 个版本的开头添加上一个字符 \(c_i (1 \le c_i \le m)\) 作为新的版本 \(i\)。
作为项目的总负责人，你希望对这些版本进行评价。对一个字符串 \(S\)，称串 \(S\) 是串 \(T\) 的超前缀，当且仅当串 \(S\) 是串 \(T^{*}\) 的前缀。 \(T^{*}\) 表示 \(T\) 重复无限次得到的一个无限长度的串，如若 \(T = abcd\)，则 \(T^{*} = abcdabcdabcd \cdots\)。我们称串 \(S\) 的 “\(kitty\) 长度” 为 \(l\)，当且仅当存在一个长度为 \(l\) 的串 \(T\) 使得 \(S\) 是 \(T\) 的超前缀，且不存在小于 \(l\) 的串 \(T’\) 使得 \(S\) 是 \(T’\) 的超前缀（定义空串的 \(kitty\) 长度为 \(0\)）。你需要做的就是对每一个版本求出其的 \(kitty\) 长度（设版本 \(i\) 的 \(kitty\) 长度为 \(kitty(i)\)）。
在实际运营中，有两种情况，我们用一个数 \(k \in \{0,1\}\) 表示。在 \(k = 0\) 的情况中， 你可以等候开发者进行所有修改后，再进行计算；但在 \(k = 1\) 的情况中，开发者希望能够实时得到自己修改得到的版本的 \(kitty\) 长度，你需要实时计算出每个版本的 \(kitty\) 长度。
第一行包含三个整数 \(n,m,k\)。
接下来 \(n\) 行，其中第 \(i\) 行包含两个整数 \(p^{′}_{i}; c^{′}_{i}\)，其中：
如果 \(k = 0\) ，则 \(p_i = p^{′}_{i}\)，\(c_i = c^{′}_{i}\)；
时间限制：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\) 小的合法的能被填出的串。
|
1 2 3 |
12 1 4 ztrs?a?isred 5 7 |
|
1 |
ztrsdadisred |
对于 \(100\%\) 的数据，保证 \(n,m \leq 5 \times 10^5, k \leq 1 \times 10^{18}\) 。
时间限制：1000MS 内存限制：262144KB
难度：\(5.5\)
班里有 \(n\) 个同学。老师为他们选了 \(n\) 个笔名。现在要把这些笔名分配给每一个同学， 每一个同学分配到一个笔名，每一个笔名必须分配给某个同学。现在定义笔名和真名之间的相关度是他们之间的最长公共前缀。设笔名为 \(a\)，真名为 \(b\)，则他们之间的相关度为 \(lcp(a,b)\)。那么我们就可以得到匹配的质量是每一个同学笔名和真名之间相关度的和。
对于两个字符串 \(a,b\)（从 \(1\) 开始标号），定义 \(a,b\) 的最长公共前缀 \(lcp(a,b)\) 为最大的非负整数 \(k\)，使得 \(k\le |a|, k\le |b|\)，且对所有 \(i=1,2,\ldots,k\)，\(a_i = b_i\) 。
给出一种分配笔名的方案，使得匹配质量最大。
第 \(1\) 行有 \(1\) 个整数 \(n\)，表示班级中同学的数目。接下来 \(n\) 行，表示每一个同学的真名。最后 \(n\) 行是老师已经安排好的笔名。每行的名称仅由小写字母组成。
将分配笔名的方案输出到文件中。第一行输出一个数，表示最大匹配质量。接下来 \(n\) 行，每行两个数 \(a,b\)，表示把编号为 \(b\) 的笔名分配给编号为 \(a\) 的同学。同学和笔名均按输入顺序从 \(1\) 至 \(n\) 编号。若方案不唯一，任意输出一种即可。
|
1 2 3 4 5 6 7 8 9 10 11 |
5 gennady galya boris bill toshik bilbo torin gendalf smaug galadriel |
|
1 2 3 4 5 6 |
11 4 1 2 5 1 3 5 2 3 4 |
对于所有测试点，\(n \leq 100000\)，输入串总长 \(\leq 800000\) 。
时间限制：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\) 行。
|
1 2 3 4 5 6 7 |
3 3 2 4 6 3 3 6 4 1 1 2 5 5 2 |
|
1 2 3 |
2 1 2 |
时间限制：1000MS 内存限制：262144KB
难度：\(4.0\)
有 \(n\) 个货物，每个货物都有各自的重量 \(w_i\) 和价值 \(c_i\)，但是载重量仅为 \(m\) 。
挑选出一些货物，总重量不超过 \(m\)，使价值之和最大。
第一行，两个整数 \(n\)，\(m\)；
接下来 \(n\) 行，每行两个整数 \(w_i\)，\(c_i\) 。
一个整数 \(ans\) 。
|
1 2 3 4 5 |
4 3 3 10 2 7 2 8 1 1 |
|
1 |
10 |
\(1 \leq n \leq 10^6\)，\(1 \leq m \leq 4^{31}\)，\(1 \leq w_i \leq 3\)，\(1 \leq c_i \leq 10^9\) 。
时间限制：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 2 3 4 5 |
3 4 1 4 2 2 5 1 1 3 3 2 2 2 5 1 |
|
1 |
11 |
最优方案如下：以餐馆 \(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 …
时间限制：3000MS 内存限制：262144KB
难度： \(6.0\) 出题人：zzx
给定正整数序列 \(a[1], a[2], \cdots , a[n]\)，你需要依次解决 \(m\) 个询问，每个询问用两个正整数 \(L, R\) 描述， 请求出有多少个数在 \(a[L],a[L+1],\cdots,a[R]\) 中出现正偶数次。
求出每个查询的结果。
输入第一行四个整数 \(n\)、\(c\)、\(m\) 以及 \(t\) 。
第二行 \(n\) 个整数 \(a[1],a[2],\cdots,a[n]\)，每个数在 \([1,c]\) 间。
接下来 \(m\) 行每行两个整数 \(l\) 和 \(r\)，设上一个询问的答案为 \(ans\) (第一个询问时 \(ans=0\) )，令 \(L=(l+t \times ans) \bmod n+1, R=(r+t \times ans) \bmod n+1\)，若 \(L>R\)，交换 \(L\) 和 \(R\)，则本次询问为 \([L,R]\) 。
对于每个询问， 输出一行对应的答案。
|
1 2 3 4 5 6 7 |
5 3 5 1 1 2 2 3 1 0 4 1 2 2 2 2 3 3 5 |
|
1 2 3 4 5 |
2 0 0 0 1 |
对于 \(50\%\) 的数据，有 \(t=0\) 。