写在前面

第一题是签到题，其他都挺难的，都不会做，还是太菜了，欢迎各位大佬提供思路。

第一题

输入一个01矩阵，问有多少个 $2\times2$ 的子矩阵满足0的个数和1的个数相等，矩阵大小最大只有 $100\times100$，暴力即可。

第二题

输入一个长度为 $n$ 的字符串，删除尽可能少的元素，使得剩下的字符串不含长度为偶数的回文子串，回文子串是连续的一段子串。问最少删除多少个元素。$1\le n\le10^5$。

思路：没有长度为偶数的回文子串，说明不存在相邻的相同字符。因为长度为偶数的回文子串中，中心两侧的字符是相同的。扫描一遍，把相邻的相同字符都删掉即可。

第三题

输入一个 $1\sim n$ 的排列，其中有的元素是红色，有的是白色。每次操作可以交换任意两个红色元素的位置，问最少操作多少次使得数组变成升序，如果无解，输出 $-1$。
第一行输入 $n$，第二行输入这个排列，第三行输入一行字符串，W表示白色，R表示红色。$1\le n\le10^5$

思路：排序，白色的位置不能变，如果变了，就无解。如果有解，那么红色的每个元素的位置就是确定的。若干个元素构成一个环，只会做环内的交换，一共有若干个环，每个环的环长减一，然后求和就是答案。

第四题

定义一个字符串的权值为字符串长度乘以字符的种类数。给定一个长度为 $n$ 的字符串，希望你将该字符串切割成若干个连续子串，使得每个子串的权值不小于 $k$。求出最终最多可以切割多少个子串。$1\le k,n\le10^{18}$
第一行输入 $n$ 和 $k$，第二行输入字符串，形式如 $a(2)b(2)a(3)$，表示两个 $a$ 两个 $b$ 三个 $a$。保证只有小写字母。如果整个字符串权值都小于 $k$，输出 $-1$。

思路：贪心

第五题

给定一棵树，最多 $2\times10^5$ 个节点，最多 $2\times10^5$ 次询问，每次询问两个节点 $s$ 和 $t$，从 $s$ 出发，每次随机选择一条之前没走过的边，问到 $t$ 的概率是多少。询问之间是独立的。
对于概率 $\dfrac{a}{b}$，$a,b$ 互质，输出整数 $x$ 使得 $b\times x\equiv a\mod 10^9+7$

思路：tarjan求LCA，树形DP