Mrhanice

分类

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

/ 注册

全部文章（共50篇）

Piggy-Bank HDU - 1114

完全背包题目描述：有一个小猪存钱罐，求在正好的重量的情况下的，存钱的最小值，如果不能满重输出This is impossible. 解题分析：不限次数，完全背包，因为是求最小值，所以初始化时是满重，但是dp[0]必须得是0，不然dp[j] = min (dp[j], dp[j-w[...

2017-08-04

0 452

Rain on your Parade HDU - 2389

HK算法，匈牙利算法超时题目描述：t时间后会有一场大雨，有m个人和n个雨伞，求在ｔ时间内，使得最多的人不被雨淋。求不被雨淋的人数。解题分析：显然是匹配问题，第一次写用匈牙利算法超时了，时间复杂度n^3或n*m,之后补题，学习了Hopcroft krap算法。用Hopcropt k...

2017-07-18

0 730

大牛们的ACM 算法阶段性练习

本文转载自某位大牛转载自某位大牛转载自某位大牛（递归不知边界了）的ACM学习之路。本文转载自这位大牛的博客建议：做到50行以内的程序不用调试、100行以内的二分钟内调试成功. acm主要是考算法的，主要时间是花在思考算法上，不是花在写程序与debug上。计划： ...

2017-06-25

0 1245

Oulipo POJ - 3461

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

2017-06-20

0 541

3xian大佬的一篇博文

刚刚接触ACM的一名新人，从学长那得知3xian大佬的这篇博文。最后一天，漫天飘起了雪花，假装欢送我离去。这次WF之战不太顺利，早期的C题大概花了1秒钟构思，然而由于输出格式多了一个空格直到两个半小时才逃脱Wrong Answer的纠缠。还好lynncui在期间独挡一面过掉D。最终成...

2017-05-29

0 2987

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

A380 URAL - 1893

简单水题，打个表就行了。代码如下： #include <iostream> #include <cstdio> using namespace std; const int maxn=200; int graph[maxn][maxn]; int main() ...

2017-05-23

0 442

Passenger Comfort URAL - 1885

题目描述：求飞机声音堵塞耳朵的时间，飞机前t秒要飞到高度H，速度不能超过v，能够堵塞耳朵的最小速度是x，求飞机声音堵塞耳朵的时间的最大时间和最小时间。解题思路：如果h/t >x ，则最大时间是t，反之则是h/x,做小时间由方程解出： x*t1+v*t2=h, t1+t2=...

2017-05-23

0 379