T1

题目描述
YJC最近在学习字符串的有关知识。今天，他遇到了这么一个概念：最长公共回文子序列。一个序列S，如果S是回文的且分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共回文子序列。YJC很聪明，他很快就学会了如何求最长公共回文子序列。他现在想把问题规模扩大一些，于是他提出了这么一个问题：给一个长度为n(1≤n≤100000)的字符串a和一个长度为m(1≤m≤20)的字符串b，求a和b的最长公共回文子序列的长度。YJC发现他不会做了，于是他来问你这个问题的答案。

输入
第一行包含一个字符串，表示字符串a。
第二行包含一个字符串，表示字符串b。

输出
一行，包含一个整数，表示a和b的最长公共回文子序列的长度。

样例输入
aaaba
aabba

样例输出
3

数据范围限制
对于50%的数据，满足1≤n≤100。
对于100%的数据，满足1≤n≤100000，1≤m≤20，字符串只包含小写字母。

提示
最长公共回文子序列是aaa，长度为3。最长公共子序列是aaba，但它不是回文的。

与洛谷P3815意思相同,但没有多测，相对没那么阴间(看一下题解就知道P3815多阴了)
这题有说暴力构造字串的，也有说用自动机的，总之不是很会

T2

题目描述
在艾泽拉斯的无尽之海里，有着一群不为人知的由各个种族的冒险者统治的岛屿，这些岛屿都很庞大，足以在上面建造许多的城市，城市之间有一些单向道路连接。
有一天，QYQ无意中发现了这些岛屿，并且发现在每个城市的地下都或多或少埋藏着一些装备、金币、宝物……
可是正当QYQ兴奋不已打算全部把它们拿走时，他却惊奇的发现你的魔法在这里被限制住了，唯一可用的技能就是闪现，而且魔法只够他使用K次这个技能了，每次使用这个技能QYQ只能从一个岛屿上闪现到另外一个岛屿上。每一个岛屿只能登上一次，QYQ可以从任何一个城市开始旅程，在任何一个城市结束旅程。
城市的数量共有n个，有m条道路，每一条道路有两个参数u，v，表示从u到v有一条道路，但你只能由u到v走，两个城市属于相同的岛屿当且仅当暂时将所有道路视为双向道路时可以从其中一个城市走到另一个城市（可以途径其它城市）。
每一个城市都有一个宝物的总价值v[i]，你的任务是帮助QYQ得到最大总价值的宝物，并输出这个值。

输入
输入的第一行包含两个整数n，m
输入的第二行到第m+1行，每行包含2个整数u,v，代表你可以从城市u走到城市v
输入的第m+2行包含n个整数，第i个整数代表v[i]，即这个城市的宝物总价值。
输入的第m+3行包含一个整数K，代表你可以使用技能的次数。

输出
输出的第一行包含一个整数，代表QYQ能获得的最大的宝物总价值

样例输入
3 2
1 2
3 1
1 2 1
0

样例输出
4
样例说明：
QYQ从3号点开始，走到2号点，最后走到1号点，结束旅程，共获得1+2+1=4价值的宝物

数据范围限制
对于30%的数据：n<=10，K=0
对于50%的数据：n<=100，m<=100，K<=1
对于100%的数据：1<=n<=100000，1<=m<=1000000，1<=v[i]<=1000，0<=K<=100000
图中可能会有重边、自环。

这题说法有二：Tarjan + DP 或 Tarjan + 拓扑排序 + 并查集,总之不会

T3题目传送门(洛谷P7795)

二分平均值(即答案)，然后将每个数减去mid，做前缀和操作，判断是否合法(字段和>=0)
代码:

T4题目传送门(洛谷P7794)

计算!

代码: