目录    题目 输入 输出 样例 提示 思路 代码    题目 As you know, majority of students and teachers of Summer Informatics School live in Berland for the most part of the year. Since corruption there is quite widespread, the following story is not uncommon. Elections are coming. You know the number of voters and the num...

系统目录  前言 序列   特征下标（序列首、序列尾） 序列的长度 合序列   定义 合序列的特征分序列 合序列的长度 分序列之间特征下标的关系   二分查找   分类   寻找元素都相等的子序列首     前言 二分查找不同变种和边界问题使得其在实际编程中难以实现，本文希望探索一种系统的二分查找实现，使在实际编程中应对各种变种能高效实现代码。本文无特殊情况会持续更新。 因左闭右开区间在编程中的优越性，现约定本文所有二分算法皆为左闭右开区间实现。 序列 特征下标（序列首、序列尾） 现有一序列A，各元素下标为 i,i+1,…,n-2,n-1，则称i为序列首，记为A0，n为序列尾，记为AN。 将序...

目录  前言 基础算法   快速排序* 并查集   带权+路径压缩+启发式合并（前提：权不考虑符号）  高精度（输入输出均为逆序字符串）   加/乘 通用模板   数论   拓展欧几里得 逆元（拓欧，最小非负整数解，特判） 质数   线性欧拉质数筛 质数个数   滑动窗口   上界最大字串和  动态规划   经典dp 状压dp   位运算 内建函数   字符串   Trie树 拓展kmp（标准kmp板子？你还没记住？） manacher  图论   遍历   dfs bfs  二分图最大匹配（前向星） 最短路径   Dij   邻接矩阵 堆优化+前向星    树   树链剖分+线段树 维护 查...

目录    知识点：最长单调子序列、分治 题目 输入 输出 样例 提示 思路 代码    知识点：最长单调子序列、分治 题目 有一支N个新兵的部队，他们的序号从左到右分别为1到N，每个新兵都有一个身高ai，现在，我们希望给这支部队尽量少的踢掉几个新兵，剩下的新兵靠拢，使得每个剩下的任意一个位置的新兵向左或者向右其中的某一边的身高是严格递减的。 输入 第一行输入一个N，表示新兵的个数（2≤N≤1000）。 第二行输入N个浮点数ai，分别表示这N个新兵的身高（0.5≤ai≤2.5）。 输出 输出一个整数，表示最少需要踢掉的新兵数目。 样例 input 6 0.7 1.9 1.6 1.9 1.6 0...

目录    知识点：线性dp、字符串 题目 输入 输出 样例   输入 输出  题意 思路 代码    知识点：线性dp、字符串 题目 Few know that the cows have their own dictionary with W (1 ≤ W ≤ 600) words, each containing no more 25 of the characters ‘a’…‘z’. Their cowmunication system, based on mooing, is not very accurate; sometimes they hear words that do ...

目录    知识点：计数原理、数学推理、反向思考 题目 输入 输出 样例   输入1 输出1 输入2 输出2  提示 题意 思路 代码    知识点：计数原理、数学推理、反向思考 题目 Not long ago Billy came across such a problem, where there were given three natural numbers A, B and C from the range [1, N], and it was asked to check whether the equation AB = C is correct. Recently Billy ...

目录    知识点：字符串、循环、STL 题目 输入 输出 样例   输入1 输出1 输入2 输出2 输入3 输出3  提示 题意 思路（罚自己写一题多解）   一、 代码 二、 代码（Runtime error on test 19）     知识点：字符串、循环、STL 题目 You are given string s. Your task is to determine if the given string s contains two non-overlapping substrings “AB” and “BA” (the substrings can go in any ord...

目录    知识点：贪心、递推、反向思考 题目 输入 输出 样例   输入1 输出1 输入2 输出2  提示 题意 思路 代码    知识点：贪心、递推、反向思考 题目 Vasya has found a strange device. On the front panel of a device there are: a red button, a blue button and a display showing some positive integer. After clicking the red button, device multiplies the displayed num...

目录    知识点：模拟、贪心、分支语句（、动态规划？） 题目 输入 输出 样例   输入1 输出1 输入2 输出2  题意 思路 代码1 代码2    知识点：模拟、贪心、分支语句（、动态规划？） 题目 You have a positive integer m and a non-negative integer s. Your task is to find the smallest and the largest of the numbers that have length m and sum of digits s. The required numbers should be n...

目录    知识点：线性dp（递推）、贪心 题目 输入 输出 样例   输入1 输出1 输入2 输出2 输入3 输出3  提示 题意 思路 代码    知识点：线性dp（递推）、贪心 题目 Alex doesn’t like boredom. That’s why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it. Given a sequence a consisting of n integers. The...

暂且就先将所有笔记写在一篇博客上吧，等需要分类管理的时候再分成多个博客放到一个专题中。  目录 同时保留原始顺序与有序顺序的方法 分组问题 状态相关与无关（CF915C Permute Digits） 问题的有序无序性 答案的唯一性 鸽笼原理 如何做思维题？ 思维过程 1. 自顶向下 2. 自底向上 贪心 双指针（CF279B Books）  关于位运算 2. 异或的逆运算性质 3. 加法的位运算性质  组合博弈 SG函数 Nim-sum（小博弈的并） 图论 几个建图方式： 快速傅里叶变换（FFT）   1. 树状数组、线段树，ST表的应用场景：区间和、区间 gcd 、最大子段和 等 满足结合...

目录 检查变量是否有误！检查变量！检查变量！检查变量！ 语法错误 数组范围 重构代码的维护范围问题 数据范围问题 初始化问题 逻辑错误 循环问题 其他 数据结构 线段树  检查变量是否有误！检查变量！检查变量！检查变量！  只记一些因细小问题而导致长时间调试的问题。 可预见本文一字一句都是痛苦罚坐的缩影QAQ。  语法错误 数组范围 1. 数组范围是否改大 2. 双向建边时N是否×2 3. 题目中出现偶数长序列等，是给定数据的n倍，数组记得乘n。 重构代码的维护范围问题 1. 单条语句改多条时要加大括号 if(j==mi[i].size()) found=true; // cout<&l...

目录    前言 取整问题 （拓展）欧几里得 逆元   拓展欧几里得法 线性逆元  （拓展）中国剩余定理 关于GCD （拓展）欧拉定理 欧拉函数   计算  φ ( n ) − > φ ( n m ) \varphi(n)->\varphi(nm) φ(n)−>φ(nm)   m为质数 n,m互质 其他情况   组合数学   算术基本定理（唯一分解定理） 所有质因数序列排列组合  几何分布   不相交路径     前言 有时候会把最基本的定义忘掉…… 当且仅当存在一个正整数c使得a × c = b，则正整数a是正整数b的因子。  C99规定，对非负整数取模的结果为非负整数，否...

目录    知识点：二分匹配、贪心、思维 题目 输入 输出 样例   输入 输出  题意 思路 代码    知识点：二分匹配、贪心、思维 题目 Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an intersection and walking through town’s streets you can never reach the same inters...