-
[综合] poj 4052 Hrinity AC自动机
题意: 给n个模式串和1个主串,求他们在主串中出现的次数,子串不重复计数。 分析: AC自动机模板题,在处理子串的时候要特殊处理,原来AC自动机是没必要写一个update_fail函数的,这已经是比较简洁的模板了。 代码: //poj4052 //sep9 #include<iostream...
72
热度 -
[综合] poj 4044 Score Sequence 排序
水题,直接贴代码。 代码: //poj4044 //sep9 #include<iostream> #include<algorithm> usingnamespacestd; inta[60],b[60]; intans2[60]; intn,m; intdeal(int...
27
热度 -
[综合] poj 4045 Power Station dfs求树上最小距离和
题意: 给一棵树,每条边的权值为R*I^2,求到所有其他节点权值和最小的点和相应最小权值和。 分析: 先将图转化成树,然后在树上dfs。 代码: //poj4045 //sep9 #include<iostream> #include<vector> usingnamesp...
18
热度 -
[综合] poj 1637 Sightseeing tour 混迹图欧拉回路
题意: 求有向边无向边混迹的欧拉回路。 分析: 对无向边任意重定向,然后转化为网络流问题。 代码: //poj1637 //sep9 #include<iostream> #include<queue> #include<algorithm> usingname...
59
热度 -
[综合] poj 2526 Center of symmetry 哈希查找
题意: 给n个不同的点,问是否存在一个点使得这n个点关于它两两对称。 分析: 首先确定这个对称中心的坐标,然后对每个点哈希查找它的对称点。 代码: //poj2526 //sep9 #include<iostream> usingnamespacestd; constintmaxN=1...
28
热度 -
[综合] poj 4046 Sightseeing 枚举思想在spfa中的应用
题意: 给一个图和q个询问,每个询问查询图中两点的(距离+路径上最大值)的最小值。 分析: 枚举路径上的最大值做spfa,这题丫的卡常数。。。队列用stl的就等着tle吧。 代码: //poj4046 //sep9 #include<iostream> #defineinf((~(0U...
70
热度 -
[综合] poj 4047 Garden 线段树lazy标记与成段更新
题意: 给长度为n的序列及k(0<k<=n<=200000),m个操作p,x,y。其中(1)p==0:将x位置处的数变为y;(2)p==1:将x,y位置处的数互换。(3)p==2查询x-y位置之间连续k个数的和的最大值。 分析: 求连续区间的和最大,可以把区间看成一个点,这样这n-...
24
热度 -
[综合] poj 4048 Chinese Repeating Crossbow 线段规范相交的判断
题意: 给n条线段和初始点,求初始点发出的射线最多能穿过多少条线段(有交点就算穿过)。 分析: 枚举线段端点,判断线段是否规范相交,需要严密的模板。 代码: //poj4048 //sep9 #include<iostream> usingnamespacestd; typedeflo...
53
热度 -
[综合] poj 3990 Fermat Point in Quadrangle 凸包和费马点
题意: 求一个四边形的费马点。 分析: 模拟退火要么超时要么wa,这题的数据就是不想让随机算法过的。。其实四边形的费马点很简单,如果是凸四边形的话费马点是对角线交点,如果是凹四边形费马点是凹点。但题目给的四个点顺序是不确定的,所以要先求下凸包。 代码: //poj3990 //sep9 #incl...
66
热度 -
[综合] poj 3787 Convex Hull of Lattice Points 求凸包
题意: 裸的凸包。 分析: graham模板直接上。 代码: //poj3787 //sep9 #include<iostream> #include<algorithm> usingnamespacestd; constintmaxN=64;structP {intx,y...
55
热度 -
[综合] poj 3680 Intervals 最大费用流
题意: 给n给开区间(ai,bi)及相应权值wi,现在要选一些区间,要求任一点不能被超过k个区间覆盖,目标是最大化总的权重。 分析: 转化为求最大费用流,改改最小费用流的模板就好。 代码: //poj3680 //sep9 #include<iostream> #include<...
43
热度 -
[综合] poj 3228 Gold Transportation 并查集
题意: 有n和城市和m条路,每个城市都有产生金量和收集金量,现在要把所有黄金收集,求经过的最短边是多少。 分析: 二分+最大流或用并查集合并等价类。 //poj3228 //sep9 #include<iostream> #include<algorithm> usingna...
69
热度 -
[综合] poj 2455 Secret Milking Machine 二分+最大流
题意: 给一图,求从点1到n的t条边不相交的路径,目标是最小化最t条路径中的最大边,输出该最大边。 分析: 求最值的问题满足单调性都可以用二分来做,二分是加速的枚举方法。这题二分枚举最大边建图,每次用长度小于等于二分值的边建图并置容量为1,求最大流即可。 代码: //poj2455 //sep9 ...
98
热度 -
[综合] poj 3911 Internet Service Providers 解一元二次方程
少有人做的水题,直接贴代码。 //poj3911 //sep9 #include<iostream> usingnamespacestd; typedeflonglongll;intmain() {lln,c;while(scanf("%lld%lld",&n,&c)=...
57
热度 -
[综合] poj 3940 Grey Area 浮点输出控制
水题,直接贴代码,注意几种控制浮点输出的方法:e格式,以指数形式输出实数。g格式:自动选f格式或e格式中较短的一种输出,且不输出无意义的零。 代码: //poj3940 //sep9 #include<iostream> usingnamespacestd; constintmaxL=...
26
热度 -
[综合] poj 3970 Party 最小公倍数
题意: 给n个数,求它们的最小公倍数。 分析: lcm(a,b)==a*b/gcd(a,b); 代码: //poj3970 //sep9 #include<iostream> usingnamespacestd; typedeflonglongll; llgcd(lla,llb) {r...
88
热度 -
[综合] poj 3881 区间交判断
水题,直接贴代码。 //poj3881 //sep9 #include<iostream> usingnamespacestd; constintmaxN=10024; intn,m; inta[maxN],b[maxN]; booljudge(intx,inty,inti) {if(...
61
热度 -
[综合] poj 1221 UNIMODAL PALINDROMIC DECOMPOSITIONS 整数拆分
题意: 给一个数n,求有多少种和为n的单峰先增对称序列,比如当n=5时结果为3:(5),(131),(11111)。 分析: 转化为求类似整数拆分问题,f(i,j)的意义是把i进行拆分,最大数小于等于j的方法数。 代码: //poj1221 //sep9 #include<iostream&...
53
热度 -
[综合] poj 3014 Cake Pieces and Plates 整数拆分
题意: 将m拆成n个数,允许某个数为0,求拆分方案数。 分析: 裸的整数拆分,设h(m,n)表示将m拆成n个数,允许某数为0的方案数,递推方程见代码。很有意思的是,参考上一篇写poj1221的博文中,设f(m,n)表示将m进行任意份数不允许有0的整数拆分,且最大元素小于等于m的方案数,则h(m,n)...
21
热度 -
[综合] poj 4022 ASCII Area dfs求二维面积
题意: 给一个有'/','\','.'组成的二维字符数组,求图中‘/’和‘\’组成的面积有多大。 分析: 每个‘/’和‘\’的格每个贡献1/2的面积,每个多边形内部的'.'贡献1的面积,关键是求多边形内部的’.‘有多少个。一开始往上下左右4个方向搜wa了,原来内部的点可以斜着扩展,比如/./这种情况...
17
热度