法1：hash 思路 很简单的思路，用一个hash表，键为字符，值为一个pair，pair的first成员存字符的出现次数，second成员为该字符的下标，维护一个下标最小值为答案即可。 代码 法2：延长字符串 思路 把整个s串延长一倍，接在原串尾部。遍历串的前半截，如果当前字符在该下标往后的片段里第一次出现的位置为当……

传送门 题目描述 给定一个起始单词，一个目标单词与一个备选字典，通过以下规则将起始单词变到目标单词去： 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 求最短变化步数。 思路 看到最短步数，首先想到BFS。但使用BFS的前提是有一个可以用来搜索的图或者树，于是思维转向如何建立图/树。 思路还是很清……

传送门 题目大意 在一条只能前进后退的一维路径上，给定起点n与重点k，只有三种移动方式： 前进一步 后退一步 使坐标变为当前值的两倍 问走到终点最短需要几步。 思路 很经典的bfs板子题，直接bfs去枚举每一种走法。每次操作依次将三种移动方式计算所得的目标坐标放进队列，然后出队判断就行了。 代码

传送门 题目大意 一个序列s，题目定义两种编码方式： 第一种方式是p，其中pi表示第i个右括号之前的左括号数；第二种是w，其中wi表示第i个右括号(包括它本身)之前完成匹配的括号对数。 现给出序列s在p方式下的编码，求出它在w方式下的编码序列。 思路 已知条件是p序列，那就从p序列入手。 对于pi，设j<i，那么……

传送门 题目大意 给定一个由10种字符(p,q,r,s,t,N,K,A,C,E)组成的逻辑表达式，其中pqrst为逻辑变量，NKACE为逻辑运算符，他们的含义分别是 K==and：x && y N==not：!x A==or：x || y C==implies：(!x)||y E==equals：x==……

传送门 题目大意 用2×1与2×2的小方块去填满一个2xn的长条形区域，问有多少种填法。 思路 很标准的dp。假设当前填到第i个位置，那么能继续往后推进的办法只有三种：竖着放一个2×1的方块，或者横着放两个2×1的方块、亦或者直接放一个2×2的方块。即，dp[n]的填法……

传送门 题目大意 一个学校有n(n<=50000)个学生，他们都可能信仰不同的宗教，你不能一个一个去问他们的信仰，但你可以通过询问得知两个学生的信仰是否一致，询问有m(m<=n*(n-1)/2)次。通过询问你可以知道校内学生的信仰总数上限，找到这个上限作为答案。 思路 其实就是一个并查集，题目翻译过来就是说……

传送门 冷知识：Y2K就是常说的千年虫。（这题的题意是真的搞，建议语文太差的人不要参与出题） 题目大意 微软公司每个月都可能盈余s元或者亏损d元，但具体是盈余还是亏损不知道。知道的是每连续的五个月统计一次总收入，都是亏损的(不难知道这样的统计一共有八次)。现问在这种条件下一年到头能盈利吗？如果能，找出最大盈利，如果不能……

传送门 题目大意 假设海岸是一条无限长的直线。陆地在海岸的一边，海洋在另一边。每个小岛都是位于海边的一个点。而任何位于海岸线上的雷达装置，只能覆盖d距离。所以如果小岛与一个雷达之间的距离最多为d，那么它可以被这个雷达覆盖。 我们使用笛卡尔坐标系，定义海岸是x轴，海边在x轴上方，陆地在下方。给定海洋中每个岛屿的位置，给定……

传送门 经 典 老 番 最近算法课讲到递归，顺手写一点经典的回溯题来巩固基础。 回溯是一种通过枚举出所有可能情况来得到解答的算法，很直白也很经典。当确定当前情况不是解或不是最后一个解时，算法会逐步退回到之前的步骤，通过更改部分组成来枚举下一种情况。 放在这道题里，要得出n个数的全排列，不难得出它的递归思路，设cur为当……