Palindrome

思路 判断一个字符串是否是回文串，可以从它的本质出发：正着读和倒着读是一样的。快速判断它正着和反着是否一样，用字符串哈希即可。又因为涉及单点修改，区间查询，那么使用线段树维护这两个值就行了。 这里讲一下如何 pushup。以正着的哈希值为例：我们要更新 \(p\) 这个点的 \(hash\) 值，已 ......

题意略。 手玩一下，发现 polybeta Bob 赢面不大。 本来想模拟的。考虑结论题。 由于计入代价的操作只有 \(s_i=0\to1\) 一个，可以统计 \(0\) 的个数为 \(cnt\)。 由于这题和 Ezy Version 的唯一区别就是初始字符串是否为回文，很自然地想到对于初始串是否回 ......

题目描述 给你一个整数x，如果x是一个回文整数，返回true；否则，返回false。 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 例如，121是回文，而123不是。 示例 1： 输入：x = 121 输出：true 示例 2： 输入：x = -121 输出：false 解释：从左 ......

这道题非常板，如你所见，大概思路是打表回文数加上完全背包求方案数，但是需要注意取余问题。 从英文题面上（题目翻译没有给出数据范围）可以看到 \(1 \leq n \leq 4 \cdot 10 ^ {4}\)，所以只要用完全背包来预处理这一范围即可。如果你还是不懂，可以去搜完全背包字样并学习该算法。 ......

You are given a string s consisting of lowercase English letters, and you are allowed to perform operations on it. In one operation, you can replace a ......

F - Palindrome Query Problem Statement You are given a string $S$ of length $N$ consisting of lowercase English letters.Process $Q$ queries described ......

字符串哈希 [OI-Wiki](字符串哈希 - OI Wiki (oi-wiki.org)) 分为两种哈希方式：以左为高位 和 以右为高位 如果只是快速查询每个字串的哈希值，用以左为高位比较简单，即 \[Hash[l...r]=Hash[1...r]-Hash[1...(l-1)]\times ba ......

首先把原串交错重构，使得转化为偶回文串划分计数，不讲（虽然很难想到）。下面先考虑回文划分计数。容易得到一个 DP：\(f_i\) 表示长度为 \(i\) 的前缀划分方案数，则枚举所有 \(i\) 结尾的回文子串即可进行转移。我们可以求出以 \(i\) 结尾的最长回文后缀，通过不断跳它在回文树上的 f ......

题目链接 点击打开链接 题目解法 首先考虑一个朴素的 \(dp\) 令 \(f_i\) 表示以 \(i\) 结尾的合法子串的个数 为了不重不漏，我们令 \(le_i\) 表示以 \(i\) 为右端点，离 \(i\) 最近的偶回文串的左端点，然后不难得到转移为 \(f_i=f_{le_i-1}+1\) ......

here 哥们不会组合数学。 首先类似这题，得出没有回文串的充要条件是没有长度为 3 的回文串。 长度为 3 的回文串，\(a_i,a_{i+1},a_{i+2}\)，只要满足 \(a_i \neq a_{i+2}\) 即可，也就是说奇数位、偶数位抠出来，新数组中相邻的数不相同。 考虑 dp，一种显 ......

非常有意思的思维题。 首先我先瑞平一下翻译，我根本没看懂，还是去看英文题面看懂的。 首先可以发现整个字符串被拆成了若干个奇回文串与偶回文串。现考虑如何判是否合法。可以发现一个回文串就是要求部分位置匹配。我们对这些匹配的位置建边，如果得到的图是联通的，那么就只能填入 \(1\) 种字符，否则就可以填入 ......

传送门 给出一个\(5000\)长的字符串 判断有多少个连续子串是超级回文的。 这里超级回文的定义是将字符串分成\(2k\)段每段按照回文对应相等。 设\(f_{l,r}\)表示区间\(l,r\)是否是符合要求的。引入\(border\)的定义：最长的前缀和后缀匹配长度。 容易想到我们如果暴力枚举每 ......

题目： Consider a positive integer N written in standard notation with k+1 digits ai​ as ak​⋯a1​a0​ with 0≤ai​<10 for all i and ak​>0. Then N is palindro ......

## 思路 发现一个进阶回文序列仅包含三个部分：$x$ 个连续的 $a$，$y$ 个连续的 $b$，$x$ 个连续的 $a$。 对于一个 $a$，我们一定会取最外面的两个 $a$，如果不取，则答案一定不小或不变，所以我们枚举到 $a$ 的时候，一定是确定了最外围的两个 $a$ 的位置。 接下来再枚举 ......

## 思路 发现一个进阶回文序列仅包含三个部分：$x$ 个连续的 $a$，$y$ 个连续的 $b$，$x$ 个连续的 $a$。 对于一个 $a$，我们一定会取最外面的两个 $a$，如果不取，则答案一定不小或不变，所以我们枚举到 $a$ 的时候，一定是确定了最外围的两个 $a$ 的位置。 接下来再枚举 ......

一道比较神秘的构造题。 ### 思路 考虑如何通过回文串的性质将所有字符连接起来。 容易发现本题需要使用通过回文串类似连边的方式将所有字符变为一整个连通块。 考虑三种情况。 1. 偶数连偶数 前面的偶数将最后一个字符与后面的偶数前 $len-1$ 个字符组成一个回文串。 2. 偶数连奇数 前面的偶数 ......

You are given a 0-indexed string s consisting of only lowercase English letters. In one operation, you can change any character of s to any other char ......

You are given an array nums consisting of positive integers. You can perform the following operation on the array any number of times: Choose any two  ......

神秘回文串题。 ~~首先容易发现要求的是区间本质不同回文串个数，所以直接上论文做法即可。~~ 容易想到增量构建回文自动机，假如现在建出了 $[1, r]$ 的 PAM，考虑有多少回文串出现在了 $[l, r]$ 内。考虑记录每个回文串的最后一次出现位置 $last_p$，那么这个串的左端点就是 $l ......

Given an integer x, return true if x is a palindrome, and false otherwise. **Example 1:** ``` Input: x = 121 Output: true Explanation: 121 reads as 12 ......

# [$\color{purple}\text{Palindrome Partition}$](https://www.luogu.com.cn/problem/CF1827C) >该说不难，只待一切走上正轨。 显然我们不能枚举每个子串，所以我们考虑枚举以 $i$ 结尾的**“好的”子串**的个数。 ......

题意 有一个字串 $S$ 长 $M$，由 $N$ 个小写字母构成。欲通过增删字母将其变为回文串，增删特定字母花费不同，求最小花费。 分析 定义状态 $dp[i][j]$ 表示使 $i$ 到 $j$ 这一段区间变成回文串所需要的最小代价。 显然，$dp[i][j]$ 只能由 $dp[i + 1][j] ......