马拉车用于解决最长回文子串问题，重点是子串，而不是子序列。对于这种问题，当然最简单粗暴的方法就是暴力求解，但太暴力也不好，毕竟会TLE。所以对于求最长回文子串的问题有一种神奇的算法——马拉车算法，神奇就神奇在时间复杂度为O(n)。        我先说一下大概思路，就是用一个Len[i]数组去存第i个位置到mx位置的长度，然后用id记录上一次操作的位置，mx标记上一次的最长子串的最右端，然后依次去递推。不太好理解(花了好几个小时才懂)，现在看不懂没关系，我尽量讲的详细点。        以hihoCoder的一道裸题为例，只要能AC就差不多懂了，题目链接：http://hih...

       本篇博客主要讲解什么是二分图，怎样判断二分图，匈牙利算法和HK(Hopcroft-Karp)算法，以及二分图多重匹配。 二分图定义：        二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。 二分图匹配：         给定一个二分图...

二维数组维护前缀和(pre[i][j] = pre[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1])，然后根据O(1)的复杂度就能算出范围内所需要的数了，给的数据范围可能没法开数组，但是可以用vector去存，还有就是用一种不太提倡的方法去开，像我的代码一样(官方题解说开一个指针数组，然后new一个...不会)。其他的主要就是一个容斥原理。 #include <bits/stdc++.h> #define ll long long using namespace std; int n,m,d,t;   int ...

这是一道阅读理解题...说实话真的没看懂题，不知道为什么第二个样例不能看0 看1 写0 写1，这样不也是20吗？？但是直觉告诉我这个和括号配对差不多，然后照着样例瞎敲了份code就过了...代码的思路就是和括号配对一样，遇到两个相邻的就pop出去，否则就push进来，栈中剩下的都是配不了对的，所以除以2乘5就是得分。如果有理解题意的麻烦给我讲一下.... #include <bits/stdc++.h> using namespace std;   int main() {   string str;   cin>>str; &n...

题意是输入n和m，然后输入n个数，有一种操作每次选k个数，使得这k个数+1然后再取余m，问至少要多少次可以使这个序列变为非递减的序列。        我们可以二分操作数，然后根据贪心去改变每个数的状态，直接看代码吧不是很难理解。 #include <bits/stdc++.h> #define ll long long #define maxn 300005 using namespace std; int pre[maxn], a[maxn]; int n,m;   bool Check(int x){ &nbsp...

  题目链接：https://codeforces.com/contest/1169/problem/C        题意是输入n和m，然后输入n个数，有一种操作每次选k个数，使得这k个数+1然后再取余m，问至少要多少次可以使这个序列变为非递减的序列。        我们可以二分操作数，然后根据贪心去改变每个数的状态，直接看代码吧不是很难理解。 AC代码： #include <bits/stdc++.h> #define ll long long #define maxn 300005 using namespace std; int pre[maxn], a[ma...

  题目链接：https://codeforces.com/contest/1169/problem/B        题意是输入n和m，然后输入m组数，输入的数都为1-n的数，然后问能否从1-n中找到两个不相同的数x和y使得这m组数中，每组都至少有一个数等于x或者等于y，如果可以输出YES，否则输出NO。        思路大致就是暴力，但是最简单的暴力的时间复杂度应该是n^2*m的，所以需要换一种思路，用ma来存每个数出现的次数，我们枚举x和y中的x，然后看有多少组数中含有x，然后我们去寻找出现了m-ma[x]次数的数，大致的思路就是这样，然后需要处理一个容斥的问题，就是我们在找x和...

  题目链接：https://codeforces.com/contest/1163/problem/C2        题意是给了n个坐标，使他们两两任意相连，然后求出他们所有的直线的相交的点数。        可以想到的思路就是对于两条直线来说只要k不同就一定会有交点，所以可以想到的思路就是求出所有的直线的斜率，然后两两比较就好了，因为C1的数据范围只有50，所以直接这一暴力就可以写，对于多点共线的情况我们只需要保留一条直线就行了。C2的数据范围是1000，用C1的做法肯定是不行的，其实可以想到对于一条直线来说，它的交点的个数就是不在这条直线上的点的个数，按找这个思路，用map+se...

  题目链接：https://codeforces.com/contest/1163/problem/B2        题意是删除一个数后，求一个最大的距离x，使得1-x中的数的出现个数相同        遍历每一位，对第i位维护一个1-i的所有数的出现次数，以及所有数的出现次数的出现次数，然后讨论一下情况就好了，比较绕。 AC代码： #include <bits/stdc++.h> #define ll long long #define maxn 100005 using namespace std; ll pre[maxn]; int n; int main...

  题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3791        直接按第一个序列建二叉搜索树，然后接下来每一个需要判断的字符串都要建一个二叉搜索树，然后遍历一遍判断两个二叉搜索树是否相同就好了，需要注意的是最后遍历二叉搜索树的数据范围。 AC代码： #include <bits/stdc++.h> #define maxn 10005 using namespace std; string str; int a[maxn], b[maxn]; int n; void insert(int x, int pre[...

          嗯...就是贴个板子   #include <bits/stdc++.h> using namespace std; struct node{ int num; node *p, *l, *r; }; node *root, *null; int n, xx; string str; void p_inorder(node *x){ // 中序遍历 if(x == null) return ; p_inorder(x -> l); printf(" %d", x -> num); p_inorder(...

  题目链接：https://codeforces.com/contest/1155/problem/D        题意是给了n个数，可以选择一个子区间，使得这个区间内的每一个数乘x，然后求一个和最大的子区间的值。        思路就是dp，对于一个区间有三种情况：                1. 选择这个数          2. 选择这个数乘x         3. 选择这个数，但是之前出现过了乘x的区间        然后更新这个过程中的最大值就好了。 AC代码： #include <bits/stdc++.h> #define ll long l...

  题目链接：https://codeforces.com/contest/1119/problem/C        题意是给了两个n*m的矩阵，可以对第一个矩阵进行操作，可以选择任意个子矩阵使其四个角的值取反，问是否能变为第二个矩阵。        如果一行或者一列的不同的个数是奇数肯定就不行，所以按这个思路扫两遍就好了。 AC代码： #include <bits/stdc++.h> #define maxn 505 using namespace std; int a[maxn][maxn], b[maxn][maxn]; int n,m; int main(...

  题目链接：https://codeforces.com/contest/1119/problem/B        题意是给了n个水瓶，一个高度h，现在要把这n个水瓶按顺序放到h*2的柜子里，柜子里可以有任意多个挡板(每个挡板上只能放2个水瓶)，问最多可以放多少个水瓶。        思路就是二分能放多少个水瓶，将二分的值传入Check，将前mid的水瓶从大到小排下序，然后依次减就好了，直接看呆码好理解点。(感觉不会爆int啊...但是不开ll就wa10... AC代码： #include <bits/stdc++.h> #define maxn 1005 #de...