数据结构题目

如果你是荣誉课的学生，请你注意以下事项：

1. 每一届的题目不一样
2. 我的代码仅提供参考和复习使用，请勿直接抄袭，事后会对代码进行查重处理
3. 请更改你的OJ账户密码（如果你们的密码仍然是你们的学号的话）
4. 如果你有任何问题，可以通过博客上的方式联系我，如果有时间我会回复
5. 祝你们取得好成绩！

回忆版

具体数据范围没有记，但是都挺严的，\(C\) 题考场上没人做，主要是因为数据范围太大

B

题目背景

已知树上每个节点最初颜色是 \(0\)，节点 \(1\) 为树根，布料只会进行 \(q\) 次染色操作，每次操作可以用数字 \(op, x, y\) 或 \(op, x, y,z\) 表示。

你需要对布料的 \(q\) 次操作进行管理。

• 如果 \(op = 1\)，表示将以节点 \(x\) 为根的子树（即 \(x\) 和其所有子孙后代节点）全部染上颜色 \(y\)。
• 如果 \(op = 2\)，表示将节点 \(x\) 到根节点 \(y\) 的路径上的所有节点（包含 \(x\) 和 \(y\) 自身）染成颜色 \(z\)。

你需要回答最终每个节点的颜色是什么。

输入格式

第一行两个整数 \(n, q\)，分别表示节点数量和操作次数。

第二行 \(n-1\) 个整数 \(p_2, p_3, \dots, p_n\)，依次表示第 \(i\) 节点的父节点。

接下来 \(q\) 行每行三个整数 \(op, x, y\) 或四个整数 \(op,x,y,z\)，表示这次 \(q\) 个操作。

输出格式

输出 \(n\) 行，每行两个数用空格分开表示每个节点的颜色。

C

题目背景

定义斐波那契字符串如下：

\(f_1=a\)

\(f_2=b\)

\(f_{i+2}=f_{i+1}+f_i\) （\(+\) 表示字符串拼接）

给定查询字符串 \(s\) 和整数 \(n\)，你需要计算出 \(f_n\) 中 \(s\) 出现的次数，由于这个数据可能会很大，你需要将结果对 \(10^9+7\) 取模。

输入格式

第一行两个整数 \(n, m\)，分别表示斐波那契字符串的下标和查询次数。

接下来 \(m\) 行每行一个字符串表示这一次的查询字符串。

输出格式

输出 \(m\) 行，每行一个整数表示答案。

D

题目背景

每个人有一个值 \(a_i\)，现在你需要计算区间数量，使得区间内不同的值的数量至少为 \(k\)。

输入格式

第一行两个整数 \(n,k\)，分别表示人数和总量。

接下来一行 \(n\) 个整数 \(a_1,a_2,\dots,a_n\)，表示每个人的值。

输出格式

输出一个整数表示答案。

E

题目描述

众所周知，俄国的克格勃力量很强大，而且对乌克兰虎视眈眈。因此决定派遣间谍进入乌克兰。乌克兰有 \(n\) 座城市，克格勃在乌克兰的每座城市都成功插入间谍，现在他们需要建立通讯线，使得任意两座城市的间谍都能直接或者通过其他多人转发间接联系得上。已知第 \(i\) 座城市乌克兰的警戒值为 \(a_i\)，要在城市 \(u\) 和城市 \(v\) 建立通信线需要花费代价 \(a_u + a_v \text{mod} k\)。但是苏联留下了一些遗产，已知有 \(m\) 条苏联克格勃留下的通信线，只需要花费代价 \(w_i\) 就能重启该通信线。现在克格勃需要花费最小代价建立或者重启通信线，使得任意两座城市之间的间谍都能相互联系得上，请问最小代价为多少。

保证 \(a_i < k\) 但不保证 \(w_i <k\)

输入格式

第一行包括三个数 \(n,m,k\)，表示乌克兰城市数量和苏联留下的通信线路数量。

第二行包括 \(n\) 个数，表示每座城市乌克兰的警戒值 \(a_i\)。

接下来 \(m\) 行，每行包括三个数 \(u_i, v_i, w_i\)，表示苏联留下的第 \(i\) 条通信线连接城市 \(u_i\) 和城市 \(v_i\)，重启代价为 \(w_i\)。

输出格式

一个整数，表示克格勃建立或者重启通信线使得任意两座城市之间的间谍都能相互联系得上的最小代价。