分类： 其他

YZOJ P4258 [FJWC2019]原样输出

YZOJ P4258 [FJWC2019]原样输出

时间限制：4000MS      内存限制：262144KB

出题人：E.Space        难度：\(7.0\)

  • 题目描述

它会把输入按行读入，原封不动地复制到输出中去。

但是在一次更新以后，它的程序出了一些问题。

它没法输出换行符了。

并且，读入的时候，总会莫名其妙地随机漏掉开头和结尾的若干个字符，甚至整行都会漏掉。

比如 orzxxxxx 可能会变成 rzxx、orz、x 或者空串。

现在你找到一份输入文件丢给它，你想知道它的输出可能有多少种情况，以及每种情况分别是什么。

由于你找到的输入文件全部来自之前的福建省选，所以所有的输入文件每行只可能包含 A、C、G、T 四种字符。

  • 输入格式

第一行一个正整数 \(n\)，表示（题面中）输入文件的行数。

接下来 \(n\) 行，表示输入文件的内容。保证这 \(n\) 行中每行的每个字符是 A、C、G、T 四种字符中的一种。

接下来一个整数 \(k, (0 \leq k \leq 1)\)，具体含义详见输出格式。

  • 输出格式

若 \(k=0\)，你需要输出一行，表示输出的可能情况个数模 \(10^9+7\) 的结果。

若 \(k=1\)，你需要按照字典序从小到大输出所有可能的输出情况，一行一个字符串，最后一行输出输出的可能情况个数模 \(10^9+7\) 的结果。

  • 样例输入

…

YZOJ P4259 [FJWC 2019] 不同的缩写

YZOJ P4259 [FJWC 2019] 不同的缩写

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

出题人：E.Space      难度：\(6.1\)

  • 题目描述

在这个游戏中一共有 \(n\) 个角色。你需要编写一些关于这些角色的对话内容。

你打算用角色名字的一个非空子序列来作为它的简称。

当然，不同的角色要用不同的字符串作为简称，否则你就变量重名了。

你想确定一个简称的分配方案使得所有角色中最长的简称尽量短。

  • 输入格式

第一行一个正整数 \(n\)。

接下来 \(n\) 行，每行一个由小写字母组成的字符串，代表一个角色的名字。

不同的角色可能会有相同的名字。

  • 输出格式

如果不存在一种分配简称的方案满足条件，输出 \(-1\)。

否则第一行输出一个正整数，表示最长的简称的最小长度。

接下来 \(n\) 行每行一个字符串，按顺序表示每个角色的简称。

若有多种方案满足条件，那么你可以输出任意一种。

  • 样例输入

  • 样例输出

  • 数据规模与约定

保证 \(n \leq 300\) ，每个名字的长度不超过 \(300\)。

 

 

 …

YZOJ P3924 [IOI2011]Race

YZOJ P3924 [IOI2011]Race

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

难度：\(7.0\)

  • 题目描述

给一棵树，每条边有权。

求一条简单路径，权值和等于 \(K\) ，且经过边的数量最小。

\(N \leq 200000, K \leq 1000000\) 。

  • 输入格式

第一行 两个整数 \(n\)，\(k\) 。

第 \(2\)~\(n\) 行 每行三个整数，表示一条无向边的两端和权值（注意点的编号从 \(0\) 开始）。

  • 输出格式

一个整数，表示最小边数量。

如果不存在这样的路径，输出 \(-1\) 。

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 2599…

[校内训练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 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\)…

YZOJ P3216 行商

YZOJ P3216 行商

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

难度：\(4.0\)

  • 题目描述

有 \(n\) 个货物，每个货物都有各自的重量 \(w_i\) 和价值 \(c_i\)，但是载重量仅为 \(m\) 。

挑选出一些货物，总重量不超过 \(m\)，使价值之和最大。

  • 输入格式

第一行，两个整数 \(n\)，\(m\)；

接下来 \(n\) 行，每行两个整数 \(w_i\)，\(c_i\) 。

  • 输出格式

一个整数 \(ans\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

 \(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\) 。

 

 

 …

YZOJ P3371 简单计数问题

YZOJ P3371 简单计数问题

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

  • 结果输出

对于每个询问， 输出一行对应的答案。

  • 样例输入

  • 样例输出

  • 数据范围

对于 \(50\%\) 的数据，有 \(t=0\) 。

对于另外 \(50\%\) 的数据，有 \(t=1\) …

YZOJ P3846 [2018省队集训]Yist

YZOJ P3846 [2018省队集训]Yist

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

难度： \(7.0\)

  • 题目描述

有一个 \(n\) 个点 \(m\) 条边的无向图，结点从 \(1\) 到 \(n\) 标号，点 \(u\) 的初始权值为 \(w_u\)。你可以对任意结点 \(u\) 进行操作，将你的得分（初始为 \(0\)）加上 \(\sum_\limits{(u,v) \in E}w_v\) ，并将 \(w_u\) 除以 \(2\) 。

给定一个长度为 \(k\) 的结点序列 \(s_1,s_2,\cdots,s_k\) （\(1 \leq s_i \leq n\)），在一轮操作中，你需要依次对 \(s_1,s_2,\cdots,s_k\) 进行操作。你想知道，在进行了无限轮操作后，你得分的极限是多少。

显然答案一定可以表示成 \(P/Q\) 的形式，你需要输出 \(P \times Q^{-1}\) 在模 \(998244353\) 意义下的值。特别的，如果得分并不收敛，输出 \(-1\) 。

  • 输入格式

本题有多组数据，请读入到文件结束。

对于每组数据，第一行三个整数 \(n,m,k\) ，含义如题所述。

第二行 \(n\) 个整数 \(w_1,w_2,\cdots,w_n\)，表示结点的初始权值。

第三行 \(k\) 个正整数 \(s_1,s_2,\cdots,s_k\) 。

接下来 \(m\) 行，每行两个整数 \(u,v\)，描述了一条无向边。

  • 输出格式

对于每组数据，输出一行一个整数，表示答案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(20\%\) 的数据，\(n,m \leq 5\)，\(k \leq 10\)；

对于 \(40\%\) 的数据，\(n,m \leq 1000\)，\(k \leq 2000\)；

对于另外 \(20\%\) 的数据，数据为随机生成；

对于 \(100\%\) 的数据，\(1 \leq …

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

  • 样例输入

  • 样例输出

…