-
[综合] poj 3103 Cutting a Block 模拟水题
水题 #include<iostream> usingnamespacestd;intmain() {intx,y,z,n;scanf("%d%d%d%d",&x,&y,&z,&n);for(inti=0;i<n;++i)printf("00%.8...
4
热度 -
[综合] poj 3241 Object Clustering 曼哈顿最小生成树
题意: 平面上有n个点,现在把他们分成k个集合,使得每个集合中的每个点都至少有一个本集合的点之间的曼哈顿距离不大于X,求最小的X。 分析: 转化为求n个点生成完全图的最小生成树的第k大边。接下来有几个重点。 1)根据莫队算法,由于边权是点的曼哈顿距离,每个点只需要跟周围8个方向中每个方向最近的点连边...
33
热度 -
[综合] poj 3307 Smart Sister 打表解因子生成数问题
题意: 给i,求由仅以2,3,5,7为因子的数中第i个是多少。 分析: 打表。 代码: //poj3307 //sep9 #include<iostream> usingnamespacestd; typedefunsigned__int64INT; constintmaxL=6606...
47
热度 -
[综合] poj 2683 Ohgas' Fortune 利率计算
水题。 代码: //poj2683 //sep9 #include<iostream> usingnamespacestd;intmain() {intcases;scanf("%d",&cases);while(cases--){intfund,year,op,ans=-1;...
63
热度 -
[综合] poj 1671 Rhyme Schemes 第二类Stirling数
题意: 求s(n,0)+s(n,1)+...s(n,n),s(i,j)为第二类Stirling数。 分析: 有递推公式s(p,k)=(p-1)*s(p-1,k)+s(p-1,k-1),1<=k<=p-1。 代码: //poj1671 //sep9 #include<iostrea...
36
热度 -
[综合] poj 2960 S-Nim nim博弈grundy值计算法入门
题意: 给k堆石子,两人轮流向某一堆中拿,拿的个数要从给定的一个集合中取,没石子拿的输,问先手必胜还是必败。 分析: grundy值计算法的入门题。 代码: //poj2960 //sep9 #include<iostream> #include<set> usingnam...
22
热度 -
[综合] poj 1021 2D-Nim 模拟
题意: 给两个平面,每个平面上有一些点,相邻的点可构成点集,为两个平面内的点集是够都对应相似。两个点集相似是指经过对称或旋转或平移后相等。 分析: 直接模拟判断。 代码: //poj1021 //sep9 #include<iostream> #include<vector>...
97
热度 -
[综合] poj 2780 Linearity 最多共线点经典问题
题意: 给n个点,其中最多有多少点共线(n<1000)。 分析: 这是一个经典问题,朴素n^3解法:枚举n^2条直线,判断每条直线与多少点相交,复杂度n^3。明显会超时。这是n^2logn的解法:枚举每个点,对某个点与其他点连的n条直线按斜率排序,设这些直线中斜率相同的直线有k条,则k更新答案...
34
热度 -
[综合] poj 3105 Expectation 按位统计
题意: 给n,求sum(i^j)/(n^2),0<=i,j<n。n<10^9 分析: 暴力n^2算法肯定超时。这是logn按位统计算法:按位先算出0出现的个数x,则1出现的个数为n-x,再算每位对和的贡献。 代码: //poj3105 //sep9 #include<ios...
2
热度 -
[综合] poj 2932 Coneology 扫面线法
题意: 给n个无交点的圆,求这n个圆中不被其它圆包含的圆。 分析: 扫面线法,用二叉树(set+lowerbound方法)维护最外圆的集合。 代码: #include<iostream> #include<algorithm> #include<vector> ...
91
热度 -
[综合] poj 2635 The Embarrassed Cryptographer 筛素数+高精度除法
题意: 给K(<10^100),L(<10^6),求K小于L的最小素因子并输出,如果没有则输出GOOD。 分析: 枚举小于L的素数用高精度除法判断是否是因子,关键是怎么高效筛素数,先给一种比较慢的筛法: primes[max_prime_num],num=0; memset(vis,0,...
16
热度 -
[综合] poj 2096 Collecting Bugs 概率dp
代码: //poj2096 //sep9 #include<iostream> #include<cmath> usingnamespacestd; doubleE[1005][1005];intmain() {intn,s;while(scanf("%d%d",&...
66
热度 -
[综合] poj 2157 Maze 枚举排列+dfs搜迷宫
题意: 给一个迷宫,求是否可从S走到G,迷宫中有门和钥匙,要获得相应种类的所有钥匙才能打开该种门(比如获得所有a才能打开A)。 分析: 枚举打开门的顺序,搜路径即可。 代码: //poj2157 //sep9 #include<iostream> #include<algorit...
18
热度 -
[综合] poj 1784 Huffman's Greed 动态规划四边形加速求最优二叉搜索树
题意: 给二叉搜索树的内部节点p1,p2...pn和外部节点q0,q1,..qn,求一棵比较数期望最小的二叉搜索树,输出期望。 分析: n^3的动态规划很容易想到,方程满足四边形优化的条件,可优化到n^2. 代码(n^3): //poj1784 //sep9 #include<iostrea...
11
热度 -
[综合] poj 1782 Run Length Encoding 自动机处理字符串
题意: 给一个字符串,要将它按规则转化为新字符串,规则有1)重复的比如aaaa转化为4a,如果重复次数超过9分开处理。2)不重复的片段在两端加1输出,如234输出1234,如果不重复片段中有1则加1个1输出,如2134输出1211341。 分析: 用自动机处理比较简单,自动机是一种能规范分支讨论的方...
39
热度 -
[综合] poj 3276 Face The Right Way 翻转问题的灵活处理
题意: 给一个0,1序列,每次连续翻转k个,求翻转m次将序列全置0的最优二元组(k,m)。 分析: 题意说是要优先优化m,但不一定要优先枚举m,可以先枚举k再在内循环中处理。这题关键是把独立关系转化为依赖关系,每位与前面一样为0,不一样为1。这样翻转一位i时,只需改变i+k,不用改变i,i+1,i+...
21
热度 -
[综合] poj 1170 Shopping Offers 完全背包
题意: 给在商店里要买的商品的种类,数量,价格,和一些组合购买选项(如同时买2个a,1个b,只要x元),求最小花费。 分析: 因为要买的商品种类数b是变量(b<=5),一开始还想背包的维数不确定怎么搞啊,后来发现按5维开背包就可以了,接下来就是完全背包了。 代码: //poj1170 //s...
72
热度 -
[综合] poj 2068 Nim 博弈论dp
题意: 给S个石子,2个队,每队n个人,每队轮流拿石子,每人能拿的最大石子数作为输入给出,问先拿的队必胜还是必败。 分析: 必败态的下个状态都是必胜态,必胜态的下个状态有必败态,状态明确了就能dp了,一开始定义的是dp[石子数][游戏经过步数],后来发现dp[石子数][选手编号]就可以了。 代码: ...
18
热度 -
[综合] poj 1254 Hansel and Grethel 直线求交
题意: 通过点和方向给出两条直线,求他们的交点。 分析: 裸的直线求交,向量做法可避免特殊情况的的讨论。 代码: //poj1254 //sep9 #include<iostream> #include<cmath> usingnamespacestd; constdoub...
64
热度 -
[综合] poj 1147 Binary codes bwt压缩算法
题意: bwt压缩算法的解压过程。 分析: 利用前缀排序去掉相同前缀相对顺序不变的性质。bwt压缩算法 代码: //poj1147 //sep9 #include<iostream> #include<algorithm> usingnamespacestd; intn; ...
27
热度