Mrhanice

POJ

codeforces(2) DP基础(3) UVA(14) 云服务器(1) 区间DP(4) 图论(2) 扩展欧几里得(1) 杂谈(2) 树状数组(1) 状态压缩DP(1) 状态空间搜索(1) 简单水题(3) 线段树(4) 背包问题(3)

/ 注册

全部文章 / POJ （共8篇）

Oulipo POJ - 3461

裸的KMP 代码如下： #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> u...

2017-06-20

0 541

Drying POJ - 3104

题目描述：晾衣服，洗衣机一分钟可以晾K水，自然风干一分钟可以减少1水。求晾干所有衣服所需要的最小时间。解题思路：二分时间，那怎么计算满足的时间呢。转换一下思路，总时间就是洗衣机工作的时间，因为如果只有自然风干的话，时间是<=洗衣机总是工作的，什么时候=呢，是k=1的时候。那么下面计算...

2017-05-29

0 585

Meteor Shower POJ - 3669

题目描述：小行星要撞地球了，它会在一定的时间点撞击想点(x，y)和四连块的点，求主人公最短多长时间到达安全地带。解题分析：输入时，把要撞的点处理好，注意更新要撞击点的最早时间。bfs即可。有一个小细节是坑，注意题目描述，主人公可以再第一象限和轴跑，也就是无上界，加入队列时只要x>0&...

2017-05-24

0 482

Prime Path POJ - 3126

题目描述：给出一个素数，要求通过变换这个素数的某个数字，使变换后的数字仍然是素数，要求变换到给定的一个素数停止，求最少的变化次数。解题分析：bfs模拟求最短路就行。把每个数当做图中的一个点。代码入下： #include <iostream> #include <...

2017-05-23

0 353

C Looooops POJ - 2115

扩展欧几里得算法题目描述：算循环的次数，初始值为A，跳出循环的条件是A！=B，A每次+C，设所有的运算都是二进制k位数，运用补码的原理，当x=2^k,则x+1溢出后=1. 解题思路：扩展欧几里得算法。推一下方程，令所求的次数为x (A+Cx)%2^k=B -> A+C...

2017-05-23

0 620

Cable master POJ - 1064

二分题目描述：仓库中有N条光缆，要求把它们截成总共K段等长的光缆，求截取的每段光缆的最大长度。解题思路：比较水的二分，就是精度坑人+读题费劲。注意这个题精度要求特别高，另外输出的时候因考虑到实际因素，保留两位小数的时候是把两位之后的数据截掉，并不是默认的四舍五入，所以用到了flo...

2017-05-23

0 488

青蛙的约会 POJ - 1061

扩展欧几里得题目描述：两只青蛙都沿着一个圆轨道往西跳，第一个青蛙一步调m,第二个青蛙一步跳n,初始时第一个在位置x,第二个在位置y，轨道长度是L,求跳多少次他俩相遇。解题思路：扩展欧几里得。在此处我令第一个青蛙位置为大写的X，第二个为大写的Y，所求的次数为小写的x.方程 (X+m...

2017-05-22

0 394

C - Asteroids POJ - 3041

匈牙利算法本文采自： http://blog.csdn.net/lyy289065406/article/details/6646007 题目描述：你的飞船有个强大的武器可以打小行星，一次可以攻击一行或者一列，求最少的攻击次数。题目分析：问题可以转化为，选取最少的点，使...

匈牙利算法

2017-05-21

0 488