Charlesss

分类

ACM_RMQ(2) ACM_二分(5) ACM_二分图(8) ACM_前缀和(1) ACM_动态规划(18) ACM_干货(6) ACM_并查集(3) ACM_拓扑排序(2) ACM_搜索(24) ACM_最短路(14) ACM_树(1) ACM_树状数组(2) ACM_生成树(8) ACM_线段树(3) ACM_覆盖问题(2) ACM_连通图(2) CodeForces(131) 未归档(172) 第九届蓝桥杯(2) 算法(3) 补题补题补题(55) 题解(3)

/ 注册

全部文章（共467篇）

并查集讲解

这是我写的第一道并查集的题，也应该是一道最简单的入门题了，所以就以这道题说下并查集，其实就是找关系，比如说这道题的题意就是有n个人聚餐，然后他们不一定都互相认识，如果a认识b，b认识c，那么就让他们仨坐一桌，再如果c认识d，d认识e，那么就让这三个人另外坐一桌，所以就是有关系的就坐一桌...

2019-07-26

0 931

Manacher(马拉车)算法详解

马拉车用于解决最长回文子串问题，重点是子串，而不是子序列。对于这种问题，当然最简单粗暴的方法就是暴力求解，但太暴力也不好，毕竟会TLE。所以对于求最长回文子串的问题有一种神奇的算法——马拉车算法，神奇就神奇在时间复杂度为O(n)。我先说一下大概思路，就是用一个Len[...

2019-07-26

1 1429

二分图详解

本篇博客主要讲解什么是二分图，怎样判断二分图，匈牙利算法和HK(Hopcroft-Karp)算法，以及二分图多重匹配。二分图定义：二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的...

2019-07-26

4 3093

牛客寒假算法基础集训营6 E. 海啸(二维数组+容斥)

二维数组维护前缀和(pre[i][j] = pre[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1])，然后根据O(1)的复杂度就能算出范围内所需要的数了，给的数据范围可能没法开数组，但是可以用vector去存，还有就是用一种不太提倡的方法去开，像我...

2019-07-19

0 929

牛客寒假算法基础训练营6 I.wzoi(思维)

这是一道阅读理解题...说实话真的没看懂题，不知道为什么第二个样例不能看0 看1 写0 写1，这样不也是20吗？？但是直觉告诉我这个和括号配对差不多，然后照着样例瞎敲了份code就过了...代码的思路就是和括号配对一样，遇到两个相邻的就pop出去，否则就push进来，栈中剩下的都是配不了对的，所以除...

2019-07-19

0 828

Codeforces 562 C

题意是输入n和m，然后输入n个数，有一种操作每次选k个数，使得这k个数+1然后再取余m，问至少要多少次可以使这个序列变为非递减的序列。我们可以二分操作数，然后根据贪心去改变每个数的状态，直接看代码吧不是很难理解。 #includ...

2019-07-19

0 682

Codeforces Round #562 (Div. 2) C. Increasing by Modulo(二分+贪心)

题目链接：https://codeforces.com/contest/1169/problem/C 题意是输入n和m，然后输入n个数，有一种操作每次选k个数，使得这k个数+1然后再取余m，问至少要多少次可以使这个序列变为非递减的序列。我们可以二分操作数，然后...

2019-05-28

0 679

Codeforces Round #562 (Div. 2) B. Pair(思维)

题目链接：https://codeforces.com/contest/1169/problem/B 题意是输入n和m，然后输入m组数，输入的数都为1-n的数，然后问能否从1-n中找到两个不相同的数x和y使得这m组数中，每组都至少有一个数等于x或者等于y，如果可以输出YES，否...

2019-05-28

0 711

Codeforces Round #558 (Div. 2) C. Power Transmission(思维 map+set)

题目链接：https://codeforces.com/contest/1163/problem/C2 题意是给了n个坐标，使他们两两任意相连，然后求出他们所有的直线的相交的点数。可以想到的思路就是对于两条直线来说只要k不同就一定会有交点，所以可以想到的思路就...

2019-05-11

0 706

Codeforces Round #558 (Div. 2) B. Cat Party(思维)

题目链接：https://codeforces.com/contest/1163/problem/B2 题意是删除一个数后，求一个最大的距离x，使得1-x中的数的出现个数相同遍历每一位，对第i位维护一个1-i的所有数的出现次数，以及所有数的出现次数的出现次数，...

2019-05-11

0 721