-
[综合] c++ 待验证问题收录
1、右值引用 右值引用的出现解决了C++长期以来被人诟病的临时对象效率问题 消除了诸如std::vector、std::string之类的额外开销,使得函数对象容器std::function成为可能左值-表达式结束后依然存在的持久对象 右值-表达式结束后就不再存在的临时对象 2、std::threa...
17
热度 -
54
热度 -
[综合] tinyxml2的linkEndChild与insertEndChild的区别
link系列:对象连接到父节点所以不能将栈对象链接过去,因为从函数返回后,栈对象就析构了。一般用法是:XMLElement*e=doc.newElement()parent->linkEndChild(e);PS:e虽然是new出来的,但不用手动释放,其父亲会析构 insert系列:将副本插入...
47
热度 -
[综合] QueryPerformanceFrequency/QueryPerformanceCounter 获取代码精确运行时间
QueryPerformanceFrequency(&nFreq);QueryPerformanceCounter(&nBeginTime);Sleep(1000);QueryPerformanceCounter(&nEndTime);time=(double)(nEndTi...
55
热度 -
79
热度 -
46
热度 -
70
热度 -
[综合] 快速高质量产生伪随机数
#include<random>//C++11intrandom_uint(intmin,intmax){std::random_devicerd;std::mt19937gen(rd());std::uniform_int_distribution<>distrib(min...
91
热度 -
[综合] c++ tuple 用法
tuple主要作用是可以省去临时结构体的定义,看起来也比较清爽。 比如想获取年月日,常规做法是定义一个结构体: structtm {inttm_mday;//dayofthemonth-[1,31]inttm_mon;//monthssinceJanuary-[0,11]inttm_year;//y...
5
热度 -
[综合] poj 1422 Air Raid 最小路径覆盖
裸的最小路径覆盖,直接用匈牙利算法即可。一个有向无环图肯定与一个二分图对应,求这个有向无环图的最小路径覆盖就是求对应二分图的最大独立集,所以最后的结果是顶点数n减去最大匹配数m。 //poj1422bynepNINE#include<iostream> usingnamespacestd...
6
热度 -
[综合] poj 2060 Taxi Cab Scheme 最小路径覆盖
题目大意: 给n个任务,每个任务的属性有开始时间和需要时间(这个任务起点终点之间的距离),两个任务满足一定的条件可以在“一趟”内完成,求完成所有任务所需的最少趟数。 思路: 把任务看做点,按若两个任务满足一定的条件则之间有一条边建图,所求的趟数就是该有向无环图的最小路径覆盖。现在关键就是描述“两个任...
15
热度 -
[综合] poj 2724 Purifying Machine 最小路径覆盖
题意: 给一堆二进制表示的数字,如果二进制表示中有”*“则可通配0和1,比如01*表示010和011,现在问最少能用多少个可带”*“的二进制新串把给的二进制原串都覆盖。 思路: 把每个原串看做点,按若两串之间不同位数小于1则有一条边建图,注意这样建图是不会有环的。然后用匈牙利算法解无向图的最小路径覆...
57
热度 -
[综合] poj 2446 Chessboard 二分图的最大匹配
题意: 给一个n*m的棋盘,上面有k个点被挖掉,问是否能用1*2的片段把剩下的棋盘恰好完全覆盖。 思路: 把剩下的顶点编号,若两个顶点可以被一个片段覆盖则他们之间有一条边,则转化为求二分图的最大匹配问题,若匹配数M+k==n*m则可以完全覆盖,否则不行。 代码: poj2446bysepNINE #...
73
热度 -
[综合] poj 2018 Best Cow Fences dp+单调队列优化
题意: 给N个数,求其中长度大于等于F的子段的最大平均值。 思路: 网上一些dp的方法是由长度n-1的最优值得到长度n的最优值的dp方法明显是错的,后来看了04年国家集训队周源的论文。这题采用的数形结合的方法把优化平均值转化为优化斜率,优化过程中用到了类似求凸包的技巧和单调队列,具体的可去搜下上述论...
25
热度 -
[综合] poj 2457 Part Acquisition 最短路spfa
题意; 给n和物品和m个关系,其中(a,b)表示用a物品可以换b物品,问用物品1换物品n最少需要几步并输出交换序列。 思路: 裸的最短路,spfa模板题。 代码: //poj2457 //sepNINE #include<iostream> #include<queue> u...
26
热度 -
[综合] poj 3072 Robot 最短路spfa
题意: 给n个点,每个点有坐标(x,y),有个robot要从1走到n,求最短路径长度,所求最短路中每段路径长度不能超过R,而且要考虑每次转向的时间,这个时间是每转1度需要1的路径长度。 思路: spfa算法求最短路,这题描述距离起点的距离函数dis一维不够用,故升到二维,dis[n][m]表示到点n...
44
热度 -
[综合] poj 3439 Server Relocation 最短路bfs
题意: 给n个点,现在要从点1走到点n,两个点之间距离小于题目给的两段绳子之和则这两点之间的距离为1,否则距离为无穷,求1到n的最短路。 思路: 一开始直接spfa跑了4800多ms...后来改成bfs且去掉预处理到了1000ms左右,如果图中边权为1的话spfa就退化成了bfs。 代码: //p...
89
热度 -
[综合] poj 3463 Sightseeing 最短路径数量
题意: 求有向图中最短路和比最短路大1的路径数量。 思路: 需要理解dijkstra算法中dis[n]数组的含义,设cnt[i]表示到点i的最短路径数量,cnt1[i]表示到点i比最短路大1的路径数量。在运行dijkstra算法的过程中每次获得最小dis[i]的时候可以对所有dis[v]+w(v,i...
69
热度 -
[综合] poj 3328 Cliff Climbing 最短路 spfa
题意: 给一张二维地图,求从标有‘S’到标有‘T’之间的最短路,特殊的地方在于每次走的方向要左右交替。 思路: spfa即可,关键在dis数组的定义,dis[0][x][y]和dis[1][x][y]分别表示两只脚在x,y点上时的最小值,距离g函数可在运行时确定,不用预处理,否则很耗内存。 代码: ...
92
热度 -
[综合] poj 1699 Best Sequence 枚举排列
题意: 给n个字符串,求合并后字符串的最小长度,合并的规则是合并后对应位字符一样,比如abc和bcd可以合并为abcd. 思路: 本来想dp的,但一看n<=10,一脸欠搜的样,于是枚举各串在最终串中的顺序,选最小长度。要注意的是任意两串合并的新串长度要预处理,否则在枚举过程中计算会超时。 代码...
98
热度