hdu专题
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)
到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)
求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
hdu 2093 考试排名（sscanf）
模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()"，有时候又没有。而它也不会给我们提示。 这种情况下，就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和
hdu 2602 and poj 3624(01背包)
01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
hdu 1754 I Hate It（线段树，单点更新，区间最值）
题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
hdu 1166 敌兵布阵（树状数组 or 线段树）
题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
hdu 3790 (单源最短路dijkstra）
题意： 每条边都有长度d 和花费p，给你起点s 终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。 解析： 考察对dijkstra的理解。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin
hdu 2489 (dfs枚举 + prim)
题意： 对于一棵顶点和边都有权值的树，使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值，找到一个该图含有m 个顶点的子图，并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析： 因为数据量不大，先用dfs枚举搭配出m个子节点，算出点和，然后套个prim算出边和，每次比较大小即可。 dfs没有写好，A的老泪纵横。 错在把index在d
hdu 1102 uva 10397（最小生成树prim）
hdu 1102: 题意： 给一个邻接矩阵，给一些村庄间已经修的路，问最小生成树。 解析： 把已经修的路的权值改为0，套个prim（）。 注意prim 最外层循坏为n-1。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri
hdu 1285（拓扑排序）
题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
poj 2104 and hdu 2665 划分树模板入门题
题意： 给一个数组n（1e5）个数，给一个范围（fr， to， k），求这个范围中第k大的数。 解析： 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码： poj 2104： #include <iostream>#include <cstdio>#include <cstdlib>#include <al
hdu 4517 floyd+记忆化搜索
题意： 有n（100）个景点，m（1000）条路，时间限制为t（300），起点s，终点e。 访问每个景点需要时间cost_i，每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问，并且当前点的访问价值应该严格大于前一个访问的点。 现在求，从起点出发，到达终点，在时间限制内，能得到的最大
hdu 4565 推倒公式+矩阵快速幂
题意 求下式的值： Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中： 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令： An=(a+b√)n A_n = (a +
hdu 3065 AC自动机 匹配串编号以及出现次数
题意： 仍旧是天朝语题。 Input 第一行，一个整数N（1<=N<=1000），表示病毒特征码的个数。 接下来N行，每行表示一个病毒特征码，特征码字符串长度在1—50之间，并且只包含“英文大写字符”。任意两个病毒特征码，不会完全相同。 在这之后一行，表示“万恶之源”网站源码，源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符（不包括回车）。
HDU 2159 二维完全背包
FATE 最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能
hdu 1569 and hdu 3657 最小割
hdu1569 给你一个m*n的格子的棋盘，每个格子里面有一个非负数。 从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的2个格子不能相邻，并且取出的数的和最大。 按国际象棋黑白染色,源点到黑点容量为数字,黑点到它周围的白点容量为无穷,白点到汇点容量为数字,最后答案为总值减去最小割（摘自网上）。 （行+列）= 奇数 黑子 连T （行+列）= 偶数 白子
hdu 2907 凹陷面
给定一个多边形，让你求出其价值。价值的定义是：-p*凹面的个数+q*凸面的个数。。。最小值为0 凸面的个数就是凸包中的点的个数，但是当出现凹面时，就会减少一个凸面，这是因为这时候的凸面是虚拟出来的！！！！！ 题意参考这里 点击打开链接 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;ret
HDU 1392 HDU 1348 凸包
求凸包的周长， 注意n=1 ， 2时特殊情况 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}frien
HDU 5833 高斯消元
n个数，任选>=1个数相乘，使得乘积是完全平方数。 其实就是开关，控制灯泡。 数 ----第i个质因子p的个数%2 = {1 ， 0} == 开关----第i个灯泡 = {开 ， 关} 最后使得所有灯泡都是灭着的方案数 = 2^自由变元个数 全部关着的情况 == 一个数也不选 应省去 import java.io.BufferedReader;
HDU 1560 IDA*
给出ｎ个串，求最短公共串（不要求连续） h ，最少还需要多长来匹配所有。 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;imp
hdu 6198 dfs枚举找规律+矩阵乘法
number number number Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence F : ⋅ F0=0,F1=1 ; ⋅ Fn=Fn
【hdu】Just a Hook（线段树区间修改）
线段树模板题，练的是懒惰标记。 懒惰标记，就是更新一段区间的时候，如果小区间被包含在了所需要更新的区间里面，那么直接对代表这个区间的数组元素赋值，之后做一个标记（表示这个区间的子区间都需要更新）但是不继续递归（这样可以节省很多的时候）。 116571152014-09-15 14:17:26Accepted1698796MS2380K1750 BG++KinderRiven #
【hdu】Billboard（线段树)
线段树的区间最大值问题，边界特殊处理一下。 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<queue>#include<vector>using namespace std;#define maxn 222222int tree[maxn << 2];int w,
【Hdu】Minimum Inversion Number(逆序，线段树)
利用线段树在nlogn的时间复杂度内求一段数的逆序。 由于给的序列是由0 ~ n -1组成的，求出初始的逆序之后可以递推出移动之后的逆序数。 #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const in
【hdu】I Hate It（线段树，结点修改求区间最大值）
线段树的模板题，还是二分递归。 #include <iostream>#include <cstdlib>#include <cstdio>#include <string>#include <cstring>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>#incl
【hdu】敌兵布阵（线段树，更加结点，区间求和）
最近开始刷线段树，主要围绕notonlysuccess的线段树总结刷。 结点修改还是比较简单的，不需要什么懒惰标记，直接二分递归就可以了。 #include <iostream>#include <cstdlib>#include <cstdio>#include <string>#include <cstring>#include <cmath>#include <vecto