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) 第九届蓝桥杯(2) 算法(3) 补题补题补题(55) 题解(3)

/ 注册

全部文章 / 未归档（共172篇）

HDU 1010 Tempter of the Bone(dfs+剪枝)

题意是问从S出发，终点为D，如果能刚好k步到达终点就输出YES，否则输出NO。如果直接深搜会超时，所以这里需要进行奇偶剪枝。奇偶剪枝就是比如说不考虑障碍物的情况下起点为S_x,S_y，终点为E_x,E_y，那么起点到终点的最短距离为dist=|S_x-E_x|+|S_...

2018-03-06

0 324

HDU 2516 取石子游戏(斐波那契博弈)

以这道题为例，斐波那契博弈就是有一堆石子，两个人轮流取，每次最少取一个，最多取上一次取的数目的两倍，第一次不能取完，最后取完石子的人获胜，那么如果这堆石子的数目不是斐波那契数列里的数，第一个取得人必赢。 AC代码： #include <iostream> #inc...

2018-02-25

0 383

CodeForces 940B Our Tanya is Crying Out Loud

题意：输入四个数n,k,a,b，然后有一个x刚开始等于n，然后有两种情况，如果x-=1的话需要花费a，如果x/=k的话需要花费b，问当x减到1的时候最少需要花费多少。 AC代码： #include <iostream> #include <cstdio> #define M...

2018-02-25

0 619

CodeForces 940A Points on the line

题意：给两个数n和d，然后输入n个数，问最少要删掉几个数才能让剩下的n个数的任意两个数相差不大于d AC代码： #include <iostream> #include <cstdio> #include <algorithm> #define M...

2018-02-25

0 572

HDU 4496 D-City(反向并查集)

题意是有n个点，m条边，刚开始这些边都是连着的，然后按顺序逐一破坏这些边，然后让你输出每破坏一次图中还剩几个集合，刚开始肯定是有一个集合的，最后都破坏完了就是n个集合了。讲一下思路，我们可以反向思考，从正面破坏，可以从倒着连接实现，开一个ans数组标记每次连接两个点后的...

2018-02-23

0 445

HDU 1272 小希的迷宫(并查集判断有无成环)

这是一道判断有没有成环的并查集的题，就是每两个点要有唯一的路可到达。不太懂并查集的可以看一下这篇博客传送门。说一下这道题的思路，首先要判断有没有成环的话，要先想清楚什么时候会成环。比如以这个图为例，我们输入1和2，1和3，2和4，3和4，当输入完2和4的时候现在pr...

2018-02-22

0 419

HDU 1213 How Many Tables(并查集讲解)

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

2018-02-22

0 393

CodeForces 932A Palindromic Supersequence

题意是让找回文串，输入的如果是回文串，可以直接输出，如果不是回文串，就把它改成回文串，输出的回文串没有特定的要求，所以我们可以想到直接把输入的字符串倒着再输出一遍就好了，比如输入abc，输出abccba。写法可以直接先输出一遍，然后再倒着输出一遍，当然也可以用reverse函数(字符串...

2018-02-19

0 514

CodeForces 934B A Prosperous Lot(水题)

题意就是从0-9这10个阿拉伯数字里找圈，比如0，4，6，8，9这五个数都是有圈的，其中8有两个圈，这道题就是输入一个数n，让你输出一个含有n个圈的数，当然这个数是随机的，当时没有理解题意，纠结了半天。还有就是如果没有这个数的话就输出-1，因为题目给了范围，说输出的数要小于10的18次方...

2018-02-17

0 496

CodeForces 934A A Compatible Pair

题意有两个小朋友挑灯笼(亮度)，第一个小朋友可能比较抠门，不想挑出来最亮的，所以他会藏一个灯笼，然而第二个小朋友就比较老实了，把最亮的挑出来，然后问他们两个挑出来的灯笼亮度相乘的最大值是多少。思路暴力大法好，但是当时做完过了以后瞬间被hack，这道题坑点还是挺多的...

2018-02-17

0 813