题目：字符串距离计算 题解： 这个题暴力就好了，三层循环枚举哪个字符转换成哪个字符，然后将第一个串中的所有该字符替换，再比较两个串中不同的字符有多少个，每次更新最小值就好了。 代码： class Solution { public:     /**      * 计算最少的距离      * @param S1 string字符串 第一个字符串  &nb...

传送门：Space Ant 题意 给出n个点，有一个小人，他每次只能往左边拐，并且不能走以前走过的路，走的路线也不能相交，问他怎么走可以走的路程最大。 题解 可以想到肯定是所有的点都走到路径会最大，然后就很容易想到这不就可以一直凸包了吗！！每次形成凸包的点删掉再继续凸包，然后每次把点的编号加入队列中，直到没有点没被走过。我用的是graham算法的凸包，先找到纵坐标最小的点，第一次按照极角排序是判断和该点连线的极角，后边都是和前一次凸包里的最后一个点的连线形成的极角判断。（想法很简单，实现好麻烦....） 代码 #include<stdio.h> #include<algori...

传送门：Treasure Hunt 题意 有一个左下角为（0,0），右上角为（100,100）的正方形，给出n条线段，线段的起点和终点都在正方形上，给定一个宝藏的坐标，问从正方形外走到宝藏至少要经过多少条线段。每次只能走线段的中点，也就是每两个交点的中点。 题解 因为肯定是从正方形的边开始走，所以枚举每条边上的相邻两个点的中点，连接宝藏所在的点，看这条线段和几条线段有交点，并更新最小值。（为什么这么做是对的呢？因为我没找到反例（逃 存每条边上的点时记得排序 : ) ，忘记排序花式wa。 代码 #include<stdio.h> #include<algorithm> ...

传送门：HDU - 6559 题意 在一个三维空间，给定一个点和他的三维速度，给定一个圆锥，问这个点最早什么时候能撞上圆锥。 题解 本来一直想着怎么求圆锥的方程，然后....队友：这不是二分吗！然后问题就转换成了要怎么求当前时间是不是已经穿过了圆锥了....然后就gg了。 正解就是联立: ① r ' = (h-z)/h*r ② x=x0+vxt; y=y0+vyt; z=z0+vz*t; ③ x2+y2=r ' 2 然后就可以求解出 t 了（这个一元二次方程及其麻烦.....）不知道为啥直接输出t1就可以了，而不是输出非负的最小值....（逃 代码 #include<bits/stdc+...

传送门：https://ac.nowcoder.com/acm/problem/19971 先记录下来，以后再学。神奇操作   题解 用到了C++ pb_ds库，真是一个神奇的库啊.... #include <ext/pb_ds/assoc_containe.hpp>#include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; 定义一颗红黑树tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_nod...

这个题就是蓝书上边的小猫爬山和假日团队赛48的A题的升级版啊...搜索+剪枝的思想 首先判断是否有一个物品的重量超过了箱子的承重，有的话就输出No，否则继续往下。 将这个题变为最少需要的箱子个数是否小于等于m个。dfs（x,sum）为第x个货物分配过程（前x-1个货物已经分配好了，用了sum个箱子），用cnt数组记录每个箱子装了多少吨，ans记录最少需要多少个箱子。 对于第x个货物有两种情况： 如果货物可以放在第 i 个箱子中，那么就将 cnt[i] 加上这个货物的重量并继续递归dfs（x+1，sum） 用一个新的箱子装这个货物...

回文树学习博客：lwfcgz    poursoul   边写边更新，大概会把回文树总结在一个博客里吧...   回文树的功能 假设我们有一个串S，S下标从0开始，则回文树能做到如下几点： 1.求串S前缀0~i内本质不同回文串的个数（两个串长度不同或者长度相同且至少有一个字符不同便是本质不同） 2.求串S内每一个本质不同回文串出现的次数 3.求串S内回文串的个数（其实就是1和2结合起来） 4.求以下标i结尾的回文串的个数   每个变量的含义 1.len[i]表示编号为i的节点表示的回文串的长度（一个节点表示一个回文串） 2.next[i]...

传送门： https://www.luogu.com.cn/problem/P3046 https://ac.nowcoder.com/acm/contest/6306/G 题意 给定n个不同的点，求这个点集有多少条对称轴 题解 对于一个点只有两种情况，一种是和另一个点关于这条线对称，一种是在对称轴上。 第一种情况：随机选择一个点p，枚举其他的点和他形成的对称轴，然后再判断这个对称轴是不是点集的对称轴。 第二种情况：当点在对称轴上时，要么另一个点 q 也在对称轴上，两点所在的直线是对称轴，这种情况直接判断这个对称轴是不是点集的对称轴。要么另一个点 q 关于这个点 p 所在的直线...

传送门：cf1395D 题意 给定一个长度为n的数组a[i]为当天说话的有趣值，如果a[i]>m，那么在 i 之后有d天不能说话。否则可以每天都说话。找到一个排列使得n天有趣值总和最大，问有趣值总和的最大值是多少。 题解 很明显用贪心。先取>m的有趣值直到取不下。根据样例1的解释可以看出将一个大于m的值放在最后，前边放<m的会更优，所以此时有两种情况，如果取了的p个大于m的值p*(d+1)（p个大于m的总共占了多少天）大于n，那么就要找到最后一个能说话的天后不能说话的天数，即d-(p*(d+1)-n)，然后可以加上<m最大的前d-(p*(d+1)-n)天，相当于...

传送门：cf1395C 题意 c[i]=a[i]&b[j]，b[j]是b数组中任意一个，求c[1] | c[2] | ... | c[n]最小值。 题解 经典的二进制枚举答案，因为a和b的最大值<29 ，所以最后的结果最大是9个位置全1，不会超过210 ，故只要枚举0到210-1即可。每次答案和a[i]&b[j]的值相与，如果有一个 j 可以使相与后答案不变，那么当前a[i]可以，如果没有，那么当前答案不可以。当所有a[i]都可行，输出答案，否则继续枚举。 代码 1 #include<bits/stdc++.h> 2 using name...

A. Permutation 题意 给定一个质数p，找到一个1~p-1的排列，使得xi+1 ≡ 2xi (mod p) 或者 xi+1 ≡ 3xi (mod p)。 题解 打表找规律，可以发现 2xi (mod p) 会形成若干个环， 3xi (mod p) 也会形成若干个环。如果在x*2中的某个环里有一个数变成了x*3那么就会形成另一个环。所以要优先考虑每次*2，下一个*2形成环了就变成*3。优先*3也是可以的，但是要考虑到如果...

题意 班里有m行n列个座位，一共有d对同学紧挨着（前后或者左右）喜欢讲话，小雪可以在教室中设置了K条横向的通道，L条纵向的通道，通道可以分开挨着的同学，问通道设置在什么位置可以使班上讲话的人数最少。 题解 简单的贪心。每条通道肯定是能分开的同学越多越好，所以枚举喜欢讲话的同学，将他们之间的路记录下来，行和列用不同的数组记录，然后行和列都由大到小排序路的个数。排序后，将行中前K个路按照路的编号由小到大排序后输出这K条路，列中前L个路也同样操作。 代码 #include<bits/stdc++.h> using namespace std...

A. Groundhog and 2-Power Representation 题意 一个数可以由2x1+2x2+2x3+.....组成，例如1315=210+28+25+2+1=2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0). 现在给出一个由2的次幂组成的表达式，输出这个数是多少。 题解 不得不说py真的强，看到不到2分钟就有人a了，还以为是原题，赛后发现py三行。（暴风哭泣 我队用的c++高精度模拟写的，队友%%% 代码 py n = input() n =&n...

题意 对于直线y=ax+b，给出n个的a[i]和b[i]。m次询问，每次询问给出直线y=cx+d的c[i]和d[i]，如果和给出的n个直线交点的最大横坐标>0，则输出横坐标，否则输出 No cross。 题解 y=ax+b    ① y=cx+d    ② 联立①②得：x = - (b-d) / (a-c) = (b-d) / (-a-(-c))。 可以看出 x 就是将所有的横坐标取相反数之后点 (-a,b) 和点(-c,d) 所在的直线的斜率，那么问题就转换成了求最大斜率。 这个问题可以用凸包求...