YZOJ P2791 商人
时间限制：2000MS 内存限制：262144KB
难度：\(6.0\)
分类： 图论
… YZOJ P3195 [NOI2017]游戏
YZOJ P3195 [NOI2017]游戏
时间限制：1000MS 内存限制：524288KB
难度： \(6.4\)
-
题目描述
小 L 计划进行 \(n\) 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。
小 L 的赛车有三辆，分别用大写字母 \(A\)、\(B\)、\(C\) 表示。地图一共有四种，分别用小写字母 \(x\)、\(a\)、\(b\)、\(c\) 表示。其中，赛车 \(A\) 不适合在地图 \(a\) 上使用，赛车 \(B\) 不适合在地图 \(b\) 上使用，赛车 \(C\) 不适合在地图 \(c\) 上使用，而地图 \(x\) 则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 \(d\) 张。
\(n\) 场游戏的地图可以用一个小写字母组成的字符串描述。例如：\(S=\underline{\mathrm{xaabxcbc}}\) 表示小 L 计划进行 \(8\) 场游戏，其中第 \(1\) 场和第 \(5\) 场的地图类型是 \(x\)，适合所有赛车，第 \(2\) 场和第 \(3\) 场的地图是 \(a\)，不适合赛车 \(A\)，第 \(4\) 场和第 \(7\) 场的地图是 \(b\)，不适合赛车 \(B\)，第 \(6\) 场和第 \(8\) 场的地图是 \(c\)，不适合赛车 \(C\) 。
小 L 对游戏有一些特殊的要求，这些要求可以用四元组 \((i,h_i,j,h_j)\) 来描述，表示若在第 \(i\) 场使用型号为 \(h_i\) 的车子，则第 \(j\) 场游戏要使用型号为 \(h_j\) 的车子。
你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 “\(-1\)”（不含双引号）。
-
输入格式
输入第一行包含两个非负整数 \(n,d\) 。
输入第二行为一个字符串 \(S\) 。
\(n,d,S\) 的含义见题目描述，其中 \(S\) 包含 \(n\) 个字符，且其中恰好 \(d\) 个为小写字母 \(x\) 。
输入第三行为一个正整数 \(m\)，表示有 \(m\) 条用车规则。接下来 \(m\) 行，每行包含一个四元组 \(i,h_i,j,h_j\) ，其中 \(i,j\) 为整数，\(h_i,h_j\) 为字符 \(A\) 、\(B\) 或 \(C\)，含义见题目描述。
-
输出格式
输出一行。
若无解，输出 “\(-1\)”（不含双引号）。
若有解，则包含一个长度为 \(n\) 的仅包含大写字母 \(A\)、\(B\)、\(C\) 的字符串，表示小 L 在这 \(n\) 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。…
YZOJ P3847 [2018省队集训]Ernd
YZOJ P3847 [2018省队集训]Ernd
时间限制：1000MS 内存限制：131072KB
难度：\(8.0\)
-
题目描述
给定一个长度为 \(n\) 且仅包含小写英文字母的字符串 \(S\)。你有一个字符串 \(T\)，初始为空串。
你可以进行 \(n\) 次操作，每次操作你可以在 \(T\) 的前端或末尾加入一个任意字母。记第 \(i\) 次操作后 \(T\) 在 \(S\) 中的出现次数为 \(f_i\)，你需要最大化 \(ans=\sum\limits_i f_i\) 。
-
输入格式
第一行一个正整数 \(n\) 。
第二行一个长度为 \(n\) 的字符串 \(S\) 。
-
输出格式
一行一个整数，表示 \(ans\) 的最大值。
-
样例输入
|
1 2 |
6 abcabc |
-
样例输出
|
1 |
9 |
-
数据规模与约定
对于 \(100\%\) 的数据，\(1 \leq n \leq 2\times 10^5\) 。
YZOJ P3939 [HAOI2016]找相同字符
YZOJ P4259 [FJWC 2019] 不同的缩写
YZOJ P4259 [FJWC 2019] 不同的缩写
时间限制：1000MS 内存限制：262144KB
出题人：E.Space 难度：\(6.1\)
-
题目描述
在这个游戏中一共有 \(n\) 个角色。你需要编写一些关于这些角色的对话内容。
你打算用角色名字的一个非空子序列来作为它的简称。
当然，不同的角色要用不同的字符串作为简称，否则你就变量重名了。
你想确定一个简称的分配方案使得所有角色中最长的简称尽量短。
-
输入格式
第一行一个正整数 \(n\)。
接下来 \(n\) 行，每行一个由小写字母组成的字符串，代表一个角色的名字。
不同的角色可能会有相同的名字。
-
输出格式
如果不存在一种分配简称的方案满足条件，输出 \(-1\)。
否则第一行输出一个正整数，表示最长的简称的最小长度。
接下来 \(n\) 行每行一个字符串，按顺序表示每个角色的简称。
若有多种方案满足条件，那么你可以输出任意一种。
-
样例输入
|
1 2 3 4 5 6 7 8 9 10 11 12 |
11 night nealchen beimingyouyu echo rankinf dntcrybecthlev lagoon cyc alphagem leehwincing clin |
-
样例输出
|
1 2 3 4 5 6 7 8 9 10 11 12 |
1 g a m e r b o y l w c |
-
数据规模与约定
保证 \(n \leq 300\) ，每个名字的长度不超过 \(300\)。
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 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]\)，含义如问题描述所示。
-
输出格式
输出一个整数，表示最高评分。
-
样例输入
|
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\)；
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\)，表示无向图的边的两个端点和边权。
-
输出格式
输出一个整数表示答案。
-
样例输入
|
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\) 。
YZOJ P3392 越野赛车问题
YZOJ P3392 越野赛车问题
时间限制：1000MS 内存限制：262144KB
难度： \(6.0\)
-
问题描述
某山上一共有 \(n\) 个广场，编号依次为 \(1\) 到 \(n\)，这些广场之间通过 \(n-1\) 条双向车道直接或间接地连接在一起。对于每条车道 \(i\)，可以用四个正整数 \(u_i, v_i, l_i, r_i\) 描述，表示车道连接广场 \(u_i\) 和 \(v_i\)，其速度承受区间为 \([l_i, r_i]\)，即汽车必须以不小于 \(l_i\) 且不大于 \(r_i\) 的速度经过车道 \(i\) 。
现计划进行 \(m\) 次训练，每次选择某山上的一条简单路径，然后在这条路径上行驶，且每次训练时的车速都是固定的。现在有在 m 次训练中分别计划使用的车速，要求一条合法的路径（车速在所有车道的速度承受区间的交集内），使得路径上经过的车道数最大。
-
数据输入
输入文件的第一行包含两个正整数 \(n, m\)，表示广场数和训练次数。接下来 \(n-1\) 行，每行四个正整数 \(u_i, v_i, l_i, r_i ( \leq n)\)，描述所有车道。最后 \(m\) 行，每行一个正整数 \(v (\leq n)\) ，表示每次训练是的车速。
-
结果输出
输出 \(m\) 行，输出每次训练时的行驶路径经过的最大车道数。
-
样例输入
|
1 2 3 4 5 6 7 8 |
5 3 3 2 2 4 1 5 2 5 4 5 2 2 1 2 3 5 1 2 3 |
-
样例输出
|
1 2 3 |
0 2 3 |
YZOJ P2417 [FJWC2016][CF79-D]翻转硬币
YZOJ P2417 [FJWC2016][CF79-D]翻转硬币
时间限制：1000MS 内存限制：131072KB
难度： \(6.0\)
-
题目描述
\(n\) 枚硬币正面朝上摆成一排，给定 \(a_1, a_2, \cdots, a_m\)，每次操作可以任意选择一个 \(a_i\)，并翻转连续 \(a_i\) 个硬币。
要求经过最少次数的操作，使得仅第 \(x_1, x_2, \cdots, x_k\) 枚硬币反面朝上，输出最少次数。
-
输入格式
第一行三个整数 \(n\)、\(k\)、\(m\) 。
第二行 \(k\) 个整数表示需要反面朝上的硬币位置，从 \(1\) 编号。
第三行 \(m\) 个整数表示 \(a_1, a_2, \cdots, a_m\) 。
-
输出格式
一个整数表示答案，若无解，则输出 \(-1\) 。
-
样例输入
|
1 2 3 |
10 8 2 1 2 3 5 6 7 8 9 3 5 |
-
样例输出
|
1 |
2 |
-
数据规模与约定
对于 \(30\%\) 的数据，\(n, m \leq 10\) 。
对于 \(60\%\) 的数据，\(m \leq 20\) 。
对于 \(100\%\) 的数据，\(1 \leq n \leq 10000\)，\(1 \leq k \leq 10\)，\(1 \leq m \leq 100\)，\(1 \leq a_i \leq n\) 。
Source: CF79-D…