zyjhtutu-CSDN博客

原创 docker-nvidia 安装问题

docker-nvidia安装过程见官网 : https://devblogs.nvidia.com/parallelforall/nvidia-docker-gpu-server-application-deployment-made-easy/我在安装过程中遇到了一个错误，如下： level=error msg="Handler for POST /v1.24/

2017-04-07 09:58:22 5815 1

原创欧拉函数 codeforces 776E

776E题解 http://www.cnblogs.com/Just--Do--It/p/6437212.html欧拉函数性质 http://www.cnblogs.com/exponent/archive/2011/08/09/2131960.html

2017-03-15 20:45:32 677

原创 codeforces 754D. Fedor and coupons

题意比较简单，给定n个区间，选择其中k个区间，并且这k个区间的重叠最大。这个题目当时也是想了很久没有想出来。后来看了题解，觉得这是一个典型的问题，有一般的解题思路。一般的解题思路为，将区间按照左端点从小到大的排序，然后利用优先队列，将排序后的区间的右端点依次进入队列（右端点小的在队首），保持队列中只有k个区间的右端点。用队列的队首减除刚入队区间的左端点，得到的便是队列中k个区间的重叠部分，依次更新

2017-02-25 08:40:16 391

原创 codeforces 747D Winter Is Coming

这个题目比赛的时候想了好久，也没有做出来，当时想是个dp或者贪心，想着贪心的题目，dp应该也能做，所以就一直在dp上想，但是没有解决办法。今天有空就看了看这个题目。codeforces给的标签是贪心，自己就往贪心上想了想，最后解决了。其实用贪心的话并不难想，先判断是否可以度过整个冬天，这个比较简单就不再多说了。假设每次遇到0下的天气都需要换成冬天用的轮胎，而用完这一天之后就换成夏天用的轮胎，这样的

2016-12-21 09:58:40 536

原创线段树 codeforces Alyona and towers 739C

今天在CF上面看到一个题目，是有关线段树的。好久没有写过线段树，基本都已经忘完。没办法，后来只得看了网上的题解。写下这篇博客，总结一下线段树的操作，便于以后学习，复习。线段树主要树用来维护区间信息，快速的更新与查询的数据结构，在运用过程中，需要根据具体情况，判断出需要维护的信息，达到快速查询，更新的效果。与它的功能对应，线段树的操作主要是更新和查询，当然还有建树（建树类类似于更新）对应的代码中，也

2016-12-16 19:09:52 569

原创 codeforces 743D. Chloe and pleasant prizes

题目大意：给定一个以1为根结点的树，树上每个节点都有一个权值。求取两个不相交的子树。使两个子树的权值和最大。刚看到这个题目的时候，以为只需要求出每个子树的最大权值，然后先选取一个最大的，然后把相关的子树和该点到父节点的的路径上的所有点去掉就可以了。提交，果断WA。然后看数据，找错误，然后还是各种WA。最后仔细思考，这种方法其实时不对的，举个例子，假设某个子树A时当前权值和最大的，那么，如果选了它，

2016-12-16 17:23:42 441

原创二分图相关概念二分图最大匹配二分图最大权匹配 poj3041 poj2195

昨天在codefoces上见了一个二分图相关的题目(http://codeforces.com/problemset/problem/741/C)，今天周末没事。就复习《算法竞赛入门经典》总结了一下二分图的相关概念，以及经典的二分图最大匹配算法，二分图最大权匹配算法。先安利一波概念：二分图：假设图G = (V, E)是一个无向图，若顶点集可以分解成两个互不相交的子集(A, B),并且图中的

2016-12-10 20:09:43 385

原创 codeforces 739B B. Alyona and a tree

这个题目想了好久都没有想出好的方法，最终看了别人的思路解决的。写一篇博客纪念一下做这个题的想法和学到的一些新东西。读这个题的时候以为会是dp，仔细想了想，又不太符合dp的特征。然后，就按照数据结构的想法思考，想了好久，还是没什么思路，而且用队列，从叶子节点模拟了一发，以为可以过。提交的时候才想起来，肯定会TLE呀，结果果断TLE，想想也是醉了。最后想着想着，觉得时间复杂度怎么也应该时n*lgn才能

2016-12-01 22:02:23 1472

原创 codeforces 725D Contest Balloons

题句题意很容易理解：Limak可以把自己获得的气球送给别人，使别人的气球大于体重。从而让别人漂浮的天花板上，不能参与排名，从而使Limak自己的排名上升。这个题目是一个典型的贪心，当Limak把自己的气球给别人的时候，他自己的手中的气球就会减少，那么他自己的排名也是有可能降低的。那么，我们就需要思考，Limak应该把气球给什么样的人，他自己的排名才有可能上升。其实，很简单，他肯定是把气球给当前排名

2016-11-12 21:04:47 391

原创 codeforces 730 J. Bottles

这个题目题意很好理解，说的是将n个水甁中剩余的水全部倒进k个瓶子中。其中，让k最小，而且所需要倒的水最少。简单的说，就是在保证k最小的前提下，让k个瓶子中原有的水量之和最大。想这个题目的时候也想了好一会，其实看清本质，就是一个0-1背包的问题。首先，k值最小不难确定，这里就不再多说。确定k值后，就是要确定出，这个n个瓶子中，选择哪k个才是符合要求的。对于每个瓶子，无非就是选还是不选的问题。那么

2016-11-06 15:37:45 805

原创 codeforces 733D Kostya the Sculptor

这个题目的题意比较简单：给定n个长方体，两个长方体可以粘成一个新的长方体的条件是两个长方体有一个面大小是相同的（长和宽都相同），最多允许两个长方体粘在一起。要求求出内切球最大的长方体（有可能是两个粘成的新的长方体，也有个能是原始的单个长方体）。解决的方法也比较简单，大致说一下思路：这个题目的关键就是如何快速的判断出这n个长方体中，哪些是可以粘在一起的。如果两两分别判断，肯定超时，我的做法是

2016-11-02 20:07:56 417

原创 codeforces 732E. Sockets

题目的题意就不多说了，这个题我做的时候想了很久。写完代码之后，提交也是一直WA17。一直在考虑是不是自己的想法有问题。后来看了别人的代码。发现其实，解决问题的思想是一样的。我的想法是将枚举每个插座要接的转换器的数量，然后依次判断每个电脑是不是正好可以连接上。但是我是用二分来实现查找的，因为涉及到会有相同的电量的插座，查找的时候家了一些小技巧，让它每次找到的都是第一个没有被使用的插座。但是可能实现上

2016-10-20 12:30:28 542

原创 731 C. Socks

今晚的比赛时间比较合适，就果断注册做了一下。结果真实惨呀。只过了一个题，第二题和第三题比赛的时候思路都是对的，后来比赛结束后判题有些细节没写好。结果WA了。也是太久没刷题的原因了。第三题刚开始是TLE，后来优化了一下。我是用bfs做的，思路通过bfs是将有关系的袜子放在一起，因为这些袜子最后是要涂成同一种颜色的。然后在这堆袜子中，某种颜色的袜子最多，就将其作为这对袜子的最终的颜色。这样保证要涂的次

2016-10-16 21:30:17 437

原创 Codeforces Round #368 (Div. 2) D - Persistent Bookcase

题目大意是对一个n层，每层有m个位置的书架进行4种操作： 1）在位置(i,j)上放一本书，如果已经有书，则不在方书 2）拿走位置(i,j)上的一本书，如果没书，则不能拿走 3）将第i层的所有位置的状态翻转，如果某位子有书，则拿走，如果某位置没书，则放一本书 4）将书架的状态还原到之前的某

2016-08-22 19:34:16 327

原创 D. Swaps in Permutation

这个题目的题意是，给一个长度为n的数字序列，其中各个元素均不相同且在1到n之间。然后给出一些位置的交换规则，即给出某些位置上的数是可以互相交换的。求出最终能交换得到的字典序最大的序列。题目的解决方法并不难，举个例子：如果位置1能和位置2山的数交换，位置1又可以和位置3上的数交换，那么，位置1，2，3对应的数实际上是可以互相交换了，那么该字典序最大的序列就是位置1，2，3上的元素从到小的序列了。

2016-07-17 20:10:25 606

原创 C. Exponential notation

这个题典型的模拟题，各种情况要考虑:1.为0的情况 1)0 2)00 3)0.02.没有小数点的情况 1)16 2)100 3)001 4) 13.带小数点的情况 1)100. 2)100.00 3)01.00 4)1.010

2016-07-17 19:50:55 398

原创 B. Remainders Game

这个题目想了很久，也还是没有什么思路。后来看了别人的想法，自己实现了一下。题目的意思是已知k和ci，问你如果给出了x%ci，是不是就能确定x%k。这个题目，个人觉得这篇博客讲的比较清楚。 http://www.cnblogs.com/shuguangzw/p/5629564.html。以下是我自己的实现的，主要是判断ci的最小公倍数是不是k的倍数。判断思路如下：将k分解p1^x1*p2

2016-07-15 20:39:38 487

原创在ubuntu上Kubernetｅｓ集群部署

1. 部署环境: （１）Ｕｂｕｎｔｕ 14.04 (2台装有该版本的笔记本电脑)　（２）Ｄｏｃｋｅｒ 1.9.1 （３） etcd-2.2.5 （４） Kubernetes 0.9.02. 配置Ubuntu 14.04 (1) 由于只有两台主机，所以这里一台主机既充当Master又充当minions：　　　　Ｍａｓｔ

2016-03-31 10:15:18 506

原创 hdu 1021

刚开始，我以为这个题需要求出0~1000000之间的Fibonacci数，后来想想Fibonacci数的增长速度特别快，肯定不会让真正求出所有的Fibonacci数。然后我仔细想想，发现3的倍数很有规律的，像f(2),f(6),f(10),f(14),f(18).....这样的才是3的倍数，所以问题就变得很简单啦~#include#include#include#includeint

2016-03-07 09:38:26 328

原创 hdu 1019

这个题需要注意的就是在计算最小公倍数的过程中数的范围有可能超过32位整数，所以我用了—int64位。#include#include__int64 gcd(__int64 a,__int64 b){ __int64 c,f1,f2; f1 = a; f2 = b; while(b!=0){ c = a%b; a = b; b = c; } return f1*f

2016-03-06 15:19:10 381

原创 hdu 1017

这个题需要之一的一点就是特别注意输出格式的问题#include#includeint main(){int n,m,t,i,j,sum,k;scanf("%d",&t);while(t--){k=1;while(1){scanf("%d%d",&n,&m);if(n==0 && m==0) break;sum=0;for(i=1;i

2016-03-06 13:47:11 641

原创 hadoop2.x上的Hive-1.x 安装

hadoop2.x上安装hive1.x1.下载hive-1.0.1.tar.gz http://mirrors.hust.edu.cn/apache/hive/,这个上面只有最新的几个版本，更老的版本下载请去http://archive.apache.org/dist/hive/2.解压hive-1.0.1.tar.gz。tar -zxvf hive-1.0.1.tar.gz3

2015-12-12 21:36:50 828

原创 558C Amr and Chemistry

题意：给出一组数据，让你对其进行整除、扩大2倍两个操作将这组数变换成相同的数。所用的步骤最少，并求出这个最少的步骤。思路：这个题目我也想了好久，之间还贡献了几次WA，思路是这样的，基本上就是贪心，这之前要明白一点就是：如果两个数之间没有2^n倍的关系，那么这两个数不管怎么扩大，都不可能到达一个相同的数。于是基于这样，可以判断出最终到达的这个数肯定小于或等于这个数组中最大的数。而我们可以预先求出

2015-07-21 10:51:15 366

原创 557C Arthur and Table

题意：题目给出的桌子的n条长度不一的腿，以及打断每条腿所需的花费。要求在最小的花费下，使桌子达到平衡。平衡的条件是最大腿的个数要大于总的腿数的一半。思路：这道题刚开始往dp上考虑，结果怎么搞，都找不出最有子结构，导致状态无法定义，最后放弃dp。想着试一试枚举平衡时最大腿的长度，然后各种数组记录。本来以为会TLE，最后过了46ms。具体实现见代码。#include#include#inc

2015-07-21 10:34:10 435

原创 526C - Om Nom and Candies

#include#include#include#include#include#include#include#include#pragma comment(linker, "/STACK:102400000,102400000")#define ll __int64using namespace std;int main(){ ll c, hr, hb, wr, w

2015-04-05 09:46:38 629

原创 526B - Om Nom and Dark Park

#include#include#include#include#include#include#includeusing namespace std;const int MAX = 1000000;int c[MAX];int ans;int dfs(int root){ int l = root*2; int r = root*2 + 1;

2015-04-05 09:45:00 442

原创 526A - King of Thieves

#include#include#include#include#include#include#includeusing namespace std;const int MAX = 1000;char s[MAX];int main(){ int n; while (scanf("%d%s",&n,s) != EOF){ int ok

2015-04-05 09:43:41 470

原创 POJ3254 Corn Fields

dp题，想了好久都没有想到什么好的方法。自己也写了好久都是一直wa。后来看了别人的想法，才恍然大悟。原来子的状态没有定义好。状态的定义还是的从基本的dp的最优子结构和无后效性考虑。这个题目值状态比较新颖。将每一行看作一个二进制数。然后定义dp[i][j]为第i行的各个位置状态为j时所能得到的数量，其转移方程为dp[i][j] = dp[i-1][k]，概括的说就时，第i行状态为k时的结果为第i-1

2015-04-01 22:02:01 327

原创 POJ1925 Spiderman

题目刚一看没有什么思路，不知道状态如何定义，后来仔细想了想。状态d[i]可以定义为从i坐标跳到终点花费的最少步骤时多少。显然，这样的定义用递归实现比较方便，也许时最近刷的dp都是用递归解决的。但是递归比较慢，导致超时。最后一直在想有没有什么方法剪掉一些状态，始终也没有想到什么好的办法。后来看了别人的题解。用的是递推。状态定义为，到达i坐标时花费的最少步数。自己按照这个思路写了一遍。下面时代码。注意

2015-03-26 22:32:01 323

原创 POJ1191 棋盘分割

由于题目是中文的，这里就不解释题目大意。是一个很好的dp题目，不过这个题目需要将平方差公式变形，两次运用dp的思想，对中间结果dp。然后的求出最终结果。#include#include#include#include#include#include#includeusing namespace std;const int MAX = 10;const int MAXN =

2015-03-24 22:51:09 507

原创 POJ 1691 Painting A Board

一个很好的DFS题目，题意为如果一个区域的上面的区域没有被油漆，那么这快区域还不能被油漆并且每块区域的只能被油漆一次。由于每块区域要求的颜色不同，让你计算一下当所有的区域都被油漆时，最少需要更换几次颜料。#include#include#include#include#includeusing namespace std;const int MAX = 30;struct

2015-03-24 22:20:51 295

原创 POJ1724 ROADS

这个题目是一个比较简单dfs，用到的技巧并不多，只是常用的剪枝。两处剪枝即可：1，当价钱超出K时；2，当前的道路长度大于已经得到的道路长度时；这个题目还有一点值的注意的是，不要用vector存图，这样容易TLE。改用邻接表就好。#include#include#include#includeusing namespace std;const int MAX = 110

2015-03-23 14:04:15 353

原创 POJ3411 Paid Roads

这个题目是寒假在家看的，当时没有想到怎么做，后来看了别人的题解。说说是如果每个城市到达的次数大于3次，所走的方案中必然出现回路。所以只需要用一个vis[]数组记录每个城市走的次数即可。至于为什么是这样，我也没有想明白。这里先粘上自己的代码吧。#include#include#include#includeusing namespace std;const int MAX = 15

2015-03-23 13:49:00 288

原创 centos7 配置iptables 开放80端口

因为最近在学习PHP,安装了PHP和apache之后，写的一些脚本在本机上一直都可以访问，单纯的为了学习PHP就没有太在意其它电脑能不能访问的问题，认为那是理所当然的可以，当时今晚在宿舍试了一下，神奇的发现竟然不可以，咋办，只能去网上找解决办法，有人就说是因为防火墙没有开放了80端口，于是就把防火关了，果然可以访问了。接下来就是配置方后墙iptables文件，将80端口开放即可，可是问题来了，由于

2014-12-14 23:19:30 5239

原创郑州大学linux安装锐捷客户端

最近在学习linux ，一直想着能在宿舍用linux直接上网，但是一直觉得这是个比较麻烦的东西，所以一直就没有去好好的研究它，直到昨天，在图书馆闲着没有事干，就去校园网上考了锐捷客户端的linux版,好好看了下附带的使用说明，觉得自己能搞好，会晚上会宿舍后就准备好好搞下，虽然很简单，但是菜鸟也是搞了好久啊，，，，这里就把过程分享给大家吧。在使用锐捷登陆之前要配好静态ip,linux静态ip的配

2014-12-14 22:58:23 4590

原创 poj3273 poj3258 二分答案

二分答案的方法比较常用，思想比较简单，就是从结果出发解决问题，已知答案在某一个区间中，并且根据某种判定条件，能够确定当前所选的值是大了还是小了，我们通过二分的方法将其找出来，从而降低时间复杂度。当然，这个判定条件就是二分答案的关键啦。通常，判定函数是一个贪心算法。二分答案的方法通常用来解决最小值最大或最大值最小等问题。今晚做了两个简单的二分答案的题目，一个是求最小值最大，一个是求最大值最小，它们在

2014-12-11 23:24:42 516

原创 hdu4455 dp

这个题目是2012年的区域赛的题目，是一个典型的dp题目，但是状态定义，即状态转移方程真是不太好想。自己一直在往多维的状态上想，但是都觉得不合理。后来，我也是看了大神的题解才明白的。自己就试着写下自己对这个题目的理解。题目的意思比较好懂：就是给定一个长度为n的序列。然后让你求出它的所有长度为m的连续子序列中，每个序列里不同元素的个数，并将求其和。题目思路：状态定义为dp[i]表示子序列的长度为

2014-12-09 23:19:52 569

原创 poj2388 简单排序——归并排序

这个题是一个很水的排序题，C/C++本身就提供了排序函数而且速度已经很好(n*log(n))的复杂度。只是前两天数据库老师讲课的时候提到了归并排序，自己就觉得当时学的时候有点模糊，今晚就自己敲了一下，发现也没当初想的那么难。其实，归并排序有好多应用场景，比喻求逆序对数就是其经典的用法。算法思想很简单，就不多说了，直接贴代码吧。poj2388#include#include#de

2014-12-09 23:08:04 357

原创 poj3264 树状数组维护区间最值

树状数组维护区间最值类似于RMQ是一种易于理解，容易实现的方法。其方法是用数组c[i]记录c[i-lowbit(i)+1] ~ c[i]的最值；对于更新节点i：则节点i影响到的节点都得更新，即：for(int j = i; j对于查询区间[u,v]最大值：查询比较麻烦，具体看例题解释；充分利用lowbit的性质逐步缩小区间的长度poj3264#include#include#

2014-12-08 23:40:10 791

原创 poj3468 树状数组解法（树状数组维护区间更新）

这个题目是一个经典的线段树维护区间跟新问题。后来在看书装数组维护区间和的时候，发现有好多大神说这个题目也可以用树状数组来解。后来就也研究了一下。当然，和大多数用树状数组解的题目的思路差不多，只是这个不太好想。根据树状数组的特点：树状数组是维护前缀和的经典做法，它的更新是对数组中的一个元素的，就是每次更新只能改变一个元素的值。那么，如何用树状数组来维护区间更新呢。源数据放在a[]数组中。这就需要构造

2014-12-07 23:00:55 591

空空如也

空空如也