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\) 场游戏中如何安排赛车的使用。如果存在多组解,输出其中任意一组即可。…

[FJWC2019 Day2] 直径

[FJWC2019 Day2] 直径

时间限制:1000MS      内存限制:524288KB

难度: \(4.0\)

  • 题目描述

你需要构造一棵至少有两个顶点的树,树上的每条边有一个非负整数边权。树上两点 \(i,j\) 的距离 \(dis(i,j)\) 定义为树上连接 \(i\) 和 \(j\) 这两点的简单路径上的边权和。

我们定义这棵树的直径为,所有满足 \(1 \leq i < j \leq n\) 的 \((i,j)\) 中,\(dis(i,j)\) 最大的。如果有多个这样的 \((i,j)\),那么均为直径。

作为一个构造题,你需要构造一个恰有 \(k\) 个直径。可以证明在给定的限制下一定有解。

  • 输入格式

一行一个正整数 \(k\),表示你需要构造出一个恰有 \(k\) 个直径的树。

  • 输出格式

第一行一个正整数 \(n\),表示你构造的树的点数。

接下来 \(n-1\) 行,每行三个整数 \(i,j,w\),表示一条连接点 \(i\) 和 \(j\) (点的编号为 \(1,2, \cdots, n\))的树边,边权为 \(w\) 。

  • 样例输入

  • 样例输出

  • 样例说明

这只是一种符合题意的输出,可能还有其他输出。在这个输出中,直径为 \((1,5),(3,5),(4,5)\) 。

  • 数据规模与约定

注意,你需要构造出的树必须满足 \(2 \leq n \leq 5000, 0 \leq w \leq 10^5\)

对于 \(30pts\) 的数据,\(1\leq k \leq 2000\) ;

对于 \(100pts\) 的数据,\(1\leq k \leq 5 \times 10^6\) 。

 

 

YZOJ P4260…