寒笑f-CSDN博客

原创小数转分数

好久没写过算法方面的代码了，偶然翻开《编程之美》看到了这个题，拿来写写。具体算法在《编程之美》2.6和2.7。#! /usr/bin/pythondef is_even(x): if 0 == (x & 1): return True else: return Falsedef cal_gcd(x, y): if x < y:

2015-05-27 19:20:16 892

原创 crontab不能成功执行shell脚本的可能原因

我们经常会需要使用crontab进行定时任务，但crontab不能成功执行脚本的情况还是很常见，总结起来，本人了解到的和自己遇到的可能原因主要有以下几个： 1. crond进程不存在，该进程是crontab的守护进程，它必须存在才能让crontab正常使用； 2. 系统时间不对； 3. 环境变量的问题：crontab执行脚本的时候不会读取用户的环境变量等配置，所以可能

2014-01-18 17:45:45 9341

本人是个不会画图的屌丝，一方面是因为需要画图的地方很少，另一方面也是因为即使需要画图，也都是很简单的几个框几个圈几条线，所以就用word之类的原始工具直接上了，结果往往是痛苦的经历换来搓搓的一张图，而且图很难修改，遇到需求变更时往往牵一发而动全身，所以每次听说画图，总有背后一凉的感觉。最近经同事介绍，了解了一下DOT和graphviz，一看到这东西就感觉遇到了真爱，简单的几行代码，轻松搞定画图，不

2013-11-09 21:57:50 45636 7

翻译如何使用Google日志库（glog）

工作有一段时间了，总是在忙碌和无所事事中矛盾着，今天据说台风17级，正好休息，于是整理一下glog。在公司管理日志用glog比较多，因为它开源，而且确实方便。官方文档在这里：http://google-glog.googlecode.com/svn/trunk/doc/glog.html 。按照个人理解翻译一下，翻译中可能会有个人理解，所以不保证原汁原味（不过尽量保持），也因水平有限，

2013-09-22 22:35:06 3459 2

原创 Codefordes round 178 div2 C

n个灯中，已经亮的有m个，则这m个灯把n个灯分成了若干有未亮的灯的区间（设为k个），每个区间分别有xi个灯。（n - m)个灯点亮的顺序有(n - m)!中情况，在这些情况中，不考虑每个区间内部的顺序，则总情况有(n - m)! / (x1! * x2! *...* xk!)。对于只有一边有灯亮的区间，这个区间内灯的点亮顺序是确定的，即为1；对于两边都有灯亮的区间：假设区间有1个灯，则点亮方法有1

2013-06-22 15:24:18 766

原创 Codeforces round 181 div2 C

枚举n个位置中有多少个为数字a(设为x)，剩下的位置放b。则如果sum = a * x + b * (n - x)是good number，那么答案加上C(n, x)，所以唯一的问题的如何计算C(n, x)。C(n, x) % Mod = n! / (x! * (n - x) !) % Mod= n! * (x! * (n - x)!)^(-1) % Mod。(p)^(-1)表示p对Mod的乘

2013-06-21 17:17:00 691

原创 poj 1683 Puzzlestan

好久不写代码了出来写个dfs。/* * Author: stormdpzh * Created Time: 2013/5/2 14:15:51 * File Name: poj_1683.cpp */#include #include #include #include #include #include #include #include #include #i

2013-05-02 19:16:28 759

原创学习笔记V——由 woj 1478 Key Logger 想到的list效率问题

昨天校赛一塌糊涂。我和我的队友都已经进入更年期了。^_^比赛中这是个简单题，一看到题目我就想到可以写，而且很简单。开始想到的是用STL的list很简单的去写，但list每次删除和添加元素之后迭代器指在什么地方不太清楚，于是就手写链表。结果TLE了，想到TLE只有可能是分配内存和释放内存的问题，于是改用数组模拟了链表，通过。今天看到大家说起list的效率，也看到哑熊（Dumbear）用list过

2013-04-22 20:11:08 868

原创 woj 1097 Circle （圆的面积并）

这两天算是整个浑浑噩噩的过了吧，感觉过的头脑甚是不清晰。晚上看到群信息有人在讨论woj，于是上去随便翻开了第一页，发现这个题没有做。一看分数是1的，以为是当初看到的简单题没有做，结果一看题目，求圆的面积并，并不是很简单。关于圆的面积并，之前知道一个做法，也在区域赛的时候准备了模版，但从来没有真正写过这个代码，左右无事，就把这个代码写出来了。这里用的是一个很不错的算法，关于算法请参考：htt

2013-04-05 00:46:43 2080 2

原创学习笔记IV——2012 Microsoft Intern Hiring Written Test （2012微软实习生招聘笔试题）

这是网上找到的一套微软笔试题。本人自己做了一下，题解贴在这里。水平有限，错误之处，欢迎拍砖！首先说一下这套题的评分标准，微软的标准总是很有意思，对于选择题，他们是一定会设法避免有人瞎蒙的！1~7 全对3分，少选2分，错选-2分8~18 全对5分，少选3分，错选-3分19~20 全对12分，少选5分，错选-5分所有题目不选均是0分。1、Suppose

2013-03-30 15:32:15 1476

原创 POJ 2826 An Easy Problem?!

这个Easy Problem确实挺Easy的，但就是细节很多，要考虑的主要有一下几点：一、任一一条木板于x轴平行时，答案为0；二、一条木板在另一条上方时，答案为0（水是垂直掉下来的，这种情况掉不到两块木板中间）；三、两木板没有交点时，答案为0；四、有点的情况下，求相应的面积即可。题目不难，但细节比较多，代码会比较长。计算几何很多时候都有这种特点吧！/* * Author: s

2013-03-29 23:46:36 683

原创 poj 1127 Jack Straws

在搜计算几何的题目，网上看到一个说这个要计算几何+并查集，然后就去看了。看完发现题目本身很简单，而且感觉完全不用并查集，当然，如果后面的询问很多的话，可以用记忆化进行优化。总之，并查集是可以不用的。判断两个线段相交的代码懒得写了，直接把判共线的一种情况用直线相交的模版来做了。/* * Author: stormdpzh * Created Time: 2013/3/29 23:03:

2013-03-29 23:42:05 733

原创学习笔记III——vector内存管理

在网易面试的时候问到了这个问题。以前自己的理解是：vector既然支持随机访问，那么肯定是分配的连续的内存。既然如此，那么如果这段连续的内存不够了呢？是在别的地方开辟新的空间，然后把所有数据都复制过去吗？在极端情况下，如果每次push_back一个元素，都遭遇内存不够，这个时候vector的效率是不是特别低下呢？关于这个问题，在《C++ Primer》一书中找到了一些解释，现在简单的概括如

2013-03-27 17:38:58 1331

原创学习笔记II——new/delete和malloc/free

上次网易面试也问到了这个问题，本来是一个很常见的问题，但真正回答起来发现好多地方不能很快的概括出来。于是现在总结一下。个人总结，有不妥之处，若有人看到，欢迎拍砖。 new/delete和malloc/free都是C++用于动态内存管理的。先总结一下他们的相同点和不同点。一、相同点：都可以用于申请动态内存。二、不同点： 1，操作对象不同。由于malloc/free是

2013-03-27 16:19:07 688

原创学习笔记 I——排序

网易面试之后，昨天又看了看排序算法，发现排序算法中看到的东西以前其实也都知道，可要立马说出来，还真是不能。现在整理一下吧。很多东西出于个人理解，纰漏之处，万一有人看到，欢迎吐槽。排序算法大一点分，有两类：基于比较的和不基于比较的。基于比较的算法都逃不了O(nlogn)的复杂度，也就是说不可能比这个复杂度还高了。因为每次比较至少得消耗logn的时间。不基于比较的排序因为省掉了比较，所以可以把复杂

2013-03-25 21:25:38 989 1

原创 poj 1101 The Game

直接bfs就可以了。奇怪的是竟然跑出了0ms。值得注意的是距离最近的不一定就是segments最少的，所以bfs的时候不能搜到一个解就退出。应该搜到queue为空。/* * Author: stormdpzh * Created Time: 2013/3/12 13:42:23 * File Name: poj_1101.cpp */#include #include #i

2013-03-12 15:31:06 1007

原创 poj 1676 What time is it?

好久没有写题了。实在闲来无事，就又写一个水题。以后不管参不参加比赛，坚持做题总是好的。cf，tc的比赛至少都是可以做做的。这个题目其实也很简单，枚举一天中的每个时间，总共有60*24个，然后拿这些时间去检验和输入的两个时间是否相符即可。代码写的比较长，不过应该还算比较清晰。惭愧的是连这个题的wa了一次，因为下标变换的时候漏写了一个-1。/* * Author: stormdp

2013-03-03 13:24:48 780

原创 poj 2699 The Maximum Number of Strong Kings

最大流。枚举可能是strong king的人数。把人数和每场比赛（共n * (n - 1) / 2场）抽象成点。建图时：（1）从源点到每个人连流量为score[i]的边；（2）从每场比赛到汇点连流量为1的边；（3）如果score[i] > score[j], 则i和j的比赛只能由j获胜，连j到i和j对应比赛的流量为1的

2012-11-15 15:06:19 544

原创 poj 1087 A Plug for UNIX

其实网络流的题目习惯之后建图还是挺容易的。习惯，好深奥啊。。。#include #include #include #include #include #include #include using namespace std;const int INF = 1 << 20;const int MaxN = 1005;struct NetWork{ st

2012-09-14 22:02:42 463

原创 poj 1034 The dog task

二分图的最大匹配。建图的时候从主人路径上的前（n - 1）个点出发，枚举m个景点，能满足条件的连边，然后求最大匹配，输出路径就可以了。/* * Author: stormdpzh * Created Time: 2012/9/11 20:14:45 * File Name: b.cpp */#include #include #include #include #inc

2012-09-11 20:48:05 988

原创 zoj 1245

分两个方向dp。f[i][j]记录以（i,j）为顶点能达到的三角形最大高度。转移时，取（i，j）“肩上”两个的较小值（当时如果（i，j）正上方是黑色的，那么f[i][j] = 1）.#include #include #include using namespace std;const int MaxN = 100 * 2 + 5;bool mp[MaxN][MaxN];ch

2012-09-05 16:01:39 566

原创 zoj 1088

约瑟夫问题。本题一开始就把第一个人拿了出去，所以本题其实是（n-1）个人的约瑟夫问题。枚举m，因为m的答案不会太大，所以可以直接枚举，然后进行O(n)的判断。总复杂度O(mn)完全可以。#include #include using namespace std;int n;bool check(int m){ int win = 0; for(int i

2012-09-02 12:36:19 727

原创 zoj 1038 T9

题目很简单，意思也很明显。不过感觉这个题过的很顺，代码也还算简单。#include #include #include #include #include #include #define pb push_backusing namespace std;vector vec[12];struct Node { string s; int p; N

2012-09-01 19:02:25 833

原创 zoj 3643 Keep Deleting

只要看到zoj，就什么题都不会做了。。。这个题搞了半天KMP，TLE了还是。比赛结束有人讲了一种方法，用栈去模拟，把b串中的元素一个个入栈，遇到和a相等的就把栈顶出栈。写了几行，过了。叹水平之差兮……/* * Author: stormdpzh * Created Time: 2012/8/26 19:32:30 * File Name: k.cpp */#include

2012-08-26 19:52:25 829

原创 poj 2143 Make a Sequence

题目很简单。只是贴出比赛中写的代码，希望以后多反思。。。由于没有时间了，就没想该怎么做，直接上去怒拍300行代码。。。还好1A了，不然就挂了。/* * Author: stormdpzh * Created Time: 2012/8/20 15:55:18 * File Name: poj_2143.cpp */#include #include #include #inclu

2012-08-20 19:48:22 670

原创 poj 2490 Pimp My Ride

很明显的状态dp。/* * Author: stormdpzh * Created Time: 2012/8/19 15:21:37 * File Name: poj_2490.cpp */#include #include #include #include #include #include #include #include #include #include

2012-08-20 19:43:41 606

原创 hdoj 3685 Rotational Painting

求出凸包和重心，然后一个个看凸包上的相邻点放在地面上能否放稳即可。比赛中写的代码很搓。。。/* * Author: stormdpzh * Created Time: 2012/8/17 15:10:30 * File Name: f.cpp */#include #include #include #include #include #include #includ

2012-08-18 11:38:54 491

原创 poj 1511 Invitation Cards

spfa求两遍最短路，然后求和。/* * Author: stormdpzh * Created Time: 2012/8/15 14:49:29 * File Name: 1511.cpp */#include #include #include #include #include #include #include #include #include #incl

2012-08-15 15:08:23 473

转载北大acm试题分类

转自 http://blog.csdn.net/lyy289065406/article/details/6642573转载请注明出处：優YoU http://blog.csdn.net/lyy289065406/article/details/6642573 最近AC题：2528 更新时间：2011.09.22 已AC题数：146

2012-08-05 13:53:03 642

原创 poj 1634 Who's the boss?

先预处理。记录每个节点的直接父亲和直接儿子，父亲下属的儿子总数就是直接儿子数 + 直接儿子的儿子数。（最坏情况下预处理时间m ^ m / 2）查询效率mq。/* * Author: stormdpzh * Created Time: 2012/7/30 13:51:03 * File Name: poj_1634.cpp */#include #include #includ

2012-07-30 14:07:17 1358

原创 poj 2342 Anniversary party

树状dp搞之。。。再次吐槽，各种不会dp，惨淡的人生啊！！！/* * Author: stormdpzh * Created Time: 2012/7/29 20:45:46 * File Name: poj_2342.cpp */#include #include #include #include #include #include #include #incl

2012-07-29 20:51:52 643

原创 zoj 3622 Magic Number

这种题一般是找规律。写几个小数然后就可以发现规律了。很容易发现1，2，5以及他们的10^n倍一定是符合条件的，另外，相对稍微隐蔽的是25，125以及他们的10^n倍。/* * Author: stormdpzh * Created Time: 2012/7/29 16:25:43 * File Name: a.cpp */#include #include #include #

2012-07-29 18:00:33 766

原创 LightOJ 1210 Efficient Traffic System

求强联通分量，缩点后分别统计出度和入度为0的点，较大者为答案。/* * Author: stormdpzh * Created Time: 2012/7/25 14:11:49 * File Name: ee.cpp */#include #include #include #include #include #include #include #include

2012-07-25 19:12:23 786

原创 poj 2051 Argus

set搞之……/* * Author: stormdpzh * Created Time: 2012/7/22 23:35:15 * File Name: poj_2051.cpp */#include #include #include #include #include #include #include #include #include #include

2012-07-22 23:49:25 596

原创 poj 2023 Choose Your Own Adventure

一个很简单的bfs。不知道为什么poj上过的人很少。。。/* * Author: stormdpzh * Created Time: 2012/7/22 22:44:36 * File Name: poj_2023.cpp */#include #include #include #include #include #include #include #include

2012-07-22 23:07:39 1022

原创 poj 2774 Long Long Message

第一个后缀数组，拍模版……/* * Author: stormdpzh * Created Time: 2012/7/22 14:22:35 * File Name: poj_2774.cpp */#include #include #include #include #include #include #include #include #include #inc

2012-07-22 14:57:53 374

原创 poj 1675 Happy Birthday!

与原点连线的最大夹角不小于120即可。/* * Author: stormdpzh * Created Time: 2012/7/19 16:01:35 * File Name: poj_1675.cpp */#include #include #include #include #include #include #include #include #include

2012-07-19 16:29:18 797

原创 poj 1673 EXOCENTER OF A TRIANGLE

垂心。/* * Author: stormdpzh * Created Time: 2012/7/19 15:12:17 * File Name: poj_1673.cpp */#include #include #include #include #include #include #include #include #include #include #inc

2012-07-19 15:40:31 558

原创 poj 1654 Area

第一个几何题目。叉积求面积。/* * Author: stormdpzh * Created Time: 2012/7/19 12:49:54 * File Name: poj_1654.cpp */#include #include #include #include #include #include #include #include #include #

2012-07-19 13:32:23 579

原创 woj 1022 Competition of Programming

贪心。记住这个。。。/* * Author: stormdpzh * Created Time: 2012/7/14 15:21:06 * File Name: woj_1022.cpp */#include #include #include #include #include #include #include #include #include #includ

2012-07-18 11:33:22 1316 2

poj题目代码

空空如也