回文1309 noip 1999
NOIP2011提高组复赛day2解析
1.计算系数 题目：https://www.luogu.com.cn/problem/P1313 解析： 直接套用二项式定理，使用快速幂计算组合数 代码： #include<bits/stdc++.h> #define ll long long using namespace std; const ......
长回文子串-动态规划解法
### 题目： 给你一个字符串 `s`，找到 `s` 中最长的回文子串。 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。 **示例 1：** ```javascript 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 ``` ## Go ......
[NOIP2012 提高组] 疫情控制 题解
# [NOIP2012 提高组] 疫情控制 ## 题意： 给定一棵树，边有边权，有一些结点上有军队（可能不止一支），军队可移动。求最短的时间，使得军队移动后，从根到每个叶子结点的路径上都有军队驻扎。军队可以同时移动。 ## 思路： ~~咳咳咳我当时读错题了以为这题虚高，然后才意识到边境结点只有叶子结 ......
[NOIP2013 提高组] 华容道 题解
# [NOIP2013 提高组] 华容道 ## 题意： 一个棋盘上，每个格子上都有一个 $1 \times 1$ 的棋子，有些棋子固定，剩下的可以移动。棋子只能移动到空白的格子里。$Q$ 次询问，每次给出空白格子的位置、目标棋子的位置以及终点的位置，问把目标棋子移动到终点的最小步数。无解输出 $-1 ......
判断回文字符数组
#include<iostream>#include<cstring>#include<algorithm>#include<ctime> using namespace std; const int MAXN=10010; int main() { char s[MAXN];int i=0,n=0 ......
[NOIP2011 提高组] 铺地毯 题解
[洛谷链接](https://www.luogu.com.cn/problem/P1003) [FZQOJ](https://qoj.fzoi.top/problem/167) ##First 这一题的题面看似很长， 但是实际上归纳下来可以总结为： (1)：告诉你有i张地毯 (2)：第2行~第i+1 ......
NOIP训练赛 #3
## T1 幸运数字Ⅱ 有 $Q$ 个询问,每次给定一个区间 $L,R$ 求区间内满足如下条件的 $x$ 的个数: $x$ 为质数或者 为两个质数的积 **【数据范围】** $L,R\leq 10^7,Q \leq 10^5$ ### 题解 欧拉筛预处理出 $10^7$ 以内满足条件的数的个数,做一 ......
洛谷P1013 [NOIP1998 提高组] 进制位
# P1013 [NOIP1998 提高组] 进制位 [P1013题目传送门](https://www.luogu.com.cn/problem/P1013) 这是一道提高+/省选-的蓝题，~~有亿点点难度~~，我们先分析一下。 ## 分析 字母的数量等于进制的大小，判错的时候，可以看一下那个表格右 ......
NOIP 2017 普及组初赛
## T1 在 8 位二进制补码中，10101011 表示的数是十进制下的 - A. 43 - B. -85 - C. -43 - D. -84 答案 **B** 反码 +1 -> 补码 10101011 是补码，第一位是 0 则表示正数，1 表示负数 10101011-1=10101010，得出对 ......
NOIP训练赛 #2
## T1 探险  **【数据范围】** $1\leq n,m,k\leq 10^3,1\leq x_1,x_2 \leq n,1\leq y_1,y_2\leq m$ ## ......
最长回文数
### 问题描述 输入一个包含`N`个正整数的数组，求出这个数组中包含的最长的回文数组是什么, 如果有相同长度的最长回文数，输出最靠前的一个。 ### 解题思路 伪码： ``` INPUT A[] FOR I IN 1,N{ FOR J IN I,N{ IF HUIWEN(A,I,J) && J-I ......
洛谷P5937 [CEOI1999]Parity Game_学习笔记
洛谷P5937 [CEOI1999]Parity Game 本来是想练习一下离散化的，结果看到这道又有并查集又有离散化的题，于是就逝了逝，在阅读题解后， 发现自己对并查集和离散化认识有点问题，于是写下这篇笔记总结一下。 看到这种给出几个条件判断矛盾的题，便想到了两种常见思路，一种是拓扑排序， ......
NC16610 [NOIP2009]Hankson的趣味题
[题目链接](https://ac.nowcoder.com/acm/problem/16610) # 题目 **题目描述** Hanks博士是BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson正在思考一个有趣的问题。 今天在课堂上，老师 ......
NOIP训练赛 #1
## T1 奇怪的冰雹  **【数据范围】** $1 \leq n \leq 4,1 \leq m \leq 120,1 \leq a_i \leq 50$ 由于 $n$ 的 ......
NOIP2013提高组初赛易错题解析
7. 正解： 可以画出递归树，画出后应该是这样子的 画出递归树，就可以得出答案时间复杂度为O(Fn) 15. 正解： 2T(n/2)=O(log n) T(n)=2*T(n/2)+2*n=O(n log n) 三.2. 错误原因：蒙的 正解： 通过观察，可以找到递推关系式，f[n]=1/n*(n+f ......
NOIP2016提高组初赛易错题解析
9. 正解： 每一个bit，都有两种可能，0和1，所以最多可以使用232=4GB的内存 14. 正解： 使用代入法，T(n)=2T(n/4)+sqrt(n),T(n/16)=2T(n/4/4/4)+1/4*sqrt(n),T(n)=2k+k*sqrt(n)=sqrt(n)+k*sqrt(n),则时间 ......
NOIP2015提高组初赛易错题解析
五.1.4. 错误原因：没读题~ 正解：由于题目中说两个连续子序列之间至少间隔1个数，所以第四个空是lmax[i-1]+rmax[i+1] ......
NOIP2017提高组初赛易错题解析
8.由四个不同的点构成的简单无向连通图的个数是（ ） A. 32 B.35 C.38 D.41 错误原因：数重了 正解： 分情况计算，6条边的有1种，5条边的有C(6,1)=6种，4条边的有C(6,4)=15种，3条边，要分度数，2+2+1+1的有12种，3+1+1+1的有4种，共38种 10.若 ......
NOIP2018提高组初赛易错题解析
2.下列属于解释执行的程序设计语言是（） A.C B.C++ C.Pascal D.Python 错误原因：忘记了 正解： C、C++和Pascal都是编译性语言，而Python是解释性语言 5.设某算法的时间复杂度函数的递推方程是 T(n) = T(n - 1) + n（n 为正整数）及 T(0) ......
P1070 [NOIP2009 普及组] 道路游戏
[传送门](https://www.luogu.com.cn/problem/P1070) 思考最朴素做法 $f_{i,j,p}$表示在第$i$个时刻终点为$j$且机器人走了$p$步获得的最大金币数，则有： $$f_{i,j,p}=r_{w(j-1),i}+\begin{cases}f_{i-1,w ......
回文自动机（PAM）学习笔记
[传送门](https://www.luogu.com.cn/problem/P5496) 我认为理解回文自动机需要图，以$abbaabba$为例，它的回文树是这样的：  令 ......
LeetCode 131. 分割回文串
#题目链接：[LeetCode 131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/description/) ##题意： 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割 ......
新手第一题，回文数
看到题目就想起来翁恺老师讲过的“逆数”思路，但还是犯了错误。首先，循环条件后面顺手打了个逗号，并且没有准备跳出循环的条件。 另外没有初始化ret，按照我的写法，x=0时没有进入循环，直接输出了结果，所以要初始化ret=0 ......
【lc】409最长回文串
链接 https://leetcode.cn/problems/longest-palindrome/description/ 分析 这题其实就是想让我们组成回文串。 回文串的特点： 1. 如果回文串长度为奇数，那么只有1个字符是奇数个，其余全是偶数个。 2. 如果回文串长度为偶数，那么全部字符都为 ......
NOIP 2023 周赛 3 题解
# A - Permutation ## summarization 构造一个 $1\dots n$ 的排列使 $\prod\limits_{i=1}^n\operatorname{lcm}(p_i,p_{(i\bmod n)+1})$ 最大。 ## solution 不难发现上式最大为 $\pro ......
【学习笔记】Manacher（马拉车）求回文子串
点击查看目录 [TOC] ## 参考资料与图片来源 [参考博客](https://www.cnblogs.com/grandyang/p/4475985.html) 我觉得这个博客讲的不好，他只讲看规律得到的结论，原因却不说，怪。 [参考博客2](https://www.cnblogs.com/lo ......
NOIP2014提高组初赛试题易错题整理
一.选择题 4.TCP协议属于（）协议 A.应用层 B.传输层 C.网络层 D.数据链路层 解析： 正确答案是B，因为TCP协议是传输控制协议的缩写 12.同时查找2n个数中的最大值和最小值，在最少比较次数是（）？ A.3(n-2)/2 B.4n-2 C.3n-2 D.2n-2 解析： 正确答案是C ......
[刷题笔记] Luogu P1064 [NOIP2006 提高组] 金明的预算方案
[Problem](https://www.luogu.com.cn/problem/P1064) ### Analysis 我们发现如果忽略主从关系，那这道题就是一个裸的 01 背包问题。 主从关系处理也非常简单，借鉴 [P2014 选课](https://www.luogu.com.cn/pro ......
[刷题笔记] Luogu P2679 [NOIP2015 提高组] 子串
[Problem](https://www.luogu.com.cn/problem/P2679) ### Description 我们可以换个思路。 从字符串 $A$ 中拿出 $k$ 个字串使其变成 $B$。求有几种不同的方案？ ### Analysis 我们发现 $A$ 中的一个字符取或者不取影 ......