- 博客(55)
- 收藏
- 关注
RSS订阅转载 【转载】LaTeX符号大全
转载于：https://blog.csdn.net/wangmeitingaa/article/details/88825621 文章目录 1、几个注意事项2、文本/数学模式通用符号3、希腊字母4、二元关系符5、二元运算符6、巨算符7、数学重音符号8、箭头9、作为重音的箭头符
2021-05-17 23:31:16
439
原创 主席树 总结
主席树（总结主要是为了给自己看，了解用法，主席树的基本原理和写法请出门左转dalao多多）思路在之前写博客的时候曾经说了一句，【线段树的可减性】，用这句话来解释线段树的原理。在之后的学习过程中发现这句话不太准确。主席树即可持久化线段树，它可以记录对线段树修改过程中，每一次修改时的状态，方便之后回退回当前状态。而同时，对于每一次修改，我们通过节点的重用，尽可能得减少空间开销，因为在单点修改时...
2019-03-25 10:48:20
223
原创 SPOJ COT 树上简单路区间第k大（主席树 + lca）
题目题意给出一棵 nnn 个节点的数，每个节点有一个权值。之后有 mmm 次询问，每次询问 u,v,ku, v, ku,v,k 表示，树上 uuu 到 kkk 的简单路径上，第 kkk 大的权值是多少思路一道图论+数据结构的特别有意思的题目，充分利用了主席树可减的特点。我们查询简单路径 (u,v)(u, v)(u,v) 时，可以通过 dfsdfsdfs 序建立主席树。而路径路径上的信息就是...
2019-03-21 11:49:09
277
原创 hdu 6464 （splay）（离线+离散化+权值线段树）
题目题意操作 111 每次可以加入 xxx 个 yyy，操作 222 查询第 xxx 大的数到第 yyy 大的数的区间和思路splay动态加点，查询第 xxx 大和第 yyy 大的元素后，通过旋转操作放在一个子树当中，很快的求出区间和，不需要离散化，操作略复杂离线+离散化+权值线段树通过离线可以把 1e91e91e9 的数据离散化到 1e51e51e5 的区间中，得到了这种映射关系之...
2019-03-19 21:05:37
230
原创 POJ 2104 区间第k大 主席树（模板）
题目题意查询区间范围内，第 kkk 大的数思路按照数列顺序依次加入，构建可持久化线段树（主席树），由于线段树的可减性，能够得到对应区间范围内的线段树主席树的模板题了代码int cnt, root[maxn], a[maxn];struct Node{ int l, r, sum;}T[maxn*40];vector<int> v;int getid(i...
2019-03-19 17:50:32
207
原创 Codeforces Round #473 (Div. 2) (A-E) (水题 + 并查集 + 构造 + 分解因数 + 贪心)
A题意给出一个数 nnn，两人每次可以选择一个数 aaa，使得 n=n−an = n - an=n−a。其中a≥1a \geq 1a≥1 且第一个人选的a应为偶数，第二个人选的应为奇数，谁不能选的时候为负。谁不能操作为负，问谁能赢。思路判断 nnn 的奇偶性即可，先手偶数不改变奇偶性，后手奇数改变奇偶性，当 n==0n==0n==0 时游戏结束，也就是说仅判断 nnn 的奇偶性即可。代码...
2018-11-05 17:20:16
219
原创 BZOJ 3224 普通平衡树（splay 模板）
题目题意中文体面，题意就不写了思路splaysplaysplay 模板题，实现插入、删除、查询等操作代码int ch[maxn][2], pre[maxn], val[maxn], size[maxn], num[maxn];int root, tot;void print(int now){ // printf(&quot;%d: ls:%d rs:%d num:%d minn:%d ...
2018-11-01 14:46:37
160
原创 ZOJ - 3965 Binary Tree Restoring （dfs）
题目题意给出一颗二叉树的两种 dfsdfsdfs 序列，即同一层上没有明确的左右子树概念，两种序列可以以根节点-左/右子树-另一颗子树的顺序实现。求一颗满足两种 dfsdfsdfs 序列的二叉树，输出每一个节点的父亲节点。题目保证有解思路因为是一颗树的重构，我们可以同时从两棵树的 dfsdfsdfs 序列入手，我们可以分别在两个序列上，找到当前子树所在的区间，并且可以通过判断当前位在两个序...
2018-10-31 09:16:22
286
原创 每天学一丢之 单调栈
每天学一丢意为每天学一点丢一点。单调栈单调栈即我们在维护栈时，同时让栈里的元素维持着单调性。即当我们维护一个单调上升的栈时，如果需要入栈一个新元素后，如果这个元素之前有比他大的值，破坏了栈内元素的单调性，我们就要把比它大的值全部出栈，此时再将新元素入栈，来保证栈内元素的单调性。单调是说栈内元素具有单调性，功能利用单调栈，我们可以在 O(n)O(n)O(n) 的时间复杂度内，维护序列中任意一...
2018-10-10 10:58:32
149
原创 HDU 6406 Taotao Picks Apples (线段树)
题目题意给出 nnn 个数，规定一个取数规则，从左至右，先取第一个数，之后每次遇到比上一个所取数字大的数，就必须取。给出 mmm 次询问，每次询问给出一个位置 xxx 和值 hhh，代表将位置 xxx 上的数字改为 hhh，问此时按照取数规则能取到多少个数。每次询问都是独立的。分析题目其实是找数列中的严格上升子序列，但是由于见到大的数就必须选，所以这个子序列是唯一的。难点在于mmm 次独立...
2018-10-10 10:20:14
141
原创 每天学一丢之 Manacher
每天学一丢意为每天学一点丢一点。ManacherManacherManacherManacher 算法主要解决的问题是最长回文子串，为了解决奇偶性的问题，我们在原字符串中加入了新的字符作为通配符，例如我们将 abababcabababcabababc 扩充为了 #a#b#a#b#a#b#c#\#a\#b\#a\#b\#a\#b\#c\##a#b#a#b#a#b#c#，因为 #\## 号都是相同...
2018-09-26 14:25:09
151
原创 2018 BACS Contest Replay（A + C + L）
一场三星gymA题意一个类似与约瑟夫环的问题，一共有 NNN 个人，可以从中选出前 YYY 个人，这 YYY 个人会按照隔一人淘汰一人的方式，淘汰至只剩一个人（成环淘汰，或者循环数组淘汰），已知，我们选择前 [L,N][L, N][L,N] 个人出来的概率是相等的，问编号为 XXX 的人存活下来的概率，用最简分数来表示。思路第一次打表找规律做题，原因可能是吉林自闭的太厉害了，于是就回来之...
2018-09-26 11:26:10
301
原创 ACM-ICPC 2018 徐州赛区网络预赛 J（最大生成树 + 树上距离）
阿斯蒂芬#include &lt;bits/stdc++.h&gt;using namespace std;#define sd(n) scanf("%d",&amp;n)#define sdd(n,m) scanf("%d%d",&amp;n,&amp;m)#define sddd(n,m,k) scanf("%d%d
2018-09-19 17:11:19
207
原创 每天学一丢之 LCA-倍增
每天学一丢意为每天学一点丢一点。LCALCALCALCA 上一篇中已经解释过，而 TarjanTarjanTarjan 离线算法可以在 O(n+q)O(n+q)O(n+q)的时间复杂度下，求得询问两点的 LCALCALCA。 而倍增是一种在线查询的算法，他的预处理复杂度是 O(nlogn)O(nlogn)O(n\log n)，每次查询是 O(logn)O(logn)O(\log ...
2018-09-14 14:03:36
187
原创 每天学一丢之 LCA-Tarjan
每天学一丢意为每天学一点丢一点。LCALCALCALCA 即树上最近公共祖先，TarjanTarjanTarjan 可以离线地去求 LCALCALCA，并且可以维护树上两个点的距离。 TarjanTarjanTarjan 的复杂度是 O(n+q)O(n+q)O\left( n+q\right) 的TarjanTarjanTarjanTarjan 不仅可以解决 LCALCALCA ...
2018-09-13 19:18:27
153
原创 ACM-ICPC 2018 徐州赛区网络预赛 B（博弈 + dp）
L题意起始有 mmm 的价值，已知有 nnn 轮抉择，每轮抉择有三种，分别为 ai,&nbsp;bi,&nbsp;ciai,&nbsp;bi,&nbsp;cia_i,\ b_i, \ c_i 其中任何一个值为 000 表示当前不可选。否则，可以选择将当前价值 +ai,&nbsp;−bi,&nbsp;×(−1)+ai,&nbsp;−bi,&nbsp;×(−1)+a_i,\ -
2018-09-12 15:48:26
183
原创 ACM-ICPC 2018 徐州赛区网络预赛 A （DP）
A题意有 nnn 个人围成圆形而坐，2k2k2^k 顶帽子，一顶帽子可以给任意多个人，一个人只能由一顶帽子，帽子的编号为 [0,&amp;amp;amp;amp;nbsp;2k−1][0,&amp;amp;amp;amp;nbsp;2k−1][0,\ 2^k-1] 。相邻两个人帽子的编号不能在k位上都相反，问有多少种坐的办法。思路相邻问题链上好分析，但是因为本题要求是围成一个圆坐，所以要考虑链的两端能否满足条件。又由按位取反操作可知，对于任意一
2018-09-11 16:57:26
271
原创 ACM-ICPC 2018 徐州赛区网络预赛 G （离散化 + 树状数组 + 区间最大值 + 模拟）
G题意按照顺序往坐标系的第一象限放矩形，其中矩形的一个顶点和原点重合。数据中给出矩形右上方顶点的位置 (x,y)(x,y)\left(x, y \right)。已知后放上的矩形会覆盖之前的矩形，问，露出来的边界的总长度是多少（不计坐标轴）（依然是来自于队友的翻译，看看题会比较好理解）思路由于题目给出，矩形不会完全覆盖，所以对于任意两个矩形的右上顶点(xi,yi)(xi,yi)\...
2018-09-11 16:23:16
139
原创 ACM-ICPC 2018 徐州赛区网络预赛 F （模拟）
F题意每次给出 nnn 个连续的时刻，每个时刻中有若干特征的实物出现，每个特征由两个值表示即 (x,y)(x,y)(x, y) 表示一个特征，当且仅当两个值都相同时，我们认为他们是同一实物。先问同一实物最多连续出现了多少时刻。（队友读的题， 随便翻译一下= =）思路模拟，用 map<PII, PII>map<PII, PII>map记录每...
2018-09-11 12:06:49
207
原创 ACM-ICPC 2018 徐州赛区网络预赛（I + H）（水模拟 + 线段树）
I题意给定一个字符串sss和一个字符LLL，将所有的 |(int)(L−s[i])||(int)(L−s[i])||(int)(L-s[i])| 转化为一个两位数后，按顺序拼接在一起，问，这个拼接而成的新序列，去掉前导0后的长度是多少思路按照模拟去实现一下过程就可以，可以计算前导零的个数，就不用算出所有的值了，现给出一种纯模拟的写法代码int a[maxn];ch...
2018-09-10 17:13:05
427
原创 CodeForces - 280D k-Maximum Subsequence Sum（区间最大k段和）（线段树 + 最大子段和 + 区间修改 + 区间查询 + 单点修改）
题目题意给定nnn个数的序列，定义两个操作 ⋅0kval⋅0kval\cdot \quad 0\; k\; val 把序列第k个数的值变为val ⋅1lrk⋅1lrk\cdot \quad 1\; l\; r\; k 询问在区间 Al⋯ArAl⋯ArA_l\cdots A_r 中，选取 mmm 段不相交的子区间，使得这 mmm 段子区间的和最大，其中0≤m≤k0≤m≤k0\leq...
2018-09-07 17:39:54
1227
原创 CodeForces - 543B Destroying Roads (Dijkstra + 堆优化 + 枚举重复部分)
题目题意有 nnn 个城市，mmm 条道路，问可删去多少条道路，使得删去后的图上，从 s1s1s_1 到 t1t1t_1 时间花费小于等于 l1l1l_1，从 s2s2s_2 到 t2t2t_2 时间花费小于等于 l2l2l_2。其中通过任意一条连接两个城市的道路的时间花费都为1思路要想删去的边尽可能多，其实也就是使得满足条件：“从 s1s1s_1 到 t1t1t_1 时间花费小于...
2018-09-06 17:12:52
204
原创 CodeForces - 543A Writing Code（背包问题 + dp + 滚动数组）
题目题意有 nnn 个程序猿要写 mmm 行代码，第 iii 个程序猿每行会出现 viviv_i 个 bugbugbug ，问最后总 bugbugbug 数不超过 bbb 的码代码方案数有多少种，答案对 modmodmod 取模 其中，方案定义为，每个程序猿码代码的行数，如果两种方案中，存在一人所码代码行数两次不同，则认为是两种方案。思路如果我们独立的看待每行代码，定义 dp[k...
2018-09-06 16:28:16
201
原创 SPOJ GSS4 (区间开根号 + 区间查询) (线段树)
题目这个题目camp里面有讲过，用到的是BOZJ 3211题意对于给定的，n个数的序列，我们定义两个操作，分别是区间开根号以及区间求和。共有m次查询 其中n,m≤1e5,∑ni=1ai≤1e18n,m≤1e5,∑i=1nai≤1e18n ,\; m\leq 1e5,\; \sum_{i=1}^n a_i \leq1e18思路我们可以简单的计算一下，一个1e181e181e...
2018-08-14 23:16:54
1076
原创 SPOJ GSS3 (区间最大子段和 + 单点更新) (线段树)
题目思路详细思路移步GSS1这里只是加入了一个单点更新得操作，找到要更新得顶点，然后把它更改，再递归调用回溯的时候维护区间特征值 EndEndEnd代码struct Node{ int l, r; int sum, maxs, maxl, maxr; //区间和, 区间最大子段和, 最大前缀和, 最大后缀和}tree[maxn<<2];...
2018-08-14 19:57:29
733
原创 SPOJ GSS1 (区间最大子段和)（线段树）
想要补camp里的那道区间最大k子段和，结果发现自己连怎么求区间最大字段和都不会。。。菜是原罪，于是找了GSS来补一下（虽然我连GSS是什么都不知道hhh题目题意给一个长度为nnn的序列，mmm次查询，每次查询一个区间[l,r][l,r][l,r]中的最大子段和（要求为连续子序列）。思路对于一个固定区间，求最大子段和我们有O(n)O(n)O\left(n\right)的...
2018-08-12 22:38:08
1059
原创 Codeforces Round #FF (Div. 1) C (Segment_Tree)
题目题意给定一个长度为n的序列，对序列定义两种操作： (1,l,r)(1,l,r)(1,\, l,\, r) 在对应[l,r][l,r][l,\, r] 的区间上，对ai+Fi−l+1ai+Fi−l+1a_i + F_{i-l+1}其中i∈[l,r]&amp;amp;nbsp;Fii∈[l,r]&amp;amp;nbsp;Fii\in[l,\, r]\ F_i为斐波那契数列的第iii项。其中F1=1F2=1Fn=F...
2018-08-12 17:23:41
193
原创 线段树模板
贴一个自己实现线段树单点修改，区间查询，区间修改的模板struct Node{ int l, r; int sum, minn, maxx; //特征值 int lazy;}tree[maxn&amp;amp;lt;&amp;amp;lt;2]; //开四倍空间int num[maxn]; //数值数组void build(i...
2018-08-11 22:41:08
410
原创 NENU SUMMER TRAINING #3 (题解)
A题意分析代码B题意分析代码C题意分析代码D题意分析E题意分析代码F题意分析代码G题意分析代码H题意分析代码特别感谢由Muvsea提供的部分思路与代码A题意输出1378n1378n1378^n 的个位数字是多少？分析我们知道对于一个数的n次幂，他的个位数字会以一...
2018-07-26 00:46:05
201
原创 NENU SUMMER TRAINING #1 （题解）
ABCDEFGHIA题意：定义一个填充块，填充块由 ‘o’, ‘g’ 交替出现组成，并且以 ‘o’ 开头，以 ‘o’ 结尾，形如：”ogo”, “ogogo”, “ogogogo”等，现在给出一个给定长度的字符串，需要将其中所有的填充块换为 ‘***’ 之后输出。思路：问题的核心在于如何找出所有的填充块，我们可以发现，填充块可以转化成，以o开头与不少于一组...
2018-07-24 08:57:12
368
原创 每天学一丢之 IDDFS （5.28）
每天学一丢意为每天学一点丢一点。然后每天二字名存实亡，还是坚持在每天学习，只是每天学习的东西不够单开一文去总结。这段时间在准备各种比赛，所以题解没有跟上，还不好说会不会补训练赛的题解。IDDFS（iterative deepening deep-first-search）迭代 加深 搜索首先第一点我们知道，在迷宫问题计算最短路的时候，我们经常使用BFS 这样做的好处是：第一次搜索到目标点时，就是到...
2018-05-28 19:04:40
1147
原创 Codeforces Round #386 (Div. 2)（A-E）（水题 + deque模拟 + 思维 + 构造&贪心 + set模拟）
A题意：制作物品的三种材料用比为1：2：4，给出三种物品的用量，问最多能制作出多少质量的物品。思路：判断每种材料最多可以制作出多少个成品，取最小值即可。#include<bits/stdc++.h>using namespace std;const int maxn = 1e5+5;int main(){ int a, b, c; cin>>a&...
2018-05-10 17:27:50
170
原创 Codeforces Round #374 (Div. 2)（A-D）(水模拟 + 水模拟 + dfs & dp + 优先队列模拟)
A题意：记录被W分离的连续B的数目思路：水题，读入模拟#include<bits/stdc++.h>using namespace std;const int maxn = 1e5+7;char s[maxn];int ans[maxn];int main(){ int n; cin>>n>>s; int cnt = 0...
2018-05-07 17:21:39
179
原创 Codeforces Round #433 (Div. 2)（ 模拟 + 思维 + 贪心 + dp ）
A题意：给出一个真分数的分子分母的和n，求满足条件的最大的真分数。真分数为：分子小于分母且分子分母互质。gcd判断。#include<bits/stdc++.h>using namespace std;int gcd(int a, int b){ if(b==0) return a; else return gcd(b, a%b);}int main()...
2018-05-03 12:11:03
171
原创 2017大学生程序设计竞赛 女生赛（A、E、C、G、B）（ 水模拟 + 水模拟 + 前缀处理gcd + 思维模拟 + dp）
A题目大意：给出题号、时间、judge。计算最后的罚时。模拟可以过，学妹的代码，Orz#include <bits/stdc++.h>using namespace std;const int maxn=3000;int wa[maxn];set<int>ac;int cnt;int ans;void init(){ for(int i=0; i&l...
2018-05-03 11:49:17
432
原创 sgu刷题笔记开篇 & 100 A+B
其实说实在话我不太喜欢多线程作战的，目前的话我的想法是保持每周三周五的训练，周六没有事情的话也参加训练，然后按照组内布置的的分工重点突破一下图论和数据结构。但是聚聚今天给我推荐了sgu，经过慎重的思考我决定维持原计划不变，在sgu中作为训练之余的训练去按顺序刷一下题目，然后此次算作一个开篇，这个和每天学一丢和CF和比赛训练不同，不定时学习更新，作为拔高。每天学一丢属于新知识点的总结记录，CF和比赛...
2018-04-25 14:54:45
257
原创 每天学一丢之 坐标离散化 （4. 24）
每天学一丢意为每天学一点丢一点。然后每天二字名存实亡，还是坚持在每天学习，只是每天学习的东西不够单开一文去总结。其实第二个本来打算写LCA的，但是LCA还没学明白加上今天刚刚又口胡一遍坐标离散化，那就总结一下吧。坐标离散化，适用于一个较大的图中，有很多无用的部分，这时我们通过离散化的方式，将他们缩小并保持原关系不变。首先给出一个一维离散化的例子。给出数轴N（N<1e5, val(N)<...
2018-04-24 19:35:25
540
原创 2016CCPC东北赛 （A、C、E、H、F、D）（ 水题 + 结论 + 水模拟 + 复杂模拟 + LCA思维 + 二维坐标带权离散化 ）
A - Minimum’s Revenge There is a graph of n vertices which are indexed from 1 to n. For any pair of different vertices, the weight of the edge between them is the least common multiple of their indexe...
2018-04-24 18:46:13
954
原创 Codeforces Round #407 (Div. 2) (A-E) ( 水模拟 + 复杂模拟/multiset优化 + dp + 欧拉路 + 平均数处理bfs)
昨天训练的题目，今天终于把题补完了。补完之后又忍不住骂了自己几句智障，感觉很不是状态。然后立一个flag吧，之后所有的cf div2的题全部补完，不会的看题解补，为区域赛准备。今年作为coder之后压力还是比较大的，不过也是一个比较好的提高的机会吧，累并快乐着。A. Anastasia and pebblesAnastasia loves going for a walk in Central U...
2018-04-19 20:58:27
220
原创 每天学一丢之01 BIT （4.17）
第一次知道BIT是在去年暑期培训的时候了，当时听线段树感觉似懂非懂，但至少知道这个线段树它想表达个什么意思，前几天校赛也用一种类似于模拟的手法实现了线段树，然后今天从套题训练又转至专题训练，就对那个暑期培训云里雾里畏之如蛇蝎的树状数组又拿出来看了一眼，然后居然发现能看懂了！！！然后居然发现这玩意儿这么简单？？？然后居然发现前几天校赛用线段树做我是不是个智障！！！每天学一丢系列，意为每天学一点丢一点...
2018-04-17 19:57:34
232
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人