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 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\) 行,输出每次训练时的行驶路径经过的最大车道数。

  • 样例输入

  • 样例输出


YZOJ P3199 [FJSC2017D8T1]飙车一时爽,一直飙车一直爽

YZOJ P3199 [FJSC2017D8T1]飙车一时爽,一直飙车一直爽

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

难度: \(4.5\)

  • 题目描述

最近 \(mnihyc\) 喜欢上了飙车,他甚至飙到了 \(40km/h\) ,这已经是严重的超速了!因此,只要他飙车时连续通过超过 \(K\) 段道路,那么他就会被交警抓走!不过幸好的是,他骑的是共享单车,所以他可以在某些路口更换他的自行车,这样交警就不会发现之前那个飙车的是他了!

简单来说,城镇中有 \(N\) 个路口,\(M\) 条双行道连接着两个不同的路口。这些路口中总共有 \(P\) 个有共享单车停靠点,分别分布在 \(a_1, a_2, \cdots, a_P\) 上。

现在 \(mnihyc\) 想知道,从 \(S\) 出发到 \(T\) ,他至少可以飙上多少段连续的道路?如果太少的话,他会选择蹲在家里推游戏的(好可怜)。

形式化的,给定一张无向图,\(\left| V \right| = N\),\(\left| E \right| = M\),边权均为 \(1\),找出一条从 \(S\) 到 \(T\) 的可重路径使得路径上相邻的关键点(\(S, T, a_1, a_2, \cdots, a_P\))之间的最大距离 \(K\) 最小

  • 输入格式

第一行一个正整数 \(CAS\) 表示测试数据组数。

每组测试数据第一行有三个数 \(N, M, P\)  如上文所述,第二行 \(P\) 个数表示 \(a_1, a_2, \cdots, a_P\) 。

接下来 \(M\) 行,每行两个数表示一条边。

最后 \(S\) 和 \(T\) 表示开始节点和的目标节点。

  • 输出格式

对于每组数据:若始终都无法找到合法的路径,输出 \(-1\),否则输出最的小的 \(K\) 。…