• 等级
  • 5311 访问
  • 139 原创
  • 0 转发
  • 42499 排名
  • 3 评论
  • 1 获赞

hiho一下 第四十二周 (快速幂+状压)

http://hihocoder.com/contest/hiho42/problems 题意: 求一个3xN的矩形有1x2的骨牌覆盖有多少种方法 思路: 咋一看有点像轮廓线dp,但是因为N的范围太大,若果使用O(n)的算法会超时,所以可以观察矩形, 与轮廓线类似,假设使用dp,是从左到右,从上到下,那么对于第i行,那么前面的i-1行就都已经dp完毕 比如这么一个矩形,前面绿色的是已经dp完毕的,...

2018-12-09 21:21:09

hiho一下 第四十周 三分·三分求极值

http://hihocoder.com/contest/hiho40/problem/1 三分法 三分法思路与二分法一致 AC代码: #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; const int Mod = 1e9 + 7; const int INF = 0x3f3f3f3f...

2018-11-29 15:46:09

hiho一下 第三十九周 二分·归并排序之逆序对

http://hihocoder.com/contest/hiho39/problem/1 分治法求逆序数 套用归并排序并且记个数即可 AC代码: #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; const int Mod = 1e9 + 7; const int INF = 0x3f...

2018-11-29 14:53:53

hiho一下 第三十六周 二分·二分查找

http://hihocoder.com/contest/hiho36/problem/1 题意: 给你一个无序的数组,问一个元素是第几位小 思路: 可以直接暴力找一下,但是也是可以借此练一下二分 按照这个思路,选出一个Mid,然后二分,这个Mid的选择可以参照快排的写法 int Partition(int l, int r) { int i = l, j = r; Point ...

2018-11-28 21:19:07

hiho一下 第三十五周 二分图三·二分图最小点覆盖和最大独立集

http://hihocoder.com/contest/hiho35/problem/1 主要是这两个定理: 最小点覆盖 == 最大匹配 最大独立集 == 点数- 最大匹配 AC代码: #include <bits/stdc++.h> using namespace std; const int maxn = 1e3 + 5; const int Mod = 1e9 + 7;...

2018-11-27 17:48:02

hiho一下 第三十四周 (匈牙利算法)

http://hihocoder.com/contest/hiho34/problem/1 匈牙利算法解决最大匹配问题,可以参考这篇博客 https://blog.csdn.net/sunny_hun/article/details/80627351 思路: 因为这道题的男女性别不知道,所以要先求出男女关系,然后利用匈牙利算法求解 AC代码: #include <bits/stdc++.h&...

2018-11-26 19:07:43

hiho一下 第二十九周(最小堆优化Prim)

http://hihocoder.com/contest/hiho29/problem/1 AC代码: #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; const int Mod = 1e9 + 7; const int INF = 0x3f3f3f3f; #define LL long...

2018-11-22 18:32:33

hohor一下第二十八周 (堆)

http://hihocoder.com/contest/hiho28/problem/1 堆的形状是一个完全二叉树,对于最大堆任意根的权值大于左右孩子的权值,而最小堆的任意根的权值小于左右孩子的权值 这里演示的是最大堆 当插入一个值的时候,把这个值添加到堆尾中,然后向上调整 void up(int p) { int q = p/2;//当前节点尾p,父节点尾q int a = H...

2018-11-22 17:19:41

hiho一下 第二十二周 (线段树)

http://hihocoder.com/contest/hiho22/problem/1 题意: 线段树的区间修改,修改包括两个操作,1是区间[L,R]变成某个数字,0是区间加上某个数字 思路: 与平时的线段树类似,但是懒惰标记变为两个,一个记录变化,一个记录加上的值,然后重写下传函数,先判断是否有清除标记,再判断是否有加上标记,因为如果一个先清除再加,那么她的子节点页同样先清除再加,注意清除的...

2018-11-19 17:52:33

hihor一下第二十一周 (离散化)

http://hihocoder.com/contest/hiho21/problem/1 主要是线段树离散化后节点表示的意义不同 AC代码: #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; const int Mod = 1e9 + 7; #define LL long long ...

2018-11-18 17:37:13

hihor一下 第十六周(RMQ_ST)

http://hihocoder.com/contest/hiho16/problems 线段树好像过不了,而且还卡cin,cout -_- ST算法就是用二维数组存储当前位置的2j2^j2j的区间的最小值 而且由递推公式 dp[i][j]=min(dp[i][j−1],dp[i+2(j−1)][j−1])dp[i][j] = min(dp[i][j - 1], dp[i + 2^(j - 1)]...

2018-11-16 19:37:53

LCA 模板

#include <iostream> #include <string.h> #include <string> #include <math.h> #include <stdlib.h> #include <vector> #include &

2018-11-14 22:26:40

hiho一下第十二周(树形dp)

http://hihocoder.com/contest/hiho12/problem/1 题意: 一棵树,由N个节点,每个节点有一个权值,求有根结点为根节点且节点为M的子树的最大值 思路: 这道题可以利用树形dp和01背包的思想,由叶子结点的父节点t开始: 假设以这个节点为根节点的子树的大小为{M–1},那么他子树节点个数的和就为{M–2},可以遍历t的子树节点J个数{M–2}(从大到小遍历,类...

2018-11-14 19:16:27

HDU - 4804 Campus Design (轮廓线dp)

http://acm.hdu.edu.cn/showproblem.php?pid=4804 题意: 与前一道类似,只是多了一个1X1的方块,而且1X1的方块在[C,D]中间。 思路: 按照之前的分析方法分析,发现在总有在上方为1的时候与以前不用,多了个填充1X1的方块,那么就可以直接套用之前的代码,稍作修改即可 最后求和的时候是求1X1的方块在[C,D]之间的数量,相加即可 #include&l...

2018-11-11 13:51:57

POJ 2411 Mondriaan's Dream (轮廓线dp)

题意: 给你一个NM的棋盘,用12的骨牌填充,问又多少中填充方法 思路: 一开始不知道轮廓线dp,看了大佬们的博客才知道, 轮廓线dp就是用状压表示行的状态,但是这个状态并不是一行的状态,而是边缘的状态 像这样dp[i][s],s表示的就是状态。 知道了这个概念的话,那么来看这道题,首先,每一个方块都有两种可能一种是向下,一种是向右,而如果用0表示在这种状态下此方块没有被覆盖到,那么1就表示被覆...

2018-11-10 20:33:07

hihoCoder 第八周 状态压缩一

http://hihocoder.com/problemset/solution/1419821 题意: 求一个序列,连续M个数字不能又超过Q个数字被选中,求选中数字的最大之和 思路: 利用dp[i][j]来表示,第i个数字,j表示,前面M个数字的x选中的状态用二进制01串表示,二进制为j, 状态转移方程为 if(Judge(j) > Q) { dp[i][j...

2018-11-10 12:17:13

hihoCoder Trie图(AC自动机)

http://hihocoder.com/contest/hiho4/problem/1 原来AC自动机是Trie图啊。。。 Trie图与KMP的作用相似,都是求字符串匹配,而且感觉求法也是类似,不过KMP是单个模式串求匹配,Trie图是多个模式串求匹配,为了实现这个功能,Tire图多了一个前缀指针,类似KMP的失配数组 首先按照Tire树建立好一个树,然后按照深度优先求取前面深度的前缀指针,这个...

2018-11-09 19:34:41

hihoCoder 第二周 Trie

http://hihocoder.com/contest/hiho2/problem/1 Trie(字典树) 在字典树里记录一下子树的个数,输出就可以了 模板: #include<bits/stdc++.h> using namespace std; #define LL long long const int inf = 0x3f3f3f3f; const int maxn = 1e...

2018-11-07 19:22:31

hihoCoder 第一周 最长回文串

http://hihocoder.com/contest/hiho1/problem/1 最长回文串,这里主要是Manacher算法 给定一个字符串,求出最长的回文串,一般会想到的是遍历中点,向两边扩展,但是这种方法对于极限情况每个点都被遍历了n次,是一个复杂度很高的算法,而Manacher算法为了解决这个问题,首先是把字符串扩展成一个新串,在每一字符的两边加入一个特殊字符,然后又引入了一个len...

2018-11-06 18:24:36

HDU - 6403 Card Game(基环树 +dp)

http://acm.hdu.edu.cn/showproblem.php?pid=6403 题意: 有N个卡片,每个卡片正面个背面都有一个数值,问需要反转几次卡片才能使得正面的不同的数字 思路: 可以把卡片的正面和背面连一条无向边,这时就把模型变成了树,树可能有多颗,这时如果把每一个点的入度变为1的话, 那么需要反转的反边就是反转卡片的数量。 如果一个数的边数>点数,那么这个数至少有一个点...

2018-11-04 18:35:41

henu_jizhideqingwa

关注
奖章
  • 持之以恒