- 浏览: 308646 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
KIDx 的解题报告
题目链接:http://acm.hdu.edu.cn/diy/contest_show.php?cid=12698
首先献上模板:
第一题:http://acm.hdu.edu.cn/showproblem.php?pid=2255
直接输入w[i][j]边权值建图套模板就可以了
第二题:http://acm.hdu.edu.cn/showproblem.php?pid=1533
将m的坐标记录到左集,h的坐标记录到右集,w[i][j]表示第i个m到第j个h的距离
w[i][j]=△x+△y 然后因为是求最小值,而KM是求最大值
所以只要这样:w[i][j] = -w[i][j]建图再套模板输出【-sum】就ok!
第三题:http://acm.hdu.edu.cn/showproblem.php?pid=1853
直接建图,注意有重边哦!
if (-c > w[a][b])
w[a][b] = -c;
当木有完美匹配输出-1
第四题:http://acm.hdu.edu.cn/showproblem.php?pid=3488
跟第三题几乎一样
第五题:http://acm.hdu.edu.cn/showproblem.php?pid=3435
跟第三题代码基本上一样,只是要双向建图,也有重边
第六题:http://acm.hdu.edu.cn/showproblem.php?pid=2426
左集是学生,右集是房子,注意 w[i][j] < 0 不可匹配,最后无法完美匹配输出-1
第七题:http://acm.hdu.edu.cn/showproblem.php?pid=2853
题目要求匹配最大值和至少要改变多少个原有匹配
思路:让原有匹配更有优势就可以了
实现:所有权值扩大100倍,原有匹配【例如a匹配b】w[a][b]++
设结果是res
最大值:res/100
至少改变个数:n - res%100
第八题:http://acm.hdu.edu.cn/showproblem.php?pid=3718
题目求的是两字符串的最大相似度
思路:因为第一个串的一种字母只能匹配第二个串的一种字母,所以可以转化为求
【字母的最大匹配值/n】
建图:【例】
第九题:http://acm.hdu.edu.cn/showproblem.php?pid=3722
直接按题目要求建图,注意跟自己匹配的值是0,w[i][i]=0
第十题:http://acm.hdu.edu.cn/showproblem.php?pid=3395
直接按题目要求建图就可以了
第十一题:http://acm.hdu.edu.cn/showproblem.php?pid=2282
建图:多余的1分别跟所有的0算出最小距离,例如3,多了2个1,要把他们跟所有0匹配,左集是1,右集是这n个数【限制匹配条件(=0)就可以了】
左集个数为m,表示有多少个1需要移动
m = 0;
for (i = 0; i < n; i++)
{
if (a[i] > 1)
{
for (j = 1; j < a[i]; j++)
{
for (k = 0; k < n; k++)
if (a[k] == 0)
w[m][k] = -min (abs(k-i), n-abs(k-i));
m++;
}
}
}
第十二题:http://acm.hdu.edu.cn/showproblem.php?pid=2813
这题比较容易超时……
用STL的map把字符串映射为序号
m1.clear();
m2.clear();
k1 = k2 = 1;
while (q--)
{
scanf ("%s%s%d", s, p, &x);
string a(s);
string b(p);
if (m1[a] == 0)
m1[a] = k1++;
if (m2[b] == 0)
m2[b] = k2++;
w[m1[a]][m2[b]] = -x;
}
第十三题:http://acm.hdu.edu.cn/showproblem.php?pid=2448
这题要读懂题目意思!
题意:n艘船要分别回到n个码头,另外有m个采矿点,一开始n艘船所在采矿点已经给出,采矿点与采矿点之间给出k条路【双向的】,码头与采矿点之间给出p条路,由于船进入码头后就不会出来,所以这条路是单向的!
实现:最短路+KM
第十四题:http://acm.hdu.edu.cn/showproblem.php?pid=2236
题意:n×n的矩阵中,没行找一个元素,每个元素之间不可同列,求这n个元素的最大值-最小值的最小差
思路:暴力枚举差值【由于元素的值0<= x <=100, 差值的范围也只能是[0,100]】
匈牙利检验就可以了
bool KM (int low, int high)
{
int i;
memset (match, -1, sizeof(match));
for (i = 0; i < n; i++)
{
memset (vis, false, sizeof(vis));
if (!dfs (i, low, high))
return false;
}
return true;
}
第十五题:http://acm.hdu.edu.cn/showproblem.php?pid=3315
默认匹配是w[i][i]
si打赢xj,w[i][j] = v[i]
如果si输了,w[i][j] = -v[i]
所有权值扩大100倍,w[i][i]++优先匹配
相似度=(res%100*100/n)%
先将矩阵中的元素不重复地存放到num数组中,然后枚举
for (i = 0; i <= 100; i++)
for (j = 0; j < k; j++)
if (KM (num[j], num[j]+i))
goto end;
踩踩更健康
题目链接: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 (int u) { int v; sx[u] = true; for (v = 0; v < m; v++) { if (!sy[v] && lx[u]+ly[v]==w[u][v]) { sy[v] = true; if (match[v] == -1 || dfs (match[v])) { match[v] = u; return true; } } } return false; } int KM () { int i, j, k, sum = 0; memset (ly, 0, sizeof(ly)); for (i = 0; i < n; i++) { lx[i] = -inf; for (j = 0; j < m; j++) if (lx[i] < w[i][j]) lx[i] = w[i][j]; } memset (match, -1, sizeof(match)); for (i = 0; i < n; i++) { while (1) { memset (sx, false, sizeof(sx)); memset (sy, false, sizeof(sy)); if (dfs (i)) break; d = inf; for (j = 0; j < n; j++) if (sx[j]) for (k = 0; k < m; k++) if (!sy[k]) d = min (d, lx[j]+ly[k]-w[j][k]); if (d == inf) //找不到完美匹配 return -1; for (j = 0; j < n; j++) if (sx[j]) lx[j] -= d; for (j = 0; j < m; j++) if (sy[j]) ly[j] += d; } } for (i = 0; i < m; i++) if (match[i] > -1) sum += w[match[i]][i]; return sum; }
第一题:http://acm.hdu.edu.cn/showproblem.php?pid=2255
直接输入w[i][j]边权值建图套模板就可以了
第二题:http://acm.hdu.edu.cn/showproblem.php?pid=1533
将m的坐标记录到左集,h的坐标记录到右集,w[i][j]表示第i个m到第j个h的距离
w[i][j]=△x+△y 然后因为是求最小值,而KM是求最大值
所以只要这样:w[i][j] = -w[i][j]建图再套模板输出【-sum】就ok!
第三题:http://acm.hdu.edu.cn/showproblem.php?pid=1853
直接建图,注意有重边哦!
if (-c > w[a][b])
w[a][b] = -c;
当木有完美匹配输出-1
第四题:http://acm.hdu.edu.cn/showproblem.php?pid=3488
跟第三题几乎一样
第五题:http://acm.hdu.edu.cn/showproblem.php?pid=3435
跟第三题代码基本上一样,只是要双向建图,也有重边
第六题:http://acm.hdu.edu.cn/showproblem.php?pid=2426
左集是学生,右集是房子,注意 w[i][j] < 0 不可匹配,最后无法完美匹配输出-1
第七题:http://acm.hdu.edu.cn/showproblem.php?pid=2853
题目要求匹配最大值和至少要改变多少个原有匹配
思路:让原有匹配更有优势就可以了
实现:所有权值扩大100倍,原有匹配【例如a匹配b】w[a][b]++
设结果是res
最大值:res/100
至少改变个数:n - res%100
第八题:http://acm.hdu.edu.cn/showproblem.php?pid=3718
题目求的是两字符串的最大相似度
思路:因为第一个串的一种字母只能匹配第二个串的一种字母,所以可以转化为求
【字母的最大匹配值/n】
建图:【例】
第九题:http://acm.hdu.edu.cn/showproblem.php?pid=3722
直接按题目要求建图,注意跟自己匹配的值是0,w[i][i]=0
第十题:http://acm.hdu.edu.cn/showproblem.php?pid=3395
直接按题目要求建图就可以了
第十一题:http://acm.hdu.edu.cn/showproblem.php?pid=2282
建图:多余的1分别跟所有的0算出最小距离,例如3,多了2个1,要把他们跟所有0匹配,左集是1,右集是这n个数【限制匹配条件(=0)就可以了】
左集个数为m,表示有多少个1需要移动
m = 0;
for (i = 0; i < n; i++)
{
if (a[i] > 1)
{
for (j = 1; j < a[i]; j++)
{
for (k = 0; k < n; k++)
if (a[k] == 0)
w[m][k] = -min (abs(k-i), n-abs(k-i));
m++;
}
}
}
第十二题:http://acm.hdu.edu.cn/showproblem.php?pid=2813
这题比较容易超时……
用STL的map把字符串映射为序号
m1.clear();
m2.clear();
k1 = k2 = 1;
while (q--)
{
scanf ("%s%s%d", s, p, &x);
string a(s);
string b(p);
if (m1[a] == 0)
m1[a] = k1++;
if (m2[b] == 0)
m2[b] = k2++;
w[m1[a]][m2[b]] = -x;
}
第十三题:http://acm.hdu.edu.cn/showproblem.php?pid=2448
这题要读懂题目意思!
题意:n艘船要分别回到n个码头,另外有m个采矿点,一开始n艘船所在采矿点已经给出,采矿点与采矿点之间给出k条路【双向的】,码头与采矿点之间给出p条路,由于船进入码头后就不会出来,所以这条路是单向的!
实现:最短路+KM
第十四题:http://acm.hdu.edu.cn/showproblem.php?pid=2236
题意:n×n的矩阵中,没行找一个元素,每个元素之间不可同列,求这n个元素的最大值-最小值的最小差
思路:暴力枚举差值【由于元素的值0<= x <=100, 差值的范围也只能是[0,100]】
匈牙利检验就可以了
bool KM (int low, int high)
{
int i;
memset (match, -1, sizeof(match));
for (i = 0; i < n; i++)
{
memset (vis, false, sizeof(vis));
if (!dfs (i, low, high))
return false;
}
return true;
}
第十五题:http://acm.hdu.edu.cn/showproblem.php?pid=3315
默认匹配是w[i][i]
si打赢xj,w[i][j] = v[i]
如果si输了,w[i][j] = -v[i]
所有权值扩大100倍,w[i][i]++优先匹配
相似度=(res%100*100/n)%
评论
4 楼
基德KID.1412
2012-05-30
lijunle 写道
KIDx大神,我想问下,第14题。我用二分+枚举差值,跑最快也要900+ms。你的枚举差值就行的思路是什么意思?为什么你的代码跑得这么快?
先将矩阵中的元素不重复地存放到num数组中,然后枚举
for (i = 0; i <= 100; i++)
for (j = 0; j < k; j++)
if (KM (num[j], num[j]+i))
goto end;
3 楼
lijunle
2012-05-30
KIDx大神,我想问下,第14题。我用二分+枚举差值,跑最快也要900+ms。你的枚举差值就行的思路是什么意思?为什么你的代码跑得这么快?
2 楼
基德KID.1412
2012-02-10
暴风雪 写道
话说,这篇总结不错啊,肿么那么多踩的,同情博主
踩踩更健康
1 楼
暴风雪
2012-02-06
话说,这篇总结不错啊,肿么那么多踩的,同情博主
发表评论
-
【生成树计数】HDU 4305 Lightning
2012-08-16 15:45 2627KIDx的解题报告 题 ... -
LOJ 1009 Back to Underworld
2012-01-10 16:50 0KIDx 的解题报告 题目链接:http://ligh ... -
【floyd的灵活运用】LOJ 1174 Commandos
2012-01-10 15:02 1428KIDx的解题报告 题目链接:http://light ... -
【差分约束(spfa版)】总结
2011-10-05 21:02 6993KIDx 的解题报告 先总结下: 第一: 感觉难点在于建 ... -
【记忆化搜索+最短路】HDU 2833 WuKong
2011-08-28 09:49 2496http://acm.hdu.edu.cn/showprobl ... -
【最短路+枚举】HDU 2962 Trucking【2012-1-20更新】
2011-08-28 09:17 1795KIDx 的解题报告 题目链接:http://acm.hd ... -
【枚举+最短路】HDU 2363 Cycling
2011-08-28 09:07 1767http://acm.hdu.edu.cn/showprobl ... -
【并查集+贪心(或)最短路+二分枚举】HDU 1598
2011-08-27 23:25 4025http://acm.hdu.edu.cn/showprobl ... -
【最短路/3大模板】总结【2012-1-22新增前插的spfa】
2011-08-28 18:15 2871首先献上模板:【点都是默认为从1到n编号,用dijk和f ... -
【HDU、二分匹配、最大匹配/新增1005+1008代码】总结
2011-08-22 14:19 1516KIDx 的解题报告 给出基本定义: 第一题:hdu ... -
【floyd/要防重边】HDU 2923 Einbahnstrasse
2011-08-16 21:48 2293http://acm.hdu.edu.cn/showprobl ... -
【floyd记录路径】HDU 1385 Minimum Transport Cost
2011-08-16 21:26 1929http://acm.hdu.edu.cn/showprobl ... -
【最短路spfa+记忆化搜索】HDU 1142 A Walk Through the Forest
2011-08-15 15:21 2176http://acm.hdu.edu.cn/showprobl ... -
【floyd神器】HDU 1217 Arbitrage
2011-08-14 22:09 1746http://acm.hdu.edu.cn/showprobl ... -
【次小生成树】POJ 1679 The Unique MST
2011-08-12 10:00 1011http://poj.org/problem?id=1679 ... -
【拓扑排序】HDU 2647 Reward【2012/3/25更新】
2011-08-11 19:26 1902http://acm.hdu.edu.cn/showprobl ... -
【拓扑排序】HDU 1285 确定比赛名次
2011-08-10 21:38 1122http://acm.hdu.edu.cn/showprobl ... -
【拓扑排序+并查集】HDU 1811 Rank of Tetris
2011-05-21 11:39 2620http://acm.hdu.edu.cn/showprobl ...
相关推荐
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
算法-连连看(HDU-1175)(包含源程序).rar
算法-命运(HDU-2571)(包含源程序).rar
算法-数塔(HDU-2084).rar
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电acm解题报告 详细解析2000-2099 适合acm初学者
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
算法-超级楼梯(HDU-2040)(包含源程序).rar
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
算法-六度分离(HDU-1869)(包含源程序).rar
算法-欧拉回路(HDU-1878)(包含源程序).rar
算法-免费馅饼(HDU-1176)(包含源程序).rar
算法-迷宫城堡(HDU-1269)(包含源程序).rar
算法-排列2(HDU-1716)(包含源程序).rar
算法-排列组合(HDU-1521)(包含源程序).rar
算法-非常可乐(HDU-1495)(包含源程序).rar
算法-畅通工程(HDU-1232)(包含源程序).rar
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
算法-确定比赛名次(HDU-1285).rar