sdj222555-CSDN博客

转载 POJ 计算几何入门题目推荐

计算几何题的特点与做题要领：1.大部分不会很难，少部分题目思路很巧妙2.做计算几何题目，模板很重要，模板必须高度可靠。3.要注意代码的组织，因为计算几何的题目很容易上两百行代码，里面大部分是模板。如果代码一片混乱，那么会严重影响做题正确率。4.注意精度控制。5.能用整数的地方尽量用整数，要想到扩大数据的方法（扩大一倍，或扩大sqrt2）。因为整数不用考虑浮点误差，而且运算比浮点

2013-10-17 12:56:02 1578

转载 POJ 图论专辑

转自http://blog.csdn.net/allenjy123/article/details/6627248红色已经AC一、最短路POJ 2449 Remmarguts' Date(中等)http://acm.pku.edu.cn/JudgeOnline/problem?id=2449题意：经典问题：K短路解法：dijkstra+A*(rec)，方法很

2012-08-10 16:53:37 1709

原创 CMU15-440-P0:Implementing a key-value messaging system

准备继续更新blog。最近工作上一直在写业务，看些课程换换脑子。15-440是CMU的一个分布式课程 http://www.cs.cmu.edu/~15-440/syllabus.html ，其实之前在学校的时候就上过分布式的课程，当时用的MIT 6.824的课件，可惜当时很多paper没有仔细去看，只是把作业做了下，除了lab1都没有写blog记录，导致后来有时间写blog的时候很多细节

2017-10-26 21:37:08 2819

原创 GCJ 2016 QR解题报告

A. 题目大意是，给你一个初始的整数，然后用他*1, * 2,*3 ....，并把所有出现过的数字记录下来，问什么时候0～9所有数字都出现了一遍。刚开始还怀疑有没有可能死循环，后来没想直接跑了一个1～100000的看了下，都有结果，就直接暴力上了。#include #include #include #include #include #include #includ

2016-04-10 16:53:51 936

原创 MIT 6.824 Lab1 mapreduce

这学期选了分布式计算这门课。不得不说真的是一门有料的课程。所有的东西讲的都是MIT 6.824上的，Lab也是一样。不过干货太多带来的也就是，需要花费比较多的时间去看资料和写代码。但是我喜欢这种感觉。课程网址是 http://nil.csail.mit.edu/6.824/2016/schedule.htmlLab1 是mapreduce的一个实验花了我大

2016-03-13 02:11:47 3635 1

原创 docker在mac上配置并建立后台容器

1. 首先需要去官网上下载并安装docker https://docs.docker.com/mac/step_one/步骤很简单。2. 启动docker 启动docker有多种方法，可以在launchpad里用quickstart terminal。也可以在命令行里使用 eval $(docker-machine env default)从而将docker启动起来

2016-03-04 17:34:52 4598 1

原创 Codeforces Round #288 (Div. 2)

A,B,C水D。有一个串，长度为n+2，现在知道他的所有n个长度为3的子串是什么求出原始的串这题跟POJ 2337有点像最后抽象出的问题就是求欧拉通路：将每个长度为3的子串，前两个字母(数字）看成一个结点，后两个字母(数字）看成一个结点，然后这个子串就相当于一条从前一个结点到后一个结点的边欧拉通路的要求就是所有边都要走一

2015-01-28 23:03:55 1190

原创 POJ 3783 Balls 动态规划

题意：给定B (B 方法就是动态规划了。虽然刚开始一直以为是个贪心或者构造dp[i][j] 表示有i层楼，剩余j个球时，最坏情况要确定K 所需的次数那么在这些楼层里我们可以选择在k层(1有两种情况，破跟不破(1)不破，则排除掉了k层，剩余i-k层则转化为 dp[i - k][j](2)破了则剩余i - 1层，球剩k - 1个转化为 dp

2015-01-24 20:57:21 2123

原创 POJ 3784 Running Median 动态求中位数堆

题意。1000个case每个case 输入若干个数，对第k个输入，如果k为奇数，则输出前k个数的中位数那么这就是动态求中位数了实现的思路也比较简洁用两个堆，大顶堆和小顶堆每次输入一个数，如果这个数比当前的中位数大，就存入小顶堆中，否则就存入大顶堆。然后调整，小顶堆元素的个数要等于大顶堆的元素个数，或者比其多1。如果小顶堆的元素太多，就

2015-01-23 17:36:21 4462

原创 POJ 3762 The Bonus Salary! 最小费用最大流

题意最后可以简化为给出若干个区间，每个区间由左端点，右端点，权值构成。挑出若干个区间，使得权值和最大，但必须满足区间任意部分重叠次数不超过k这题跟POJ3680一样一样的构图是这样先把这些区间都给hash了。 hash完必然这些区间端点都落在1,2,3..., cnt 这些数中， cnt是hash完不同数的个数然后建边，源点为S，汇点为TS到1

2015-01-23 16:23:23 1191

原创 POJ 3761 Bubble Sort 冒泡排序的扩展

给一个序列，如果经过k次冒泡能使其变为单增序列，则称该序列为k回合冒泡序列现在给你n,k，问在n的全排列中，k回合冒泡序列有多少个这题看规模就是要推一个公式出来discuss里的一个解法非常好，让人可以理解对于n个元素，假设为{0,1,...n- 1},可以发现对于任意一个排列，假设L(i) 表示位置i上的元素的前面有多少数字比它大, 那么得到了一个L序列。那么可

2015-01-23 15:29:37 1016

原创 POJ 3785 The Next Permutation 全排列字典序法

给一个排列求下一个排列按字典序跟普通排列不同的地方就是有相同的数字那么就把普通的一改就完事#include #include #include #include #include #include #include #include #include #define MAXN 222#define MAXM 6122222#define INF 10000

2015-01-23 00:53:15 1369 1

原创 POJ 3715 Blue and Red 二分图

说是有一个军事演习n个士兵，其中有m个关系表示某两个人是好友现在士兵已经分好了两组了，用来进行对抗，但是这两组之间可能有好友，会影响军事演习的情况所以要去掉尽量少的人，使得这个两组之间没有好友。那么题目给了一个分组方案了，但是不同组之间可能有好友，我们就要在这些个不同组的好友之间连边然后求二分图最大匹配，求出来的结果就是要去掉的人数但是题目又要求字典序要

2015-01-23 00:38:57 1665

原创 POJ 3764 The xor-longest Path 字典树求最大异或

题意，一颗树，每个边有个值，在树上找一条简单路径，使得这条路径上的边权异或值最大把这题模型转换一下，对于任意一条路径的异或，表示为f(u, v)则f(u, v) = f(1, u) ^ f(1, v)这是显然的其中f(1, i)是可以再O(n)内处理出来然后就是在一个数组内，找两个数异或值最大然后就可以用字典树来搞每个数变成01串，然后插入字典树，

2015-01-22 23:15:44 5065 2

原创 POJ 3716 Panda's Birthday Present 条件概率

看了http://hi.baidu.com/bfcdygoporbjuxr/item/569897ddc1fc561d21e2503f 这个题解感觉写的有点费劲，而且虽然写了一点关于公式(m+n+10)/7的，但我感觉还是不好理解啊。不过其中讲的主要思路还是有用的。对于一个骰子有t个面为1的概率是 P(T=t)=C(6,t)/64。在有t个面为1的情况下，投n次，

2015-01-22 20:26:10 1539 1

原创 POJ 3728 离线 LCA

题意很简单给一个树(n 若干个询问(5w)对每个询问，问的是从u点走到v点(简单路径），商人在这个路径中的某点买入商品，然后在某点再卖出商品，最大可能是多少注意一条路径上只能买卖一次，先买才能卖用的方法是离线LCA，在上面加了一些东西对于一个询问，假设u,v的LCA是f那么有三种可能，一个是从u到f 买卖了。一个是从f到v买卖了，一个是从

2015-01-22 01:38:17 2094 1

原创 POJ 3744 Scout YYF I 简单递推

题意就是一个人，站在坐标为1的点处，然后每次走路有p的概率一下走出去坐标1，1-p的概率一下走出去坐标2路上某些点(n 想一下就知道这些雷之间实际上是独立不相关的可以分段考虑然后互相之间乘一下就行假设有个雷在x点现在人在坐标1然后不踩雷就得从1点到x-1点并且从x-1点迈出坐标2到x+1从x-1迈出坐标2到x+1的概率是1-p之前1到x-1这段

2015-01-21 21:42:37 885

原创 Codeforces Round #281 (Div. 2)

这场题也不难。不过自己一直犯逗。不是题目看错就是数组开小。A，B，C，D都还挺水的，E其实也挺简单，只不过我当时没想明白。。C的话，枚举所有可能的d即可，复杂度是排序的nlognD的话，对于奇数来说，黑方只需要跟白方对称走就一定能赢偶数的话，白方往1,2走一步就变成了奇数的情况，然后黑方咋走，白方就对称走就行。所以最后白方一定能赢E

2014-12-04 17:12:07 959

原创 Codeforces Round #280 (Div. 2)

这场题简单的令人吃惊ABC几乎都是签到题D的话把两个人的射击时间转化成整数求个gcd，除一下。假设两人的射击频率分别是1秒x,1秒yx,y的gcd为g转化一下就相当于第一个人 y/g 秒射一发，第二个人x/g秒射一发然后两个人在 x/g*y/g 秒时会同时射击那么每个x/g*y/g秒就是一个周期了假设怪物的血有a，那么a%(x+y)就是

2014-12-04 16:57:04 828

原创 BestCoder #20

A,B水B的话可以花式做线段树可以优先队列可以最好的方法就是离散后，对一个线段xi,yi分成两个端点xi和yi+1表示在xi点会加入一个线段，在yi+1会减少一个线段用数组来存就是a[xi]++, a[yi+1]-- ，然后求a数组的最大前缀和就行了D 题是个DP题意是，有n（1e3)个数对，a[i],b[i]某个人有m(1e3)个能量，按顺

2014-12-01 01:51:16 1992 1

原创 HDU 3842 Machine Works cdq分治斜率优化

本题是利用cdq分治实现斜率优化的一个题目斜率优化之前做的几个题都是斜率单调，并且插入点时由于点在某一维单调，所以仅仅操作队首和队尾就能完成优化了但是本题显然不是主要参考了两个东西从《Cash》谈一类分治算法的应用(Day1)cdq分治相关这两个直接在百度上搜，第一个出来的就是本题的题意是一个公司获得了一个厂房n(10^5)天的使用权

2014-11-08 13:48:21 3366

原创 Codeforces Round #276 (Div. 1)

这个场由于系统出问题 unrated了题目都还挺短小精悍的A题目大意是有n个询问(10^4)，每个询问是找出在[l,r]区间内二进制位1最多的数l,r范围是10^18然后就是贪心。用 l 从低位往上贪就行了，0变1如果不超范围就变long long l, r;int n;int main(){ scanf("%d", &n); f

2014-11-07 16:01:23 1568 2

原创 Codeforces Round #148 (Div. 1)

Awool sequence 表示一个序列中可以找到一个连续的子区间使得区间异或值为0那么求的是不含这种情况的序列个数题目中数据范围是，在0~2^m - 1中选n个数作为一个序列 n和m都是10^5仔细思考一下。第一位有2^m-1种情况第二位由于不能跟其一样有2^m-2种情况第三位由于不能跟第二位一样，并且不能跟前两位的异或值一样，有2

2014-11-05 17:21:03 1044 1

原创 SRM 638 Div2

2333.。。由于TC参赛数太少，加上不断的fst 我都降到div2了。还好做完就回div1了。。250水题500水题。。直接bfs扩展就行了注意判重，我还用康托展开了真是多此一举。。1000这题理解错题意了。。我说看别人代码怎么看着不对劲来着不过还是非常容易的一道题二进制枚举烧哪些叶子结点然后对每种烧法求最短路求完最短路，枚举边

2014-11-03 13:38:35 1341

原创 SRM 400 Div1

这套题做的蛋疼菊紧250 简单题。问一个数能否被表示成某个素数的若干次方我用了一个很损精度得法其实只要判平方完了直接枚举素数就OKvectorans;bool check(int x) { int m = (int)sqrt(x * 1.0) + 1; if(x == 2) return true; for(int i = 2; i

2014-11-02 23:12:52 954

原创 Codeforces Round #149 (Div. 2)

这个round真的太简单了。。A，B就不说了C 题目说了合法的点不会超过10^5个那么直接离散化，完了跑bfs就行了离散化用map就行#include #include #include #include #include #include #include #include #include #define MAXN 111#define MAX

2014-11-01 21:25:55 895

原创 Project Euler problem 69

考察欧拉函数的一道题首先要知道【定理】正整数n(n≥2)可以唯一分解成素数乘积，即：n =p[1]^r1 * p[2] ^r2 * p[3]^r3. *...* p[s]^rs其次欧拉函数有两个性质，可以用来编程，单独求phi函数：① phi(m) = m ( 1- 1/p[1]) ( 1- 1/p[2])…( 1- 1/p[s])② phi(p^k)

2014-10-27 22:00:56 986

原创 Project Euler problem 68

题意需要注意的一点就是，序列是从外层最小的那个位置顺时针来的。

2014-10-27 21:47:02 916

原创 Codeforces 274 DIV1 C - Riding in a Lift 动态规划

题意很简单吧。

2014-10-25 22:42:39 683

原创有限制的最小费用最大流格格取数

给你一个m x n (1 ij这个题目有个限制，不然就非常简单了，每行每列至少选择了一个数，即每行可以多选，这与平常所做的那种简单的最小费用最大流有些不一样。那么在建图上我们需要做出一些变化还是那样每行每列都对应一个结点我们需要强制其每行每列都选择到了数首先源点向每个行结点连容量为1，花费为-100000的边每个列结点向汇点连容量为1，花费为-100000的边，

2014-10-23 16:43:49 939

原创 UVA1440 有下界的最小流

题意很简单：给出一张有向图，每次你可以从图中的任意一点出发，经过若干条边后停止，然后问你最少走几次可以将图中的每条边都走过至少一次，并且要输出方案这个转化为网络流的话，就相当于求一个最小流，并且存在下界，即每条边至少走一次这让我联想到很久之前的一道题，也是有向图，问走多少条路径可以将整个图中的每条边都走过，但是跟本题不同的是，那题是不允许重复走边的。那道题目的解是这样的：

2014-10-22 21:14:01 1583

原创 POJ 3709 K-Anonymous Sequence 斜率优化

容易得出简单的递推方程如下f[i] = min{f[j] + sum[i] - sum[j] - (i-j) *x[j+1] }然后发现复杂度太高这时可以看出是一个比较经典的斜率优化f[i] = min{f[j] +j *x[j+1] -sum[j] -i *x[j+1]} +sum[i]按照http://blog.csdn.net/sdj22

2014-10-20 23:31:51 2117

Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到T个城镇 (1 <= T <= 25,000)，编号为1T。这些城镇之间通过R条道路 (1 <= R <= 50,000，编号为1到R) 和P条航线 (1 <= P <= 50,000，编号为1到P) 连接。每条道路i或者航线i连接城镇A_i (1 <= A_i <= T)到B_i (1 <= B_i <= T)，

2013-11-21 18:43:39 2684

原创 [Usaco2009 Nov]lights 燈

又是一关于操作灯开关的题目。一眼看去就知道是高斯消元。但是，该题的重点是输出一个最小操作数的解！这就需要进行枚举自由变元了！如果学习过线性代数的话就知道了。将矩阵转为下三角矩阵后。有一种东西叫关键元。就是每一行的第一个非零元。通常来讲这个第i行的关键元应该在第i列才对。否则就会出现多解的问题。那么如果多解的话。这个本来应该是关键元的地方就成了自由变元了。

2013-11-08 14:18:44 1795

原创 [Usaco2009 Jan]安全路经Travel dijkstra + 并查集

这题确实非常好！对最短路径可以有更深刻的理解。Gremlins最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的地是牛棚_i).每一个gremlin只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经.所以它们在牛_i到牛棚_i之前的最后一条牛路上等牛_i. 当然,牛不愿意遇到Gremlins,所以准备找一条稍微不同的路经从牛棚_1走到牛棚_i.所以

2013-11-07 11:35:04 2229

原创 [Usaco2007 Oct]Bessie's Secret Pasture DP

农夫约翰已经从他的牧场中取得了数不清块数的正方形草皮，草皮的边长总是整数（有时农夫约翰割草皮的刀法不合适，甚至切出了边长为0的正方形草皮），他已经把草皮放在了一个奶牛贝茜已经知道的地方。贝茜总是希望把美味的草皮放到她的秘密庄园里，她决定从这些草皮中取出恰好4块搬到她的秘密庄园中，然后把它们分成1×1的小块，组成一个面积为N(1网上有人直接枚举过的。。n ^ 2的复杂度吧，也

2013-11-06 21:50:22 1527

原创 [Usaco2009 Mar]Cleaning Up

有N头奶牛，每头那牛都有一个标号Pi，1 这里的M貌似没什么用。分成若干段是想分多少段就多少段。首先需要发现这个问题。如果在某段区间中，不同的数超过了sqrt(n)个，那么很显然，我们还不如将整个区间分为n段。那么我们就不用管区间不同数超过sqrt(n)的数了。令数组b[j]表示从b[j] + 1到i 不同的数的数量不超过j的最左端也就是说a[b[j

2013-11-06 18:24:06 1976

原创 [Usaco2007 Feb]Cow Sorting牛排序

农夫JOHN准备把他的 N（1 这题刚开始我还以为是逆序对。后来想了想。需要求个置换，然后每个置换内部搞就可以了。这时每个元素必然不在自己的位置上。然后置换内部搞的话。首先肯定是拿最小的元素跟其他元素换来换去。这样在内部肯定是最优的。但是我没考虑到一个问题就是，我既然可以拿置换内部最小的去跟别的元素换。我也可以所有数中最小的元素换到这个置换中，再去跟置换

2013-11-06 18:10:22 2039

原创 [Usaco2008 Jan]电话网络贪心 or 树形DP

Farmer John决定为他的所有奶牛都配备手机，以此鼓励她们互相交流。不过，为此FJ必须在奶牛们居住的N(1 <= N <= 10,000)块草地中选一些建上无线电通讯塔，来保证任意两块草地间都存在手机信号。所有的N块草地按1..N 顺次编号。所有草地中只有N-1对是相邻的，不过对任意两块草地A和B(1 <= A <= N; 1 <= B <= N; A != B)，都可以找到一个以A开

2013-11-06 18:03:30 1850

原创 HDU 4763 EXKMP

题意是在一个字符串中找出一个前缀一个后缀和一个中间的子串，互相不重叠并且三部分完全一样运用的是exKMP对自身求一个next数组next[i]表示以i为开始位置的子串与整个串的前缀最长匹配到多少长度然后就是枚举了首先求一个可能存在的最大长度。在一个位置i中，如果要满足要求，子串的最大长度不能超过 min(i, next[i], (len - i) / 2);所

2013-11-01 14:47:56 2655

归并排序实现

堆排序实现

插入排序实现

java 俄罗斯方块源码

空空如也