hihocoder专题

#1121 : 二分图一•二分图判定（HIHOCoder +二分图的判定）

#1121 : 二分图一•二分图判定时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述大家好，我是小Hi和小Ho的小伙伴Nettle，从这个星期开始由我来完成我们的Weekly。新年回家，又到了一年一度大龄剩男剩女的相亲时间。Nettle去姑姑家玩的时候看到了一张姑姑写的相亲情况表，上面都是姑姑介绍相亲的剩男剩女们。每行有2个名

hihoCoder #1174:拓扑排序·一

【题目链接】：click here~~ 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述由于今天上课的老师讲的特别无聊，小Hi和小Ho偷偷地聊了起来。小Ho：小Hi，你这学期有选什么课么？小Hi：挺多的，比如XXX1,XXX2还有XXX3。本来想选YYY2的，但是好像没有先选过YYY1，不能选YYY2。小Ho：先修课程真是个麻烦的东西

【hihocoder #1506 : 投掷硬币】递推

【链接】：hihocoder #1506 : 投掷硬币【题目】： 1506 : 投掷硬币时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述小Hi有一枚神奇的硬币。已知第i次投掷这枚硬币时，正面向上的概率是Pi。现在小Hi想知道如果总共投掷N次，其中恰好M次正面向上的概率是多少。输入第一行包含两个整数N和M。第二行包含N个实数P1, P

HihoCoder上网络流算法题目建模总结

经过了几天的学习和做题，我利用刘汝佳书上的网络流算法模板完成了HihoCoder上的几个网络流算法，HihoCoder可能还会继续更新网络流算法，所以我也会接着总结。这个主要是对网络流算法的建模做分析和理解，不具体分析网络流算法，网络流算法会单独总结。网络流一·Ford-Fulkerson算法题目连接本题没有建模，就是标准的网络最大流求解，将图建完后直接应用最大流算法即可解决。但在

hihocoder--数字三角形

问题描述小Hi和小Ho在经历了螃蟹先生的任务之后被奖励了一次出国旅游的机会，于是他们来到了大洋彼岸的美国。美国人民的生活非常有意思，经常会有形形色色、奇奇怪怪的活动举办，这不，小Hi和小Ho刚刚下飞机，就赶上了当地的迷宫节活动。迷宫节里展览出来的迷宫都特别的有意思，但是小Ho却相中了一个其实并不怎么像迷宫的迷宫——因为这个迷宫的奖励非常丰富~ 于是小Ho找到了小Hi，让小Hi帮助他获取尽可能

hihoCoder hiho一下第五十一周欧拉路·三

题目1 : 欧拉路·三时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述小Hi和小Ho破解了一道又一道难题，终于来到了最后一关。只要打开眼前的宝箱就可以通关这个游戏了。宝箱被一种奇怪的机关锁住：这个机关是一个圆环，一共有2^N个区域，每个区域都可以改变颜色，在黑白两种颜色之间切换。小Ho控制主角在周围探索了一下，果然

hihocoder #1175 : 拓扑排序·二

#1175 : 拓扑排序·二时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述小Hi和小Ho所在学校的校园网被黑客入侵并投放了病毒。这事在校内BBS上立刻引起了大家的讨论，当然小Hi和小Ho也参与到了其中。从大家各自了解的情况中，小Hi和小Ho整理得到了以下的信息：校园网主干是由N个节点(编号1..N)组成，这些节点之间有一些

hihocoder 1364 : 奖券兑换（多重背包）

#1364 : 奖券兑换时间限制: 20000ms 单点时限: 1000ms 内存限制: 256MB 描述小Hi在游乐园中获得了M张奖券，这些奖券可以用来兑换奖品。可供兑换的奖品一共有N件。第i件奖品需要Wi张奖券才能兑换到，其价值是Pi。小Hi使用不超过M张奖券所能兑换到的最大奖品总价值是多少？输入第一行两个整数N，M。接下来N行，每行

hihocoder #1362 : 修补木桶（二分）

时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述一只木桶能盛多少水，并不取决于桶壁上最高的那块木板，而恰恰取决于桶壁上最短的那块。已知一个木桶的桶壁由N块木板组成，第i块木板的长度为Ai。现在小Hi有一个快捷修补工具，每次可以使用修补工具将连续的不超过L块木板提高至任意高度。已知修补工具一共可以使用M次(M*L<N)，如何修补才

hihocoder #1361 : Playfair密码表

描述小Hi和小Ho经常用Playfair密码表加密自己的代码。密码表是按以下步骤生成的。 1. 随机选择一个只包含大写字母的单词S作为密钥。 2. 将S中的所有字母J替换为字母I。 3. 将S中的字母依次填写进一个5x5的矩阵，按照从上到下、从左到右的顺序填充格子。填充过程中略过已经在密码表中的字母。 4. 将'A'-'I', 'K'-'Z'(除去J之外的所有大写字母)中没

hihocoder[Offer收割]编程练习赛6及参考

题目1 : Playfair密码表时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述小Hi和小Ho经常用Playfair密码表加密自己的代码。密码表是按以下步骤生成的。随机选择一个只包含大写字母的单词S作为密钥。将S中的所有字母J替换为字母I。将S中的字母依次填写进一个5x5的矩阵，按照从上到下、从左到右的顺序填充格子。填充过程中略过已经在密码表中

hihocoder[Offer收割]编程练习赛5及参考

题目1 : 小Ho的防护盾时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述小Ho的虚拟城市正在遭受小Hi的攻击，小Hi用来攻击小Ho城市的武器是一艘歼星舰，这艘歼星舰会以T(T为大于0的整数)个单位时间的间隔向小Ho的城市轰击。歼星舰总共有N枚炮弹，其中第i枚会造成Ai点伤害值。幸好小Ho的城市有K层护盾，每层护盾可以抵挡M点伤害。当某次轰击使得伤害值

hihocoder[Offer收割]编程练习赛3及参考

题目1 : hiho密码时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述小Ho根据最近在密码学课上学习到的知识，开发出了一款hiho密码，这款密码的秘钥是这样生成的：对于一种有N个字母的语言，选择一个长度为M的单词；将组成这个单词的所有字母按照顺序不重复的写出（即遇到相同字母时跳过）；然后将字母表剩下的没有使用过的字母按照顺序在其后进行排列。如对于有5

hihoCoder挑战赛14 题目2 : 赛车树的性质

题目2 : 赛车时间限制: 20000ms 单点时限: 1000ms 内存限制: 256MB 描述幻想乡有一个赛车场。赛车场里有N个地点。同时地点之间还有单向的道路存在。这些道路使得赛车场形成了一个外向树的结构。也就是说，道路将这N个地点连成了一个有根树。并且所有的边都是从父亲指向孩子的。由于幽香喜欢刺激，每次她去赛车场都会从根节点出发，选择最长的一条路

hihoCoder挑战赛14 题目1 : 不等式

时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述给定n个关于X的不等式，问最多有多少个成立。每个不等式为如下的形式之一： X < C X <= C X = C X > C X >= C 输入第一行一个整数n。以下n行，每行一个不等式。数据范围: 1<=N<=50,0<=C<=1000 输出一行一个整数，表示最多可以同时成

hihocoder 1124 : 好矩阵 dp

好矩阵时间限制: 3000ms 单点时限: 1000ms 内存限制: 256MB 描述给定n, m。一个n × m矩阵是好矩阵当且仅当它的每个位置都是非负整数，且每行每列的和 ≤ 2。求好矩阵的个数，模109 + 7 输入第一行一个整数T，表示测试点个数。下面T个测试点。每个测试点一行，包含两个整数n，m。1 ≤ T ≤ 104. 1 ≤ n, m ≤ 1

hihoCoder- Trie树

时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。这一天，他们遇到了一本词典，于是小Hi就向小Ho提出了那个经典的问题：“小Ho，你能不能对于每一个我给出的字符串，都在这个词典里面找到以这个字符串开头的所有单词呢？” 身经百

hihoCoder 1143 : 骨牌覆盖问题·一(递推，矩阵快速幂)

【题目链接】：click here~~ 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述骨牌，一种古老的玩具。今天我们要研究的是骨牌的覆盖问题：我们有一个2xN的长条形棋盘，然后用1x2的骨牌去覆盖整个棋盘。对于这个棋盘，一共有多少种不同的覆盖方法呢？举个例子，对于长度为1到3的棋盘，我们有下面几种覆盖方式：

买零食 HihoCoder - 1272 (大爆搜DFS)

小Ho很喜欢在课间去小卖部买零食。然而不幸的是，这个学期他又有在一教的课，而一教的小卖部姐姐以冷若冰霜著称。第一次去一教小卖部买零食的时候，小Ho由于不懂事买了好一大堆东西，被小卖部姐姐给了一个“冷若冰霜”的眼神，食欲都下降了很多。从那以后，小Ho就学乖了，去小卖部买东西只敢同时买3包以内的零食，并且价格加起来必须是5的整数倍，方便小卖部姐姐算价格。但是小Ho不擅长计算，所以他把小卖部里所

基因工程 HihoCoder - 1052(有意思)

小Hi和小Ho正在进行一项基因工程实验。他们要修改一段长度为N的DNA序列，使得这段DNA上最前面的K个碱基组成的序列与最后面的K个碱基组成的序列完全一致。例如对于序列"ATCGATAC"和K=2,可以通过将第二个碱基修改为"C"使得最前面2个碱基与最后面两个碱基都为"AC"。当然还存在其他修改方法，例如将最后一个碱基改为"T"，或者直接将最前面两个和最后面两个碱基都修改为"GG"。小

hihocoder 1098 最小生成树二·Kruscal算法【最小生成树】【模板题】

hihocoder 1098 最小生成树二·Kruscal算法描述随着小Hi拥有城市数目的增加，在之间所使用的Prim算法已经无法继续使用了——但是幸运的是，经过计算机的分析，小Hi已经筛选出了一些比较适合建造道路的路线，这个数量并没有特别的大。所以问题变成了——小Hi现在手上拥有N座城市，且已知其中一些城市间建造道路的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通

hihocoder#1055 : 刷油漆算法详解以及java源码实现

原题地址详见：http://hihocoder.com/problemset/problem/1055?sid=869767 题目分析：简而言之，就是获得一棵树如果涂连续节点，节点数目一定，最终获得的最大值是多少。思路： dp[u][j]表示以节点u为根的大小为 j 的树可得到的最大分数，答案就是dp[1][m]。状态转移方程为：dp[u][j]=max(dp[v1]

hihocoder 2018-2-13

描述且说上一周的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！小Ho现在手上有M张奖券，而奖品区有N件奖品，分别标号为1到N，其中第i件奖品需要need(i)张奖券进行兑换，同时也只能兑换一次，为了使得辛苦得到的奖券不白白浪费，小Ho给每件奖品都评了分，其中第i件奖品的评分值为value(i),表示他对这件奖品的喜好值。现在他想知道，凭借他手上

hihocoder 1789 阶乘问题（数论）

http://hihocoder.com/problemset/problem/1789 求一个最大的整数 m，使得 k^m 是 n! 的约数我们可以看成是k^m*x=n！，且m为最大了，那意味着x不能拆成k*y了，所以我们就只要求n！中每个乘数拆成若干个质数相乘，然后求这些质数能组成多少个k。因为是质数，所以都是互不干扰的，不存在重复的问题。因此我们可以先求k是由哪些质数相乘

[Offer收割]编程练习赛2 hihocoder 1272 买零食 (DFS 或 dp 水题)

时间限制:5000ms 单点时限:1000ms 内存限制:256MB 描述小Ho很喜欢在课间去小卖部买零食。然而不幸的是，这个学期他又有在一教的课，而一教的小卖部姐姐以冷若冰霜著称。第一次去一教小卖部买零食的时候，小Ho由于不懂事买了好一大堆东西，被小卖部姐姐给了一个“冷若冰霜”的眼神，食欲都下降了很多。从那以后，小Ho就学乖了，去小卖部买东西只敢同时买3包以内的零食

hihocoder 1261 String Problem II (Trie树)

时间限制: 50000ms 单点时限: 5000ms 内存限制: 512MB 描述我们有一个字符串集合S，其中有N个两两不同的字符串。还有M个询问，每个询问都会先给出一个字符串w，你需要回答以下三个问题： 1. 输出所有S的串中，可以由w恰好添加两个字符得到的串中，编号最小的3个。 2. 输出所有S的串中，可以由w修改不超过2个字符得到的串中，编号最小的3个。 3. 输出所有S