分类： 算法

YZOJ P2872 [POJ 1637]Sightseeing tour

YZOJ P2872 [POJ 1637]Sightseeing tour

Time Limit：1000MS      Memory Limit：131072KB

Difficulty: \(6.0\)

  • Description

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.

  • Input

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, …

YZOJ P2163 [THUSC2015]解密运算

YZOJ P2163 [THUSC2015]解密运算

时间限制：1000MS      内存限制：131072KB

难度：\(7.0\) （自评）

  • 题目描述

对于一个长度为 \(N\) 的字符串，我们在字符串的末尾添加一个特殊的字符 “.” 。之后将字符串视为一个环，从位置 \(1,2,3,\cdots,N+1\) 为起点读出 \(N+1\) 个字符，就能得到 \(N+1\) 个字符串。

比如对于字符串 “ABCAAA”，我们可以得到这 \(N+1\) 个串：

接着我们对得到的这 \(N+1\) 个串按字典序从小到大进行排序（注意特殊字符 “.” 的字典序小于任何其他的字符）结果如下：

最后，将排序好的 \(N+1\) 个串的最后一个字符取出，按照顺序排成一个新的字符串，也就是上面这个表的最后一列，就是加密后的密文 “AAAC.AB” 。

请通过加密后的密文求出加密前的字符串。

  • 输入格式

第一行有两个整数 \(N, M\)，分别表示加密前的字符串长度和字符集大小，其中字符用整数 \(1,2,3,\cdots,M\) 编号，添加的特殊字符 “.” 用 \(0\) 编号。

第二行为 \(N+1\) 个整数，表示加密后的字符串。

  • 输出格式

输出仅一行，包含 \(N\) 个整数，用空格隔开，依次表示加密前字符串中每个字符的编号。

  • 样例输入

  • 样例输出

  • 数据规模与约定

\(N,M \leq 200000\) 。

 

 …

YZOJ P3933 [Baltic2004]sequence

YZOJ P3933 [Baltic2004]sequence

时间限制：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\) 。

 

 

Source: BZOJ 1367…

YZOJ P3629 [校内训练20180406]表达式

YZOJ P3629 [校内训练20180406]表达式

时间限制：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表示。…

YZOJ P1868 土地划分

YZOJ P1868 土地划分

时间限制：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]\)，含义如问题描述所示。

  • 输出格式

输出一个整数，表示最高评分。

  • 样例输入

  • 样例输出

  • 数据规模与约定

\(100\%\) 的数据 \(N \leq 10000, M \leq 40000\)；

保证运算过程中及最终结果不超过32位带符号整数类型的表示范围。…

YZOJ P3049 [SHOI2010]Minimum Spanning Tree

YZOJ P3049 [SHOI2010]Minimum Spanning Tree

时间限制：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\) 。

 

 

 …

[校内训练20161216] T2 版本管理git

[校内训练20161216] T2 版本管理git

时间限制：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}\)；

如果 \(k = 1\)，则 \(p_i = p^{′}_{i} \oplus kitty(i …

YZOJ P3389 [FOI 2018 四校联训 Round 3]消息密匙

YZOJ P3389 [FOI 2018 四校联训 Round 3]消息密匙

时间限制：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}\) 。

 

 

 …

YZOJ P3385 [校内训练20171201]笔名分配问题

YZOJ P3385 [校内训练20171201]笔名分配问题

时间限制：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\) 编号。若方案不唯一，任意输出一种即可。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于所有测试点，\(n \leq 100000\)，输入串总长 \(\leq 800000\) 。

 

 

 …

YZOJ P3361 [校内训练20171117]数点问题

YZOJ P3361 [校内训练20171117]数点问题

时间限制：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\)，\(n,m\le 200,000\)，\(k=1\)…