cyl纤云弄巧-CSDN博客

原创算法学习kruskal

Codeforces Round #446 (Div. 1)题意有n个节点m条边的无向图图G，可以保证连通性。现在有q个询问，每个询问有k个边，判断是都在同一个最小生成树中，若存在则输出YES否则输出NO。样例输入：5 71 2 21 3 22 3 12 4 13 4 13 5 24 5 242 3 43 3 4 52 1...

2018-07-14 22:02:22 300

原创回文串算法Manacher

回文串算法Manacher首先用一个非常巧妙的方式，将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度：在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如#a#b#a#。下面以字符串12212321为例，经过上一步，变成了 S[] =

2017-12-26 20:31:46 406

原创 HDU 5371

HDU 5371题意：长度为n 的数列，现在有一种对称形式为aba (其中b与a对称)，输出满足题意的最长的数列长度。思路：用Manacher求出辅助数组Mp，然后重点来了。若想求出上面的形式，不妨枚举b的起点，那么直接判断第二个a是否满足即可，还是利用到Mp的性质。#include <iostream>#include <cstdio>#include <cstring

2017-12-26 20:31:00 377

原创 POJ1849

POJ1849题意：有一颗n个结点的带权的无向树, 在s结点放两个机器人, 这两个机器人会把树的每条边都走一遍, 但是最后机器人不要求回到出发点. 问你两个机器人走的路总长之和的最小值是多少?思路：1. 假设只有1个机器人遍历树,且要求回到原点, 它最少需要走多少路? 答: 它需要走树总长sum的两倍, 即每条树边它都要走两次才行. 这个结论画个图就明白了, 对于每条边,

2017-12-24 21:08:57 351

原创 Gym - 101522B树的直径

Gym - 101522B题意：给出一棵树，然后按照所给出的方式建立新的边，然后可以一层层的建边直到无边可建。问需要多少个小时，每一个小时可以建立一条边，可以多线程建立。思路：画图可以找到规律，最坏的情况是n个点是一个线性的，那么时间将是最长，根据线性找规律发现其长度与时间是以2倍递增的，每一个新的小时便可以在原来的基础上画2倍的线，所以找出最长边然后判断2的ans次方即可。#inc

2017-12-23 17:04:47 385

原创 Hiho 1044 状态压缩dp

Hiho 1044题意：有n个座位连续分布，现在给出限制条件m个连续座位上最多可以打扫q个位置，问最多能打扫多少垃圾。思路：对于前面的状态枚举每一种可能，对于当前状态只有两种选择，分别计算即可。#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std

2017-12-17 18:30:09 270

原创 Gym 101617H dfs + 离散化 + 枚举

Gym 101617H题意：有n个房间，m个门，k个桥，每一个门只允许特殊范围编号的人通过，问从出发点s到t可以有多少人通过。思路：读完题发现k没有什么作用。。对于这样的题在比赛的时候并没有读，太菜！从答案来看求的人数，通过题意可以发现这必然是一个连续的区间，左右端点不知道的情况下很难暴力，也无法枚举答案，因为很难验证。正解很巧妙，对于答案所在的区间必然是存在于某几个

2017-12-17 16:38:59 319

原创 Gym 101617J dp

Gym 101617J题意： n个金矿，每一个金矿都有一个初始值代表第一天里面所含的金子数量，每天减少di，现在从金矿1出发，问最多能获得多少金子。思路：时间是最难解决的问题，因为时刻在变化，但是如果能够对时间做处理，那么题目就很简单了。不妨枚举时间和前一个所在位置的状态，当时间和状态都满足的时候才可以继续走。#include <iostream>#include <cstd

2017-12-16 20:46:54 266

原创 Gym 101617Jbfs+优先队列

Gym 101617J题意： n个金矿，每一个金矿都有一个初始值代表第一天里面所含的金子数量，每天减少di，现在从金矿1出发，问最多能获得多少金子。思路：用bfs的方式思考，对于每一个状态就是沿着路径暴力搜索，利用bfs层的思想，对于采金矿的时间也是合理的，但是这样会超时，所以需要用到优化。1. 对于时间有一个最大的时间，可以通过输入算出2. 对于某一个金矿的到达存在不同的方式，记录

2017-12-15 17:49:28 368

原创 Gym 101617D dp

Gym 101617D题意：有一个nXn的图，由.和#组成，现在从1，1出发，每次跳最多k个格子，落点不能是#，问到（n，n）最少需要几步，如果无法到达则输出-1.注意只能向右和下走。思路：此题可以从dp方式来思考，当走到当前一步时，最重要的是判断从哪里开始，从上或者左，不妨开两个数组a和b分别记录行和列的信息:a[j]a[j] 保存当前j列中.所在的位置b[i]b[i] 表示能够到

2017-12-15 12:49:02 260

原创 Gym 101617D 线段树

Gym 101617D题意：有一个nXn的图，由.和#组成，现在从1，1出发，每次跳最多k个格子，落点不能是#，问到（n，n）最少需要几步，如果无法到达则输出-1.注意只能向右和下走。思路：直接bfs查询会超时，因为2000的数据会存很多点，但是如果对能到达的格子快速查找最小的步数可以用高级数据结构来完成，线段树。对于每一行和每一列用线段树维护#include <iostream

2017-12-15 12:48:33 233

原创 HDU 5459 根据题意找规律

HDU 5459 根据题意找规律题意：求一个字符串所有c字符位置到其它位置所需的步数和。思路：就根据题目的意思，如果要求出下一项则需要前两项的和加上前两项移动需要的步数，此时如果能从这里想的话就很简单了。#include <iostream>#include <cstdio>#include <cstring>using namespace std;typedef long lo

2017-12-08 19:52:59 325

原创 POJ 3167

POJ 3167题意：原串长度为n，匹配串长度为m，输出匹配串在原串中出现几次，并且输出其出现的位置。思路：利用kmp的思想，求出Next数组，求的方法是对于数字的排列存在规律，因为两个数列不同只能比较相对大小，其体现在当前数字之前的比其小的个数和与之相等的个数，预处理其存在的个数。 as[i][j]as[i][j] : 在a[i]a[i] 位置之前（包括本身）k数字存在的个数

2017-12-05 22:31:46 391

原创 HDU 3374

HDU 3374题意：字符串长度为n（n<=1000000），问从哪个位置循环是最大字符串，从哪一个字符串循环时最小字符串，如果存在多个输出最大、最小的位置以及有多少个。思路：利用kmp算出有多少个循环，便是多少个。利用最大和最小表示法求出位置，注意输出最小的位置。#include <iostream>#include <cstring>#include <cstdio>

2017-12-03 20:29:27 402

原创 HDU5442 最小（大）表示法

最小（大）表示法一个字符串扩增到两倍的时候，在0~n-1的范围中都可以通过循环找到与原字符串同构的字符串，但是其中有两个特殊的字符串，字典序最大和字典序最小（数字也可以当做字典序来处理），直接暴力找到最小或者最大的算法复杂度是O(n^2) ，有一种最小（大）表示法可以解决此问题。百度论文：https://wenku.baidu.com/view/c6c5e7335a8102d276a22fa

2017-12-02 10:12:43 316

原创 HDU 5441并查集 by cyl

HDU 5441题意：杰克喜欢旅游，从城市a到城市b是他最喜欢的，现在有n个城市m个路。当杰克在从城市a到城市b 的时候需要坐车，但是需要有等待时间t，他无法忍受超过x 的等待时间。问：给出不同的x的忍耐时间，最多有多少a->b的方式，a->b和b->a当做两种不同的方式。思路：由于x值有很多个，不能每次查找的时候都要新建立一个图，为了利用上一步的运算，不妨对询问先从

2017-11-30 21:50:45 333

原创 HDU 5438拓扑+bfs或者dfs

HDU 5438题意：有个人有p个池塘，每一个池塘有其价值，池塘之间有连接的管道，现在主人由于资金的问题，需要抛弃一些池塘，其特点是与之相邻的池塘只有一个，当然如果删除了一个池塘之后剩下的池塘仍然有类似的池塘还要接着删除。删除之后，问连通图中池塘的个数为奇数个的连通图所有池塘的价值和。思路：记录每一个池塘所连接的边，其实也就是入度，此题的边是双向的，所以直接记录即可。

2017-11-30 21:48:33 285

原创 HDU 5437by cyl优先队列

HDU 5437题意：有个人要过生日，有k个朋友来拜访，但是他家里实在是有点小，只能依次让朋友进门，有m个特定的时间，每次可以进入p个人，每一个朋友来会带礼物，价值为v。主人还是比较贪心的，他让朋友进入的条件是谁的礼物价值大谁先进，价值相等就按照拜访的顺序进入。思路：可以看出是细节题，考察了对优先队列的掌握，问题在于要猜测出题人的思路，或者说是算法不错但是无法AC的时候，多思考是不是

2017-11-30 21:44:50 282

原创 V - Digital Deletions HDU-1404

V - Digital Deletions HDU-1404题意：给出一个不超过6位的数字（有可能会出现前导零），有两种操作：1. 更改某一位的数字比其原来的小2. 如果某一位是0可以将其和之后的数字删除例如：两个人在玩游戏，谁先操作到最后谁获胜。思路：此题可以sg打表，利用最简单的性质：同样逆推局面推出胜态。用相反的操作，还原胜态。#include <iostream>#in

2017-10-19 11:12:15 275

原创 I - Ugly Problem HDU-5920

I - Ugly ProblemHDU - 5920 题意：有一个大数，长度不超过1000，现在需要分解它，并且分解出来的数字都是回文数字，求出每一个分解的个数和每一个分解的的数字。要求个数不能超过50.题意：此类题需要思维发散，向回文串的思路走的话会想到先找出一半，然后复制另一半，得到的数字必然是回文串，并且尽可能的大，当然会遇到此回文串比原串大，即应该将左边的一半减一再还原，

2017-10-16 21:46:50 260

原创 D - Weird journey

D - Weird journey题意： n个城市，m条路，现在要找出这样的路：经过m-2条路两次，其它两条路经过一次。问：有多少这样的路径。思路：一定要看清楚题。根据题意发现类似于欧拉图，根据欧拉图的定义只有满足两个条件的才能画出图，不妨把经过两次的边转化为欧拉图，根据欧拉图“一笔画”性质，可以得出肯定是相邻边，并且无论相邻节点的度是多少都能连城欧拉路，所以目的就是找出

2017-10-13 21:37:16 290

原创 C - Functions again 简单DP，需要转化

C - Functions again题意：给出一个序列，定义一个区间函数为：求出最大的值。思路：直接求没有办法求出，思考其公式，假如最终答案是区间l，r，其和最大，那么必然是正负正负正的形式，所以只需求出所有的正负情况，然后求出区间的最大子序列和即可。#include <iostream>#include <cstdio>#include <cstring>#include

2017-10-13 15:33:58 265

原创 D - Mike and distribution

D - Mike and distribution题意：有两个数列，个数相同，现在选出不超过n/2+1个数列下标，使得在每一个数列中下标的数字之和的二倍大于原数列，输出答案和下标。思路：题意是经过化简的，因为题中并没有说要选择多少个下标，只是一个范围，那么最简单的做法当然是选择越多越好。方法：思考挑选的个数，明显是大于数列个数的一半的。先对A数列做一次排序，那么从大

2017-10-12 20:26:28 245

原创 C. Mike and gcd problem

C. Mike and gcd problem题意：定义一种beautiful数列，满足gcd(b1,b2,···,bn) > 1. 现在给出一个数列A，有一种操作：对ai操作，使得a[i] = ap[i]-a[i+1],a[i+1] = a[i]+a[i+1] 问最少多少次操作使得题中满足beautiful。思路：数学题就多思考，有公式的情况下向公式思考。根据操作的方法

2017-10-12 12:02:06 290

原创 B. Mike and strings

B. Mike and strings题意：有n个相同长度的字符串，现在问是否可以通过一种操作使得恢复成一样的字符串，若能，输出最少的次数。操作：把当前字符串的第一个字母放到最后一个字母的后边。 n < 50. length < 50.思路：看到数据的范围就感觉可以暴力求，但是对于字符串的题，不要急于动手打代码。想清楚思路：成为相同的字符串

2017-10-12 12:01:26 299

原创 Codeforces Round #411 (Div. 2) E - Ice cream coloring

E - Ice cream coloring题意：有一棵树T，节点为1~n，现在有m种ice cream，每一个节点都有si种ice cream，现在新建一棵树G，节点为ice cream 的种类数，标号为1~m，边是否相连有如下规则： if and only if there exists a vertex in T that has both the v-th and the u

2017-10-11 22:19:10 251

原创 codeforces 810 D . Glad to see you!

D. Glad to see you!题意：题意往往是最难的对于弱鸡来说。简化题意如下：有n个数字1到n，现在一个人选了k个，现在让你从k个中找出两个数字，找的方法是：询问！这便是交互问题，通过询问的方式：询问三个数字1 x y，1代表问，x、y代表你想问的两个数字，另一个人会回答真正的两个数字离x、y哪一个数字最近，离x近或者两个一样近是TAK，否则是NIE。最后输出答

2017-10-09 22:01:12 526

原创 codeforces 810 C - Do you want a date?

codeforces 810C - Do you want a date?题意：有一个集合，其中有n个数字，这个集合有很多子集，现在规定每一个子集必须至少有两个数字，其中子集中两个数字最大的差值就是这个子集的函数值，现在求出所有子集的函数值的和，需要取模。思路：很容易想到枚举集合中最大的值的位置，需要对元素排序，例如在i位置和j位置（i#include <iostream>#in

2017-10-09 18:09:34 302

原创 POJ 1170 0-1背包变形

0-1背包变形题意：有n个物品，每一种物品的属性是：唯一的数字代号，数量，价格。现在有s种优惠，意味着不同的物品搭配会比原来省钱，现在要问最少花多少钱把所有的物品买下。思路：把物品当做0-1背包来考虑，即使是优惠组合也是0-1背包，那么可以直接暴力写了。#include <iostream>#include <cstdio>#include <cstring>#include

2017-09-25 19:29:16 311

原创 HDU 4055 计数dp + 排列组合

计数dp + 排列组合题意：有一列数字，当第i数字比前一个数字大的时候就可以生成一个字符I，否则就是D，现在给出字符串，求出数列有多少种排列方式，注意字符串？代表比前一个数字大小都可以。思路：此类题可以从当前第i数字是哪一个考虑。定义：dp[i][j]dp[i][j] 表示第i个数字是j的组合数。那么当第i个字符串是‘I’，dp[i][j]=sum(dp[i−1][1]+..

2017-09-22 15:21:10 344

原创 zoj 3747 排列组合dp

排列组合dp题意：现在要挑选n个士兵成为一个排列，从三个不同的军团之中，第一个军团最少u个人连续站在一起，第二个军团最多有v个士兵站在一起，问有多少种不同的挑选方式。思路：对于最多和最少问问题尽量转化为最多的问题，比如第一个军团的限制条件，那么在求的时候转化为最多有i个人。排列组合计数问题很容易从前一个状态推到当前的状态，定义:dp[i][0]dp[i][0] 表示第i个人是

2017-09-21 13:20:53 402

原创 CF B. Working out dp 递推

CF dp 递推题意：给出nxm个数字矩阵，求出从左上角到右下角的最大权值和，权值就是数字，求出从左下到右上的最大权值和，当然两条路只能交叉一个位置，并且此位置上的权值不能算入和。求出两条路的最大权值和。思路：注意边界不能作为交叉位置。终极思想是枚举相叉位置，知道位置之后只需求出每一条路是怎么走的就行，很容易得出只有两种走法，别想太多，试试就知道。那么四种走法dp求出既可。#includ

2017-09-20 21:27:23 282

1304 字符串的相似度题目来源：基准时间限制：1 秒空间限制：131072 KB 分值: 320 给出一个字符串S，计算S同他所有后缀的相似度之和。例如：S = “ababaa”，所有后缀为：ababaa 6babaa 0abaa 3baa 0aa 1a 1S同所有后缀的相似度的和 = 6 + 0 + 3 + 0 + 1 + 1 = 11Input输入一个字符串S(1 <= L <= 10000

2017-09-13 22:29:56 293

原创 HDU 6205 贪心

贪心题意：题意：给你若干堆牌，所有牌默认向下，每次从第一堆开始，将固定个数的牌翻上，然后下一堆继续，直到没有足够的牌翻上，然后你可以获得当前操作过的堆的所有牌。一开始你可以调整堆的顺序，把第一堆放到最后一堆，你可以重复这个操作，问你要重复多少次这个操作，才能获得最多的牌。思路：拿牌的开始一定是a[i]>b[i]a[i] > b[i] ，那么就从这里开始拿，每次拿都会计算出一个结果，那

2017-09-11 21:49:10 278

原创 POJ 2135 网络流MCMF入门题

网络流MCMF入门题题意： n个点，m条边，现在要从1到n走两次，边只能经过一次，问最短的距离是多少。思路：转化为网络流问题，对没一条边的最大流量为1，那么用次一次就是0，自然只能走一次。直接可以对f做出限制，相当于模板题，不过要注意的是sol.f和N，M的使用。#include <iostream>#include <stdio.h>#include <cstring>#inc

2017-09-09 21:11:22 286

原创知道前序序列和后序序列求二叉树的个数+大数

知道前序序列和后序序列求二叉树的个数+大数题意：给出一个二叉树的前序遍历和后序遍历，问有多少个满足这样结构的二叉树？思路：直接画一个最简单的二叉树，比如根节点恰好只有一个儿子，那么写出前序遍历和后序遍历会发现，根据两个遍历结构无法判断二叉树根节点的儿子是左儿子还是右儿子，那么其实只要找出这样的结构有多少个就行了，那么答案就是2的多少次方。#include <iostream>#in

2017-09-09 09:16:28 1374

原创 HDU 5985 概率问题

概率问题题意：有n种硬币，现在有一个方法可以得出一个或者一种lucky硬币，所有硬币抛下然后去掉背面朝上的，继续抛直到只剩一种硬币或者没有硬币为止。问每一种硬币成为lucky的概率是多少。思路：若想知道在某一步只剩下第i种硬币的话，需要知道其它硬币已经没有的概率。定义：die[i][j]表示第i种硬币在第j次抛全部被去掉的概率，很容易得出(1−pk)cntdie[i][j] 表示第i

2017-09-07 22:06:53 515

原创 POJ 2411 状态压缩DP

状态压缩DP题意：有n乘m 的棋盘，现在有1乘2的方块和2乘1大小的方块，问有多少种不同的组合方式。思路：这道题有很多种方法可以做，轮廓线dp和插头dp、状态压缩都行，先讲一下状态压缩方法。大神的题解：http://blog.csdn.net/u013480600/article/details/19569291两种方块方的方式有横竖两种方式可以放置，状态压缩一般压缩到二进制中用01

2017-09-06 22:23:10 370

原创 HDU 2188 博弈 + sg打表

博弈 + sg打表只要当前状态可以转移到的状态中有一个是败态，那么当前状态就是胜态。如果当前状态可以转移到的所有状态都是胜态，那么当前状态就是败态。题意：两个人玩加法游戏，谁先加到>= n,谁胜利，每次每一个人只能加1~m区间的数字。利用第二条性质，可以直接打出表。博弈真是一个妖怪！换了一道题，我竟然还用原来的方法，看来未得真谛，所以要多多思考，当前局面和必败局和必胜局的关系。

2017-08-31 10:33:51 280

原创 POJ 2505 博弈SG打表

博弈SG打表题意：两个人玩乘法游戏，每个人只能乘以2~9，谁先达到>=n谁胜，先手只能乘以1.思路： SG的：除任意一步所能转移到的子局面的SG值以外的最小非负整数。直接打表找到规律。#include <iostream>#include <cstdio>#include <cstring>#include <set>using namespace std;const int

2017-08-31 09:44:22 398

空空如也

空空如也