- 博客(309)
- 收藏
- 关注
RSS订阅原创 centos 7 jupyter配置
一、生成jupyter的配置文件执行命令jupyter notebook --generate-config会在用户目录下生成文件/home/usrname/.jupyter/jupyter_notebook_config.py二、生成密钥打开ipython或者是pythonIn [1]:from notebook.auth import passwdIn [2]:passwd()# 该密码将是你浏览器访问服务器时需要输入的密码Enter password: 123Ve
2021-03-29 15:49:05
404
1
原创 VScode中launch和task参数解释
一、launch.json{ // 使用 IntelliSense 了解相关属性。 // 悬停以查看现有属性的描述。 // 欲了解更多信息，请访问: https://go.microsoft.com/fwlink/?linkid=830387 "version": "0.2.0", "configurations": [ { "name": "g++.exe - 生成和调试活动文件", "type":
2020-06-27 11:10:12
4811
原创 win10上sublime3运行C++不弹出终端问题解决
{ "cmd": ["g++","-Wall", "${file}", "-o", "${file_path}/${file_base_name}"], "file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$", "working_dir": "${file_path}", "selector": "source.c, source.c+...
2020-04-27 13:12:15
613
原创 win10安装anaconda+pytorch-cpuOnly
一、下载anaconda并安装1.从anaconda的官网下载安装包准备不小于5GB的空间，最好不小于20GB最好不小于20GB最好不小于20GB，因为后期还需要安装其他包。安装过程中可以选择自动添加到系统环境路径。二、创建pytorch环境1.打开软件从win10界面左下端图标找到Anaconda Navigator双击打开；第一次打开比较慢，需要初始化很多内容。2.创建环...
2020-04-27 13:11:18
1428
原创 AOE关键路径
时间发生的先后顺序存在一定时间上的限制，时间A必须在其前驱活动发生完之后才能发生； 边：表示活动的持续时间，两个事件之间必须先进行相应的活动时间； 点：表示事件四个关键属性 Ve[i]:表示事件i发生的最早时间； Vl[i]:表示事件i最晚发生的时间 e[i]:表示活动i最早发生的时间； l[i]:表示活动i最晚发生的时间；
2017-12-06 21:39:14
429
原创 考研数据结构----MaxHeap
原理 这里我们建立的是最大堆，用完全二叉树来表示这个堆； 1. 堆顶比两棵子树中的任何元素都要大； 2. 每棵子树同样满足这个条件； 即根是树中最大值，没课子树的根是子树中的最大值 所以我们在构造的时候要先从最小的子树开始构造，这样才能构造更大的子树/** 建立大顶堆，a[1]为最大元素 */typedef struct { /*自底向上调整每一个元素
2017-07-23 12:17:35
468
原创 LightOJ 1062 Crossed Ladders（二分）
int main(int argc, const char * argv[]){ int kase;cin >> kase; while(kase--) { double x, y, c;cin >> x >> y >> c; double l = 0, r = min(x, y); Rep(i, 1, 100) {
2017-02-17 19:05:43
440
原创 LightOJ 1061 N Queen Again（搜索+状压DP）
题目 给出一张8*8的图，上面有8个皇后，现在每次只能移动一个皇后往同一个方向走任意步，总共有8个方向；问最少需要多少步使得所有皇后相互不会攻击对方？思路 单纯的暴搜是不行的，时空都会炸。 假如我们知道最终每个皇后应该在的位置，然后再来计算最少步数就会简单不少，这里可以用状压来做； 因为最终的情况是每行有一个皇后，所以我没需要记录每行皇后所在的列，然后枚举哪个皇后移动到这个位置
2017-02-17 19:02:29
561
原创 LightOJ 1060 nth Permutation(组合数--k大字典序)
题目 给一串长度不超过20的字符串，求n-th permutation of the string.0<n<2310 < n < 2^{31} 思路 先排序，求出当前串有K种组合，如果n大于k，显然impossible； 然后就是每个位置枚举字符，判断下合理性就行了；char s[30];long long f[22];typedef struct item { cha
2017-02-17 18:43:53
492
原创 LightOJ 1057 Collecting Gold(状压DP)
题目 n∗m,(n,m)<(20,20)n*m,(n,m) < (20,20)的格子图上有一个人，和不超过15个的金矿；求这个人从当前位置出发获取所有金矿然后再回到这个位置需要走的最少路程？每次只能往邻近的四个方向走；思路 因为没有障碍物，所以算两个格子间的距离很方便； 开始用的穷举所有的获取金矿的先后顺序，然后TLE了； 最后就状压过了，dp[sta][i]表示达到状态sta
2017-02-14 15:25:21
484
原创 LightOJ 1055 Going Together （暴力搜索……繁琐）
题目 一张n*n的格子图，上面有空地、障碍物、三个出口和三个小人；每次一条指令让他们往四个方向移动一格，不能动的原地不动，动的就移动一格；一个格子上最多同时只有一个人思路 暴力bfsconst int dx[] = {0, -1, 0, 1};const int dy[] = {1, 0, -1, 0};bool mark[11][11][11][11][11][11];char
2017-02-14 15:16:35
400
原创 lightoj1054 Efficient Pseudo Code(欧拉函数+Divisor function)
题目 求nmn^m所有约数的和在mod 1e9+71e9 + 7的结果；思路 数学知识点 n可以写成 n=px11∗px22∗...n = p_1^{x1}*p_2^{x2}*...，那么nm=pm∗x11∗pm∗x22...n^m = p_1^{m*x1}*p_2^{m*x2}... 这样就可以用下面这个公式求解了，具体数学看上面的链接，这里x取1； σx(n)=∏ri
2017-02-14 15:07:04
451
原创 lightoj1052 String Growth (矩阵求解Fibonacci)
题意 给出一个只含有{a, b}两种字符的串，每次扩展就用ab把串中的b给替换掉，同时用b把a给替换掉；然后给出第n次扩展后的串长为x，第m次扩展后的串长为y，求第k次扩展后的串长为多少？思路 首先简单的扩展几个串可以发现，a的个数和b的个数都是fibonacci数，且按照fibonacci数数增长； 这样我们假设一开始由p个a，q个b；然后求出第n次和第m次的fibonacci数，
2017-02-14 14:52:57
395
原创 lightoj1038 - Race to 1 Again(期望DP)
题意 给出一个1≤N≤1051 \leq N \leq 10^5，每次选其一个约数相除，知道得到结果为1为止，求期望次数；思路 期望dp，求x平均除多少次得到1；假设x有c个因子（含1和本身），E[x]表示结果； 那么E[x] = (E[1] + E[a1] + E[a2] + … + E[x] + c) / c;加c是因为每次要多走一步才能得到ai，每次选者的概率为1/c；
2017-02-05 23:41:25
296
原创 lightoj1035 欧拉函数（暴力）
题意 用表达式x=px11px22...x = p_1^{x_1}p_2^{x_2}...的形式表示N!，1≤N≤1001 \leq N \leq 100；思路 先求出100以内的素数，然后暴力分解，记录每个素数出现的次数；/*****************************************Author :Crazy_AC(JamesQi)Time
2017-02-05 23:35:13
744
原创 lightoj1037 状压DP(入门级)
题意 简单思路 dp[sta]表示状态为sta时需要打的最少次数，dp[0] = 0;/*****************************************Author :Crazy_AC(JamesQi)Time :2016File Name :*****************************************///
2017-02-05 23:29:20
347
原创 Lightoj1028 欧拉函数
题意 一个十进制数1≤n≤10121 \leq n \leq 10^{12}，现在用base进制来表示，问有多少种表示方法使得最后一位上的数为0？ 等同于求出n有多少种约数，即n%base==0n \% base == 0；思路 开始想的是枚举sqrt内的数，TLE了，因为有10000组数据。。。。 有一个表达式x=px11∗px22∗px33...x = p_{1}^{x
2017-02-05 14:59:55
491
原创 poj3481 Double Queue(set模拟or splay)
题目链接 题目意思明确。可以用两个set来模拟，一个大的优先，一个小的优先，同时删除、同时加入。struct item1 { int k, p; item1() {} item1(int k, int p) : k(k), p(p) {} bool operator < (const item1& rhs) const { return p <
2016-10-24 16:45:24
472
原创 hdu5919 Sequence II(主席树求区间数种数和k大查找)
题目链接 给你一个含有n个数的数列，m次查询。每次查询给出l和r两个数，表示子序列a[l]…a[r]，然后子序列中有k种数(需要自己求出k值)， p[j]表示第j种数从左到右第一次出现的位置，那么会得到p[1]…p[k] && p[1] < p[2] < … < p[k]。然后倒着建立主席树，然后就类似区间k小的查找。#include <stdio.h>#define min(x, y
2016-10-04 23:16:15
549
原创 hdu 4822 Tri-war(LCA倍增)
题目链接 给出一棵树，n,3≤n≤105个点n,3 \leq n \leq 10^5个点，然后m次讯问，1≤m≤105m次讯问，1 \leq m \leq 10^5，时限是10000ms，显然每次讯问要控制在log级。 每次讯问给出a,b,c三个不同的点，对于每个点求出树上的点到它的距离严格小于到其他两个点的距离的个数。 如果是两个点，可以找到两个点的路径中点，把树分成分别包含a，b
2016-09-28 21:23:04
850
原创 Gym 100543A Parades
题目链接 一颗有n个点的树，然后上面有m条关系链[u, v]（就是u到v的路径），选出x条链，相互没有边重合，但是点是可以重合的。求x的最大值。 思路：树形dp＋状压dp。 对于以u为根的子树，dp[u]表示这棵子树能有的最大x的值（也就是被选中的x条链满足题目条件且每条链的所有边都在子树中，不经过[fa, u]）。 第一部分就是dp[u] = ∑dp[v] && v is a
2016-09-24 22:13:50
508
原创 CodeForces 474E Pillars(线断树区间最大)
题目链接 给出n个数字，和最小间隔d。从i能走到j的充要条件就是|ai−aj|≥d\vert a_i - a_j \vert \ge d ，求最长的路径长度并输出路径，有多解输出任意一组路径。 思路就是dp[i]表示以i结尾的最长路径长度，dp[i]<-{pre{dp[j]}里面满足条件且最长的长度} ＋ 1， 这里查找的就可以是区间最大值的查找，因为要记录路径，所以里面还需要最大值
2016-09-19 19:59:56
565
原创 Codeforces 652D(一维树状数组)
题目链接 有n根木棍，每根的范围是[li,ri][l_i,r_i]，没有两个的rir_i是想通的，问每根棍子完全覆盖多少根棍子。 第i根棍子覆盖第j根棍子，必要条件就是li≤ljl_i \leq l_j &&rj≤ri r_j \leq r_i 。 那么按照l进行排序，l相同的r大的排在前面，然后从后往前扫。const int maxn = 2e5 + 10;struct seg
2016-09-19 16:40:46
618
原创 csu1808 地铁（最短路）
一个城市中有n个站m条线路（指直接相连接u-v），也就是和城市地铁一样，在某个站换线需要花额外的时间，求1号站到n号站的最短时间消耗。 猛的一看就是普通的最短路问题，但是实际需要改变很多，不能单纯的按照原来的方式求解dis[v]表示到v的最小时间花费。 因为你无法知道这个最小值是由哪条线路过来的，会直接影响后面的换线时间消耗。所以我们纪录走i号线到v的最小时间， 这样就能明白起最小
2016-09-06 09:52:05
722
原创 UVALive 7148 LRIP(树分治＋STL)
题目链接 题目大意：给出一棵树有1≤n≤1051 \leq n \leq 10^5个节点，每个节点有个权值1≤ai≤1051 \leq a_i \leq 10^5 ，求一个由节点构成的 最长权值不降连续子串，且串的最大值和最小值的差diff≤D,1≤D≤105diff \leq D, 1 \leq D \leq 10^5，样例数T≤10T \leq 10。 思路：用树分治比较方便。考
2016-08-28 16:35:01
774
原创 Gym 100646H You’ll be Working on the Railroad(搜索)
题意就是找一条从0到1的简单路径，费用最小。这里的费用定义如下： 1.路径条数=1,费用就为这条边的费用。 2.路径条数=2,费用就为两条中最小的。 3.路径条数>2,费用等于所有边的费用减去路径中最大和次大的费用。 且要求费用相同的话路径条数最少，路径条数 也也 相同的话字典序最小。/*****************************************Au
2016-08-27 15:55:49
699
1
原创 Acdream1103 瑶瑶正式成为CEO(费用流＋树剖)
题目链接 中文题意就略去。求1到u的最小费用可以用费用流来做，其他的就直接遍历一遍。那么铁路的a值的更改需要用树剖来维护， 并且每次查询前需要把线断树中的a值更新到tree，再重新构网络流的图跑费用流。先算出流量为0时的费用 sum=∑cisum = \sum c_i， 然后对于每单位流量，相当于其经过的边要少花c，当流量超过了a时就不能相当于少花了，所以这里需要拆边，分为流量小于等
2016-08-27 12:53:10
499
原创 HDU 4729 An Easy Problem for Elfness(树上主席树+LCA+二分)
题目大意：给你一棵树，每条边有一个容量。然后m个询问，每个询问是互相独立的，给你两个点S, T，一个预算K， 建一条容量为1的新边的费用A(可以建在任一两个节点之间，包括S,T)，将某一条现有的边容量扩大1的费用B。 问从S到T在预算允许的情况下最大流是多少。 这个分两种情况来讨论最优解： 1.如果A≤BA \leq B，显然新建不会比扩展差，可以建立kA\frac{k}{A
2016-08-23 21:14:44
445
原创 SPOJ COT(树上k大，主席树＋LCA)
给出一颗含有n个节点的树，每个节点有个权值。问u到v的路径上第k小的权值是多大。 做法就是主席树＋LCA，每个节点建立一颗从根（默认为1）到它的线断树，那么u->v路径的线断树就等于T[u] + T[v] - 2*LCA(u, v) + (l <= a[LCA] && a[LCA] <= r)。/*****************************************Author
2016-08-23 20:45:12
557
原创 Aizu 2677 Breadth-First Search by Foxpower(LCA + BFS)
题目链接 题目大致意思就是给出含有n节点的树，1为树根。从1开始bfs搜索整棵树，不过有顺序。深度小的比大的优先， 同一深度的其优先值为其父节点在上一层的搜索顺序，如果同属一个父节点，那么就是节点编号小的优先。然后求出路径总和sum。比如这次搜索到了u，下次需要搜索到v， 那么sum += dis(u, v)。树上的dis就是lca了，因为边权为1. 然后剩下的就是模拟这个过程
2016-08-22 23:37:00
381
原创 spoj DQUERY - D-query(区间不同数的个数 主席树 or BIT)
题目链接 给出含有n个数字的序列，每次问区间[l,r]不同数的个数。 可以用主席树也可以用树状数组，做法都是同一个原理。从左往右扫一遍，记录每个数上一次出现的位置。当扫到i位置时， 把a[i]上一次出现的位置-1，i这个位置+1。然后对于所有询问区间[x, i]进行回答（BIT区间求和）。主席树也是这个原理， 只是要保存历史版本。const int maxn = 3e4 +
2016-08-21 12:20:49
917
原创 poj2104 K-th Number(静态区间k大，主席树)
主席树 给出一个有n个元素的数列，每次问区间[a, b]间第c小的数是哪个。#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>using namespace std;#define Rep(i, l, r) for (int i = l;i <= r;++i)#define Rrep(
2016-08-20 17:14:20
409
原创 CodeForces 547B (单调栈)
题意 一个有n个元素的序列，没连续l个元素的最小值为这个串的strength值，求所有连续l个元素的strength是的最大值。分析 a[i]如果是其所在串的strength值，那么必然它是最小值，往前和往后找小于它的第一个位置l、r，显然[l + 1, r + 1]区间的strength等于a[i]。 就可以更新长度为len(len = r - l + 1)的strength。还有
2016-08-17 17:18:36
558
原创 Gym 100851F Froggy Ford(dijkstra)
题意有条宽为w的河流，两岸分别在x = 0, x = w处，河中间有n个石板。在河的一岸有一只青蛙想通过石板跳到对岸去。现在可以在河中间某个位置多加一块石板，使得在单步跳跃中的最大值最小。思路Dijkstra变形，用两维来表示是否路径中使用过额外的石板。dis[0][u]表示没使用额外石板的最大最小，dis[1][u]表示使用额外石板的最大最小。然后就用Dijkstra格式进行转移了。/**
2016-08-15 21:35:54
865
原创 Lightoj1267 Points in Rectangle (II)(排序＋树状数组)
题意二维平面上给出p个点，然后q次讯问。每次讯问一个矩形内有多少个点落于里面，包涵边界。思路容易想到二维树状数组，但是空间炸了。可以降维处理，去掉x这一维。离散化y值，把所有点放在一起排序，每个点还有其编号、离散化后的y值、是否是询问矩形上的点、左下角还是右上角等信息。然后按照x的大小排序，剩下的看代码。const int MAXN =1e6 + 12;int p, q;struct po
2016-08-12 23:24:02
460
原创 Lightoj1083 Histogram(线断树＋二分)
选定a[i]是，以它的高为准，往左找第一个小于它的后一个位置，往右找第一个小于它的前一个位置。const int maxn = 3e4 + 123;int a[maxn];int n;struct SegmentTree { struct node { int l, r, _min; }p[maxn<<2]; void build(int rt,int
2016-08-05 13:41:59
404
原创 codeforces 703D Mishka and Interesting sum (树状数组区间异或)
题意给出一个有n个元素的数组a[...], 1 <= a[i] <= 10^9,(n,m <= 10^6)。m次讯问区间[l,r]见出现了偶次的数的异或值。思路可以先求出1到i的异或值sum[i] = sum[i - 1] ^ a[i];树状数组部分有点同于求区间数的种数。last记录每个数前一次出现的位置。走到i时，如果a[i]出现过，那么把他上次出现的位置异或掉，再在i位置上异或上a[i]。
2016-08-05 10:10:33
802
原创 Lightoj 1411 - Rip Van Winkle`s Code(线断树)
题意就是用快速的方式实现在面的四种操作。long long data[250001];void A( int st, int nd ) { for( int i = st; i <= nd; i++ ) data[i] = data[i] + (i - st + 1);}void B( int st, int nd ) { for( int i = st; i <= nd;
2016-08-03 10:11:11
464
原创 Lightoj1188 Fast Queries(树状数组离线)
题意给出n个数，Q次询问l，r表示数组l到r区间内有多少种数字。思路离线处理每个区间，把区间按照r的值从小到大排序。用vis[...]数组记录每个数前面出现的最近的位置。处理到位置i时，如果前面出现过a[i],那么把前面的那个位置清0，然后标记新的位置，再就是求前缀和了。。。const int maxn = 1e6 + 1234;struct Querys { int l, r, i
2016-08-02 22:55:53
457
原创 Lightoj1187 Lining up Students(树状数组)
题意有n个人，每个人有不同的身高，n个人站成一条线，每个人说出左边比自己高的人数，问最左边的人是第几高的。思路可以从最右边开始做，比如n = 10, a[n]=2，说明左边比他高的有5人，那么b[n] = 8;a[n-1] = 4,说明左边比他高的有4人，b[n-1] = 5,因为8出现在了他的右边，不能算在里面，这样就显然是二分＋树状数组,因为线断树TLE了。/****************
2016-08-02 22:48:39
346
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人