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 解释：从左 ......

题目描述 给你一个字符串s，找到s中最长的回文子串。 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。 示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2： 输入**：s = "cbbd" 输出："bb" 提示： 1 <= s. ......

这道题非常板，如你所见，大概思路是打表回文数加上完全背包求方案数，但是需要注意取余问题。 从英文题面上（题目翻译没有给出数据范围）可以看到 \(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 ......

#include <stdio.h> #include <math.h> int main(){ int a,b; int num[12000]={0}; //保存回文数的数组 int al[8]={0}; //保存取余后的原位置上的数字 int i,j,k=0,ii,temp,length=0,s ......

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

又名：《最近 vjudge 题全部罚坐》。 唯一 Trick：回文序列，就想区间 dp！时间复杂度 \(O(n ^ 2)\)！ 如果是序列：\(f_{l, r}\) 表示 \([l, r]\) 的最长回文子序列，\(f_{l, r} = \max(f_{l + 1, r}, f_{l, r - 1} ......

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

Minimum Changes to Make K Semi-palindromes Given a string s and an integer k, partition s into k substrings such that the sum of the number of letter ......

CF1867B XOR Palindromes 这里是一个关于 \(n\) 的奇偶性分类讨论的做法。 设最终的答案序列为 \(\{ans_{n+1}\}\)，它由 \(0,1\) 组成。 首先计算出原序列中有序数对 \((i,n-i+1)\) 的个数，使得 \(s_i \not= s_{n-i+1} ......

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

思路 题目问的是改 \(i\) 位，能不能让原串变成回文串，其中 \(0\le i \le n\)。 首先，我们可以统计前后对称位置不一样的对数，记为 \(k\)，那么至少也得改 \(k\) 次，假设剩下前后对称位置一样的有 \(m\) 对（如果 \(n\) 为奇数，则最中间的一位不计入 \(m\) ......

题目链接 题解 知识点：构造。 首先反证法容易证明一个结论：每次增加一个字符，本质不同的回文子串至多增加一个。 那么无解的条件就是，\(c_i - c_{i-1} > x_i -x_{i-1}\) ，即距离不够数量的增加。 其他情况均有解，可以考虑利用 abc 作尾部填充，因为其只在一开始提供 \( ......

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

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

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

打表 先把一到一亿的质数兼回文数打出来。（用文件输入输出会方便复制一些） 最后效果如下： 太长故折叠 0,2,3,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11 ......

<p><a href="https://www.cnblogs.com/LuoGuyexc/articles/17397324.html">更好的阅读体验</a>。</p><p>一道贪心题。</p><p>首先，本质不同的回文串最多只有 $n$ 个.</p><p>我们注意到 $k$ 很小，甚至小于字符 ......

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 ......