- 博客(202)
- 收藏
- 关注
RSS订阅
原创 各类数据结构（持续更新）
update : 2021/6/8文章目录基础数据结构并查集程序自动分析解释模板更多例题树状数组楼兰图腾解释模板更多例题线段树区间修改(加 & 乘)解释模板更多例题区间染色解释模板（懒标记法）模板（倒序插入维护区间染色）更多例题可持久化线段树(主席树)【模板】可持久化线段树1（可持久化数组）解释模板【模板】可持久化线段树2（主席树）解释模板更多例题基础数据结构并查集程序自动分析解释把相同的直接加入到一个集合里面，然后再之后判断他们是否真正相同. 注意离散化。模板#include<
2021-06-08 11:00:00
316
原创 各类动态规划（持续更新）
有误地方还请指明。比较懒，有的地方简略或者笔误。动态规划区间DP石子合并解释状态表示 dp(i,j)表示合并 i ~ j 所花费的最小价值目标状态 dp(1,n)初始化 dp(i,i) 为0转移方程 dp(i,j) dp(i,j) = min(dp(i,j),dp(i,k)+dp(k+1,j)) dp(i,j) += sum(i,j) 表示当前状态可以以k为分界点进行两堆的合并。而dp(i,k) 也可以由更小的区间进行合并.模板#include<bits/stdc++.h&
2021-03-24 18:36:18
418
原创 阿里云服务器centos8配置mysql数据库
阿里云服务器Centos8安装Mysql文章目录阿里云服务器Centos8安装Mysql第一步第二步第三步第四步第五步第六步第七步参考第一步使用最新的包管理器安装MySQL用dnf 命令 下载 mysqlsudo dnf install @mysql如果出现如下错误按照这篇博客修改完美解决CentOS8 yum安装AppStream报错，更新yum后无法makecache的问题 - 白_胖_子 - 博客园 (cnblogs.com)之后重新执行上述命令就会出现成功结果第二步设置开机
2022-02-22 16:49:37
1035
原创 Java并发编程
Java并发编程文章目录Java并发编程并发编程的要素线程的五大状态悲观锁和乐观锁synchronized作用原理使用缺点Thread 方法构造方法常用方法静态方法线程实现的方法实现Runnable接口继承Thread类通过 Callable 和 Future 创建线程创建线程的三种方式的对比线程之间的协作wait/notify/notifyAll举个例子sleep/yield/join举个例子多线程的使用线程池详解使用ExecutorService常用方法ScheduledExecutorService
2022-02-22 16:45:02
439
原创 Java网络编程基础
网络编程基础文章目录网络编程基础Socket 编程ServerSocket构造方法常用方法Socket构造方法常用方法InetAddress举个例子InetAddressSocket和ServerSocket服务端客户端多用户并发服务端客户端写的Demo参考Socket 编程套接字使用TCP提供了两台计算机之间的通信机制。 客户端程序创建一个套接字，并尝试连接服务器的套接字。当连接建立时，服务器会创建一个 Socket 对象。客户端和服务器现在可以通过对 Socket 对象的写入和读取来进行通信。
2022-02-22 16:38:42
162
原创 Socket不同局域网下进行连接【利用frp】
Socket不同局域网下进行连接【利用frp】文章目录Socket不同局域网下进行连接【利用frp】原理公网IP配置安全组配置frp下载对应的frp版本服务器上配置frp客户端上配置frpSocket代码服务端客户端结果参考原理云服务器和本地Socket连接拥有一台有公网IP的云服务器作为中转站，将局域网下的电脑将数据信息发送给中转的服务器，然后这个中转的服务器将收到的数据转给另外一台电脑，这样就可以实现两台电脑之间的互相通信。原因：我们可以实现在局域网下的通信而不能在不是同一局域网下的通信是因为
2022-01-27 20:43:56
3949
原创 阿里云服务器配置Java环境
阿里云服务器配置Java环境文章目录阿里云服务器配置Java环境准备下载Jdk传输下载的Jdk在服务器上安装Jdk解压jdk进入到/usr/bin目录新建jdk目录将解压的文件移到此目录下配置环境变量执行命令使修改立即生效测试使用参考准备操作系统：CentOS 8.0 64位。使用工具：Xshell：用于通过SSH协议远程连接服务器；Xftp：用于从本地向服务器上传文件；这两个版本都有教育版，是免费的。下载Jdk目前最流行的是jdk8，所以下载jdk8。注意下载对应的jdk，看自己系统的
2022-01-27 20:33:49
2658
1
原创 JAVA IO简单总结
JavaIO基本类简单总结文章目录JavaIO基本类简单总结IO流之间的关系IO的分类Java流操作的相关类或接口字节流简单介绍InputStreamByteArrayInputStream构造方法常用方法举个例子FileInputStream构造方法常用方法举个例子PipedInputStream构造方法常用方法举个例子ObjectInputStream构造方法常用方法举个例子DataInputStream构造方法常用方法举个例子BufferedInputStream构造方法常用方法举个例子Output
2022-01-15 23:49:12
251
原创 Minimum Inversion Number（HDU1394）（线段树求逆序对+思维）
题目地址配套地址维护逆序对，主要是第一次求完解之后，每次考虑将一个数放到最后数量的变化。变化为 (n - a(i)) - (a(i) - 1)a(i) >= 1。可以树状数组和归并排序#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<bits/stdc++.h>using namespace std;const int N = 2e5 + 10;const int mod =
2021-10-21 20:57:57
96
原创 敌兵布阵（HDU1166）（区间求和+单点修改）
题目地址配套地址写了一个区间修改的。[pos,pos]修改的。可以去掉add#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<bits/stdc++.h>using namespace std;const int N = 2e5 + 10;const int mod = 998244353;//#define int long longtypedef long long ll;#d
2021-10-20 23:57:53
87
原创 I Hate It （HDU1754）（区间最值+单点修改）
题目地址配套地址维护mx，编写push_up#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<bits/stdc++.h>using namespace std;const int N = 2e5 + 10;const int mod = 998244353;//#define int long longtypedef long long ll;#define endl '\n'
2021-10-20 22:36:30
77
原创 Just a Hook（HDU1689）（线段树区间赋值）
题目地址配套地址给维护区间值懒标记需有上传维护和下放#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10;const int mod = 998244353;//#define int long longtypedef long long ll;#define endl
2021-10-20 22:10:48
73
原创 CCF 202109-4（状态压缩 + 期望DP）
配套地址将每一个卡牌是否选取用状压 sss 表示。设 dp(s,j)dp(s,j)dp(s,j) 表示 到达 状态(111....11)(111....11)(111....11) 且 当前硬币数为 j 个还需要选的次数。那么if(s>>z)&1==1：if (s >> z) \& 1 == 1：if(s>>z)&1==1：dp(s,j)=dp(s,j+1)×p(z)dp(s,j) = dp(s,j+1) \times p(z)dp(
2021-10-02 23:33:37
667
原创 势能线段树模板题二
题目地址配套地址#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<bits/stdc++.h>using namespace std;const int N = 2e5 + 10;const int mod = 998244353;//#define int long longtypedef long long ll;int a[N];#define l(x) t[x].l#
2021-09-18 14:55:49
175
原创 Tickets （HDU1260）（线性DP）
题目地址配套地址设dp(i,0)dp(i,0)dp(i,0) 表示第 i 个人单独买票，dp(i,1)dp(i,1)dp(i,1) 表示第 i 个人与前面的那个人一起买票。故有转移方程dp(i,0)=min(dp(i−1,0),dp(i−1,1))+s(i)dp(i,0) = min(dp(i-1,0),dp(i-1,1)) + s(i)dp(i,0)=min(dp(i−1,0),dp(i−1,1))+s(i)dp(i,1)=min(dp(i−2,0),dp(i−2,1))+d(i−1)dp(i
2021-09-16 18:47:44
137
原创 免费馅饼（HDU1176）(线性DP)
题目地址配套地址时间看成纵坐标，位置看成横坐标，然后就是类似数字金字塔。#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10;const int mod = 998244353;//#define int long longtypedef long long ll;int
2021-09-16 17:17:20
75
原创 Doing Homework（HDU1074）（状压DP）
题目地址配套地址设 dp(i)dp(i)dp(i) 表示当前状态为 i 时，得到的最小扣分。枚举最后的作业，来更新当前状态。注意题目给出的是升序，故枚举最后的作业是逆序，最后的作业字典序尽可能的大。#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<bits/stdc++.h>using namespace std;const int N = 16;const int mod = 99
2021-09-16 16:09:39
79
原创 P5144 蜈蚣 （线性DP）
题目地址配套地址设 dp(i,j)dp(i,j)dp(i,j) 表示前 iii 个点分成前 jjj 段 得到的最大值。转移方程dp(i,j)=dp(k−1,j−1)+xorkidp(i,j) = dp(k-1,j-1) + xor_{k}^{i}dp(i,j)=dp(k−1,j−1)+xorki枚举最后一段的起点，进行转移，注意长度为1单独处理#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<
2021-09-11 18:21:09
127
原创 Educational Codeforces Round 113 (Rated for Div. 2)
Educational Codeforces Round 113 (Rated for Div. 2)文章目录[Educational Codeforces Round 113 (Rated for Div. 2)](https://codeforces.ml/contest/1569)A. Balanced Substring解释代码B. Chess Tournament解释代码C. Jury Meeting解释代码D. Inconvenient Pairs解释代码A. Balanced Substr
2021-09-11 15:36:32
196
原创 Codeforces Round #742 (Div. 2)
Codeforces Round #742 (Div. 2)A. Domino Disaster解释输入输出代码int tt; cin>>tt;while(tt --) { int n; cin>>n; string s,ans = ""; cin>>s; for(int i=0;i<n;i++) { if(s[i] == 'L' || s[i] == 'R') ans += s[i]; else
2021-09-11 14:36:33
128
原创 2021牛客暑期多校训练营9
2021牛客暑期多校训练营9文章目录2021牛客暑期多校训练营9E: Eyjafjalla解释代码H: Happy Number解释代码E: Eyjafjalla解释将问题转换成，求一个节点的最远的祖先节点ppp满足w(p)<=rw(p) <= rw(p)<=r，再求以p为子树的所有节点sss的w(s)>=lw(s) >= lw(s)>=l的个数。求一个节点的最远的祖先节点ppp满足w(p)<=rw(p) <= rw(p)<=r，这个可以用树
2021-09-05 21:23:40
99
原创 2021牛客暑期多校训练营8
2021牛客暑期多校训练营8文章目录2021牛客暑期多校训练营8A: Ares, Toilet Ares解释代码D: OR解释代码E: Rise of Shadows解释代码K: Yet Another Problem About Pi解释代码F: Robots解释代码J: Tree解释代码A: Ares, Toilet Ares解释n,m,k,l。基本没什么用，现在已经过了a题，还剩下一题，每次去厕所得到的代码都有yz\frac{y}{z}zy的失败率，求过题的期望。注意坑点,当某次长度为0，
2021-09-04 10:58:16
160
原创 2021牛客暑期多校训练营7
2021牛客暑期多校训练营7文章目录2021牛客暑期多校训练营7F:xay_loves_trees解释代码H:xay_loves_count解释代码I:xay_loves_or解释代码F:xay_loves_trees解释思考对于第一棵树，当dfs遍历时以u为最深节点，判断它最多能往回走多高（h + 1），那么此时形成的连续链大小为 depth - h。对于第二棵树，处理好dfs序，一棵树父亲节点的dfs序区间一定包含子树。对于第一棵树，dfs遍历，当处理到u节点时，先询问它儿子节点的最大值，存
2021-09-01 22:51:08
133
原创 Deltix Round, Summer 2021 (Div. 1 + Div. 2)
Deltix Round, Summer 2021 (Div. 1 + Div. 2)地址文章目录Deltix Round, Summer 2021 (Div. 1 + Div. 2)A解释：代码B解释代码C解释D解释代码E解释代码A解释：令a < b , 操作一步可以构造 (−x,x)(-x,x)(−x,x) 再次操作可以使得使得a和b补全a和b的2x差值，当x为奇数，无解。特判，当x为0且a=0，则操作0步，当x为0且a != 0,操作一步。综上，令 x = b - a.x %
2021-09-01 22:12:33
105
原创 2021牛客暑期多校训练营6
2021牛客暑期多校训练营6文章目录2021牛客暑期多校训练营6C:Delete_Edges解释代码F:Hamburger_Steak解释代码H:Hopping_Rabbit解释代码I:Intervals_on_the_Ring解释代码J:Defend_Your_Country解释代码C:Delete_Edges解释结论题。题目转换为从n个点中任意选择三个点，使得三个点不会重复出现的方案数。输出 (x+y+z)%n==0,1<=x<y<z<=n(x + y + z) \%
2021-08-17 00:39:23
92
原创 2021牛客暑期多校训练营5
2021牛客暑期多校训练营5文章目录2021牛客暑期多校训练营5B:Boxes解释代码D:Double_Strings解释代码H:Holding_Two解释代码J:Jewels解释代码K:King_of_Range解释代码B:Boxes解释贪心可知，最多使用一次C，多次使用效果一样，早使用不比晚使用差。优先开权值小的更优。对于每一个箱子的期望，只有它后面是全黑或者全白时，才没有贡献。所以答案为 ∑i=1nwi×(1−12n−i)\sum_{i=1}^{n}w_i\times (1-\frac{1
2021-08-13 16:18:05
82
原创 2021牛客暑期多校训练营4
2021牛客暑期多校训练营4文章目录2021牛客暑期多校训练营4B: [Sample Game](https://ac.nowcoder.com/acm/contest/11255/B)解释代码C: [LCS](https://ac.nowcoder.com/acm/contest/11255/C)解释代码E: [Tree Xor](https://ac.nowcoder.com/acm/contest/11255/E)解释代码F: [Just a joke](https://ac.nowcoder.co
2021-08-11 19:43:22
81
原创 2021牛客暑期多校训练营3
2021牛客暑期多校训练营3文章目录2021牛客暑期多校训练营3B: [Black and white](https://ac.nowcoder.com/acm/contest/11254/B)解释代码C:[Minimum grid](https://ac.nowcoder.com/acm/contest/11254/C)解释代码E: [Math](https://ac.nowcoder.com/acm/contest/11254/E)解释代码F:[24dian](https://ac.nowcoder.
2021-08-07 23:35:08
103
原创 2021牛客暑期多校训练营2
2021牛客暑期多校训练营2文章目录2021牛客暑期多校训练营2C:Draw_Grids解释代码D:Er_Ba_Game解释代码F:Girlfriend解释代码G:League_of_Legends*解释代码I:Penguins解释代码K:Stack解释代码C:Draw_Grids解释不能形成环，只能形成树，所以有nm个点，那就能连nm-1边。代码int n,m; cin>>n>>m;int ans = n*m - 1; cout<<(ans % 2 ?
2021-08-07 23:31:11
136
原创 HDU多校2021第一场
HDU暑假多校第一场文章目录HDU暑假多校第一场[1001]Mod,_Or_and_Everything解释代码[1005]Minimum_spanning_tree解释代码[1006]Xorsum解释代码[1007]Pass!解释代码[1008]Maximal_submatrix解释代码[1009]KD-Graph解释代码[1010]zoto解释代码[1001]Mod,_Or_and_Everything解释打表可以看出规律。性质设m=(n-1)/2(n mod i ) <= m，且
2021-07-31 00:19:29
434
原创 Codeforces Round #734 (Div. 3)
Codeforces Round #734 (Div. 3)文章目录A. Polycarp and Coins解释代码B1. Wonderful Coloring - 1解释代码B2. Wonderful Coloring - 2解释代码C. Interesting Story解释代码D1. Domino (easy version)解释代码D2. Domino (hard version)解释代码E. Fixed Points解释代码F. Equidistant Vertices解释代码A. Poly
2021-07-25 18:33:48
136
原创 2021牛客暑期多校训练营1 部分题解
2021牛客暑期多校训练营1文章目录2021牛客暑期多校训练营1A: Alice and Bob解释代码B: Ball Dropping解释代码D: Determine the Photo Position解释代码F: Find 3-friendly Integers解释代码G: Game of Swapping Numbers解释代码H: Hash Function解释代码I: Increasing Subsequence*解释代码K: Knowledge Test about Match解释代码A:
2021-07-24 23:12:30
221
原创 谜一样的牛（acwing）（树状数组+二分）
题目地址配套地址/* 从后往前，每个位置(i)的值应该为， 将i后面所有确定好的数插入到数列中，第(A[i]+1)个空位对应的下标。 可以用二分加树状数组。 树状数组处理上述语句的前半段，二分处理后半段，去快速查找那个位置。*/#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int c[N],n,a[N],ans[N];bool vis[N];#define
2021-06-30 22:07:30
75
原创 一个简单的整数问题2（acwing）（数状数组）
题目地址配套地址区间修改还是以维护差分。区间查询就需要再推一个公式化简。假设维护的差分序列为b[].查询一段区间[l,r]，可以用连段的差值相减，即求一段区间[l,r] = [1,r] - [1,l-1].有[1,p]的值为 ∑i=1p∑j=1ib[j]\sum_{i=1}^{p}\sum_{j=1}^{i}b[j]∑i=1p∑j=1ib[j] , p 为l-1或者r再次化简，得到∑i=1p(p−i+1)b[i]\sum_{i=1}^{p}(p-i+1)b[i]∑i=1p(p−i+1)
2021-06-30 20:56:52
109
原创 一个简单的整数问题（acwing）（树状数组/线段树）
题目地址配套地址/* 区间修改，单点查询。 假设还是维护的是原数组，区间修改时，需要对每一个数进行需改，需要枚举。 那可以将区间修改变成点修改降低时间复杂度，即维护差分。 单点查询，因为维护的是差分序列，则需要将该点及前面点的总和。*/#include<bits/stdc++.h>using namespace std;#define int long longconst int N = 1e5 + 10;int n,m;int a[N],
2021-06-30 12:08:10
87
原创 游走（luogu）（期望）
题目地址配套地址答案为sumcnt\frac{sum}{cnt}cntsum sum 为所有路径的总长度，cnt为所有路径的个数。题中信息可以得到，改图形是一个DAG，可以设f(i)表示以i为起点的所有路径的总长度之和，g(i)表示以i为起点的所有路径的个数。那么f(i)=∑j∈s(f(j)+g(j))f(i) = \sum_{j\in{s}}(f(j) + g(j))f(i)=∑j∈s(f(j)+g(j)) ，首先边长为1，对于f(j)中的所有路径，当变成由i为起点时，每个路径都要加1的长
2021-06-29 15:26:22
191
原创 单选错位（luogu）（期望）
题目地址配套地址尽管刚开始是完全正确，但是错位了，正确的概率对每题还是一样的。决定概率变化的只有题目的数量不同。每次比较前面一个和后面一个选项个数，每次以大的作为概率计算。#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<bits/stdc++.h>using namespace std;const int N = 1e7 + 10;const int mod = 1e9 + 7;
2021-06-29 11:43:15
158
原创 绿豆蛙的归宿（luogu）(期望DP)
题目地址配套地址逆向：设E(i) 表示到i点到n点还需要的期望步数仅考虑 x -> y这一条边，边权为w。设 y 点所连的各个点的边权为l1，l2，...，lnl_1，l_2，... ，l_nl1，l2，...，ln，概率为p1，p2，...，pnp_1，p_2，...，p_np1，p2，...，pn那么 E(y) = p1l1+p2l2+...+pnlnp_1l_1 + p_2l_2 + ... + p_nl_np1l1+p2l2+...+pnlnE(x) =
2021-06-29 10:58:59
186
1
原创 Stone Games （nowcoder）(主席树)
题目地址配套地址#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<bits/stdc++.h>//#define int long longusing namespace std;typedef pair<int,int> pii;typedef long long ll;const int INF = 0x3f3f3f3f;const double eps = 1e-
2021-06-26 21:33:53
121
原创 关押罪犯（acwing）（扩展域并查集 / 二分图）
题目地址配套地址/* 扩展域并查集 编号i表示与i同一间监狱，i+n表示与i不同监狱。 先按c从大到小排序，如果到了某次，当前两个人不得不在同一监狱，则输出。 #include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int fa[N];struct edge{ int a,b,c; bool operator < (const edge&T)
2021-06-26 15:06:57
155
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人