哒哒哒哒哒

分类

最小生成树(1) 最短路(1) 未归档(121) 题解(2)

/ 注册

全部文章（共125篇）

The Cow Lexicon POJ - 3267 dp

　　题意给出一个母串和一个字典问母串最少删去几个字母删去后的母串是由字典里面的单词拼起来的　　思路：dp[i]表示从i到母串结尾最少需要删除多少个字母初始化dp[length]=0 最坏情况dp[i]=dp[i+1]+1 　　状态转移方程 dp[i]=min(dp[i]...

2019-01-12

0 445

Dividing POJ - 1014 多重背包二进制优化

多重背包模型写的时候漏了一个等号找了半天 i<<=1 ！！！！！！ 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespac...

2019-01-12

0 453

Cash Machine POJ - 1276 多重背包二进制优化

题意：多重背包模型 n种物品每个m个问背包容量下最多拿多少这里要用二进制优化不然会超时 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using name...

2019-01-12

0 446

Girls and Boys HDU - 1068 二分图匹配（匈牙利）+最大独立集证明

最大独立集证明参考：https://blog.csdn.net/qq_34564984/article/details/52778763 最大独立集证明：上图，我们用两个红色的点覆盖了所有边。我们证明的前提条件是已经达到最小覆盖。即条件1.已经覆盖所有边，条件2.所...

2019-01-11

0 564

Colored Sticks POJ - 2513 并查集+欧拉通路+字典树hash

题意：给出很多很多很多很多个棒子左右各有颜色（给出的是单词）相同颜色的可以接在一起，问是否存在一种方法可以使得所以棒子连在一起思路:就是一个判欧拉通路的题目，欧拉通路存在:没奇度顶点或者只有2个奇度顶点同时要连通。关键在于给颜色hash和判断连通性 hash用字典树...

2019-01-11

0 417

Repository HDU - 2846 字典树

　　题意：给出很多很多很多很多个单词类似搜索引擎一下输入一个单词判断有一个字符串包含这个单词　　思路：字典树变体，把每个单词的后缀都扔字典树里面，这里要注意dd是一个单词但是把d 和dd都放字典树　　拿d匹配这一个单词会匹配两次所以要开个数组记录一下上一个使该位置数量加一的字符串...

2019-01-10

0 425

Phone List HDU - 1671 字典树

题意：给出一堆一组一组的数字判断有没有哪一个是另外一个的前缀思路：字典树插入的同时进行判断不过当处理一组数字的时候需要考虑的有两点1.是否包含了其他的序列2.是否被其他序列包含刚开始开的1e4死活不过 1e5直接过了。。 1 #include<bits/s...

2019-01-10

0 404

Hat’s Words HDU - 1247 字典树

题意：给出数个单词输出单词如果该单词是由字典中的单词组成的思路:字典树先把全部建树然后对于每一个单词进行分割，分别拿两半到字典树里面去找小心RE！ 1 #include<bits/stdc++.h> 2 #include<string> 3 ...

2019-01-10

0 325

HDU1800 字典树写法

　题意：高级魔法师可以教低级魔法师魔法扫把技能，同时教会了的低级魔法师又可以教比他更低级是，是传递的关系同时如果教会了的话，他们可以同时坐一个扫把问最少需要多少个扫把思路：就是判断相同的数字最多的是几个他们分别乘坐一个扫把，这样其他的也能合理分配进这几个扫把坑：这里刚开始数组开得...

2019-01-10

0 543

HDU1075 字典树板子题

题意：给出两组字符串一一映射，给出一种组成的文字，要求映射成另外一种思路：使用字典树，把映射的另外一个字符存在字典树的单词节点处例如 abc 123 则把123存在abc节点中的c处即可同时这里使用的是静态的数组，操作和写起来都更方便，就是要提前判断开的空间，过大过小都会有莫名其妙...

2019-01-10

0 459