2022.11.17补题祭

前言：

考完期中考试了！！生物逆袭了！！全年级前十（可能是因为题目太简单我比较细心吧）但还是错了一些不该错的题目......（生物惨痛87分）

感觉这次期中考试情况良好，在会做难题的同时，也要好好巩固基础才行呀！！速度还是得提上来，要有量与质的突变！！相信自己，总能行的

要发展成一个全能的人啊！

最近做核酸的次数越来越频繁，好多地区都被封了（我想回家啊！！！）

宜：参加模拟赛
可以AK虐全场
宜：泡妹子
说不定可以牵手

今晚上来补题录：（有些题目可能观看者打不开，我把部分题目复制了一下）

模拟赛14

CSP-S全国排位赛第二场

CSP-S全国排位赛第一场

2021 CSP/NOIP挑战赛 Contest03

2021 CSP/NOIP挑战赛 Contest04

NOIP 2021全国排位赛

CSP-S 2022模拟赛14

A. 秘密邮件

题目描述

Sharon 收到了一封来自外星球的秘密邮件。邮件由 n 个大写英文字母组成，不巧的是 Sharon 收到邮件以后一不小心打乱了原来的字母顺序。但是聪明的Sharon 记住了原邮件的完整内容，现在她每次可以选择打乱后的邮件中相邻的两个字母进行交换，问最少交换多少次能够将打乱的邮件恢复成原邮件。

输入格式

第一行一个整数 n 表示邮件的长度。

第二行一个长度为 n 的只包含大写字母的字符串表示打乱后的邮件。

第三行一个长度为 n 的只包含大写字母的字符串表示原邮件。

为保证打乱后的邮件可以恢复成原邮件，所有的测试数据满足任意一种大写字母在两封邮件中的出现次数相同。

输出格式

共一行包含一个整数，表示最少的交换次数.

样例

样例1输入

复制

4
ABCD
DBCA

样例1输出

复制

5

数据范围与提示

样例说明

第一次交换第一个和第二个字母得到 BACD；

第二次交换第二个和第三个字母得到 BCAD；

第三次交换第三个和第四个字母得到 BCDA；

第四次交换第二个和第三个字母得到 BDCA；

第五次交换第一个和第二个字母得到 DBCA。

数据范围

B. 押韵字符串

内存限制：512 MiB时间限制：1000 ms输入文件：string.in  输出文件：string.out

题目类型：传统评测方式

题目描述

Lay博士是一个诗词爱好者,众所周知大多诗词都需要押韵.

Lay博士觉得两个单词A,B是押韵的,当且仅当A,B的最长公共后缀长度LCS大于等于A,B中较长串的长度-1.即 LCS(A,B)≥max(|A|,|B|)-1.（两个单独的小写字母也算押韵）

现在Lay博士看到了一篇文章,他想知道能否将文章中的某些单词选出来,再按照某种顺序排列得到的序列满足任意两个相邻的串都押韵.

现在他想知道这个序列最大的长度.

（单词只含小写字符）

输入格式

第一行一个整数,表示文章中的单词数量.

接下来行,每行一个单词.

数据保证任意两个单词不相同.

输出格式

输出一行 表示最长的序列长度.

样例

样例1输入

复制

4 
honi 
toni 
oni 
ovi 

样例1输出

复制

3

样例2输入

复制

5 
k 
ask 
psk 
krafna 
sk 

样例2输出

复制

4

样例3输入

复制

5 
pas 
kompas 
stas 
s 
nemarime

样例3输出

复制

1

数据范围与提示

数据范围

30%的数据 n<=18

另有40%的数据 n<=3000

100%的数据 n<=500000,字符串总长<=3000000.

样例解释

样例二解释：ask-psk-sk-k

C. 最近公共祖先

内存限制：128 MiB时间限制：1000 ms输入文件：lca.in输出文件：lca.out

题目类型：传统评测方式：文本比较

题目描述：

给定一棵n个结点的有根树，结点编号为1 ∼ n，其中根结点为1号结点。 每个结点 都对应着一种颜色（黑/白）和一个固定的权值，初始时所有结点的颜色都为白色。 现 在你需要实现以下两种操作：

• Modify v：将结点v的颜色修改为黑色；（可能一个点被修改多次）
• Query v：找到一个黑色结点u，使得结点u和v的最近公共祖先z对应的权值尽可能大，输出结点z的权值。  如果此时树中不存在黑色结点，输出−1。

输入格式

第一行为两个正整数n和m，分别表示树中的结点数以及操作总数目。 第二行为n个正整数w1, w2, • • • , wn(wi <=1000000000)，分别表示这n个结点对应的权值。 接下来n − 1行，每行两个正整数ai, bi，表示结点ai与结点bi之间有一条边相连。 接下来m行，每行由一个字符串str和一个正整数v组成，分别表示操作类型以及操作对应结点的编号。

输出格式

对于每个询问操作，每行输出一个整数，对应着这个询问的答案。

样例

输入

7 7
4 3 5 7 6 5 2
1 4
2 1
7 5
6 2
2 5
3 4
Query 1
Modify 2
Modify 4
Query 3
Modify 2
Modify 5
Query 6

输出

-1
7
4

数据范围与提示

对于10%的数据：n <= 100, m <= 200

对于20%的数据：n <= 3000, m <= 3000

对于另外20%的数据：对于编号为i的结点，其父亲节点编号在[1, i − 1]内均匀随机 

对于另外20%的数据：保证Query操作在所有Modify操作完成之后 

对于100%的数据：n <= 100000, m <= 200000