求题解 玄关~

T1、质数因子$(prime)$

问题描述：

$NOIP$ 普及组有一道质数因子题：已知 $n$ 是两个质数的乘积，求其较大的那个质数因子。下面我们来改编一下：输入正整数 $n$，如果它恰好是两个质数的乘积，则输出其较大的那个质数因子，否则输出 $-1$。

输入格式：

第一行为正整数 $t(≤1000)$，表示数据组数；接下来 $t$ 行，每行一个正整数$n(≤2.1*10^9)$。

输出格式：

对于每个 $n$，输出其较大质数因子，或者 $-1$。

输入样例:

3
15
105
2000000014

输出样例:

5
-1
1000000007

T2、字符串变换$(convert)$

问题描述：

给定一个字符串 $s$，全部由小写字母组成，定义字符变换规则：把其中所有的字符 $x$ 变成 $y$，而所有的 $y$ 变成 $x$，即 $x$ 和 $y$ 互换。如字符串“apple”，令 $a$ 和 $p$ 互换，则变成“paale”。下面对 $s$ 最多进行一次变换，求变换后字典序最小的字符串。

输入格式：

第一行为正整数 $t(≤5)$，表示数据组数；接下来 $t$ 行，每行一个完全由小写字母组成的字符串 $s$，长度不超过 $10^5$。

输出格式：

对于每组输入，输出变换后字典序最小的字符串。

输入样例:

3
hamza
racecar
mca

输入样例:

ahmzh
arcecra
acm

T3、捐款$(donation)$

问题描述：

n 个人为一项慈善活动捐款，第 $i$ 个人捐款上下限分别是 $ai$ 和 $bi$，捐款的最小金额为 $p$，如果 $p<ai$，那么这个人会捐款 $ai$；如果 $ai≤p≤bi$，那么这个人会捐款 $p$；如果 $p>bi$，那么这个人不会捐款。请你来设定 $p$，使得捐款的总金额最大。

输入格式：

第一行为正整数 $t(≤5)$，表示数据组数；每组数据中，第一行正整数 $n(≤10^5)$ 表示捐款人数，接下来 $n$ 行，每行两个正整数 $ai$ 和 $bi$ 表示捐款上下限 $(ai<bi ≤10^9)$。

输出格式：

对于每组数据，输出两个整数分别表示最大的 $p$ 和总捐款额。

输入样例:

1
2
5 10
20 25

输出样例:

10 30

样例解释：

设置 $p=10$，则总捐款额为 $10+20=30$。

T4、记忆难度$(memory)$

问题描述：

想要背诵一段很长的数字，比如圆周率，可以将这些数字分割成一个个片段，根据每个片段的规律做不同的记忆训练。不妨假定每个片段最少 $3$ 个数，最多 $6$ 个数。各种片段的记忆难度定义如下：

• 若所有数字相同，如 666，88888 等，记忆难度为 1；
• 公差为 1 或者-1 的等差数列，如 3456，43210 等，记忆难度为 2；
• 两个数字交替出现，如 313，68686 等，记忆难度为 4；
• 其他等差数列，如 7531，369 等，记忆难度为 5，但注意，36912 不算等差数列，因为我们只考虑一位数字，不属于上述任何一条规律的，比如 2794 等，记忆难度为 10。

现在给定一个由数字构成的字符串 $s$，请找出一个分割片段的方法，使得所有片段的记忆难度之和最小。

输入格式：

第一行为正整数 $t(≤5)$，表示数据组数；接下来 $t$ 行，每行一个数字字符串 $s$，串长满足 $3≤|s|≤10^5$。

输出格式：

对于每组数据，输出其记忆难度之和的最小值。

输入样例:

3
314159265358979323846
271828182845904523536
12122222

输出样例:

34
40
5

样例解释：

样例 1，分成(314159)(265358)(979)(323846)，总难度为 10+10+4+10=34；

样例 2，分成(271828)(182845)(904523)(536)，总难度为 40。

求题解 玄关~