![[码蹄杯]2025年题目学习](/images/banner7.webp)
括号序列
唐僧师徒途经一座神秘的古庙，庙前刻着一行字：“欲往决赛，需解此阵！” 小码哥自告奋勇上前查看，发现地上刻着一串由“(”和“)”括号组成的符号（长度为偶数），显然是某种法阵，但次序混乱，使得灵气无法流转。 小码哥看了一眼，笑道：“这法阵应该是要变成一套匹配的符号，才能显现出通往西天的正确道路，但怎么判断是否匹配呢？” 悟空指着庙旁的一块石碑说道：“规则在这儿！这几种情况都可以递归地定义一个括号序列是匹配的: 1.空序列是匹配的。 2.若A和B都是匹配的，则AB是匹配的。 3.若A是匹配的，则(A)是匹配的。
但此法阵只能交换相邻两个符号的位置，那我们最少需要多少次才能使其完全匹配呢？ 小码哥摩拳擦掌：“交给我吧，我一定能算出来！”
输入格式:第一行一个整数 T(T< 10^6)，表示测试数据组数。对于每组测试数据:一行一个字符串，表示括号序列。数据保证，最终结果一定可以匹配。所有字符串长度之和不超过 10^6 输出格式:对于每组测试数据:输出一行一个整数，表示答案。
输入:
3 ()())( )( ()()
输出:
1 1 0
标签
找规律 括号匹配
解题思路
根据题目可以获得的信息有:
1.括号字符串是肯定可以匹配的，只是次序乱了 2.每次只能交换两个字符的位置
括号的特点:
匹配的括号: () , 不匹配的括号: )(, 也就是说如果不匹配，肯定是 ) 出现在 ( 的 前面。那么在判断需要移动几次的时候，肯定要依据 ( 来，才能得到正确的结果，因为不匹配时, ( 肯定是出现在不匹配字符串的后面的位置的。
通过分别统计(和)的数量（leftbracket 和 rightbracket），和字符串当前所在的位置，来判断需要移动几次。具体操作如下:
如果当前为
(, 并且当前已经有统计的 rightbracket, 那么可以把当前的(向前移动 rightbracket的数量的位置，完成一个括号的匹配，匹配完成后rightbracket–, 表示当前已经匹配完成了一个(。 如果没有 rightbracket, lefbracket++.如果当前为
), 并且当前已经有 leftbracket, 说明在其之前有(, 此时 leftbracket–即可，表明已经匹配了一个括号。如果没有, rightbracket++.
代码实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt(); //t组数据
while(t -- > 0) {
String str = sc.next(); //括号字符串
int leftBracket = 0; //左括号的数量
int rightBracket = 0; //右括号的数量
int ans = 0; //当前第t组的答案
for(int i = 0; i < str.length(); i++) {
if(str.charAt(i) == '(') { //当前为左括号
if(rightBracket > 0) { //右括号的数量不为0
ans += rightBracket; //答案 += 当前的右括号数量
rightBracket--; //减去一个右括号的数量（来表示当前左括号和右括号已经匹配）
}else {
leftBracket++; //右括号数量为0，说明无法匹配，记录当前的左括号
}
}else { //当前为右括号
if(leftBracket > 0) { //如果左括号数量大于0
leftBracket--; //使得左括号和右括号匹配，左括号--
}else {
rightBracket++; //无法匹配，增加右括号的数量
}
}
}
System.out.println(ans);
}
判断奇偶
唐僧师徒跋山涉水，终于来到了一座雄伟的石桥前，桥边站着一位神秘老者，拦住了他们的去路。“此桥乃通往决赛的关键之路，若想通过，需解开一道神秘考验。”老者捋着胡子说道。 小码哥自告奋勇上前询问：“请问前辈，是什么考验？” 老者点头道：“此考验涉及两组长度均为n神秘数列，分别称为‘天数列’a1~an和‘地数列’b1 ~ bn.每个数皆为正整数。” 他指了指桥上的一块石碑，上面刻着一道古老的公式：
((\sum_{i=1}^na_i)\times (\sum_{i=1}^nb_i))^{\sum_{i=1}^na_i}
“请判断，结果究竟是奇数还是偶数。若是奇数，请回答odd，若是偶数，则回答even。” 八戒挠了挠头：“小码哥，这道题可得交给你了！”
输入 输入格式： 第一行一个整数
n(1\le n\le 10^5)
第二行n个整数
a_1\sim a_n(1\le a_i\le 10^9)
第三行n个整数
b_1\sim b_n(1\le b_i\le 10^9)
输出格式： 一行一个字符串，表示答案。
样例 输入: 2 2 3 4 5
输出: odd
标签
数学 奇偶判断
解题思路
如果按照朴素的思想，使用pow()方法直接根据原公式计算，值会过大，导致溢出错误，不适用于int,long类型，需要考虑使用更大的BigDecimal, 十分不方便。
考虑更简单高效的方法：奇数和偶数的公式口诀
- 奇数 +- 奇数 = 偶数，偶数 +- 偶数 = 偶数;
- 奇数 +- 偶数 = 奇数, 偶数 +- 奇数 = 奇数。
- 奇数 × 奇数 = 奇数， 奇数 x 偶数 = 偶数
- 偶数 × 任意数 = 偶数
也就是说，和指数无关，只要底数是奇数，结果就是奇数，底数是偶数，结果就是偶数。所以，只需要判断
((\sum_{i=1}^na_i)\times (\sum_{i=1}^nb_i))
的奇偶性就行了。也就是说如果
\sum_{i=1}^na_i 和 \sum_{i=1}^nb_i 都是奇数，那么结果肯定是奇数，否则结果肯定是偶数
代码实现
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //t组数据
long tian = 0;
long di = 0;
for(int i = 0; i < n; i++) {
int tianNum = sc.nextInt();
tian += tianNum;
}
for(int i = 0; i < n; i++) {
int diNum = sc.nextInt();
di += diNum;
}
if(tian %2 == 1 && di %2 == 1) {
System.out.println("odd");
}else {
System.out.println("even");
}
寻找出口
唐僧师徒行至一片荒山野岭，四周弥漫着诡异的白雾。突然，一阵阴风袭来，众人只觉眼前一花，便发现自己身处一个错综复杂的二维迷宫中。“糟了！是妖怪的迷踪阵！” 八戒惊慌失措地说，“我们该怎么出去？” 小码哥定睛一看，壁上刻着一串神秘的、由U、D、L、R组成的指令符号 s s，似乎指引着正确的出路。他发现，自己现在所在的初始位置为 (0, 0)，只要按照这些指令行走，就能找到离开的出口。规则如下：
U：坐标变成(x,y+1)。 D：坐标变成(x,y-1)。 L：坐标变成(x-1,y)。 R：坐标变成(x+1,y)。 “师父，快让小码哥算算，出口最终的坐标到底在哪儿？” 八戒着急地说道。
样例
输入 一行一个字符串s，保证字符串仅包含U,D,L,R四种字符，字符串长度不超过 10^5
输出 一行两个整数x,y，表示最终的出口坐标。
标签
字符串
解题思路
初始化x和y为0，根据当前字符串的内容增减对应的x,y即可
代码实现
Scanner sc = new Scanner(System.in);
String str = sc.next();
int x = 0;
int y = 0;
for(int i =0; i < str.length(); i++) {
if(str.charAt(i) == 'U') {
y+=1;
}else if(str.charAt(i) == 'D') {
y-=1;
}else if(str.charAt(i) == 'L') {
x-=1;
}else if(str.charAt(i) == 'R') {
x+=1;
}
计算灵力值
唐僧师徒行至一座荒山，忽然狂风大作，天空瞬间阴云密布。悟空警觉地握紧金箍棒，低声道：“师父，妖气冲天，怕是白骨精又来了！” 果然，不远处一片白雾翻腾，白骨精变幻身形，施展妖法，召唤出一列神秘的魂骨灵珠。灵珠共有n颗，并按顺序从1到n编号，每颗上都刻着一个整数a1,a2,… an, 其中蕴含着不同的灵力。 老妖阴笑道：“此阵乃我精心布下，若想破阵，你们需从中夺取足够的灵力，否则便永远留在此地！” 小码哥挺身而出，仔细研究这些灵珠，发现可以进行如下操作： 1.若选择编号为偶数的灵珠，可将其收走，并将灵珠上的数值加到灵力值中，然后灵珠会消失。 2.若选择编号为奇数的灵珠，可将其销毁，但灵力值不变。 3.每当销毁或收走一颗灵珠，剩下的灵珠会按照从左到右的顺序重新从1开始编号。 现在，小码哥的初始灵力值为0，他可以进行任意次数操作，但只有获得最高的灵力值，才能助师徒四人成功破阵！ 悟空皱眉道：“这妖法好阴险，得想个最佳策略才行。小码哥，快算算最多的灵力是多少吧！”
输入格式 第一行一个整数 T( 1 ≤ T ≤ 10^6)，表示测试数据组数。对于每组测试数据:第一行一个整数 n(1 ≤n≤ 10^6 )。第二行 n 个整数 a1 ~ an(-10^9 < ai < 10^9 ) 数据保证所有组的n的和不超过 10^6
输出格式： 对于每组测试数据，输出一行一个整数，表示答案。
样例 输入: 1 3 1 2 3
输出: 5
标签
找规律
解题思路
根据操作： 1.若选择编号为偶数的灵珠，可将其收走，并将灵珠上的数值加到灵力值中，然后灵珠会消失。 2.若选择编号为奇数的灵珠，可将其销毁，但灵力值不变。 3.每当销毁或收走一颗灵珠，剩下的灵珠会按照从左到右的顺序重新从1开始编号。
可以发现除了数组中的第一个数之外，所有的数都是可以取到的。但是需要注意的是需要求最多灵力值，也就是说<=0的数不需要。
代码实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0) {
int n = sc.nextInt();
int num1 = sc.nextInt(); //数列中的第一个数，不需要
long ans = 0;
for(int i = 2; i <= n; i++) {
int num = sc.nextInt(); //从第二个数开始，都可以获得
if(num > 0) { //只要>0的
ans += num;
}
}
System.out.println(ans);
}
}
最小公倍数
唐僧师徒一路西行，忽然狂风大作，烈焰冲天，四周温度骤然上升！沙僧低声道：“师父，妖气冲天，怕是红孩儿来了！”果然，前方火光四射，一个身穿红衣的孩童踏火而来，正是红孩儿！他大笑道：“想要活着过此地？必须先接下我的三昧真火试炼！” 话音未落，天空中浮现出n团炽热的火焰，每团火焰都有一个独立燃烧周期 a1, a2 … an, 表示它们在经过该时间后会重新燃起，形成不灭的循环！ 红孩儿冷笑道：“这些火焰不会自行熄灭，只有找到一个它们共同的熄灭时刻，才能让它们同时熄灭！” 沙僧皱眉道：“这妖火威力无穷，若不及时熄灭，我们怕是难以抵挡。” 红孩儿继续冷笑道：“即便你算得出结果，还需要对998244353取模，否则火焰依旧不灭！” 沙僧擦了擦额头的汗：“小码哥，咱们的生死可全指望你了，快算算共同熄灭的时刻吧！”
输入格式:第一行一个整数 n(1 ≤ n ≤ 10^4)第二行 n 个整数 a1 ~ an(1 ≤ ai≤ 10^9 ) 输出格式:一行一个整数，表示答案。
样例 输入 2 1 2
输出 2
标签
数学 gcd(最大公约数) lcm(最小公倍数)
解题思路
需要找到一个「所有火焰都完成了整数个周期，刚好再次重合到最初状态」的时间，也就是所有火焰周期的最小公倍数。 最小公倍数：
\text{lcm}(x, y) = \frac{x \times y}{\gcd(x, y)}
由于需要求多个数的最小公倍数，所以需要依次进行
\text{lcm}(a_1, a_2, a_3) = lcm(lcm(a_1, a_2), a_3), \ldots
由于周期值可能很大 ，且 LCM 会更大），我们需要注意溢出问题。 使用 BigInteger 最稳妥，因为 Java 的 BigInteger 内置 gcd、乘法、除法，且支持任意大整数。
代码实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
BigInteger mod = BigInteger.valueOf(998244353);
BigInteger lcm = BigInteger.ONE; //最开始的llm
for(int i = 0; i < n; i++) {
BigInteger num = sc.nextBigInteger();
lcm = lcm(lcm, num); //得到每次的最小公倍数
}
lcm = lcm.mod(mod);
System.out.println(lcm);
}
public static BigInteger lcm(BigInteger a, BigInteger b) {
return a.multiply(b).divide(a.gcd(b)); // lcm = a * b / gcd(a,b)
}
lowbit神功
唐僧师徒继续赶路，途经一座仙山，此山乃仙人所居，传闻山中藏有一门神秘仙法，修得此术者，能法力大增。
仙人传授的lowbit神功，其奥义如下：
lowbit(x) 代表x在二进制表示中，最低位的 1 以及其后所有的 0 组成的数。例如： lowbit(6(10)) = lowbit(110(2)) = 10(2)
仙人见唐僧一行人路过，决定考验他们。仙人给出了一份法力序列，包含 n 个正整数 a1 ~ an, 并要求进行q次操作，每次操作可能是以下两种之一：
1.法力精进：对法力序列中的所有元素a施展lowbit神功，变为a+lowbit(a)，以此提升法力。 2.法力汇总：将当前所有元素相加，询问总和，但因天庭的计算规则，过大的结果必须对 998244353 取模，避免引发天劫。 每进行一次操作2，需要计算出一次正确答案，最后便可通过该试炼，修成法术，助力冲击总决赛。
听完规则后，小码哥自告奋勇道：“让我来试一试！”
格式 输入格式： 第一行两个整数n,q(1≤n,q≤10^6)。 第二行n个正整数
a1 ∼an (1 ≤ ai ≤10^9)。 接下来q行，每行一个整数opt(opt∈[1,2])，表示对应的操作。
输出格式： 对于每个操作2，输出一行一个整数，表示答案。
样例
输入 3 3 1 2 3 2 1 2
输出 6 10
标签
lowbit 位运算
解题思路
什么是lowbit, 如何通过位运算实现lowbit lowbit(x) 表示 x 二进制表示中最低位的 1 以及其后面的 0 组成的值，也可以理解为「最低位的 1 对应的权值」。
比如：𝑥=6 二进制：110
lowbit(6) = 2（二进制的 10）
为什么是 x & -x
补码知识 在计算机里，负数 是用 补码 表示的： −x=∼x+1 即「按位取反」后再「加 1」。
举个例子 例子：x = 12 二进制：1100
取反（按位取反）：0011
加 1：0100
得到：−12=0100
1100 (12) & 0100 (-12) 等于 0100 => 4, 也就是 12 的 lowbit 是 4。
例子：x = 10 二进制：1010
取反：0101
加 1：0110
1010 & 0110 等于 0010 => 2，lowbit(10) = 2。
为什么这样得到「最低位的 1」？
从补码原理来看：
对于一个整数 x，x−1 会把 x 的「最后一个 1」变成 0，并把它后面所有的 0 变成 1。
所以 −x（即 x+1）刚好保留了最后一个 1 所在的位置。
当你把 x 和 −x 按位与时，只会留下「最低位的 1」对应的那一位，其它位都为 0。
直接暴力遍历整个数组，每次操作1都更新所有 a[i]，会 超时（因为 n、q 都可达 1e6）。 所以我们优化成下面这种结构：
| 类别 | 操作策略 |
|---|---|
| 是 2 的幂的数（例如 1,2,4,8） | lowbit(x) == x，所以每次加倍（x += x） |
| 其他数 | 每次只能逐步 + lowbit(x)，直到它们变成 2 的幂 |
变量解释
public static int MOD = 998244353; // 模数
public static List<Integer> arr = new ArrayList<>(); // 存放“非2的幂”的数
在 main 函数中： 初始数据统计：
long sumA = 0, sumB = 0, sumBlb = 0;
| 变量 | 含义 |
|---|---|
sumA | 当前所有 是2的幂 的数的总和 |
sumB | 当前所有 非2的幂 的数的总和 |
sumBlb | 所有 非2的幂 数的 lowbit(x) 总和（也就是下一轮 +lowbit(x) 后增长多少） |
arr | 当前仍然是“非2的幂”的数（我们将逐步追踪它们，直到它们变成 2 的幂） |
处理每次操作
操作 1：施展 lowbit 神功
if (opt == 1) {
ans = ((sumA + sumBlb) % MOD + ans) % MOD; // 更新总和
sumA = (sumA * 2) % MOD; // 所有 2 的幂 *2
解释：
sumA + sumBlb 表示所有数中，这一轮增加的量（sumA 变为 2 倍，非2的幂每个加 lowbit）
然后逐个处理 arr（非2的幂的数）：
核心处理逻辑：
for (int i = arr.size() - 1; i >= 0; i--) {
int num = arr.get(i);
int lb = lowbit(num);
int newNum = num + lb;
int newlb = lowbit(newNum);
我们对每个数进行 +lowbit(num) 操作
然后检查它是不是已经变成 2 的幂了
是 2 的幂：
if (isPower(newNum)) {
sumA = (sumA + newNum) % MOD; // 加入 sumA
sumB = (sumB - num + MOD) % MOD; // 从 sumB 移除
sumBlb = (sumBlb - lb + MOD) % MOD; // 从 sumBlb 移除
Collections.swap(arr, i, arr.size() - 1); // swap后移除（避免O(n)删除）
arr.remove(arr.size() - 1);
}
还不是 2 的幂：
else {
sumB = (sumB - num + newNum + MOD) % MOD; // 用 newNum 替代旧值
sumBlb = (sumBlb - lb + newlb + MOD) % MOD; // 更新对应 lowbit 值
arr.set(i, newNum); // 更新 arr[i]
}
操作 2：直接输出当前总和
else {
System.out.println(ans % MOD);
}
辅助函数 lowbit(int x)：
return x & (-x);
获取 x 的最低位 1 所代表的值
isPower(int x)：
return (x & (x - 1)) == 0;
判断是否是 2 的幂（只有一个 1）
代码实现(详细注释)
public static int MOD = 998244353;
public static List<Integer> arr = new ArrayList<>(); //用来存非2的幂的数
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //数字
int q = sc.nextInt(); //操作
int[] nums = new int[n]; //用来存 n个正整数
for(int i =0 ; i <n; i++) {
nums[i] = sc.nextInt();
}
long sumA = 0, sumB =0, sumBlb = 0;
//sumA用来存2的幂，因为2的幂的lowbit数等于它本身
//sumB用来存所有非2的幂的数
//sumBlb用来存所有非2的幂的数 + lowbit 之后的值
for(int i =0; i < n; i++) {
if(isPower(nums[i])) { //如果这个数是2的幂
sumA = (sumA + nums[i]) % MOD; // sumA加上这个数
}else {
arr.add(nums[i]); //加入集合
sumB = (sumB + nums[i]) % MOD; // sumB加上这个数
sumBlb = (sumBlb + lowbit(nums[i])) % MOD;
}
}
long ans = (sumA + sumB) % MOD; //初始，还没有进行过lowbit, = sumA + sumB
while(q-- > 0) {
int opt = sc.nextInt();
if(opt == 1) { //操作1 ： 所有的num 变为 num + lowbit(num)
// 原始 sumB 的值已经包含在 ans 里了（一开始 ans = sumA + sumB),
// 每次操作1，只需要加上新增的变化量：sumA（2 的幂翻倍）+ sumBlb（非2的幂加 lowbit）
ans = ((sumA + sumBlb) % MOD + ans) % MOD;
sumA = (sumA * 2) % MOD; //更新sumA的值
for(int i = arr.size() - 1; i >=0; i--) {
int num = arr.get(i);
int lb = lowbit(num);
int newNum = num + lb; //得到新的非2的幂的数 + lowbit的和
int newlb = lowbit(newNum); //新的数的lowbit的值
if(isPower(newNum)) { //如果新的数是2的幂，把其加入到sumA(存2的幂的数之和的部分)， 从非2的幂值和的sumB, sumBlb和 arr里将当前num移除
sumA = (sumA + newNum) % MOD; //把其加入到sumA，
sumB = (sumB - num + MOD) % MOD; //从非2的幂值的数 num 从 sumB里移除
sumBlb = (sumBlb - lb + MOD) % MOD; //从sumBlb里将 非2的幂值的数 num 的lowbit 从 sumB + lb 的和里移除
Collections.swap(arr, i, arr.size() - 1); // 从arr里移除 num, 先交换到最后一个位置再移除
arr.remove(arr.size() - 1);
}else {
sumB = (sumB - num + newNum + MOD) % MOD; //不是，更新num 为 newNum
sumBlb = (sumBlb - lb + newlb + MOD) % MOD; //更新 lb 为 newlb
arr.set(i, newNum); //把newNum 放到原来 num的位置进行更新
}
}
}else {
System.out.println(ans % MOD); //操作二直接输出答案，简化代码
}
}
}
public static int lowbit(int x) { //一个数 lowbit 计算后的值
return x & (-x);
}
public static boolean isPower(int x) { //判断是否是2的幂 4 = 2^2, 2 = 2^1;
return (x & (x - 1)) == 0;
}
拯救圣莲池2
圣莲池修复后不久，唐僧师徒正欲出城赶路，国王大使却匆匆赶来道：“圣僧留步，圣莲池又不行了，还望各位能再次出手相救啊！” 重返圣莲池，小码哥发现，池中依然有n朵圣莲，每朵圣莲都蕴含着一丝残存的灵力，灵力值均是正整数，分别为
a_1，a_2，…，a_n可是祭坛铭文发生了变化。要让圣莲池恢复生机，依然要进k次净化仪式，但每次净化的步骤有了少许改变： 1.吸收灵力：选择灵力最强的圣莲，将其灵力值吸收并加入恢复之力（初始恢复之力为0）。 2.莲花枯萎或再生：若选中的圣莲灵力值仅剩 1，则彻底枯萎消失；否则，该圣莲的灵力衰减 1，继续存在于池中。 小码哥自信满满地说：“别急，让我再来算算，这下经过k次仪式后积攒了多少恢复之力！”
格式
输入格式：
第一行两个整数n,k(1\le n\le 3\times 10^5,1\le k\le 10^9)
第二行n个正整数a_1\sim a_n(1\le a_i\le 10^9,\sum_{i=1}^na_i\ge k)
输出格式： 一行一个整数，表示答案。
样例:
输入 3 4 1 2 3
输出 8
标签
二分 数学 等差数列
解题思路
暴力解法会导致超时。这里使用二分+数学计算的方法
具体思路为：先对所有莲花进行从小到大的排序，使用二分的方法找到一个临界值。从这个临界值到最大值，吸取的所有的灵力刚好足够进行K次操作，那么就找到了最大的答案，同时优化了程序的复杂度，
逐步实现
检查函数，用于在二分查找的过程中进行判断。target为当前二分找到的值。
cnt += nums[i] - target + 1;用于计算得到当前灵力值的莲花够不够使用k次。
public static boolean check(int[] nums, long target, long k) { //用于找到用于计算灵力值开始的最小值
long cnt = 0;
for(int i =0 ;i < nums.length; i++) {
if(nums[i] >= target) {
cnt += nums[i] - target + 1; //得到可以用于计算灵力值数字的个数
}
}
return cnt >= k; //如果这个个数大于等于K， 就说明可以使用left作为最小值
}
二分实现，找到合适的起始位置
long left = 0, right = 1_000_000_000_0l;
while(left + 1 != right) { //可以看做找一个最小值，取到一段从大到该最小值的数列完成计算灵力值
long mid = (right - left) / 2 + left;
if(check(nums, mid, k)) { //用于找到合适的位置
left = mid;
}else {
right = mid;
}
}
实现灵力值的计算部分，通过等差数列求和快速计算
\text{和} = \text{个数} \times \frac{\text{首项 + 末项}}{2}
比如：莲花 = 7，left = 4 ⇒ 需要取出：7 + 6 + 5
个数 = 3
和 = (7 + 5) * 3 / 2 = 18
k -= (nums[i] - left)：这些取出来的已经贡献给了操作次数，k 要相应减少
为什么还要有第二段：
因为我们只取到 left + 1 为止，还没处理 == left 的这部分！
但 k 次操作还没用完，所以我们要继续：
让能“再取一个 left 值”的莲花各自贡献一次（直到 k 为 0）
举个完整例子说明： 假设：
nums = [7, 5, 4]
二分得出：left = 4
k = 6
第 1 段处理： 7：7 → 6 → 5 （贡献：7+6+5 = 18），取了 3 次，k = 3
5：5 → 4 （贡献：5+4 = 9），取了 2 次，k = 1
4: 没处理
s = 18 + 9 = 27，k = 1（还剩 1 次）
第 2 段处理： 现在从头遍历，找到能提供 4 的莲花：
7 还能再提供一次 4 → s += 4，k = 0
最终 s = 31
long s = 0;
for(int i = 0; i < n; i++) {
if(nums[i] >= left + 1) { //当前数比left+1大，可以用于计算灵力值
//等差数列求和公式，求当前的数到达left，之间总的灵力值之和
s += (nums[i] - left) * (left + 1 + nums[i]) / 2;
//从k中扣除对应的次数
k -= (nums[i] - left);
}
}
//到达==left 时
for(int i = 0; i < n && k >0; i++) {
//如果当前的数能加入灵力值
if(nums[i] >= left) {
s += left; //把left加入总灵力值
k--; //减少次数
}
}
完整代码实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long k = sc.nextLong();
int[] nums = new int[n];
for(int i =0; i < n; i++) {
nums[i] = sc.nextInt();
}
long left = 0, right = 1_000_000_000_0l;
while(left + 1 != right) { //可以看做找一个最小值，取到一段从大到该最小值的数列完成计算灵力值
long mid = (right - left) / 2 + left;
if(check(nums, mid, k)) { //用于找到合适的位置
left = mid;
}else {
right = mid;
}
}
long s = 0;
for(int i = 0; i < n; i++) {
if(nums[i] >= left + 1) { //当前数比left+1打，可以用于计算灵力值
//等差数列求和公式，求当前的数到达left，之间总的灵力值之和
s += (nums[i] - left) * (left + 1 + nums[i]) / 2;
//从k中扣除对应的次数
k -= (nums[i] - left);
}
}
//到达==left 时
for(int i = 0; i < n && k >0; i++) {
//如果当前的数能加入灵力值
if(nums[i] >= left) {
s += left; //把left加入总灵力值
k--; //减少次数
}
}
System.out.println(s);
sc.close();
}
public static boolean check(int[] nums, long target, long k) { //用于找到用于计算灵力值开始的最小值
long cnt = 0;
for(int i =0 ;i < nums.length; i++) {
if(nums[i] >= target) {
cnt += nums[i] - target + 1; //得到可以用于计算灵力值数字的个数
}
}
return cnt >= k; //如果这个个数大于等于K， 就说明可以使用left作为最小值
}
符文方阵
话说唐僧师徒行至金光岭，忽见山巅有无数阵旗迎风而立。每面阵旗对应一个m行m列的符文方阵，共有n个这样的方阵a1~an。每个方阵中，第i+1行第j+1列的符文记为ai,j，其中 0 <= j, j < m。
破解此阵需用融合之法，规则类似于矩阵乘法，只不过每个元素需要取模，具体规则如下：若有两个m行m列的方阵p,q，则得到的新方阵c = f(p,q) 也是m行m列的方阵，其中
c_{i,j}=(\sum_{k=0}^{m-1}p_{i,k}\times q_{k,j})\space mod\space 2现在，小码哥需按顺序融合完所有方阵，便可破阵通过！那么，小码哥应该如何计算
f(a_1,f(a_2,f(a_3,…f(a_{n-1},a_n))))
格式 输入格式：
第一行两个整数n,m(2\le n\le 50,1\le m\le 50)
输出格式： 输出m行，每行m个整数，表示最终结果。
样例 1 输入： 2 3 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 0 0
输出： 1 1 1 0 1 1 1 0 0
标签
数学 矩阵乘法
解题思路
使用三维数组可以很方便的实现存储n个m x m的矩阵。在矩阵合并部分，要注意从后向前，矩阵计算的顺序。
逐步实现
构造单位矩阵的目的，是为了方便我们从最后一个矩阵开始往前“融合”，模拟这个嵌套融合结构：
f(a1, f(a2, f(a3, ..., f(an-1, an)...)))
而在编程中，我们无法直接“从最里层往外”写递归，就用一个技巧：
把融合顺序改为从最后一个往前乘（矩阵是有序的）：
res = an
res = an-1 × res
res = an-2 × res
...
res = a1 × res
所以一开始我们写成：
int[][] res = 单位矩阵;
for (int i = n-1; i >= 0; i--) {
res = f(a[i], res);
}
造单位矩阵的目的是为了让第一次乘法是：
res = an × 单位矩阵 = an
这样融合的“结果矩阵”就可以从后往前逐步更新。
核心矩阵乘法部分
public static int[][] f(int[][] A, int[][] B) {
int[][] res = new int[A.length][B[0].length];
for(int i = 0; i < A.length; i++) { // 遍历 A 的行
for(int j = 0; j < B[0].length; j++) { // 遍历 B 的列
int temp = 0;
for(int k = 0; k < A.length; k++) { // 对当前行与列做“点乘”
temp += A[i][k] * B[k][j]; // 正常乘法
}
res[i][j] = temp % 2; // 最后模2
}
}
return res;
}
完整代码实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][][] arr = new int[n][m][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
for(int k = 0; k < m; k++) {
arr[i][j][k] = sc.nextInt();
}
}
}
int[][] res = new int[m][m];
for(int i = 0; i < m; i++) {
for(int j = 0; j < m; j++) {
if(i == j) {
res[i][j] = 1;
}
}
}
//进行矩阵融合操作
for(int i = n -1; i >= 0; i--) {
res = fushion(arr[i], res); //注意这里进行运算的两个矩阵放入函数中的顺序
}
show(res);
sc.close();
}
public static int[][] fushion(int[][] p, int[][] q) {
int[][] res = new int[p.length][q[0].length]; //对应p的行数和q的列数
for(int i = 0; i < p.length; i++) {
for(int j = 0; j < q[0].length; j++) {
for(int k = 0; k < p.length; k++) {
res[i][j] += (p[i][k] * q[k][j]);
}
res[i][j] %= 2;
}
}
return res;
}
public static void show(int[][] arr) {
for(int i = 0; i < arr.length; i++) {
for(int j = 0 ; j < arr[0].length; j++) {
if(j < arr[0].length - 1) {
System.out.print(arr[i][j]+" ");
}else {
System.out.println(arr[i][j]);
}
}
}
}
移动数组
通往决赛最后一关，唐僧师徒来到了盘丝洞，被七位蜘蛛精困住。蜘蛛精们决定考验考验师徒几人的智慧。他们指着洞壁上刻的一行文字说：“欲出此洞，需解此谜。” 小码哥定睛一看，洞壁上显示着一个长度为n的整数序列a1
an，旁边还附有一个长度为q的操作序列 b1bq 。 蜘蛛精说道：“若想让此洞之门大开，你需按照数组b从b1到bq的顺序对数组a进行操作。若bi = 1，将序列a的开头元素移至最后；若bi=2，将序列a的结尾元素移至开头。经过q次操作后，序列a将呈现出何种姿态？若你能解开此谜，将每一个位置的值正确告知于我，你们便可重获自由，离开这盘丝洞。” 小码哥看着洞壁上的数字序列，陷入了沉思…
格式 第一行两个整数
n,q(1\le n,q\le 10^6)
第二行n个整数
a_1\sim a_n(1\le a_i\le 10^9)
第三行q个整数
b_1\sim b_q(1\le b_i\le2 )
输出格式： 一行n个整数，表示最终的a1~an。
样例
输入 3 1 1 2 3 1
输出 2 3 1
标签
数组 循环数组偏移模拟
解题思路
朴素的想法是使用一个双端队列，通过移除/添加首尾元素实现操作。但是这种方法的时间复杂度较高O(q + n)， 每次都要对链表进行修改，会导致超时。正确的实现思路为：设置一个偏移量用来表示当前数组的整体偏移位置，在进行操作时只需要更改偏移量，输出时对原数组下标进行偏移处理即可得到正确的答案。
逐步实现
偏移操作，左移，因为是第一个元素移动到末尾，看作其他的元素像左移动了一位，右移同理
int offset = 0;
for(int i = 0; i < q; i++) {
int op = sc.nextInt();
if(op == 1) {
//左移，偏移-1， +n 是为了防止出现负数，%n是为了不超出总元素个数
offset = (offset - 1 + n) % n;
} else {
//右移，偏移+1
offset = (offset + 1) % n;
}
}
offset表示最后整体向右需要偏移多少位才能得到正确的答案。所以这里需要用i - offset来得到合适的下标。这里使用StirngBuilder先构建字符串再输出，避免了输出超时。
// 使用 StringBuilder 来避免输出超时
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++) {
//原下标-偏移量
sb.append(a[(i - offset + n) % n]);
if(i != n - 1) sb.append(" ");
}
System.out.println(sb.toString());
完整代码
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int q = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int offset = 0;
for(int i = 0; i < q; i++) {
int op = sc.nextInt();
if(op == 1) {
//左移，偏移-1， +n 是为了防止出现负数，%n是为了不超出总元素个数
offset = (offset - 1 + n) % n;
} else {
//右移，偏移+1
offset = (offset + 1) % n;
}
}
// 使用 StringBuilder 来避免输出超时
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++) {
//原下标-偏移量
sb.append(a[(i - offset + n) % n]);
if(i != n - 1) sb.append(" ");
}
System.out.println(sb.toString());
sc.close();
}
最小值之和
街头，杨志正为卖祖传宝刀一筹莫展。恶霸牛二想霸占杨志的宝刀，于是百般刁难。
牛二拿出一串长度为n的整数序列a1
an, 定义一个函数f(i,j), 表示序列aiaj的最小值。接着，牛二要求小码妹说道：“若你能计算出\sum_{i=1}^{n} \sum_{j=i}^{n} f(i, j)的值，我便买下这把宝刀。”小码妹胸有成竹地回答道：“此乃小技耳，且看我如何破解。”她迅速写出一段代码，轻松计算出答案。
格式 输入格式：
第一行一个整数
n(1\le n \le 10^4)
输出格式： 一行一个整数，表示答案。
样例
输入 3 1 2 3
输出 10
解题思路
这道题没什么难点，唯一需要注意的就是如何计算
\sum_{i=1}^{n} \sum_{j=i}^{n} f(i, j)
可以看做一个双层循环
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
sum += f(i, j); // 先固定 i，再枚举所有 j ≥ i
}
}
完整代码
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long sum = 0;
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for(int i = 0; i < n; i++) {
int min = arr[i];
for(int j = i ; j < n; j++) {
min = Math.min(min, arr[j]);
sum += min;
}
}
System.out.println(sum);
sc.close();
}
哨岗逆序对
雪夜漫漫，林冲怀着满腔悲愤与无奈，顶风冒雪奔赴梁山，小码妹相伴同行。 二人历经艰辛，终于抵达梁山脚下。此时，梁山的一位哨头告知小码妹，梁山各哨岗的守卫力量可排成一个长度n的正整数序列a1~an, 每个数代表哨岗的守卫强度。
哨头要小码妹算出，在这些哨岗中，有多少组哨岗对（i, j)(1 <= i, j <= n) ，满足第i个哨岗的守卫强度大于第j个哨岗，即ai > aj,算出的数对数量需对 100取模。
格式 输入格式： 第一行一个整数n ( 1 <= n <= 3 x 10 ^ 5) 第二行n个整数a1~an(1 <= ai <= 100)
输出格式： 一行一个整数，表示答案。
样例 输入 3 3 2 1
输出 3
标签
归并排序 桶排序
解题思路
不能暴力循环，这样子会超出数据范围。
可以考虑的方式有归并排序，在排序过程中遇到i < j 且 ai > aj就进行统计。
或是采用桶排序中的计数思想：题目中数字的范围很小，1-100。通过一个数组来计算数字出现的频率。每次统计 当前数 之前出现在其之前出现过的， 比它大的数字。（注意每次统计完后要在数组中加上当前统计了的数字）
关键步骤
归并排序
// 合并两个有序数组，并统计逆序对
static long merge(int[] arr, int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
long count = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
// arr[i] > arr[j]，说明 [i, mid] 的所有元素都比 arr[j] 大
count += (mid - i + 1);
temp[k++] = arr[j++];
}
}
在排序操作时，如果遇到 i < j 且 arr[i] > arr[j] 的情况时，进行逆序对的统计
计数法
int[] arr = new int[101]; //频率数组/桶 初始化全为0
int ans = 0; //逆序对计数器
int mod = 100;
for(int i = 0; i <n; i++) {
int cur = sc.nextInt(); //读取当前数字
// 内循环： 查找逆序对 查找cur之前有多少大于它的数
for(int j = cur + 1; j <= 100; j++) {
ans = (ans + arr[j]) % mod;
}
//更新频率数组，没有就+1
arr[cur]++;
}
arr 数组用于统计数的个数。for(int j = cur + 1; j <= 100; j++)， 遍历比cur 大的数， 把arr数组中统计到的数作为答案加入ans。
理解为arr存的是在cur这个数之前其他数的情况，如果在其之前存在比cur大的数，那么说明找到了一个逆序对。arr[cur]++把当前的数存入统计频率数组中。
代码实现
归并排序
static final int MOD = 100;
static int[] temp; // 辅助数组
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
temp = new int[n]; // 初始化辅助数组
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
long result = mergeSort(arr, 0, n - 1);
System.out.println(result % MOD);
}
// 归并排序，同时统计逆序对
static long mergeSort(int[] arr, int left, int right) {
if (left >= right) return 0;
int mid = (left + right) / 2;
long count = 0;
count += mergeSort(arr, left, mid);
count += mergeSort(arr, mid + 1, right);
count += merge(arr, left, mid, right);
return count;
}
// 合并两个有序数组，并统计逆序对
static long merge(int[] arr, int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
long count = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
// arr[i] > arr[j]，说明 [i, mid] 的所有元素都比 arr[j] 大
count += (mid - i + 1);
temp[k++] = arr[j++];
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
// 拷贝回原数组
for (int t = left; t <= right; t++) {
arr[t] = temp[t];
}
return count;
}
桶排序计数法
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[101]; //频率数组/桶 初始化全为0
int ans = 0; //逆序对计数器
int mod = 100;
for(int i = 0; i <n; i++) {
int cur = sc.nextInt(); //读取当前数字
// 内循环： 查找逆序对 查找cur之前有多少大于它的数
for(int j = cur + 1; j <= 100; j++) {
ans = (ans + arr[j]) % mod;
}
//更新频率数组，没有就+1
arr[cur]++;
}
System.out.println(ans);
sc.close();
}
开启密码
烈日高悬，黄泥冈气氛燥热。吴用等人智取生辰纲，然而，生辰纲却被一把神秘的锁具锁住，唯有解开密码方能开启。 据可靠消息，密码线索藏在一个长度为n的整数序列a1~an中，小码妹必须要找出其中出现次数最多的数字，若有多个答案，就按从小到大的顺序排列出来，只有这样才能成功开启生辰纲。
输入格式： 第一行一个整数n(1 <= n <= 3*10^5) 第二行n个整数a1~an(1 <= ai <= 10^9)
输出格式： 输出若干行，每行一个整数，表示出现次数最多的整数（需要从小到大输出）。
样例 1 输入 3 1 1 1
输出：1
样例2 输入 3 1 2 3
输出： 1 2 3
样例3 输入 3 21 21 12
输出 21
标签
HashMap 排序
解题思路
考虑到数的大小，不能使用桶计数法，会超出数组范围。转而考虑使用HashMap来实现计数，这道题主要考察对于HashMap的使用
详细实现
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>(); //使用HashMap统计数和出现的个数
for(int i = 0; i < n; i++) {
int num = sc.nextInt();
map.put(num, map.getOrDefault(num, 0)+1); //注意这个getorDefault方法
}
注意，这里使用的统计方法map.getOrDefault(num, 0)+1, 这样可以轻松的实现统计对应的数的出现个数
int maxFreq = 0;
for(int count: map.values()) { //得到出现的最大频率
if(count > maxFreq) {
maxFreq = count;
}
}
List<Integer> result = new ArrayList<Integer>(); //答案数组
for(Map.Entry<Integer, Integer> entry: map.entrySet()) {
if(entry.getValue() == maxFreq) { //如果map中有数的统计频率和maxfreq中的一样，加入答案数组中
result.add(entry.getKey());
}
}
Collections.sort(result); //对其进行从小到大排序
得到最大频率，统计出现次数等于最大个数的数，注意这里使用的map.entrySet()直接获取到map的keyset()和valueset()方便后续操作
完整实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>(); //使用HashMap统计数和出现的个数
for(int i = 0; i < n; i++) {
int num = sc.nextInt();
map.put(num, map.getOrDefault(num, 0)+1); //注意这个getorDefault方法
}
int maxFreq = 0;
for(int count: map.values()) { //得到出现的最大频率
if(count > maxFreq) {
maxFreq = count;
}
}
List<Integer> result = new ArrayList<Integer>(); //答案数组
for(Map.Entry<Integer, Integer> entry: map.entrySet()) {
if(entry.getValue() == maxFreq) { //如果map中有数的统计频率和maxfreq中的一样，加入答案数组中
result.add(entry.getKey());
}
}
Collections.sort(result); //对其进行从小到大排序
for(int num: result) {
System.out.println(num);
}
sc.close();
}
不同子串
李逵在沂岭成功斩杀四虎，为母报仇后，满心悲怆准备归返梁山。 下山路中，他发现一块巨石上刻着一串奇怪的符号，全是由小写英文字母组成。传言，谁能算出它有多少个本质不同的子串，就能获得指引或特殊机缘。李逵对这等烧脑之事毫无头绪。李逵向小码妹求助：“妹子，俺虽有力气打虎，可这玩意儿实在看不懂。你帮俺算算，若真能得个啥好处，也算没白跑这一趟！”小码妹说道这有何难。
输入格式： 一行一个长度不超过 200 200的字符串。
输出格式： 一行一个整数，表示答案。
样例
输入：abc
输出：6
解题思路
看到子串问题的第一反应是通过DFS遍历找到所有子串，但是题目中要求的是不同子串。子串是固定的，所以没有必要用DFS来做，使用for循环来找到子串，set来去重就足够了
代码实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int n = str.length();
Set<String> set = new HashSet<>();
for (int i = 0; i < n; i++) { //起始位置
StringBuilder sb = new StringBuilder();
for (int j = i; j < n; j++) { //找到子串的尾部位置
sb.append(str.charAt(j));
set.add(sb.toString());
}
}
System.out.println(set.size());
sc.close();
}
分配岗哨
施恩在快活林开了一家酒店，生意兴隆，但被恶霸蒋门神霸占。武松准备帮助施恩夺回快活林，但需要先解决一个难题：快活林周边有 n个哨岗 ，每个哨岗的坐标为(xi, yi)。为了确保战斗的胜利，小码妹需要将这些哨岗分配给武松和施恩，满足以下条件：
1.所有的哨岗必须被分配完。
2.如果两个哨岗属于同一方，它们之间的欧几里得距离必须大于d。
小码妹需要判断是否能够将n个哨岗分配完，并且满足上述条件，使得武松和施恩能够顺利夺回快活林。如果可以，输出YES；否则，输出NO。
定义：两个点（x1, y1）, (x2, y2)的欧几里得距离为
\sqrt{|x_1-x_2|^2+|y_1-y_2|^2}
输入格式 第一行一个整数T(1 <= T <= 1000), 表示测试数据组数
对于每组测试数据：
第一行两个整数n, d(1<=n, 且T数组里的n之和不超过1000, 即\sum n\le 1000，1\le d\le 10^9)
接下来n行，每行两个整数x,y(1 <= x, y <= 10^9),分别表示n个哨岗的坐标。
输出格式： 输出T行，分别表示每组测试数据的答案。
样例 1 输入 2 2 1 1 1 1 2 3 10 1 1 1 3 2 2
输出 YES NO
解题思路
把这道题看做一道二分图的问题。
什么是二分图：
在一个有向图 G=(V, E) 中，所有的顶点可以分成两个集合，使得所有的边全部都满足两边的顶点分别位于不同的集合。
为什么能看做二分图：题目中提到把所有节点分配给两人，若能完全分配，则为二分图。
具体如何看做二分图来实现：按照1，2，3的顺序来作为第一个节点，第二个节点，第三个节点。若两节点直接的欧氏距离满足要求<=d，则这两个节点(如 1,2 )就能连到一起(说明不属于同一方，方便后续染色处理)
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T -- > 0) {
int n = sc.nextInt();
long d= sc.nextInt();
long d2 = d * d; //得到用于比较的欧氏距离^2(避免开方)
point[] pointList = new point[n]; //存储每个节点
for(int i = 0; i < n; i++) {
long x = sc.nextLong();
long y = sc.nextLong();
pointList[i] = new point(x, y);
}
//用邻接矩阵来建图
ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
for(int i = 0 ; i < n; i++) {
graph.add(new ArrayList<Integer>());
}
for(int i = 0 ; i < n; i++) {
for(int j = i + 1; j < n; j++) {
long dx = pointList[i].x - pointList[j].x;
long dy = pointList[i].y - pointList[j].y;
long dist2 = dx * dx + dy * dy;
if( dist2 <= d2) { //如果距离 <= d, 就连接一条边
graph.get(i).add(j);
graph.get(j).add(i);
}
}
}
如何判断是否是二分图：进行染色处理，把每个节点相邻的节点染为不同的颜色，如果最后没有颜色冲突，说明能够成功二分。这里使用bfs实现。
public static boolean bfs(ArrayList<ArrayList<Integer>> graph, int[] color, int start) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(start); //加入第一个节点
color[start] = 1; //给第一个节点染色
while(!queue.isEmpty()) {
int cur = queue.poll();
for(int v: graph.get(cur)) {
if(color[v] == 0){ //相邻的节点还未染色
color[v] = -color[cur]; //染成和当前相反的颜色
queue.add(v);
} else {
if(color[v] == color[cur]) { //说明当前的颜色冲突了
return false;
}
}
}
}
return true;
}
完整代码
class Main {
static class point{
long x, y;
point(long x, long y){
this.x = x; this.y = y;
};
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T -- > 0) {
int n = sc.nextInt();
long d= sc.nextInt();
long d2 = d * d; //得到用于比较的欧氏距离^2(避免开方)
point[] pointList = new point[n]; //存储每个节点
for(int i = 0; i < n; i++) {
long x = sc.nextLong();
long y = sc.nextLong();
pointList[i] = new point(x, y);
}
//用邻接矩阵来建图
ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
for(int i = 0 ; i < n; i++) {
graph.add(new ArrayList<Integer>());
}
for(int i = 0 ; i < n; i++) {
for(int j = i + 1; j < n; j++) {
long dx = pointList[i].x - pointList[j].x;
long dy = pointList[i].y - pointList[j].y;
long dist2 = dx * dx + dy * dy;
if( dist2 <= d2) { //如果距离 <= d, 就连接一条边
graph.get(i).add(j);
graph.get(j).add(i);
}
}
}
int[] color = new int[n]; //对每个节点都进行染色， 0 ： 未染 1：红 2：蓝
boolean flag = true; //判断最后是否可以分配完
for(int i = 0; i < n; i++) {
if(color[i] == 0) { //从未染色的第一个节点开始
if(!bfs(graph, color, i)) { //如果有颜色冲突，说明不能给整张图成功染色
flag = false;
break;
}
}
}
System.out.println(flag ? "YES":"NO");
}
}
public static boolean bfs(ArrayList<ArrayList<Integer>> graph, int[] color, int start) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(start); //加入第一个节点
color[start] = 1; //给第一个节点染色
while(!queue.isEmpty()) {
int cur = queue.poll();
for(int v: graph.get(cur)) {
if(color[v] == 0){ //相邻的节点还未染色
color[v] = -color[cur]; //染成和当前相反的颜色
queue.add(v);
} else {
if(color[v] == color[cur]) { //说明当前的颜色冲突了
return false;
}
}
}
}
return true;
}
}
包含1的子串
李逵下山接母，行至山林深处，却被假扮他的李鬼拦住去路。李鬼自知武力不敌，便拿出一块木板，妄图以此刁难李逵和同行的小码妹。 木板上是一个仅含字符0和字符1的长度为n的字符串。李鬼宣称，若他们能求出有多少个子串满足该子串中至少包含1个字符1，便放他们通行。 小码妹想道，这不仅关乎能否摆脱李鬼的纠缠，更关系到李逵接母的行程。她对李逵说道：“交给我吧，我能解决！”
格式 输入格式：
第一行一个整数n(1\le n\le 3\times 10^4)
第二行一个长度为n的仅包含0和1的字符串。
输出格式： 一行一个整数，表示答案。
样例1： 输入: 2 10 输出:2
子串 数学
解题思路
如果采用传统的双循环，枚举所有子串，在时间上会超时。改为采用统计全零子串的方式。 这种方式的好处是：不需要双重for循环，while嵌套，找到全零区间的首尾索引即可统计出所有的零子串。使用总子串数-所有的零子串，即可得到所有的包含1的子串
代码解释
long total = (long)n * (n + 1) / 2; //子串个数 = n( n + 1) / 2
long zeroOnly = 0;
int i = 0;
while (i < n) {
if (str.charAt(i) == '0') {
int j = i;
while (j < n && str.charAt(j) == '0') j++;
int len = j - i; //得到这个全零的子串区间
zeroOnly += (long)len * (len + 1) / 2; //得到这个区间，全零子串的个数
i = j; //更新全零区间起始位置
} else {
i++;
}
}
一含有n个字符的字符串的子串数量 = n (n + 1) / 2。 同理，根据这个公式，我们知道零子串的长度就可以得到零子串的子串数量。
在while循环里，我们使用i 和 j 分别作为起始索引和终止索引，找到零区间的长度来计算全零子串，更新全零区间的起始位置
完整代码
//包含1的子串个数 = 总子串个数 - 全零的子串个数
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String str = sc.next();
long total = (long)n * (n + 1) / 2; //子串个数 = n( n + 1) / 2
long zeroOnly = 0;
int i = 0;
while (i < n) {
if (str.charAt(i) == '0') {
int j = i;
while (j < n && str.charAt(j) == '0') j++;
int len = j - i; //得到这个全零的子串区间
zeroOnly += (long)len * (len + 1) / 2; //得到这个区间，全零子串的个数
i = j; //更新全零区间起始位置
} else {
i++;
}
}
System.out.println(total - zeroOnly);
sc.close();
铺砖块
江州城内，宋江、戴宗即将被押赴法场，梁山泊好汉们精心筹备劫法场行动。 法场附近有一处隐蔽的藏身之所，是个长为a、宽为b的房间，好汉们计划在此提前布置。小码妹需要为这个房间铺满特殊的砖块，以便更好地隐藏和准备武器等物资。已知砖块长度为正整数，可以用不同的砖块来铺满。布置有两个严格要求:
1.房间必须刚好被砖块铺满，且砖块不能有重叠。 2.每块砖块的周长不能是4的倍数，否则可能会引起官兵的怀疑。
小码妹能否满足以上两个条件铺好砖块吗？如果可以，输出YES，否则输出NO。
格式 输入格式： 第一行一个整数
T(1\le T\le 10^5)
表示测试数据组数。对于每组测试数据：
一行两个整数
a,b(1\le a,b\le 10^9)
输出格式： 输出T行，对于每组测试数据，输出YES或者NO。
样例1
输入 1 2 3
输出 YES
找规律
解题思路
题目对砖块的要求：每块砖块的周长不能是4的倍数，也就是说 2x(l + w) 不能为4的倍数。
以一批砖块举例
| 长 | 宽 | l + w | 周长 = 2×(l + w) | 4 的倍数？ | 合法砖？ |
|---|---|---|---|---|---|
| 1 | 1 | 2 | 4 | ✅ | ❌ 不合法 |
| 1 | 2 | 3 | 6 | ❌ | ✅ 合法 |
| 2 | 2 | 4 | 8 | ✅ | ❌ 不合法 |
| 2 | 3 | 5 | 10 | ❌ | ✅ 合法 |
| 3 | 3 | 6 | 12 | ✅ | ❌ 不合法 |
| 2 | 5 | 7 | 14 | ❌ | ✅ 合法 |
发现合法砖块的l + w 一定是奇数。需要在满足l 和 w 一奇一偶的情况下，那么可以得到砖块的面积 l * w 一定为偶数
则可以得到，房间面积必须为偶数，否则无法符合要求铺满整个房间。
那么思路就很简单了，如果 l * w % 2 = 0, 说明可以铺满，反之无法铺满整个房间。
代码实现
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
StringBuilder sb = new StringBuilder();
while(t-- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
if((a*b) % 2 == 0) {
sb.append("YES\n");
}else {
sb.append("NO\n");
}
}
System.out.println(sb);
sc.close();
01序列
宋江欲报江州之仇，谋划智取无为军。 在行动筹备阶段，宋江获取了一份来自无为军的秘密情报，它是一个长度为n的仅含字符0和字符1的序列a1-an。宋江郑重地对小码妹说：“小码妹，此序列暗藏玄机。我们需要求出该序列中最长的一个合法子区间长度是多少？而合法子区间是指序列a中的一个子区间，能够满足该序列的元素是0和1从左到右交替出现的。这对摸清无为军城内的兵力部署和防御弱点至关重要，关系到此次行动的成败，你务必仔细分析！”
格式
输入格式
第一行一个整数n(1\le n\le 10^6)，
第二行n个整数a_1\sim a_n(0\le a_i\le 1)
输出格式 一行一个整数，表示答案。
样例1
输入 5 0 1 0 1 1
输出 4
解题思路
统计相邻元素是否相同，只需要比较当前元素的前一个元素或后一个元素是否相同，并进行统计。最后得到的答案+1，防止遗漏次数。
代码实现
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int res = 0; //总的最长不同区间
int cur = 0; //当前的最长不同区间
int pre = sc.nextInt(); //前一个数
for(int i = 1; i < n; i++) {
int num = sc.nextInt(); //当前数
if(num != pre) {
cur++;
res = Math.max(cur, res);
}else {
cur = 0;
}
pre = num;
}
System.out.println(res+1);
sc.close();
接龙字符串
梁山好汉排定座次后，宋江决定和小码妹玩一场特殊的字符串接龙游戏。宋江给小码妹n个字符串
s_1,s_2,…,s_n游戏规则如下：
1.每个字符串只能使用一次。 2.除了第一次选择的字符串之外，每次选择的字符串的开头必须为上一次选择的字符串的结尾。 3.你可以选择一个或者一个以上字符串。
宋江会给小码妹q次询问，每次给小码妹两个小写英文字母x和y，小码妹能否选择若干个字符串，使得第一次选择的字符串的开头为x,最后一次选择的字符串的结尾为y吗？
格式 输入格式： 第一行一个整数
T(1\le T\le 10^5)
表示测试数据组数。
对于每组测试数据： 第一行两个整数
n,q(1\le n,q\le 10^5,且T组数里的n之和不超过10^5，即\sum n\le 10^5)
第二行n个字符串
s_1,s_2,…,s_n, 字符串长度在2∼10之间，保证字符串仅由小写英文字母构成。
接下来q行，每行两个小写英文字母x, y，表示对应询问。
输出格式： 对于每组测试数据： 输出q行，如果能够选择若干个字符串满足条件，输出Yes，否则输出No。
样例1 输入 1 3 5 abc cbd deh a e a d a h c d d d
输出 No Yes Yes Yes No
图 Floyd BFS/DFS
解题思路
查询只查以x开头, y结尾的字母的字符串能否连到一起。对于一个具体的字符串，我们只需要看其首尾的字母，其中间的部分可以忽略。我们可以据此做一个包含26个字母的图，对每个字符串，其首尾字母相连，构成了一条边。把所有的边关系都找到之后，通过x,y的查询就是在图中查找x,y之间是否能够连通了。
代码详解
在第i组数据中
boolean[][] reach = new boolean[26][26]; //26个字母
int n = sc.nextInt();
int q = sc.nextInt();
for(int i = 0 ; i < n; i++) {
String str = sc.next();
char p1 = str.charAt(0);
char p2 = str.charAt(str.length() - 1);
reach[p1 - 'a'][p2 - 'a'] = true; //字符串首尾字母可连接
}
得到当前字母的连接情况
传递闭包，得到所有可连接的边：使用Floyd算法
// Floyd 传递闭包：reach[i][j] |= reach[i][k] && reach[k][j]
for(int k = 0; k < 26; k++) {
for(int i = 0; i < 26; i++) {
if(!reach[i][k])continue;
for(int j = 0; j < 26; j++){
if(reach[k][j]) {
reach[i][j] = true;
}
}
}
}
完整代码
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
StringBuilder res = new StringBuilder();
while(t -- > 0) {
boolean[][] reach = new boolean[26][26]; //26个字母
int n = sc.nextInt();
int q = sc.nextInt();
for(int i = 0 ; i < n; i++) {
String str = sc.next();
char p1 = str.charAt(0);
char p2 = str.charAt(str.length() - 1);
reach[p1 - 'a'][p2 - 'a'] = true; //字符串首尾字母可连接
}
// Floyd 传递闭包：reach[i][j] |= reach[i][k] && reach[k][j]
for(int k = 0; k < 26; k++) {
for(int i = 0; i < 26; i++) {
if(!reach[i][k])continue;
for(int j = 0; j < 26; j++){
if(reach[k][j]) {
reach[i][j] = true;
}
}
}
}
for(int i = 0 ; i < q; i++) {
String x = sc.next();
String y = sc.next();
if(reach[x.charAt(0) - 'a'][y.charAt(0) - 'a']) {
res.append("Yes\n");
}else {
res.append("No\n");
}
}
}
System.out.println(res);
sc.close();
拓展知识
1. Floyd–Warshall 求最短路径
状态：
dist[i][j]表示 i 到 j 的最短路径长度。 初始化：dist[i][j] = 边权，若无边则设为INF，自己到自己是0。 转移：
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
含义：
允许经过点 k，看看能否让 i→j 的最短路径更小。
2. Floyd 求传递闭包（可达性）
状态：
reach[i][j]表示 i 是否能到 j。 初始化：- 有边的地方置
true，无边置false。 转移：
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
if (!reach[i][k]) continue; // 小优化
for (int j = 0; j < n; j++) {
if (reach[k][j]) reach[i][j] = true;
}
}
}
含义：
允许经过点 k，如果 i 能到 k 且 k 能到 j，那么 i 就能到 j。
3. 代码上的主要区别
| 方面 | 最短路 | 传递闭包 |
|---|---|---|
| 矩阵类型 | int / long（保存距离） | boolean（保存可达性） |
| 初始化 | dist[i][j] = INF 或边权 | reach[i][j] = false/true |
| 转移公式 | dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]) | reach[i][j] = reach[i][j] OR (reach[i][k] AND reach[k][j]) |
| 结果含义 | 最短路径长度矩阵 | 可达性矩阵（传递闭包） |
4. 总结一句话
同样是三重循环：
- 最短路版更新的是「距离大小」
- 传递闭包版更新的是「是否可达」
回文子序列
在十八路诸侯讨伐董卓的战役中，华雄勇猛无敌，诸侯们皆为之胆寒。关羽主动请缨，欲斩华雄以振军威。为了帮助关羽，小码哥在营帐中研究着一道难题。他手中有一个长度为n的仅包含小写英文字母的字符串s，其中隐藏着破解华雄武艺的秘密。小码哥需要找出这个字符串中有多少个非空子序列是回文序列（输出答案对 998244353 取模的结果）。 小码哥知道，子序列是指一个序列删除若干个元素，剩下的元素按照原来的顺序依次拼接后形成的序列；而回文序列则是指一个序列从左到右读和从右到左读一模一样。
格式 输入格式： 第一行一个整数
n(1\le n\le 5000)
第二行一个长度为n的仅包含小写英文字母的字符串s
输出格式： 一行一个整数，表示答案。
样例1 输入 3 aba
输出 5
解题思路
朴素想法：用 DFS/回溯枚举子序列：指数复杂度，绝对超时/爆内存。
改为使用区间DP
下面把「区间 DP 是什么」和这题里递推公式「从哪来」讲清楚——先讲通用方法，再专门推导本题的公式。
一、什么是区间 DP（Interval DP）？
定义：当一个问题的最优解 / 计数可以按子区间组合而成时，把状态定义在下标区间上（如 i..j），利用较短区间的结果推更长区间的结果，这类 DP 就叫区间 DP。
典型特征：
序列或字符串问题；
子问题是连续区间；
状态
f[i][j]只依赖于更小的区间，比如f[i+1][j]、f[i][j-1]、f[i+1][j-1]等；计算顺序通常：
- 按区间长度
len = 1..n递增； - 或者
i从大到小，j从小到大。
- 按区间长度
常见场景：括号匹配、石子合并、回文相关、删除/合并区间最优、子串统计等。
二、本题建模：统计回文子序列（非空、按下标计数）
我们要求字符串 s 的非空回文子序列数量（不是去重的不同字符串；两个子序列只要下标集合不同就算不同）。
定义区间状态：
f[i][j] = \text{在子串 } s[i..j] \text{ 内的非空回文子序列个数}
边界：
- 当
i == j，只有一个单字符子序列，它必为回文：f[i][i] = 1。
目标：输出 f[0][n-1] (mod M)，其中 M = 998244353。
三、递推公式的推导（核心）
考虑固定一个区间 s[i..j]（i < j），把这个区间内的回文子序列分成几类来数。最常用的划分是按是否使用两端字符 s[i]、s[j] 来分类：
设
- A：完全位于
s[i+1..j]的回文子序列（不使用s[i]） - B：完全位于
s[i..j-1]的回文子序列（不使用s[j]） - C：完全位于
s[i+1..j-1]的回文子序列（既不使用s[i]也不使用s[j]） - D：使用两端
s[i]和s[j]的回文子序列
- A：完全位于
那么 s[i..j] 中所有回文子序列的集合就是：
\underbrace{A \cup B}_{\text{不含两端}} \cup \underbrace{D}_{\text{含两端}}
其中 A ∩ B = C（完全在中间的被 A、B 都算到）。
于是有计数恒等式：
|A \cup B| = |A| + |B| - |C|
\Rightarrow |A \cup B \cup D| = |A| + |B| - |C| + |D|
把集合大小换回 DP 量：
- |A| = f[i+1][j]
- |B| = f[i][j-1]
- |C| = f[i+1][j-1]
关键在于：|D| 等于多少？
情况一：s[i] != s[j]
如果两端字符不同，就不可能存在“同时使用两端还能回文”的子序列（因为回文两端必须相同）。 因此 |D| = 0。
代回式子：
f[i][j] = f[i+1][j] + f[i][j-1] - f[i+1][j-1].
情况二：s[i] == s[j]
此时可以构造“两端都用”的回文子序列：
两端固定为 s[i] 与 s[j]，中间可以嵌入 s[i+1..j-1] 的任意一个回文子序列（按下标计数），此外中间也可以什么都不选（记为“空回文”）。
因此：
|D| = \underbrace{f[i+1][j-1]}_{\text{中间选任意回文}} + \underbrace{1}_{\text{中间选空，得到长度为 2 的回文}}
代回总式：
\begin{aligned}
f[i][j]
&= f[i+1][j] + f[i][j-1] - f[i+1][j-1] + (f[i+1][j-1] + 1) \\
&= f[i+1][j] + f[i][j-1] + 1.
\end{aligned}
这就得到两种转移：
- 若
s[i] != s[j]：
\boxed{f[i][j] = f[i+1][j] + f[i][j-1] - f[i+1][j-1]}
- 若
s[i] == s[j]：
\boxed{f[i][j] = f[i+1][j] + f[i][j-1] + 1}
直觉理解：
- “不等”时只做容斥；
- “相等”时本应容斥减去一次中间的，但又因可以“包裹中间任意回文 + 空”而补回
f[i+1][j-1]+1，净效应变成了 +1。
备注：这里的“+1”对应中间取空那一种（即仅用两端形成的回文子序列）。之所以不显式地看到
-f[i+1][j-1] + (f[i+1][j-1] + 1)，是我们把它合并简化了。
四、计算顺序与实现细节
计算顺序
要保证用到的子问题已被算好：
- 方案 A：按区间长度
len = 1..n枚举，内层枚举起点i，令j=i+len-1； - 方案 B：
i从n-1到0递减，j从i+1到n-1递增。
取模与负数
有减法时要小心负数：
long val = (a + b - c) % MOD;
if (val < 0) val += MOD;
空间优化
- 二维
f[i][j]是 O(n^2) 空间；n=5000时可能偏大。 - 可用滚动数组降到 O(n)：令
dp[j] = f[i+1][j]（上一层），本层用ndp[j] = f[i][j]，转移时还用到ndp[j-1]（即f[i][j-1]）与dp[j-1]（即f[i+1][j-1]）。
五、把推导落到代码（O(n) 空间版）
import java.io.*;
import java.util.*;
public class Main {
static final int MOD = 998244353;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
String s = br.readLine().trim();
// dp[j] = f[i+1][j]（上一层）
int[] dp = new int[n];
for (int i = n - 1; i >= 0; i--) {
int[] ndp = new int[n]; // 本层 f[i][*]
ndp[i] = 1; // f[i][i] = 1（非空）
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
long val = ((long) dp[j] + ndp[j - 1] + 1) % MOD;
ndp[j] = (int) val;
} else {
long val = ((long) dp[j] + ndp[j - 1] - dp[j - 1]) % MOD;
if (val < 0) val += MOD;
ndp[j] = (int) val;
}
}
dp = ndp; // 滚动
}
System.out.println(dp[n - 1]);
}
}
六、小例验证（帮助理解）
s = "aba"
- 单点：
f[0][0]=1('a'),f[1][1]=1('b'),f[2][2]=1('a') - 区间
[0,1]：s[0]!=s[1]⇒f[0][1]=f[1][1]+f[0][0]-f[1][0]=1+1-0=2（“a(0)”、“b(1)”） - 区间
[1,2]：同理=2（“b(1)”、“a(2)”） - 区间
[0,2]：s[0]==s[2]⇒f[0][2]=f[1][2]+f[0][1]+1=2+2+1=5对应：a(0), b(1), a(2), aa(0,2), aba(0,1,2)共 5。
七、容易混淆的两类题
- 本题：统计的是“按下标计数”的回文子序列总数（不去重），用上述递推即可。
- 另一类题：统计“不同回文子序列的种类数”（去重），那就要去重处理，递推会更复杂（要考虑相同字符的最近位置），不是本文的公式。
八、要点回顾
区间 DP：状态在
i..j，按短到长推进。本题按是否用两端分类 + 容斥：
s[i] != s[j]：容斥 f[i][j] = f[i+1][j] + f[i][j-1] - f[i+1][j-1]s[i] == s[j]：容斥 + 包裹中间 f[i][j] = f[i+1][j] + f[i][j-1] + 1
取模注意负数；可用滚动数组把空间降到 $O(n)$。
这样，区间 DP 的思想与这道题的递推就完整了。
一、为什么情况二要加 +1？
我们在考虑区间 s[i..j] 时，假设 s[i] == s[j]。
此时我们能构造新的回文子序列，形式是：
s[i] + (中间部分的某个回文子序列) + s[j]
其中「中间部分」取自 s[i+1..j-1]。可能有两种情况：
选中间的某个非空回文
- 例如
s = "aba"：在区间[0,2]，中间[1,1]的 “b” 是回文，用两端包裹得到"aba"。 - 这类新回文的数量是
f[i+1][j-1]。
- 例如
中间什么都不选（空子序列）
- 这时候得到的就是
s[i]s[j]，一个长度为 2 的回文。 - 例如
s = "aa"：中间空，直接得到"aa"。 - 这正是额外的
+1。
- 这时候得到的就是
所以总数是：
f[i+1][j-1] （中间选非空回文）
+ 1 （中间选空）
这就是情况二公式里的 +1。
二、二维数组版写法（更直观）
时间复杂度 O(n^2)，空间 O(n^2)，对 n=5000 勉强能过（约 25e6 int ≈ 100MB 内存）。写法比滚动数组更直观。
import java.io.*;
public class Main {
static final int MOD = 998244353;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
String s = br.readLine().trim();
int[][] f = new int[n][n];
// 区间长度从 1 开始
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (i == j) {
f[i][j] = 1; // 单字符
} else if (s.charAt(i) == s.charAt(j)) {
long val = (long) f[i + 1][j] + f[i][j - 1] + 1;
f[i][j] = (int) (val % MOD);
} else {
long val = (long) f[i + 1][j] + f[i][j - 1] - f[i + 1][j - 1];
val %= MOD;
if (val < 0) val += MOD;
f[i][j] = (int) val;
}
}
}
System.out.println(f[0][n - 1]);
}
}
三、小例子验证
s = "aba"：
f[0][0]=1, f[1][1]=1, f[2][2]=1f[0][1]=2(“a”,“b”)f[1][2]=2(“b”,“a”)f[0][2]=f[1][2]+f[0][1]+1=2+2+1=5，即 { “a”,“b”,“a”,“aa”,“aba” } ✅
代码实现
import java.io.*;
public class Main {
// 模数
static final int MOD = 998244353;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 读入长度 n
int n = Integer.parseInt(br.readLine().trim());
// 读入字符串 s（仅小写字母）
String s = br.readLine().trim();
// f[i][j] 表示子串 s[i..j] 内的“非空回文子序列”的数量（按下标计数，不去重）
int[][] f = new int[n][n];
// 按区间长度 len 从小到大填表
// len = 1：单字符区间
// len = 2..n：一般区间
for (int len = 1; len <= n; len++) {
// 枚举区间起点 i（确保 j = i + len - 1 不越界）
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1; // 区间终点
if (i == j) {
// 单个字符：唯一的非空回文子序列就是它自身
f[i][j] = 1;
} else if (s.charAt(i) == s.charAt(j)) {
// 情况二：两端字符相等
// 递推公式：
// f[i][j] = f[i+1][j] + f[i][j-1] + 1
//
// 推导直觉：
// - 把完全在右侧的回文（不含 s[i]）加上完全在左侧的回文（不含 s[j]）
// - 两端相等时，本应做一次容斥减去 f[i+1][j-1]，但同时可以“用两端包裹中间任意回文（含空）”
// 新增数量为 f[i+1][j-1] + 1（+1 对应中间取空，得到 s[i]s[j] 这个长度为 2 的回文）
// - 两者抵消后净效果为 +1
long val = (long) f[i + 1][j] + f[i][j - 1] + 1;
f[i][j] = (int) (val % MOD);
} else {
// 情况一：两端字符不等
// 递推公式：
// f[i][j] = f[i+1][j] + f[i][j-1] - f[i+1][j-1]
//
// 含义：左区间 + 右区间，减去两者重叠的“完全在中间”的部分（容斥）
long val = (long) f[i + 1][j] + f[i][j - 1] - f[i + 1][j - 1];
// Java 的 % 可能产生负数，统一规范化到 [0, MOD)
val %= MOD;
if (val < 0) val += MOD;
f[i][j] = (int) val;
}
}
}
// 答案是整个串 s[0..n-1] 的回文子序列数
System.out.println(f[0][n - 1]);
}
}
说些什么吧！