- 博客(148)
- 收藏
- 关注
RSS订阅原创 C++ stl vector
#include <iostream>#include <vector>#include <algorithm>using namespace std;/*c++ stl是非常好用c++封装的官方库 学会使用stl在写代码的时候非常有帮助vector的基本用法vector可以简单理解为是一个动态数组 这里只介绍最简单的用法 关于容量以及如何动态扩...
2020-02-21 17:09:33
201
原创 C++结构体自定义排序
声明：本机无C++环境，以下代码均没有编译测试，最近golang写的比较多，语法可能会有问题，请自行测试代码sort排序函数简单使用#include <bits/stdc++.h>using namespace std;int a[100];bool cmp1(int x,int y) { return x > y;}bool cmp2(int x,int...
2020-01-09 13:31:12
2531
原创 linux bash脚本初学
本文大部分资料来自：https://my.oschina.net/FEEDFACF/blog/1789695这个语言的学习感觉学到后面很难去实现一些比较大型的任务，目前学的也很浅，先发一下所有的知识点总结。顺便吐槽，这些东西是真难记啊～～～比较符 描述 n1 -eq n2 检查n1是否与n2相等n1 -ge n2 检查n1是否大于或等于n2n1 -gt n2 检查n1是否大于...
2019-03-28 20:10:14
759
3
原创 c++网络编程并发处理
client.cpp#include<bits/stdc++.h>#include<unistd.h>#include<sys/types.h>#include<sys/socket.h>#include<netinet/in.h>#include<arpa/inet.h>#define SZ 10usin...
2019-03-27 21:08:42
621
原创 c++网络编程初步学习
今天学习了一下网络编程的初步知识，其实大部分就是socket的api调用。简单学习一下大部分参考：c++网络编程https://blog.csdn.net/ZH0314/article/details/77387162环境：manjaro ide：vscode参考代码的时候有的地方在我的linux环境下会出问题，这里做了一些修改。socket相关函数 so...
2019-03-25 22:27:34
10612
4
原创 c++多线程初步学习
c++多线程学习学习资料来源于C++多线程菜鸟教程：c++多线程本人使用环境 manjaro ide为vscode c++11,这里需要注意，对于线程相关代码编译时需加入 -lpthread 即 g++a.cpp -lpthread否则会显示undefined reference to `pthread_create'我这里使用为vscode按照刚开始配置文件无法通过vs...
2019-03-23 17:44:39
1024
原创 剑指offer题目合集及解法
最近做了剑指offer的题目，很多题目的最优解很有意思，很多时候想不到，写篇博客专门来记录一下。 二维数组中的查找在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。利用排序的特性class Solution {public: ...
2019-02-03 17:49:02
372
原创 c++ primer学习记录（二）
stringgetline(cin,s); 读取一行cin读入会自动忽略开头的空白（空格符 换行符 制表符）从第一个真正的字符读起，直到遇到下一处空白为止getline函数的参数是一个输入流和一个string对象，函数从给定的输入流中读取内容，直到遇到换行符（换行符也被读入），之后将所存内容存入到string对象中（不存换行符）size()函数返回值是size_type 无符号类...
2019-01-29 17:04:19
173
原创 c++ primer学习记录（第一章）
虽然C++作为比赛的代码已经写了很多了，但是很多细节上的东西还是存在很多不懂得地方，重新学习并记录.jpg。 cerr和clog为ostream定义的两个对象。cerr通常输出警告和错误消息，被称为标准错误。clog用来输出程序运行时的一般性信息。程序员调试时输出打印语句，应保证一直刷新流，否则，如果程序崩溃，输出还留在缓冲区中，可能会造成对于程序崩溃位置的错误判断。 char...
2019-01-18 10:53:02
161
原创 hdu4777 树状数组
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4777 题目大意：给n个数，求LR区间内有多少个数和当前区间所有其他数互质。 解题思路：训练赛完全想不到，首先我们需要预处理出 对于一个数 i 它最左和最右到哪不互质，记为 pl pr，那么当我们查询区间 L R时，实际上就是查询区间中有多少 pl<L pr>...
2018-10-19 21:20:41
259
原创 后缀数组之求出现次数L到R次的字符串的个数
题目大意：给你一个字符串，求出现次数在L到R次之间的字符串的个数。 解题思路：利用height数组求解，首先我们要知道求L到R次的数量可以利用L次以上的数量减去R+1次以上的数量求得，那么这个题就转换为了求出现k次以上的字符串的个数。首先k=1 特判，即 n-sa[i]-height[i]，即所有不相同子串。k>1时，利用height数组，对每k-1个heigh...
2018-09-23 21:09:45
733
原创 pycharm配置pyuic的时候出现ModuleNotFoundError: No module named 'PyQt5'的解决方案
教程：https://www.jianshu.com/p/094928ac0b73最近在学习用python写界面，就学到了pyqt。按照教程的方法一步一步到最后之后，再尝试将.ui转换为.py文件时总是出现类似于ModuleNotFoundError: No module named 'PyQt5'的提示，自己整了整整一天，尝试过重新安装python等等类似方案都不行，最后尝试...
2018-09-06 22:35:18
10055
6
原创 2018 Multi-University Training Contest 7-1009 & hdu6394:Tree(LCT)
题目大意：这题基本上就是弹飞绵羊的树上版，所以题意就不多讲了。可以参考另外一篇博客:弹飞绵羊普通版 解题思路：首先肯定可以用树分块来写，思路就是跟线性的是一样的。其次的话如果用LCT的话近似裸题，只是需要求一下对于点x，向上跳k次会跳到哪个点，用倍增求出来即可。然后我添加了一个n+1作为1结点的父亲，跳出去的点默认跳到n+1，之后就和线性的一样了，这次主要也是为了测试LC...
2018-08-30 09:14:17
184
原创 BZOJ2002：Bounce 弹飞绵羊（LCT）
之前用分块解过这道题，不过最近学到了LCT，发现它也是LCT的模板题，就用LCT做了一下。分块解法：https://blog.csdn.net/f2935552941/article/details/78157052 LCT的话，推荐一篇博客，讲的比较清楚，但是如果想深入了解的话建议可以找国家集训队的论文看一下。推荐博客：https://blog.csdn.net/Jerem...
2018-08-27 17:05:17
174
原创 2018CCPC网络赛：Neko's loop（单调队列）
题目大意：给你n个数，每次可以选择从任意一点开始跳跃，每次跳跃至 (i+k)%n 的位置并获得当前位置的最大快乐值，求跳m步的过程中能够获得的最大快乐值，可以在任何时刻终止该操作。 解题思路：其实这个题初看比较复杂，但是无聊打了个表发现对于 长度为n 的序列，它所有的循环节是等长的。等于说整个序列就是由一些循环节构成的，那么我们把循环节专门挑出来计算跳m步即可。那么问题就...
2018-08-26 21:04:31
435
原创 2018CCPC网络赛1001：Buy and Resell（优先队列）
题目大意：1到n每个城市有一个价值为a[i]的物品，当你到达这个城市的时候，可以花费a[i]买一个物品，也可以卖掉手中一个物品获得a[i]，也可以什么都不做。问最后能够获得的最大利润是多少，最大利润相同时求最少的交易次数，同一时刻手中可以持有多个物品。 解题思路：维护一个优先队列，每次到达一个城市，判断一下当前优先队列中最小的值是否小于当前城市的a[i]，如果小于的话，就假设...
2018-08-25 21:27:02
363
原创 hdu多校第九场 1005（hdu-6430:TeaTree）
题目大意：对于一个结点 x，它的值可以是当前子树内任意两点的gcd值。但是要求 lca(i,j)=x。最后问你每个结点最大的值可能是多少，如果不存在输出-1。 解题思路：本来想用树上dsu来写的，结果写了一上午，总感觉dsu有哪些地方不对劲，开始删删改改，最后发现写出来了一个暴力合并，复杂度的话不太会证明，可能因为约数较少的缘故，所以复杂度不是很高。具体实现就是预先打...
2018-08-24 15:44:45
170
原创 牛客网暑期ACM多校训练营（第九场）E：Music Game（单位求贡献）
题目大意：有n个点，每个点被点击的成功率为p[i]/100，如果有连续的x点成功被点击，你将获得x^m次方的分数，问你在已知所有点被点击成功的概率的情况下，问你最后获得分数的期望。 解题思路：思路的话其实我感觉对于期望题我就只会对单位求贡献，这个题目也是一样的。就是从这个位置开始连续x点成功的概率*获得分数，算起来也很简单，假设从 i 开始 连续 x 个成功的概率 ，其实就是...
2018-08-18 21:02:47
226
原创 2018 Multi-University Training Contest 8-1012：From ICPC to ACM（模拟+贪心）
题目大意：这道题目题意比较复杂，但是仔细分析以后模型还是比较简单的。。。题意就是接下来有n个月，ci di mi pi 分别表示第 i 个月的原材料价格，客户要求的计算机数量，mi表示生产一台计算机的人工成本，pi表示这个月能生产的计算机数量。同时我们可以预先储存一些原材料和计算机，对于储存的原材料的数量没有限制，计算机数量有限制，并且储存需要一定的成本。ei Ri Ei...
2018-08-15 19:53:16
280
原创 2018 Multi-University Training Contest 6-1009:Werewolf(脑洞+图论)
题目大意：有n个人，其中每个人的身份有狼人和村民，他们彼此之间知道相互的身份。每个人都会谈论除了自己以外其他一个人的身份。已知，村民只会说真话，狼人会说真话也会说谎话，求出在任何情况下都只能为村民和只能为狼人的玩家的数量。 解题思路：首先因为狼人会说真话，所以理论上绝对的村民是不存在的。因为任何村民都有可能被狼人假冒。所以村民数量永远是0，那么什么情况下一定为狼人呢，这种...
2018-08-11 10:01:20
156
原创 hdu:6346(最小权匹配+km算法复杂度检测题)
题目大意：虽然看不懂为啥是最小权匹配，但是只是用来检验一下km算法板子的复杂度。结果kuangbin大佬的板子T了。。。就去网上扒了另外的一份板子，没用读入挂的情况下700msAC（原题给了5s）。。。真是跪了，保存一下以备不时之需。。。就是注意一下这题需要long long 。。。Ac代码：#include<bits/stdc++.h>using names...
2018-08-10 14:50:04
1173
2
原创 BZOJ:2152(点分治)
题目大意：给一棵树，树上每个边有权值，AB每次从树中随机选择两个点，如果两点间点的权值和为3的倍数，则A获胜，否则B获胜。A比赛完后会对树进行研究，想知道他能获胜的概率是多少。 解题思路：其实就是点分治，对于重心V，我们统计出它两边权值和分别%3为0为1为2的个数，那么对于重心V的答案就是 d[1]*d[2]*2+d[0]*d[0]，这些就是A能够获胜的方案，然后再减去重...
2018-08-08 10:17:33
306
原创 POJ1741：tree（点分治）
题目大意：给你一颗树，树上每条边有自己的权值，问你两点间权值和小于等于k的点对有多少个。 解题思路：点分治模板题。今天学了一下点分治这个东西，看了整整一天，还是感觉没怎么搞懂，大概原理明白了，但总是觉得还有点欠缺= =，题目稍微一变就不会做的样子。。。还需继续学习。。。点分治个人认为也是一种比较重要的算法，在解决树上路径问题的时候有很大的作用，推荐学习一下，直接看论文...
2018-08-07 20:24:00
158
原创 牛客网暑期ACM多校训练营（第五场）F：take （树状数组维护期望）
题目大意：给你n个箱子，每个箱子打开后有p概率获得大小为 d 的钻石，按照顺序从第一个箱子开始打开。每当打开箱子后发现箱子里的钻石比当前手上的钻石大，就交换一次。问最后打开所有箱子后交换次数的期望是多少。 解题思路：对于一个箱子，我们打开它以后会发生交换的概率其实是 pi*（1-pj） pi 指的是当前打开这个箱子得到钻石的概率， 1-pj 指的是在这个箱子之前...
2018-08-06 21:06:33
149
原创 牛客网暑期ACM多校训练营（第五场）E：room（最大权匹配）
题目大意：有n个宿舍，每个宿舍住了四个人。年末宿舍需要重新分配。你收到了n份宿舍的人员请求，求问怎样安排宿舍使得交换的次数最少。 解题思路：刚开始想了一下，然后队友发现对于新旧的宿舍可以建边，它们的权值就是两个宿舍相同的人数。然后直接跑km算法即可。最后用总人数减去跑出来的权值就是答案。 Ac代码：#include<bits/stdc++.h>...
2018-08-06 20:52:32
228
原创 2018 Multi-University Training Contest 5 1007:Glad You Came(线段树暴力)
题目大意：给你n个初始化为0的数，m次操作，每次操作将 l r 区间内的所有小于val的更新为val。最后查询所有数的异或和。 解题思路：刚上来队友给我讲了题意后第一反应，这不是个线段树区间更新裸题嘛。但后来一想如果是这样不可能过的人这么少。就强行自己干掉了线段树写法，yy了另一种mlogm的写法，真的智障，T了两发以后发现线段树的复杂度貌似是mlogn的就滚去写线段...
2018-08-06 20:32:53
213
原创 牛客网暑期ACM多校训练营（第六场) I题：Team Rocket （线段树）
题目大意：一维坐标系上有n条线段，每条线段都有 l r 。每次破坏一个点x 所有包含这个点x 的线段都会被破坏。现在要求你针对每次询问输出每次有多少条线段被破坏，被破坏过的线段不能被破坏(强制在线)。m次询问完后统一输出每条线段分别是在第多少次操作后被破坏的，没有被破坏的输出0。 解题思路：比赛的时候想到了 一种思路，就是按照每条线段的左端点排序，然后针对右端点建立主席树...
2018-08-06 11:20:22
199
原创 hdu-4358:Boring counting(优美算法之树上启发式合并)
通过这道题了解到了神奇的树上dsu算法，起因是最近想再学习一波线段树，然后就找了一套线段树总结的题目。在那个总结里面看到了这道题，感觉很有意思。然后晚上回了宿舍就和室友在讨论，然后室友告诉我树上启发式合并随便做？？？当时一脸懵逼，树上启发式合并是什么鬼，其实个人对启发式合并还是有一点了解的。之前做了一道可持久化并查集，那里面并查集的合并没有用正常的路径压缩，是用判断两个并查集大小的方式进...
2018-07-31 21:00:22
919
原创 POJ - 3294：Life Forms （后缀数组之求至少k个串中出现的子串）
题目大意：给你n个串，求在至少n/2（大于n/2）个串出现的最长子串,按字典序从小到大输出。 解题思路：日常二分，二分长度，然后对其存在进行判断即可。这里我感觉用set处理起来比较简单，对于height[i]大于等于k的值，直接把 pos[sa[i]] 和 pos[sa[i-1]] 加入到set中。最后判断set中的元素个数是否大于n/2，如果大于 就把 sa[i] 储存...
2018-07-31 20:08:21
209
原创 POJ - 3261：Milk Patterns （后缀数组之求至少重复k次的子串长度）
题目大意：给你一个串，以及整数k，求这个串中至少重复k次的子串的长度。 解题思路：二分二分二分！！！后缀数组，一言不合就二分。直接二分长度，然后判断当前长度是否合法即可。 Ac代码：#include <iostream>#include <cstdio>#include <cstring>#include <...
2018-07-31 19:48:24
148
原创 POJ - 2406:Power Strings (求最小循环节)
题目大意：给你一个串S，问你它的子串最多重复多少次可以得到S串。 解题思路：这竟然是后缀数组这一节的练习题，明显的kmp求最小循环节。。。最小循环节：n-next[n]。顺便吐槽一下 万恶的POJ，不能用 bits/stdc++.h Ac代码：#include <iostream>#include <cstdio>#inclu...
2018-07-31 19:41:45
125
原创 2018 Multi-University Training Contest 3 hdu多校第三场 Problem A：Ascending Rating(单调队列)
题目大意:给你n个数，对于第i个数求区间（i , i+m-1）的最大值以及严格递增序列的长度。 解题思路：n是1e7，所以肯定是单调队列，但是单调队列注意要倒着维护，倒着维护感觉会比较的简单。最大值直接取 head 即可，长度即tail-head的长度。 Ac代码：#include<bits/stdc++.h>using namespace std...
2018-07-30 21:02:04
356
原创 dls板子
最近打多校，发现dls有很多神奇的板子，先偷过来，慢慢研究一下。 头文件：#include <bits/stdc++.h>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb...
2018-07-30 10:40:48
1437
原创 牛客网暑期ACM多校训练营（第四场）J:Hash Function(数据结构+乱搞)
题目大意：有一种hash方式为，当a[i]%n产生冲突时，就往后推到一位没有冲突的地方。现在给你hash后的序列，能否推出hash前的顺序，如果可以，输出最小字典序。 解题思路：刚开始比赛的时候想的是拓扑排序，因为对于拓扑排序来说在A事件没有发生前，是不可能发生B事件的。那么就是说如果我a[i]%n的结果是pos 那么就可以对于 pos 到 i 所有的数对于a[i]连一条有向...
2018-07-30 09:04:49
200
原创 BZOJ-3674:可持久化并查集（可持久化数据结构）
题目大意：中文题目，不多解释。n个集合 m个操作操作：1 a b 合并a,b所在集合2 k 回到第k次操作之后的状态(查询算作操作)3 a b 询问a,b是否属于同一集合，是则输出1否则输出0请注意本题采用强制在线,所给的a,b,k均经过加密,加密方法为x = x xor lastans,lastans的初始值为00<n,m<=2*10^5 解题思路：...
2018-07-27 21:24:55
194
转载 线段树题目总结
转载自大佬的线段树博客，留个纪念，开始准备重新刷线段树了= = 之前做了些线段树相关的题目，开学一段时间后，想着把它整理下，完成了大牛NotOnlySuccess的博文“完全版线段树”里的大部分题目，其博文地址Here，然后也加入了自己做过的一些题目。整理时，更新了之前的代码风格，不过旧的代码仍然保留着。 同样分成四类，不好归到前四类的都分到了其他。...
2018-07-27 17:02:46
631
原创 c++ pb_ds库之rope
今天打了牛客网的多校，有一道splay的题目发现别人用了300多的代码A了。。。震惊了，发现竟然有封装好的rope库...赶紧学习一下，以后splay的题目就直接用库写了。。。这种数据结构真的懒得学。。。 主要参考自：rope讲解 命名空间：using namespace __gnu_cxx; 头文件#include<ext/rope>...
2018-07-26 21:34:32
1184
原创 HDU - 5008:Boring String Problem (后缀数组之求不重复子串的第k大)
题目大意：给你一个S串，多次询问第k大的不重复子串。 解题思路：因为之前做过一个重复子串的第k大，所以这个题做的比较轻松。毕竟我感觉那个题目比这个难得多。首先用一个数组直接储存1 到 i这个位置所有的不重复子串和。查询第k大的时候直接先二分找到我们所要找的子串的起始下标。知道起始下标之后相当于我们就知道了这个串。这个时候因为题目有要求串相同的时候保证l r尽可能的...
2018-07-26 20:43:03
296
原创 HDU - 4416:Good Article Good sentence(后缀数组之求与其他串不相同字串)
题目大意：给你一个S串和m个T串，求S串中有多少子串不是另外m个T串的子串。 解题思路：对于所有的串，首先将他们连接。接下来我们就要统计对于0到 strlen(s) 这些位置，每个位置有多少与它重复的子串，统计出来之后拿串的总个数减去重复的即可。统计重复的就从前往后扫一遍 对于在S串和在T串的情况考虑。同时也要从后往前扫一遍。最后在把S串中自己重复的子串去掉即可。...
2018-07-26 09:23:12
282
原创 hdu多校第二场：6315 （线段树暴力）
题目大意：给你一串b数组，数组中的数为1到n，顺序可能被打乱。a数组初始化为0，有两种操作操作1：对于l r区间的a数组+1操作2：查询l r之间的 ai/bi 向下取整。 解题思路：这道题比赛卡了一下午，搞蒙了，很早的时候想出了维护最少需要升级经验的正解，但是和队友讨论感觉会T啊，因为有1这些数在，总感觉复杂度不对劲，后来想了一大堆其他做法也没做出来，然后又转回去写...
2018-07-25 21:07:23
209
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人