- 博客(42)
- 收藏
- 关注
RSS订阅原创 虚拟机下 Ubuntu 16.04 的优化
主要是记录一下虚拟机安装 Ubuntu 16.04 后进行优化的步骤，省的以后一直查资料。环境：宿主机 macOS Catalina 10.15.7虚拟化软件：Parallels Desktop 16.1.2VM：Ubuntu 16.04一、删除没必要的预装软件$ sudo su$ apt-get remove libreoffice-style-galaxy unity-webapps-common thunderbird totem rhythmbox simple-scan gnom
2021-01-14 17:47:15
317
原创 【ZJOI2006】书架 - Splay
题目链接洛谷P2596题目描述现在书架从上到下摆了n本书，编号1-n，要求维护一个数据结构来支持下面5个操作Top S 把编号为s的书放到顶部Bottom S把编号为s的书放到底部Insert S T如果编号为S的书上面有x本，那么把这本书放在一个位置使得它上面有X+T本书，保证T∈{−1,0,1}T \in \{-1, 0, 1\}T∈{−1,0,1}Ask S查询编号为S的书上...
2019-09-20 10:46:23
189
原创 Gym - 100889H Hitting Points 计算几何+三分+二分
题目链接Hitting Points题意按逆时针顺序给你二维平面上严格凸包的n个点,编号0到n-1, 有q次询问, 每次询问确定一个编号为idx的基础点, 以idx和(idx+1)%n构成的向量为x轴, 在(k,0)这个点上有一条垂直于x轴的线绕(k,0)这个点逆时针旋转, 问第一次碰到的点的编号是多少. 如果碰到两个点就输出两个答案.做法考虑落到每一个点的时候有多少点在线的上方, 这...
2019-07-27 10:41:24
138
原创 2018CCPC吉林 D题 The Moon 概率dp
题目链接The Moon题意按照下述流程玩抽奖游戏,当抽中奖品后游戏结束概率qqq初始化为2%2\%2%玩家有p%p\%p%的概率赢得游戏如果赢得游戏则进入步骤3否则进入步骤4玩家有qqq的概率抽中奖品.如果没有抽中奖品则qqq变为min(100%,q+2%)min(100\%, q+2\%)min(100%,q+2%),然后回到步骤1qqq变成min(100%,q+1.5%),...
2019-07-16 19:41:02
215
原创 2018CCPC吉林 H题 Lovers 线段树
题目链接Lovers题意现在有n个空字符串s1,s2,⋯ ,sns_1,s_2,\cdots ,s_ns1,s2,⋯,sn和m次操作,操作分为以下两种wrap l r d, 对于任意j∈[l,r]j \in[l, r]j∈[l,r],将sjs_jsj变成dsjdds_jddsjd,就是在两边各家一个数字dquery l r, 求∑i=lrval...
2019-07-16 19:24:40
164
原创 UVA - 12169 扩展欧几里得
题目链接UVA-12169题意现在有一个长度为2n的序列B，序列满足Bi=(a∗Bi−1+b) mod 10001B_i=(a*B_{i-1}+b)\ mod\ 10001Bi=(a∗Bi−1+b) mod 10001，其中a和b两个参数未知。现在给定下标为奇数的序列B，求下标为偶数的序列B。求出任意一个即可.思路我们先写一下式子B3=(aB...
2019-07-03 22:35:44
137
原创 POJ - 2142 扩展欧几里得
题目链接POJ-2142题意给两种没有数量限制的砝码，重量分别为a和b，现在要在天平上称重量为d的物品，砝码可以放在天平的两侧，问能不能称，不能称输出-1，否则输出使用两种砝码的个数，要求个数和最小思路对于天平来说要满足力臂相等，即ax+by=dax+by=dax+by=d，其中∣x∣|x|∣x∣表示第一种砝码的数量，∣y∣|y|∣y∣是第二种砝码的数量，那么答案就是∣x∣+∣y∣|x|...
2019-07-03 22:22:48
122
原创 HDU-1576 扩展欧几里得 or 逆元
题目链接HDU-1576题意一句话，给定n和B，求AB mod 9973\frac{A}{B}\ mod\ 9973BA mod 9973，其中n=A%9973，数据保证B能整除A思路发现9973是个质数，可以直接用费马定理求下B的逆元再乘A就完事了。然后发现可以用扩欧做。记ans=AB mod 9973ans = \fra...
2019-07-03 19:39:24
124
原创 BZOJ-2286 虚树+树形dp
题目链接题意一棵有n个节点的无向树，根节点为1，告诉你k个关键节点，现在要割断一些边使得这k个点与根节点不连通，求割掉的边的最小边权和。思路记录dis[v]表示点1到点v的路径中最小的边权。如果u是关键节点，dp[u] = dis[u]，否则dp[u] += min(dis[v], dp[v])使用虚树优化。虚树仅仅记录了关键节点和他们的lca代码#include <bits...
2019-04-23 20:07:54
98
原创 CodeForces - 1141A 水题
题意给定数a和b，问把a乘2乘3能否变成b，输出次数思路首先a能被b整除，之后不断用2和3去除，如果最后能变成1就可以，不然不行。代码n, m = map(int, input().split())if m % n != 0: print(-1) exit(0)m = m // nans = 0while m > 1 and m % 2 == 0: ...
2019-03-24 21:34:17
171
原创 POJ - 2689 区间筛素数（模板）
题目链接题意给定区间[l, r]，长度小于1e6，l和r小于1e9，问这个区间中相邻两个素数差值的最大值和最小值。如果只有一个素数或者没有素数则输出There are no adjacent primes.思路模板题因为每个合数x都有一个小于x\sqrt{x}x的因子，所以只要筛出[2,r][2, \sqrt{r}][2,r]之间的素数，然后枚举素数p，把这个区间中p的倍数全部筛掉即...
2019-03-06 08:19:28
207
原创 ZOJ-3707 斐波那契 数论
vjudge链接题意定义s[n]s[n]s[n]为集合{1,2,3,⋯&ThinSpace;,n}\{1, 2, 3, \cdots, n\}{1,2,3,⋯,n}中不包含连续数字的子集个数。如果s[n]s[n]s[n]满足对于任意的iϵ[1,n)i\epsilon[1, n)iϵ[1,n)都有gcd(s[i],s[n])=1gcd(s[i], s[n]) = 1gcd(s[i],s[...
2019-03-02 16:49:56
189
原创 Gym-101982D （假的）数位dp
链接中的D题题意问在[0,2b−1][0, 2^b-1][0,2b−1]中为k的倍数的数的二进制表达中1的个数。思路g[i][j]g[i][j]g[i][j]表示前i位的数中模k为j的数的1的个数，答案为g[b][0]g[b][0]g[b][0]第i位数有两种情况，为0的时候g[i][j]=g[i−1][j]g[i][j] = g[i-1][j]g[i][j]=g[i−1][j]，为...
2019-03-01 16:01:37
559
原创 CF - 1066F 动态规划
题目链接题意给出n个全在第一象限的点，从原点出发，只能在走完切比雪夫距离相等的点后才能走其他点，问最少走多少步能经过所有点。思路不看标签绝对想不到是个dp首先有个最优策略：在走每一层的时候从左上角走到右下角或从右下走到左上是距离最短的所以可以先处理出每一层左上和右下的点分别是什么然后一层一层地转移。ps[i][0,1]ps[i][0, 1]ps[i][0,1]表示第i层左上和右下的...
2019-03-01 09:37:32
235
原创 计算几何 模板
#include &lt;cmath&gt;#include &lt;iostream&gt;#include &lt;vector&gt;typedef double db;const db eps = 1e-9;const db pi = acos(-1);// 判断符号inline int sign(db a) { return a &lt; -eps ? -1 : a &
2019-02-27 20:19:41
148
原创 最短路 模板
堆优化的Dijkstra NlogN 邻接表#include &lt;utility&gt;#include &lt;queue&gt;typedef std::pair&lt;int, int&gt; P; //first为点的编号, second为边的权值const int N = 100005;int dis[N];vector&lt;P&gt;e[N];
2019-02-27 18:21:41
187
原创 CodeForces - 1117D 矩阵快速幂
CodeForces - 1117D 矩阵快速幂题意思路代码题目链接题意一个长度为n的串全是1，问有多少种方式用0替换1满足0的长度正好为m（可以没有）思路如果当前位置放1的话可以直接从前一位转移过来，如果放0的话则从i-m+1到i应该都是1，即从i-m转移过来。所以f[i]表示到第i位的方案数，则转移方程为f[i] = f[i-1] + f[i-m]。由于n很大所以做矩阵优化。[fn...
2019-02-27 18:03:02
345
原创 HDU - 6183 动态开点线段树
HDU - 6183 动态开点线段树题目链接考虑对每种颜色都沿y轴建立线段树，维护区间点的x坐标的最小值。线段树需要动态开点不然会mle#include &amp;amp;lt;algorithm&amp;amp;gt;#include &amp;amp;lt;cstdio&amp;amp;gt;#include &amp;amp;lt;cstring&amp;amp;gt;const int N
2019-02-27 13:20:05
173
原创 扩展欧几里德
扩展欧几里得 求解不定方程 ax+by=gcd(a, b) 的整数解对于方程 ax+by=c, 如果 gcd(a, b)|c, 则有解, 解为 ax+by=gcd(a, b) 的解乘以 c/gcd(a, b); 否则无解long long exgcd(long long a, long long b, long long& x, long long &y){ i...
2018-08-21 12:50:00
94
原创 组合数 模板
Lucas定理 mod小于10^5namespace Lucas{ inline long long qpow(long long a, long long x, long long mod) { long long res = 1; while (x) { if (x & 1) res = ...
2018-08-20 16:27:00
78
原创 网络流 模板
Dinic+当前弧优化 O(n^2m)链式前向星的下标要从偶数开始，head初始化为-1const int N = 105;struct edge { int to, next, flow; }e[N*N*2];int cnt, head[N];namespace MaxFlow{ int cur[N], depth[N]; int dfs(int u, int ...
2018-08-11 15:04:00
78
原创 Sequence operation HDU - 3397 (线段树区间合并)
题目来源：Sequence operation题意给你一个长度为n的01串，现在有m次操作0 a b表示把区间[a, b]全部变为01 a b表示把区间[a, b]全部变为12 a b表示把区间[a, b]翻转，0变1,1变03 a b输出区间[a, b]中1的个数4 a b输出区间[a, b]中最长连续的1的长度思路用线段树维护区间从左、右开始数0和1的最大长...
2018-08-09 20:19:00
120
原创 LCA倍增 模板
LCA倍增 最近公共祖先构造 NlogN 查询 ogN先调用pre()构造对数数组 再调用dfs(root, 0, 0)查询深度 再调用work()构造跳表最后调用lca(u, v)查询在有根树中节点u和v的最近公共祖先const int N = 10005;struct edge { int to, next; } e[N << 1];int n, head[...
2018-08-08 13:56:00
105
原创 线段树 + 树状数组 + ST表 模板
线段树区间修改+区间求和 logNconst int N = 1e5 + 5;int a[N];namespace SEG{ struct tag { long long sum; long long lazy; } c[N << 2]; void pushDown(int k, int l, int r)...
2018-08-07 15:21:00
187
原创 Ultra-QuickSort POJ - 2299 (树状数组求逆序对)
题目来源：Ultra-QuickSort题意现在随机给你一组数，每次可以交换相邻的两个数，问最少交换几次可以使得这组数变为升序分析显然如果两个相邻的数如果是逆序则需要需要交换这两个数字。现在考虑两个不相邻的逆序对a[i] 和 a[j](a[i] > a[j], i < j)，对于这两个中间的数a[k]如果a[k] > a[j]，则需要交换a[k]和a[j] 而且交...
2018-08-06 19:52:00
90
原创 Balanced Lineup POJ - 3264 (ST表)
题目来源：Balanced Lineup题意给你n个数，有q次询问，每次询问给定两个数l和r，输出区间l到r最大值与最小值的差思路题目给定数字后没有再进行修改，属于离线查询，可以直接使用st表在nlogn的时间内处理所有区间的最值，在常数时间内查询区间最值。用线段树维护区间最值也可以log[n] 存放了以二为底n的对数向下取整后的结果，预处理下这个数组 比调用库函数要快一点...
2018-08-06 19:36:00
174
原创 Counting Intersections HDU - 5862 (离散化+树状数组扫描线段)
题目来源：Counting Intersections题意给你n条与坐标轴平行的线段，问有几个交点。数据保证没有重合的、长度为0的线段，没有共起点共终点的线段。思路由于所有线段都是和坐标轴平行的，所以可以把与x轴平行的线段和y轴平行的线段分开来看，将横着的线段纵坐标插入树状数组中，求所有竖着的线段起点到终点的区间和即为答案。求解的过程需要按照横坐标从小到大排序，横线段的点优先。...
2018-08-06 19:29:00
116
原创 Computer HDU - 2196 (树形dp)
题目来源：Computer题意给定一棵有n个节点的树，根的编号为1，求每个点到离它最远的点的距离。思路先dfs求出每个点u向下的最大距离f[u][0]和次大距离f[u][1]，并且用数组node[u]记录最大路经过了与u直接相邻的哪一个子节点。现在用f[u][2]记录满足题意的最大路。再跑一边dfs，对于当前节点u，如果它的子节点v，满足了node[u] = v，说明u的最...
2018-08-05 12:45:00
72
原创 C++快速读入
namespace IO{ inline char nc() { static char buf[100000], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1+...
2018-08-05 12:20:00
938
原创 Straight Master Gym-101775J (差分)
题目来源 Straight Master题意有n种扑克牌，每种扑克牌有ai张，每次可以打出3到5张连续的牌作为顺子，问这副牌能不能用顺子全打出来思路换一个思路，给定一个长度为0的序列，每次可以选择长度为3,4,5的区间并将这个区间内的数全部加一，最终可以得到一个新的序列，问这个序列的每个数分别是多少，这个序列就是给定的n种扑克牌。对于这个问题，可以用差分的思想，对于区间[L, ...
2018-08-02 11:21:00
120
原创 A Walk Through the Forest HDU - 1142(Dij+记忆化搜索)
题目来源: A Walk Through the Forest题意你要从编号为1的办公室回到编号为2的家里，每次移动只会从当前点移动到 到家的最短路小于当前点到家的最短路 的点上，问一共有多少种回家的路线思路先求出所有点到家的最短路，然后进行搜索。暴力搜索会超时，考虑记忆化搜索。数组f[i]记录当前点回到家的路线条数，对于当前点u来说f[u]=所有与u相邻接的点的f值的和。求和的过...
2018-07-27 19:53:00
98
原创 Candies POJ - 3159(差分约束+栈优化SPFA)
题目来源: Candies题意现在给n个小朋友分糖果，给出m条语句Ａ B C表示小朋友A认为给B的糖果不能比自己多C(可以等于C)，问小朋友N与小朋友1的糖果数量差最少是多少思路给出的m条语句表示的意思写成数学语言为给A的糖果数和给B的糖果数满足B-A<=C。这就变成了典型的差分约束系统，可以从点B到点A建立一条权值为c的有向边，最终要求的即为点N到点1的最短路。这个题如果...
2018-07-27 19:43:00
140
原创 最短路径模板
堆优化的Dijkstratypedef pair<int, int> P; //first为边的权值，second为点的编号const int N = 100005;int dis[N];vector<P>e[N]; //first为点的编号, second为边的权值priority_queue<P, vect...
2018-07-27 16:09:00
96
原创 Bound Found POJ - 2566(尺取)
题目来源：Bound FoundDescriptionSignals of most probably extra-terrestrial origin have been received and digitalized by The Aeronautic and Space Administration (that must be going through a defiant pha...
2018-07-25 17:07:00
132
原创 Subset POJ - 3977(折半枚举+二分查找)
题目来源：SubsetDescriptionGiven a list of N integers with absolute values no larger than 1015, find a non empty subset of these numbers which minimizes the absolute value of the sum of its elements. I...
2018-07-25 17:00:00
223
原创 Robin Hood CodeForces - 671B(最小值最大化+最大值最小化)
题目来源：Robin HoodStatementWe all know the impressive story of Robin Hood. Robin Hood uses his archery skills and his wits to steal the money from rich, and return it to the poor.There are n citize...
2018-07-24 19:33:00
301
原创 Vasya and String Codeforces - 676C(尺取)
题目来源：Vasya and StringStatementHigh school student Vasya got a string of length n as a birthday present. This string consists of letters 'a' and 'b' only. Vasya denotes beauty of the string as the ...
2018-07-24 12:25:00
131
原创 NPY and shot HDU - 5144(物理+三分)
题目来源： NPY and shotProblem DescriptionNPY is going to have a PE test.One of the test subjects is throwing the shot.The height of NPY is H meters.He can throw the shot at the speed of v0 m/s and at ...
2018-07-24 11:42:00
142
原创 Bridges Gym - 100712H (Tarjan缩点)
题目来源： 2015 ACM Amman Collegiate Programming ContestStatementAn edge in an undirected graph is a bridgeif after removing it the graph will be disconnected.Given an undirected connected graph, yo...
2018-07-24 11:21:00
129
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人