基德KID.1412
- 浏览: 319323 次
- 性别:
- 来自: 珠海
-
最新评论
-
xialluyouyue：
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294：
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412：
su1216 写道竖线代表或者，不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216：
竖线代表或者，不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu：
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
文章列表
KIDx 的解题报告
先总结下：
第一：
感觉难点在于建图
第二：
①：对于差分不等式，a - b <= c ，建一条 b 到 a 的权值为 c 的边，求的是最短路，得到的是最大值
②：对于不等式 a - b >= c ，建一条 b 到 a 的权值为 c 的边，求的是最长路，得到的是最小值
③：存在负环的话是无解
④：求不出最短路（dist[ ]没有得到更新）的话是任意解
第三：
一种建图方法：
设x[i]是第i位置（或时刻）的值（跟所求值的属性一样），那么把x[i]看成数列，前n项和为s[n]，则x[i] = s[i] - s[i-1]；
那么这样就可以最起码建立起类似这样的 ...
KIDx 的解题报告
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1410
Problem Description
枫之羽认为自己很强，想当武林盟主，于是找现任武林盟主氢氧化铜挑战。氢氧化铜欣然接受了挑战，两人约好于下个月的月圆之夜在HDU校园内的三根柱子上进行决战。这场PK赛肯定能吸引武林中所有人前来观战，所以他们找了有商业运作潜力的经济人你，让你来组织这场百年一见的世纪之战，假设两人都有一定的血HP1、HP2.HP1是枫之羽的，HP2是氢氧化铜的。他们也有一定攻击力AP1、AP2，AP1是枫之羽的，AP2是氢氧化铜的。当进行攻击时， ...
KIDx 的解题报告
题目链接：http://acm.hdu.edu.cn/diy/contest_show.php?cid=12698
首先献上模板：
#define M 505
#define inf 0x3fffffff
bool sx[M], sy[M];
int match[M], w[M][M], n, m, d, lx[M], ly[M];
//n：左集元素个数； m：右集元素个数
void init ()
{
memset (w, 0, sizeof(w)); //不一定要，求最小值一般要初始化为负无穷！
}
bool dfs (in ...
http://acm.hdu.edu.cn/showproblem.php?pid=1025
很难说清楚，自己模拟几下就会慢慢明白，模板题
求的是最长递增子序列的长度
#include <iostream>
#include <algorithm>
#include <string>
//#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include ...
KIDx 的解题报告
http://acm.hdu.edu.cn/listproblem.php?vol=31
4001：直接一个最长递增子序列模板，注意数据范围就可以了
#include <iostream>
#include <algorithm>
using namespace std;
#define L __int64
#define M 1005
struct block{
L a, b, c, d;
}x[M];
L dp[M];
bool cmp (block x, block y)
{
if ...
首先献上模板：【点都是默认为从1到n编号，用dijk和floyd时要注意重边】
①DIJK
#define inf 0x3fffffff
#define M 105
int dist[M], map[M][M], n;
bool mark[M];
void init ()
{
int i, j;
for (i = 1; i <= n; i++) //i==j的时候也可以初始化为0，只是有时候不合适
for (j = 1; j <= n; j++)
map[i][j] = inf;
}
void dijk (int u)
...
http://acm.hdu.edu.cn/showproblem.php?pid=2833
题意：求2条最短路径的最多公共点数
首先要说的是：求出最短路后，如果dist[u] + map[u][v] = dist[v]，则uv这条边必定在最短路上
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue&g ...
KIDx 的解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2962
题意：找能够到达终点的最大高度下的最短路
这样的效率排第七，，中规中矩吧，用的是前插链接表的spfa实现，当然我还开了输入外挂，此代码中木有加外挂
#include <iostream>
#include <queue>
using namespace std;
#define inf 0x3fffffff
#define M 1005
struct edge{
int v, w, h, next;
}e[200 ...
http://acm.hdu.edu.cn/showproblem.php?pid=2363
题意：求最小高度差下的最短路
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#includ ...
http://acm.hdu.edu.cn/showproblem.php?pid=1598
题意：找到从起点到终点的一条路，而且这条路经过的边的最大权值与最小权值之差最小，输出这个差
①最短路+二分枚举
二分枚举差，再枚举下界，上界=下界+差，在上下界的限制之下仍可到达终点，说明存在这么一个差，但是差还可能更小，所以继续二分
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define inf 0x3fffffff
#define ...
http://openoj.awaysoft.com/JudgeOnline/problem.php?id=1634
暗黑破坏神
Description
无聊中的小x玩起了Diablo I...
游戏的主人公有n个魔法
每个魔法分为若干个等级，第i个魔法有p[i]个等级(不包括0)
每个魔法的每个等级都有一个效果值，一个j级的i种魔法的效果值为w[i][j]
魔法升一级需要一本相应的魔法书
购买魔法书需要金币，第i个魔法的魔法书价格为c[i]
而小x只有m个金币(好孩子不用修改器)
你的任务就是帮助小x决定如何购买魔法书才能使所有魔法的效果值之和最大
开始时所有魔法为0级 效 ...
http://acm.nyist.net/JudgeOnline/problem.php?pid=362
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <stack>
#includ ...
KIDx 的解题报告
给出基本定义：
第一题：hdu 1054 Strategic Game
http://acm.hdu.edu.cn/showproblem.php?pid=1054
求：最小顶点覆盖 == 【最大匹配(双向建图)】/2
证明：最小顶点覆盖 == 最大匹配http://www.matrix67.com/blog/archives/116
第二题：hdu 1068 Girls and Boys
http://acm.hdu.edu.cn/showproblem.php?pid=1068
求：最大独立集 == |P| 减 【最大匹配(双向建图)】/2
由于只能是男女之 ...
http://acm.hdu.edu.cn/showproblem.php?pid=1026
题意：问从图的左上角到达右下角需要的最短时间，如果格子是数字n（1-9），说明有怪兽，要打死他花费n的时间
Sample Input
Sample Output
It takes 13 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3) ...
http://acm.hdu.edu.cn/showproblem.php?pid=2923
一开始题意理解错了……英语太水了
要从公司开始按所给顺序把车拉回来，是一辆一辆车拖回来……这是常识……我竟然想着最后一堆车拖回来
Sample Input
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> ...