hiho专题

HIHO #1190 : 连通性·四（点的双联通分量）

题目链接点的双联通分量，不注意写出了一个bug，找了2个多小时= =，我的边存的是0开始的，然后ans数组一开始也是0，然后就是if的地方。。。。。还是tarjan的算法，结合提示，这里需要存边，然后栈里面保存的是边，而不是点，这里我用边在边集es中的编号，作为边的标志 #include<bits/stdc++.h>using namespace std;#define cl(a,b

HIHO #1185 : 连通性·三

题目链接先使用tarjan算法，计算强连通分量，进行缩点成DAG，然后在使用拓扑排序计算 tarjan中，我们只需要从1号节点计算，因为开始时在1号点。建立新图的过程中，1号点不能到达的点也不用建立到新图里面 #include<bits/stdc++.h>using namespace std;#define cl(a,b) memset(a,b,sizeof(a))#defin

HIHO #1184 : 连通性二·边的双连通分量

题目链接 Tarjan算法，介绍可以看题目讲解，很好很清楚无向图边的双联通分量的定义：对于一个无向图的子图，当删除其中任意一条边后，不改变图内点的连通性，这样的子图叫做边的双连通子图。而当子图的边数达到最大时，叫做边的双连通分量。或者说，对于一个连通图，如果任意两点至少存在两条”边不重复”的路径。也就是要去每条边至少在一个简单的环中，也就是说所有的边都不是桥同样是2个方法： 1）题

HIHO #1183 : 连通性一·割边与割点

题目链接使用Tarjan算法计算无向图的割点和桥，提示讲解的也很清晰需要注意的是，某一个割点可能会被多次计算，所以一般是先记录然后最后统一输出 1）按照题目的伪代码直接实现 2）稍微优化一下的，省一些空间 #include<bits/stdc++.h>using namespace std;#define cl(a,b) memset(a,b,sizeof(a))#define

HIHO #1182 : 欧拉路·三（有向图输出欧拉路径）

题目链接 A)建图是巧妙，使用边表示每一个数字，那么就是走完每一个边一次再回到起点，便是求欧拉回路 B)建图是有向图，建图需要注意，同时，输出的时候逆序输出 C)path保存的是完整的路径，输出的时候只需&1即可 #include<bits/stdc++.h>using namespace std;#define cl(a,b) memset(a,b,sizeof(a))#defin

HIHO #1181 : 欧拉路·二（fleury算法输出欧拉路径）

题目链接伪代码 DFS(u):While (u存在未被删除的边e(u,v))删除边e(u,v)DFS(v)EndPathSize ← PathSize + 1Path[ PathSize ] ← u 点之间可能存在多条边，所以存边，然后标记每条边的标号，还是一个常见的存边的表示法 #include<bits/stdc++.h>using namespace std;#define c

hiho一下第四十九周欧拉路·一

【题目链接】：click here~~ 时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述小Hi和小Ho最近在玩一个解密类的游戏，他们需要控制角色在一片原始丛林里面探险，收集道具，并找到最后的宝藏。现在他们控制的角色来到了一个很大的湖边。湖上有N个小岛(编号1..N)，以及连接小岛的M座木桥。每座木桥上各有一个宝箱，里面似乎装着什么

hiho 1000: A+B

时间限制: 1000ms 单点时限: 1000ms 内存限制: 256MB 描述求两个整数A+B的和输入输入包含多组数据。每组数据包含两个整数A(1 ≤ A ≤ 100)和B(1 ≤ A ≤ 100)。输出对于每组数据输出A+B的和。样例输入 1 23 4 样例输出 37 代码（C语言）： #include <stdio.h>in

hiho一下第56周高斯消元

小Ho：<吧唧><吧唧><吧唧> 小Hi：小Ho，你还吃呢。想好了么? 小Ho：肿抢着呢(正想着呢)...<吞咽>...我记得这个问题上课有提到过，应该是一元一次方程组吧。我们把每一件商品的价格看作是x[1]..x[n]，第i个组合中第j件商品数量记为a[i][j]，其价格记作y[i]，则可以列出方程式： a[1][1] * x[1] + a[1][2] * x[2] + ... +

hiho #1127 : 二分图三·二分图最小点覆盖和最大独立集（无向图二分图匹配）

题目链接：点击打开链接 #1127 : 二分图三·二分图最小点覆盖和最大独立集时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述在上次安排完相亲之后又过了挺长时间，大家好像都差不多见过面了。不过相亲这个事不是说那么容易的，所以Nettle的姑姑打算收集一下之前的情况并再安排一次相亲。所以现在摆在Nettle面前的有2个问题：

hiho 1165 益智游戏（因子个数+贪心）

#1165 : 益智游戏时间限制: 20000ms 单点时限: 1000ms 内存限制: 256MB 描述幽香今天心情不错，正在和花田里的虫子玩一个益智游戏。这个游戏是这样的，对于一个数组A，幽香从A中选择一个数a，虫子从A中选择一个数b。a和b可以相同。她们的分数是a*b的因子的个数。幽香和虫子当然想要获得尽可能的高的分数，你能告诉她们应该选择哪两个数吗

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

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

hiho太阁面经算法竞赛10

题目1 : Binary Watch 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 Consider a binary watch with 5 binary digits to display hours (00 - 23) and 6 binary digits to display minutes (00 - 59). For example 11

hiho一下第六十二周题目1 : Browser Caching stl 应用

题目1 : Browser Caching 时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述 When you browse the Internet, browser usually caches some documents to reduce the time cost of fetching them from remo

hiho一下第六十一周题目1 : Combination Lock 线段树成段更新

时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述 Finally, you come to the interview room. You know that a Microsoft interviewer is in the room though the door is locked. There is a combinatio

hiho一下第六十周题目1 : String Matching Content Length dp 最长公共子序列

题目1 : String Matching Content Length 时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述 We define the matching contents in the strings of strA and strB as common substrings of the two strings

hiho一下第五十九周题目1 : Performance Log

题目1 : Performance Log 时间限制: 8000ms 单点时限: 1000ms 内存限制: 256MB 描述 You are given a txt file, which is performance logs of a single-threaded program. Each line has three columns as follow

hiho一下第五十八周 Beautiful String dp

题目1 : Beautiful String 时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述 We say a string is beautiful if it has the equal amount of 3 or more continuous letters (in increasing order.) Here are

hiho #1482 : 出勤记录II(DP)

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述小Hi的算法课老师每次上课都会统计小Hi的出勤记录。迟到会被记录一个L，缺席会被记录一个A，按时上课会被记录一个O。一学期结束，小Hi的出勤记录可以看成是一个只包含LAO的字符串，例如"OOOOLOOOLALLO……"。如果小Hi整学期缺席不超过1次，并且没有连续3次迟到，小Hi的出勤记

Hiho 数论一·Miller-Rabin质数测试，大素数判断

题目1 : 数论一·Miller-Rabin质数测试时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述小Hi和小Ho最近突然对密码学产生了兴趣，其中有个叫RSA的公钥密码算法。RSA算法的计算过程中，需要找一些很大的质数。小Ho：要如何来找出足够大的质数呢？小Hi：我倒是有一个想法，我们可以先随机一个特别大的初始奇

HIHO Coder - 1299 打折机票

描述因为思念新宿的"小姐姐"们，岛娘计划6月份再去一趟东京，不过这次看来她需要自掏腰包。经过了几天的夜战，岛娘终于在体力耗尽之前，用Python抓下了所有6月份，上海至东京的全部共 n 张机票。现在请你帮助债台高筑的岛娘筛选出符合时间区间要求的，最贵的机票。输入输入数据的第一行包含两个整数 n, m(1 ≤ n, m ≤ 105)，分别表示机票的总数，和询问的总数。接下来的 n 行，

hiho一下第九十八周题目1 : 搜索一·24点

题目1 : 搜索一·24点时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述周末，小Hi和小Ho都在家待着。在收拾完房间时，小Ho偶然发现了一副扑克，于是两人考虑用这副扑克来打发时间。小Ho：玩点什么好呢？小Hi：两个人啊，不如来玩24点怎么样，不靠运气就靠实力的游戏。小Ho：好啊，好啊。 <经过若干局游戏之后>

【hiho一下第四十二周】骨牌覆盖问题·二

原题地址：http://hihocoder.com/contest/hiho42/problem/1 2xN的骨牌问题：http://blog.csdn.net/smile_watermelon/article/details/45151175 题目描述上一周我们研究了2xN的骨牌问题，这一周我们不妨加大一下难度，研究一下3xN的骨牌问题？所以我们的题目是：对于3xN的棋盘，使用1x2

【hiho一下第四十一周】骨牌覆盖问题·一

原题地址：http://hihocoder.com/contest/hiho41/problem/1 题目描述骨牌，一种古老的玩具。今天我们要研究的是骨牌的覆盖问题：我们有一个2xN的长条形棋盘，然后用1x2的骨牌去覆盖整个棋盘。对于这个棋盘，一共有多少种不同的覆盖方法呢？举个例子，对于长度为1到3的棋盘，我们有下面几种覆盖方式：输入第1行：1个整数N。表示棋盘

hiho 完全背包（动态规划）

题目链接：点击打开还是最经典的完全背包问题，完全背包和01背包还是有区别的，完全背包中每一个物品可以选择多次，最后推出的递推公式跟01背包的基本上算是一样的，还是设一个二维数组dp[][]，dp[i+1][j]表示从前i个奖品中选出总奖券不超过j时总价值的最大值，w[]数组表示每个奖品需要的奖券数，v[]数组表示每个奖券的价值；递推关系：|dp[0][j]=0; |dp[i+1][j]=ma

hiho一下116周网络流

网络流二·最大流最小割定理时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述小Hi：在上一周的Hiho一下中我们初步讲解了网络流的概念以及常规解法，小Ho你还记得内容么？小Ho：我记得！网络流就是给定了一张图G=(V,E)，以及源点s和汇点t。每一条边e(u,v)具有容量c(u,v)。网络流的最大流问题求解的就是从s到t最多能有多少流量。