- 博客(116)
- 收藏
- 关注
RSS订阅原创 无 root 源码安装 tmux （只有代码）
tar zxf ncurses-6.2.tar.gzcd ncurses-6.2/./configure --prefix=$HOME/localmake && make installtar -zxf openssl-1.1.1h.tar.gzcd openssl-1.1.1h/./config --prefix=$HOME/local/openssl --openssldir=$HOME/local/openssl sharedmake && make i
2021-05-11 15:16:20
165
原创 docker 容器如何开启 ssh 远程连接和 X11
docker 容器如何开启 ssh 远程连接和 X11创建容器安装 ssh 及修改配置安装 xorg 及修改配置创建容器docker run -it -p 50002:22 -v (dir):(dir) -e DISPLAY (image)安装 ssh 及修改配置进入 docker 后passwd # add root passwardapt updateapt install vim openssh-serverservice ssh startservice ssh status
2021-05-11 15:13:33
6297
3
原创 hdu2430Beans(单调队列)
看好几篇题解都不知道怎么做！先抄一遍代码再说，好像发现了点问题，构造了一个多小时的数据，再想，再想，懂啦！！！———————————————————————-题意： a[1], a[2], …, a[n] 取连续的一段（至少取一个），使得 (a[i+1] + a[i+2] + … + a[j]) % p <= k, 并且 (a[i+1] + a[i+2] + … + a[j])最大。 先
2017-02-27 23:45:51
455
1
原创 hdu5571Triple（二维树状数组）
题意： 有二元组集{(a,b)}和三元组集{(c,d,e)}。当 (a,b)和(c,d,e) 满足 b==e 时，(a,c,d)组成新的三元组集 C {(a,b,c)}。 计算三元组集 C 中 满足 不存在除与本身相等外满足(u>=a,v>=b,w>=c)的三元组(u,v,w) 的三元组(a,b,c)。 思路： 自己写的时候完全没有思路啊~ 参考了http://async.icpc-c
2017-02-13 13:13:59
367
原创 hdu5514Frogs（容斥原理）
显然，第 i 只青蛙能跳过的石头的 id = k*gcd(a[i],m)。所以题目就是相当于求 0 ~ m - 1 这些数中至少是一个 a[i] (a[i]|m) 的倍数。 0 ~ m - 1 这些数中是 d (d|m) 的倍数的和为 d * m/d * (m/d - 1) / 2 。 但是，这样计算必然会重复。 先把 m 的因数求出来，最多不多于300个，再把是 a[i] 倍数的因数标记（
2017-02-12 00:03:50
332
原创 uvalive7271(A Math Problem) 数位dp
根据题目条件可以推得 f(2n) = 3 * f(n) , f(2n + 1) = f(2n) + 1 = 3 * f(n) + 1 . 也就是把一个二进制数直接看成三进制数，接着就是从 1 到 n(3进制)中模 k 余 (0 ~ k-1 ， 十进制)的数的个数的 xor。（看题解的，本来我也没想到） 用数位dp就可以解决了，刚开始的数位dp我写得有点问题，照着题解（我看的第一个题解数位d
2017-02-09 22:18:04
571
原创 The xor-longest Path ( POJ - 3764)
题意： 求树上的最长xor简单路径，即以 u，v 为端点的一条简单路径，使路径上全部边权的异或和（记为f(u,v)）最大。 由于 f(u,v)=f(0,u)^f(0,v)，所以先求出所有节点与根0 的简单路径的异或和，然后问题就转化为 n 个数中选两个数是它们异或和最大。用字典树实现，边插入边计算。从 最高位31 到 最低位0 ，尽量取与插入的数 位上不同。（贪心！）#include <iostre
2017-01-27 19:45:27
275
原创 CodeForces749D(Leaving Auction) 二分二分二分
题意： 将会有 n 个人在竞价，一共叫了 n 次价（价格递增）。一个人可以叫多次价，但不会自己压自己的价 （例如 1 1 \n 1 2 这是不会出现的），当然也就会出现有的人没叫价。 现在有 q 个询问，每个询问为 有 k 个人没来，分别为 li ，现在求最后的winner和价格。 （所有的 k 加起来 < 200000）。 思路： 考虑第一小问，如果我们把每个人叫的最高价记录
2017-01-07 13:27:09
392
原创 [CodeForces-325D] [Problem E]Reclamation
思路： 判断海的一个地方是否能填就相当于判断填了之后上下两块陆地能否四连通的连起来，也就相当于所有填成的海地（包括当前判断是否能填的这块）是否能八连通地围绕这圆柱体围成一个圈。 本来是 r * c。 补成 r * 2c 。 填每块海地时，要填 (ri,ci)和 (ri,ci+c)。如果所有填成的海地（包括当前判断是否能填的这块）是否能八连通地围绕这圆柱体围成一个圈，则 (ri,ci)和(ri
2016-12-31 16:36:04
358
原创 hihocoder1391Countries（2016北京网络赛）
对于每一个导弹，预处理出A需要的防御区间范围（对于从A发出的导弹，如果到达B的时间没有没有在 x , x+TB内，则这颗导弹一定不会打到A，所以既可以去掉。）。当且仅当 导弹i的防御区间范围含于 A的防御有效区间(未知) 内时，导弹i不会打到A.然后问题就成了，选取某个长度为 TA 的连续区间K（即A的有效防御区间），使得K包含的那些导弹的防御区间对应的伤害值最大。 做法： 预处理出来所有导弹的防
2016-12-23 23:28:23
299
原创 51nod1195斐波那契数列的循环节
求 Fib 数模 n 的循环节： 1. 对 n 做因数分解： n=p1^e1 * p2^e2 * … * pt^et; 2. 求出每个素数 pi 对应 Fib 数模 pi 的循环节mi0 ，则 pi^ei 对应的 Fib 数模 pi^ei 的 循环节 mi=mi0 * pi^(ei-1); 3. Fib 数模 n 的循环节就等于 lcm(mi)。 关键在于如何求Fib 数模素数 pi
2016-12-23 10:37:21
2021
原创 cf451e Devu and Flowers(容斥原理)
首先考虑无限制的情况，则它就相当于 求Sigma(li)=s的方案，用隔板法可以得 C(s + n -1 , n - 1)。 假设只有两个花瓶， 则 容斥 ： 无限制 - 花瓶1超限制花瓶2无限制 - 花瓶1无限制花瓶2超限制 + 花瓶1,2均超限制 即 C(s + n - 1,n - 1) - C(s - f1 - 1 + n - 1,n - 1) - C(s - f2 - 1 +
2016-12-14 20:41:25
359
原创 同余意义下的高斯消元解决几类常见的问题+例题
高斯消元法以下高斯消元指的是列主元高斯消元法。高斯消元法除了解浮点数线性方程，它还可以用于求矩阵的秩，求某些线性空间中的一组线性无关的基，解同余方程组。求秩SGU 200 Cracking RSA题意： 给你m个正的整型数，这m个数的质因子仅来自前t个质数，求它们能组成多少完全平方数。（每个数最多选一次，且不能一个数都不选） Sample test(s) Input
2016-12-13 19:10:05
3183
原创 Jzzhu and Cities( cf450D) 最短路
最初的思路： 先建最短路的有向图L（同时为无环图，根为1），然后把图L按以下赋值， 如果为铁路，赋值 1；否则赋值 0。 记录每个点两个值， 入边为铁路的数目sum，入边的是否只有铁路mm（当全是铁路时，显然要留下一条铁路，当有公路时，当然铁路一条都不能留）。 这样，对于每一个点所连的铁路的最多能去掉的个数就等于sum-mm， 此时从根开始深搜，计算sum和mm。然而，t（dijkstr
2016-12-07 22:14:54
290
原创 hdu4498Function Curve（数值积分）
先把所有曲线的交点(加上0.0和100.0)都找出来，排个序，然后相邻的两个节点用辛普森自适应积分求出，当然要先求出此时对应的最小值函数，只需要取这一段的中点m，求出哪条曲线使ki * (x - ai) * (x - ai) + bi最小（扫一遍），那么这一段对应的最小值函数就是这个曲线。#include <cstdio>#include <algorithm>#include <cmath>
2016-11-19 21:48:28
356
原创 cf343dWater Tree(dfs序)
三个操作： 1. 将u及其子树全部灌水，子树就是dfs序in[u]和out[u]中间那一部分 2. 将u及其祖先排水，暴力搞tle了，一点小优化仍然tle，其实只需要将u单点排水即可，因为询问u时，如果u或u的子树的某个节点是空的，那么u一定也应该是排水的（只是没有将它排水，排水的话就超时了）。 3. 询问u时，检查u及u的子树是否全部灌水了。 但，由于操作2，比如样例中的那棵树， 先1号
2016-11-18 23:22:17
481
原创 bzoj2243染色（树链剖分+区间合并）
这道题是点的树链剖分。 修改链，询问链。 树链剖分的意思就是将树线性化 树剖之后就变成区间修改和区间询问了。 询问的是颜色段数量，所以就是区间合并，并且树链合并时还要判断两个链的端点是否颜色相同。 （3个半小时，菜不成声）#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#define
2016-11-06 10:37:49
268
原创 ccpc杭州K题（hdu5943） Kingdom of Obsession
首先如果s+1~s+n中有两个数是素数，那么肯定是no；也就是如果1~2e9中素数的最大距离如果是m，那当n>m时就不成立了。（其实上这有一点问题） 我直接假设m=1000，事实上m比500还要小。 那么现在问题就降为 1≤T≤100. 1≤n≤1000. 0≤s≤1e9. 那么问题就很简单了，如果s+k是某个i的倍数，那么s+k就是可能和i进行匹配（1可以和任何一个数匹配）。然后找最大
2016-10-29 19:19:32
486
原创 hihocoder 1251 Today Is a Rainy Day（ 2015北京区域赛C题）
首先两种操作，一次性执行完2操作，最后再用1操作比混合着用1操作快。 所以先处理一次性执行操作完2操作， 也就是由123456 –> a1,a2,a3,a4,a5,a6 最多6 ** 6种转移 bfs预处理 最后再执行1操作，但不能每次都比较一次原序列和经过一系列2操作的现在的序列，需要一点技巧。（Tle了4发） 对于每一个数字k，统计它在the final list出现的次数c[
2016-10-28 22:19:19
442
原创 hdu5136Yue Fei's Battle(计数dp)
题意求树的直径有k个点的不同构数的个数 从树的直径所在的链中间切开后就得到两个二叉树(记树的深度所在的链的节点数为d)，且如果k是偶数，那么k = 2 * d，如果k是奇数，那么会得到三个二叉树，其中有两颗二叉树d = k / 2,另外一颗 <= k / 2。 而令dp[i]为树的深度所在的链的节点数等于i的不同构的数的个数 sum[i]为树的深度所在的链的节点数小于等于i的不同构的数的个数
2016-10-23 00:18:21
288
原创 bnu52297Coins（弱校联盟第一场）--找规律
比赛的时候不会，看题解补题的。 if a >= 2 那么1可以由一个1表示，2可以由两个1表示，这样 1 ~ 3c 范围内的所有数都能被表示，同理3c + 1 ~ 3c + 2b范围内的所有数也可以被表示，3c + 2b + 1 ~ 3c + 2b + a范围内的所有数也可以被表示。 elif a == 1 if b >= 2 那么1~3
2016-10-04 10:37:45
297
原创 hdu5114 Collision（一元同余方程）
推了一晚上，还是没发现问题会转化成同余方程。 为了避免小数，所有点坐标*2 对于这种题，感觉应先考虑一维的情况， x1,x2,[0,x0]，方向1 那么if x1==x2，就直接相撞 else 设移动tx步 不妨对x2做对称，则x2变为2k*x0-x2，此时方向为-1 则 x1+1* tx=2k* x0-x2+(-1)* tx 即
2016-09-30 20:31:31
427
4
原创 hdu1151Air Raid poj2594Treasure Exploration题解
Air Raid 题目的意思就是给一个有向无环图，求从最少的点出发，不能重复的走完所有点。其实就是有向无环图的最小路径覆盖。 有向无环图的最小路径覆盖=节点数-匹配数（拆点）//建图，有向无环图的最小路径覆盖=节点数-匹配数（拆点）#include <iostream>#include <stdio.h>#include <algorithm>#include <stdlib.h>#i
2016-09-26 23:08:52
268
原创 hdu5294(Tricks Device)题解
题意：Innocent Wu只能走最短路， 两问：1，Dumb Zhang要阻止他找到自己，最少需要切断多少路。 做法：把最短路都找出来然后建图，然后求图的最小割（最大流等于最小割） 2，Dumb Zhang最多切断多少路但Innocent Wu仍能找到Dumb Zhang。 做法：在最短路的图上找出起点1能到终点n经过
2016-09-23 20:32:18
284
原创 hdu5698瞬间移动
两种做法： 一：枚举步数x，那么从（1,1）到（n，m）就可以看成从行1到n走了x步，从列1到m走了x步。这两个过程是独立的。所以只要将1到n走了x步的路线数乘以1到m的路线数就是（1,1）到（n，m）走x步的路线数。 问题简化为1到n走x步的路线数怎么求。 1到n路线的最小单元就是从i到i+1的路线，总共有n-1个这样的单元。 那走x步就相当于把这n-1个单元组成x个各自连续的区间段。
2016-09-20 19:44:59
289
原创 hdu5876Sparse Graph(求补图的最短路)
网赛的时候没做出来，后来看题解懂的。 首先将所有节点都放进集合a，表示未求出最短距离。 由于以S为起点，所以dis[S]=0,从集合中将其删除，扔进队列。 每次跑队列的时候，取出首元素u，将集合a遍历一边，如果集合中的元素x与其没有边相连（用set存边，这样可以较快判断），那么dis[x]=dis[u]+1。并将其扔进队列，从集合中删除它。#include <iostream>#includ
2016-09-20 15:29:59
263
原创 hdu2732Leapin' Lizards（Dinic）
刚开始想这道题想了很久，然后就有个思路，没立即敲。 然后敲的时候将起跳后忍受能力减1，记为降落时忍受能力减1。 增加一个源点n*m * 2和汇点n *m *2+1。 首先，对于每个点node，将其分为两个点node1和node2，node1连向node2的权值就等于这个点的承受能力（当然承受能力为0就不连了，因为没有柱子），然后如果可以从i跳到j，就将i2连向j1，权值无穷大，这里可以是40
2016-09-16 23:20:15
356
原创 cf-64d（Parking Lot）成段更新+区间合并
题目看了一个小时，想了半个小时，敲了一个小时，debug将近三个半小时。。。。。。//还是看数据的 将停车分成两个操作，先找出停车的起始点位置，然后再成段更新。 这里用线段树维护区间最多能停多长的车（包括前距和后距） 找其实点时，先判断能否放在起点，此时它要放的长度只需lth(+f也无妨), 如果可以，就找到了。 否则要放的长度需要lth+b+f（当放在末尾时，其实不需要+f，但为了方便，
2016-09-06 23:09:02
402
转载 acm-图论的一些概念及性质
图论的一些知识点，先mark一下§1图论点、边集和二分图的相关概念和性质 点覆盖、最小点覆盖 点覆盖集即一个点集，使得所有边至少有一个端点在集合里。或者说是“点” 覆盖了所有“边”。。极小点覆盖(minimal vertex covering)：本身为点覆盖，其真子集都不是。最小点覆盖(minimum vertex covering)：点最少的点覆盖。点覆盖数(vertex covering n
2016-08-31 21:06:28
1495
原创 poj2296 Map Labeler(2-sat+二分)
由于每个点要么在label的顶边或者在label的底边且在中间，并且有且只有一个在label上，所以就可以转化为2-sat问题。 建图如下： 不妨设 点yi<=yj。(i表示向下，！i表示向上) if(|xi-xj|>=d) continue; if(yj-yi>=2*d) continue; if(yj-ji>=d) i||!j else if(yj-ji>0) i&&!j e
2016-08-30 15:57:36
266
原创 hdu4430 Yukari's Birthday(二分)
题意： 给定一个n，计算满足x^1+x^2+……+x^r=n且使x*r最小（如果有多个，取r最小的那个）的x，r值。 由于2^40大于1e12，所以我们可以枚举r从1到40，但这样可能会超时，所以可以根据3^26大于2e12，我们可以枚举r从1到26，并单独计算x=2的情况。 对于给定的每个r，x^1+x^2+……+x^r这个式子就关于x单调递增，所以就可以用二分来做。#include <io
2016-08-29 20:32:34
374
原创 cf645c Money Transfers(贪心)
想了很久，隔了一段时间，又想了很久，还是不会，看别人的代码，简直吓哭了。。。。。。妙，题意相当于： 给定一个区间[1,n]，区间首尾相连，最多把它分成几块，使得每一块的和都是0.（假设答案是p，那么n-p就是这道题的答案） 所以维护一个前缀和，然后前缀和出现的最多次数就是答案， 突然觉得好蠢。。。。。。#include <iostream>#include <stdio.h>#includ
2016-08-29 19:14:16
412
原创 hdu3949xor(高斯消元)
看了半天题，没想出怎么用高斯消元解题，看完别人ac明白。 首先，用二进制去看待每一个数，因为xor其实就是二进制的不进位加法。 比如 （十进制）2^0 2^1 1 1 2 1 3 1 1 其实
2016-08-28 19:54:32
454
原创 poj3678Katu Puzzle(2sat入门)
这道题算是2sat建图入门题。 把6种逻辑表达式转化为有向图 2-sat就是合取范式 1.a&&b=1就相当于是a和b两个析取式的合取范式，而a又可以写成a||a。 2.a&&b=0 ==》 !a||!b=1 3 a||b=1 4 a||b=0 ==》 !a&&!b=1 同1 5 a^b=1 ==》(!a&&b)||(a&&!b)=1数理逻辑的知识可以推出
2016-08-25 11:51:48
246
原创 poj1360（完全背包+多重背包+鸽巢原理）
题意，fj去买价格为t的物品， shopkeeper只接受n种货币，价值分别vi，对于每种货币fj有ci个，但 shopkeeper都有无数个这种货币。求最少使用多少货币完成交易。 对于fj，进行一次多重背包， 对 shopkeeper，进行一次完全背包。 最重要的是要考虑上界， 鸽巢原理： fj最多支付maxv*maxv+t， shopkeeper最多找零maxv *maxv。 证明：
2016-08-24 11:38:13
425
原创 hdu3535AreYouBusy（分组背包问题）
常见的有三种， 一，每组最多取一个， 一维数组的伪代码 for 所有的组k for v = V to 0 for 所有的i属于组k f[v] = max{f[v], f[v -c[i]] + w[i]} 注意顺序不能写反，因为要限制每组最多取一个 二，每组任意取 既然上面的顺序是限制每组最多取一个，那调换一下顺序即可，其实就是01
2016-08-23 22:56:49
306
原创 2-sat入门（例题hdu1814,poj3648）持续更新
2-sat问题描述2-sat问题是这样的：有n个布尔变量xi，另有m个需要满足的条件，每个条件的形式都是“xi为真/假或者xj为真/假”。比如“x1为真或者x2为假”。注意这里的“或”是指两个条件至少一个是正确的。由于在2-SAT问题中，最多只对两个元素进行限制，所以可能的限制关系共有11种： A[x] (1) NOT A[x] (2) A[x] AND A[y] A[x] AND NOT
2016-08-23 10:32:50
432
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人