- 博客(112)
- 收藏
- 关注
RSS订阅原创 图计算ss
比较好的C++项目在编写多线程代码时，可以参考一下。https://github.com/thu-pacman/GridGraphhttps://github.com/thu-pacman/GeminiGraph
2022-03-28 16:32:38
330
原创 【无标题】
性能：通过简单的增加机器就可以达到与机器数量匹配的性能（可拓展性）容错：一台机器是可靠的，但是在一个大规模的分布式系统中，一些在单个机器上很少出现的问题就会被放大。会将一些几乎很少发生的问题变成一个常见的问题。（可用性问题）...
2022-02-22 15:47:37
99
原创 6.824 Lab 记录
raft 论文（背诵全文）Lab 2Aleader election 和 voted 不考虑日志的逻辑。应实现如下内容：初始化集群，以及两个定时器：HeartBeatTimer（stable），ElectionTimer（random）.开启ticker协程，select 监听计时器事件。headtbeat：leader 定时广播 AppendEntriesReq，维护集群状态，并根据Resp.Term 判断自己是否因掉线过导致版本落后，从而即使更新当前节点state。节点收到AppendEnt
2021-11-08 16:22:41
569
2
原创 有效解决“你的账户已被停用，清向系统管理员咨询”问题
产生这个问题是因为当前用户被管理员所停用，不能正常登陆。那么最直接的方法就是在创建一个用户跟着以下步骤操作保证顺利解决问题：重启电脑之前按住shift依次点击：疑难解答—高级选项—启动设置—，然后电脑再次重启后，选择启用带命令提示符的安全模式（F7）最后输入以下命令即可添加用户net user xxx 123 /add (xxx为新增用户名，123为密码)net localgroup administrators xxx /add (xxx 同上)最后切换用户重启即可。ps：如
2021-06-16 22:55:42
2865
1
原创 第十一届山东省大学生程序设计竞赛 K Piggy Calculator 笛卡尔树+倍增
link题意：定义运算符号x(i), A x(i) B =（A+B）*i，i越大优先级越大，其次从左往右。，给定一个只有该符号的式子，q次询问求区间表达式的值。题解：对符号建笛卡尔树，区间操作转化为在树上跑链的操作（要先维护前驱结点），存储一些信息后倍增就可以了。#include<bits/stdc++.h>#define mp make_pair#define pb push_back#define SZ(x) (int)(x.size())#define all(x) x.
2021-05-11 16:09:11
324
1
原创 树上背包正确姿势
三个限制：sz[u]i-j<=sz[u]-sz[v]j<=sz[v]void dfs(int u,int fa) { sz[u]=dp[u][1]=1; for(int v:G[u]) if(v!=fa) { dfs(v,u); sz[u]+=sz[v]; for(int i=sz[u];i>=1;i--) { for(int j=max(1,i-sz[u]+sz[v]),rk=min(sz[v
2021-05-09 18:03:54
69
原创 The 18th Zhejiang Provincial Collegiate Programming Contest F D B
linkF. Fair Distribution看到数据范围应该想到与根号有关，那么分两种情况讨论：①：机器人个数<sqrt(x)②：机器人个数>sqrt(x)---->机器人平均能源数<sqrt(x)分别枚举即可。#include<bits/stdc++.h>#define mp make_pair#define pb push_back#define SZ(x) (int)(x.size())#define all(x) x.begin(),x
2021-05-09 00:55:35
530
原创 cf 1485 F Copy or Prefix Sum 奇怪的dp
link题意有一数组BBB，求满足以下条件的数组AAA的个数B[i]=A[i]，ORB[i]=∑j=1iA[j]B[i]=A[i] ，OR \\B[i]=\sum_{j=1}^{i}A [j]B[i]=A[i]，ORB[i]=j=1∑iA[j]题解dp[i][j]dp[i][j]dp[i][j]表示∑k=1iA[k]=j\sum_{k=1}^{i}A[k]=j∑k=1iA[k]=j的方案数，那么显然有n2log2nn^2\log_{2}^{n}n2log2n的转移方程dp[i][j]
2021-02-14 21:59:54
257
1
原创 887 鸡蛋掉落
dfs就假如当前有N层楼要确认，K个鸡蛋。那么枚举当前鸡蛋放在x后变成了两个子问题dfs(x-1,k-1),dfs(n-x,k)，dfs就好。复杂度为O(nkn)状态数枚举次数考虑到dp[N][K]随着N递增而递增，所以固定k对所有x画图后发现 dfs(x-1,k-1)递增，dfs(n-x,k) 递减。那么要想使他俩的最大值最小直接二分就可以了（找到最后一个L使得dfs(L-1，K-1)《=dfs(N-L,K) 和最小的R(前面的式子返回来)）。复杂度O(NK*log（n）)class Soluti
2021-01-10 14:24:29
96
2
原创 leetcode 312. 戳气球
挺明显的区间dp状态dp[i][j]为开区间（l,r）的最大值。这种状态能保证区间剩下来的数字是固定的为i,j想到这个状态就不难写了。class Solution { int real(int x,vector<int>& nums) { x--; if(x>=0&&x<nums.size()) return nums[x]; return 1; }public: int maxC
2021-01-08 00:19:41
77
原创 高效遍历一个小于1e6的数的所有质因子的方法
另min_prime[x]为x的最小质因子遍历方法为for(x;x>1;x/=min_prime[x]) {…}
2021-01-07 23:58:13
169
1
原创 二叉树三序遍历非递归
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */class Solution {public: /** * * @param root TreeNode类 the root of binary tree * @return int整型vector<vector<>> */
2021-01-07 01:58:37
111
原创 正则表达式匹配
暴力dfs就直接讨论当前怎么匹配就可以了极限复杂度目测2^nclass Solution {public: bool match(char* str, char* pattern) { int n=strlen(str),m=strlen(pattern); return dfs(str,pattern,0,n-1,0,m-1); } bool dfs(char* str,char* pattern,int i,int n,int j,i
2021-01-07 00:53:46
139
原创 字典序的第K小数字
给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。1 ≤ k ≤ n ≤ 109。n=10时，字典序：1，10，2，3，4，5，6.。。可以把这n个数字看成字典树，那么每一个前缀都代表一个数字，其中每个节点有10个儿子，0~9.那么字典树的先序遍历的第k个就是答案。所以得到了一个O(k)的做法。这类问题通常通过逐位判断答案的前缀来求解。那么考虑当前已经求得答案的一个前缀为ans以及还需要遍历的节点个数k，那么对于要选择那个子节点其实就是从0~9找到第一个前缀字数和>=k的位置
2021-01-05 13:34:42
376
原创 寻找两个有序数组的中位数 O(log(m+n))AND O(log(min(n,m)))
O(log(m+n)) :不断排除某个数组的前缀而相应的更改K，那么当K=1或其中一个数组长度为0时结束。class Solution {public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n=nums1.size(),m=nums2.size(); return 1.*(getk(nums1,0,n-1,n
2021-01-04 17:22:15
238
原创 数据流的中位数
用一个大根堆和一个小根堆动态维护，并且①大根堆最大数字小于小根堆最小②小根堆大小+1>=大根堆的大小>=小根堆的大小那么当添加一个数字的时候只需考虑，如何改变队列而不影响上面两个条件，有两种情况：①当前两个队列大小相等，那么要将小根堆中的数字和当前 数字里最小的插入大根堆。②不等，则相反。class MedianFinder { priority_queue<int>p; priority_queue<int,vector<int>,grea
2021-01-04 16:09:00
56
原创 带有随机指针的链表的复制
/*// Definition for a Node.class Node {public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; }};*/class Solution {public: Node* copyRandomList(Node*
2021-01-03 00:33:38
103
原创 cf 1450 F The Struggling Contestant
link题意：给一长度为n的数组A，求以排列p满足A[pi],A[pi-1]不同，定义每一个排列的权值为abs（pi-pi-1） >1 的i的个数。输出满足条件排列的最小权值。无解输出-1思路：如果不考虑权值的话就是一个插数的过程，那么有解的情况就是出现次数最多的数要小于（n+1）/2。考虑怎么构造权值最小的排列。首先对于ai==ai-1的这些位置是一定要分开的。记为k,那么此时最小可能的答案就为k（翻转，重拍每个排列后每个端点的代价都为1），考虑什么情况下这个k会变大，无非就是某个数作为端点的
2020-12-10 12:42:44
273
原创 codeforces 1442 D Sum 可撤销01背包QwQ
link题意：有n个单调不减数组，求从这n个数组中选择k个数的最大和，（只能拿数组的一个前缀）n,k<3000思路：因为数组是单调的，所以能得到一个结论就是我们最多只会拿不全一个数组（当有两个数组都拿一部分时，那么肯定可以通过减少某个数组拿的数字去拿另一个数组来增大这个和）。所以我们就可以通过枚举哪个数组不全选，然后对剩下的数组跑01背包，在枚举当前数组选几个来更新答案，但可惜这是O(nnk)的，有一个巧妙的优化就是，我们分治整个区间，对于一个l,r维护不选这个区间内的数字的dp值。那么当
2020-11-09 20:44:16
456
原创 Educational Codeforces Round 97 (Rated for Div. 2) F ,G
linkF： Emotional Fishermen题意：n个数，求这n个数满足下面要求的排列数量max[i-1]2<=a[i] OR max[i-1]>=2a[i]思路：对于每一个前缀来说，出现的数字个数最多为 num[max[i]]+1,其中num表示max[i]>=a[j]的j的数量。所以有dp[i]表示最大值为ai时的方案数转移方程为：dp[i]=sigma(dp[j]A(n-num[j]-2,num[i]-num[j]-1))其实就是在更新前缀最大值时，考虑他所
2020-10-30 19:03:22
221
原创 D. Bouncing Boomerangs 模拟
link题意：n*n的矩阵，上面放着障碍物。现在有一个人分别在第i列投掷一个飞镖，沿着投掷方向前进，在遇到障碍物时会向右转弯，直到飞出矩阵。现在给你在每列投掷飞镖遇到的障碍数Ai<=3。还原障碍物所在位置，要求每行每列障碍物不能超过2个。思路：由于在考虑如何放当前列的障碍物时要考虑当前咧后面的列的障碍物是怎样放的，所以要从后往前枚举每一列来放障碍物，ai=1时在当前列随意放一个就行ai=2时那么只能放在i之后的j使得aj==1并且每个j只能用一次ai=3时有两种情况：1.放在之后的aj=
2020-10-23 10:53:50
156
原创 Codforces 1248 G Lucky Numbers (多重背包)
题意：把n划分成k个数，求最大价值，每个数的价值 由Fi和该数的第i位上是否为3的倍数决定。给定k<1e6,Fi i<6。Q次询问n思路：按位考虑的k个数的贡献，那么可以将第i位看成容量为3k的背包，就是一个多重背包，可以用二进制优化，但是这样直接分有问题。因为只能在3的倍数之间转移。那只需要先直接求出每个数的价值，然后背包容量就变成了3（k-1）接着转移就可以了。#include<bits/stdc++.h>using namespace std;typedef long
2020-10-21 19:40:21
158
原创 牛客练习赛71 C 数学考试
link题意：求长度为n的排列有多少个 要求满足 m个条件 ：pi 表示前pi个数不是1~pi的全排列m<n<=2000思路：1️⃣：考虑用总方案数减去不符合条件的方案数：即对于位置 x 为，x! - （不符合条件）。设F[i]为前i-1个条件满足，第i个条件不满足的方案数，并且我们增加一项p[m+1]=n，那么F[m+1]即为答案转移方程：F[i]=sigma(F[j]*(j-i)!)(1<=j<i)第一次遇到这样的dp状态-_- 很奇妙。。 它是通过枚举最后一个不满足
2020-10-10 17:18:25
168
原创 CodeForces 1417 F Graph and Queries 无向图连通块问题转化为树上问题 重构树
link题意：给一无向连通图，每个点有一个权值，q次操作 每次操作有两种1,v 寻找v所在连通块内权值最大的点，并输出这个权值并且把改点权值变成02.x 删掉第i条边思路： 查询图上连通块内最大值和修改我们只学过在一棵树上利用dfs序，然后线段树维护。那么考虑如何将此题转化成一棵树。我们把删边考虑为倒着加边。在加边过程中利用并查集维护连通块。并且将每一时刻每一个点的连通块转化为一颗’子树’，这样在查询的时候就可以通过查询子树点权最大值来得到结果。如何将各个时刻的连通块转化为一颗树？只需要在加
2020-10-03 22:32:02
856
原创 Grakn Forces 2020 D E F
Dn个人,m个摄像坐落于二维平面上，x,y位置摄像能监视到的范围为(0 x, 0 y)每次移动可以选择将所有人x+1,或者将所有人y+1;问最少移动次数使得所有人都不在监视范围内；坐标<1e6考虑枚举操作x+1多少次，然后O1计算此时还需要操作y+1多少次来更新答案。mx[i][j]表示第i个人执行x+1 j次后还需要执行 y+1 的次数。那么所有人执行j次x+1后 还需执行y+1 的最少次数就为 max(mx[1~n][j]) 预处理即可。EMST 好题题意：有m个由1~n中的若干不同
2020-10-01 10:16:25
1689
2
原创 codeforces 1392 F Omkar and Landslide
link题意：有一长度为n的单调递增序列 。现在这个序列很不稳定，每秒钟都会发生如下变化：如果满足a[i]+1<a[i+1] 那么a[i]++,a[i+1]–。求最终序列。由于保证单调递增，所以说，只要有一个位置发生+1的变化，那么这个影响会一直传递到1。直到a[1]=a[2]，此时，若在发生变化会使a[2]++。那么可以发现最后的序列为一个公差为1的等差数列，但是其中允许有一对相同的数字。那么求和 直接模拟即可最后的a[i]=i-1+(s-n*(n-1)/2)/n+(s-n*(n-1)/
2020-08-19 16:58:16
169
原创 HDU 6774
link丨T丨<=20， 丨S丨<=1e5最长公共子序列加速。O(m^2)dp[i][j]为T串前i个当前最长公共子序列为j时，在S串中最短的位置#include<bits/stdc++.h>#define pb push_back#define SZ(x) ((int)(x).size())#define all(x) (x).begin(),(x).end()using namespace std;typedef long long ll;typedef ve
2020-07-24 11:46:29
177
原创 hihocoder 后缀自动机
link重复旋律5求不同子串个数，SAM后统计所有节点的mx-mi+1即可#include <bits/stdc++.h>using namespace std;typedef long long ll;const int SZ = 26;const int maxn = 1e6+5;namespace SAM{ struct SamNode{int trans[SZ],slink,mi,mx;}sam[maxn<<1]; int tot; char s[maxn
2020-07-06 13:14:11
154
原创 后缀自动机
endpos相同的所有子串都会走到同一点。增量法构造，每新增一个字符，相当于多i+1个后缀，考虑这些后缀的endpos是否都为z(最长那个)。我们沿着slink_path（u）一直走，出现sam[u].trans[c]!=-1时说明发生endpos集合变化（即此后缀在之前出现过）这里又分两种情况1）对新增的串对状态x的endpos无影响2）产生影响，例：abcxabcxbc+x时 abcx 的endpos 由abcx,bcx,cx,x变为abcx+bcx的endpos。所以需要拆点。（待补）
2020-07-05 21:23:21
181
原创 Acesrc and Travel 换根
link换根DP，建议用以下写法，通过存储前缀极值，从而不需要复杂的分类讨论#include<bits/stdc++.h>#define fi first#define se second#define pb push_back#define SZ(x) ((int)(x).size())#define all(x) (x).begin(),(x).end()#define rep(i,a,b) for(ll i=(a);i<=(b);i++)#define per(i
2020-06-30 15:22:13
127
原创 Victor and String 回文树拓展
link前后端同时插入，增加前缀fail指针，发现对于每个节点，前缀fail和后缀fail相同。那么分情况直接更新就好了。并且在前面插入字符时不会影响原树的fail。因为每个节点的fail长度比他本身小。并且要注意，当插入一个节点时，如果它新生产的回文串的长度等于此时总串的长度，要同时更新L_last,R_last#include<bits/stdc++.h>using namespace std;typedef long long ll;///len表示当前节点对应回文子串长度
2020-06-25 12:02:33
149
原创 双倍回文
link容易发现满足要求的回文串的长度一定是 4的倍数，并且有长度为其一半的后缀回文。建立fail树后记忆化搜索即可#include<bits/stdc++.h>#define pb push_backusing namespace std;typedef long long ll;;const int SZ = 26;///字符集const int maxn = 5e5 + 6;struct PAM { struct PamNode{int fail,trans[S
2020-06-24 19:53:08
181
原创 Palindrome Mouse 回文自动机
link考虑每个点对答案贡献为除他本身外，所在fail链上节点个数和回文树上该节点祖先节点个数。这样写会有两个问题1.重复节点2.时间复杂度考虑递推，该节点的贡献为其父亲节点贡献+它所延伸出fail链的个数+1#include<bits/stdc++.h>using namespace std;typedef long long ll;;const int SZ = 26;///字符集const int maxn = 1e5 + 6;struct PAM { s
2020-06-24 17:42:18
107
原创 回文自动机
目录Palindrome auto machineQ1 节点会不会很多？Q2 怎么建树？Q3 建树后可以求什么？Q4 怎么求？模板例题：P5496Palindrome auto machine又称回文树，顾名思义，对于一个字符串的回文树来说，每个节点表示一个回文串。例：abbabba对应节点有：a,b,bb,bab,abba,bbabb用于统计某字符串有多少个回文子串之类问题。Q1 节点会不会很多？考虑每添加一个字符对回文树节点个数的影响如图所示，当添加c后，考虑以c为结尾最长的回文串A，
2020-06-23 20:31:37
1034
原创 Code forces 1367 Flying Sort
找x,x+1,x+2,…x+k这样的子序列，其中首尾不必全部 出现，中间必须全部出现分三种情况dp#include<bits/stdc++.h>#define ls rt<<1#define rs rt<<1|1#define pb push_back#define all(x) (x).begin(),(x).end()using namespace std;typedef long long ll;typedef vector<int>
2020-06-22 21:02:29
171
原创 楼教主 男人八题之一 Poj 1741 Tree
link树上距离小于等于k点对对数点分治模板首先考虑经过某一点zx的对数，那么我们可以通过dfs处理出所有点到zx的距离后求dis [a]+dis[b]<=k的个数(排序后双指针)，但是这样算的时候还有可能两点没过zx，所以要容斥一下(减去所有以儿子节点为根的数量即为不经过zx的数量)。如果随便枚举zx的话，最坏复杂度会达到O(n^2)所以我们让每次枚举的点为重心，复杂度为O(nlog n) （每次都会减少大于s/2个节点）#include<bits/stdc++.h>#de
2020-06-17 13:06:08
143
2
原创 Pangu and Stones UVALive - 8177 区间dp
link石子合并变形，每次只能将[ L ，R ]堆石子合并为一堆.在普通石子合并dp [i] [j]上 添加一维 dp[i][j][k] 表示i~j区间还剩k大堆的最小花费那么dp[i][j][1]=min dp[i][j][z] l<=z<=r而当k>1时转移的意义相当于不断划分石子,有转移方程dp[i][j][k]=min dp[i][z][1]+dp[z+1][j][k-1]#include<bits/stdc++.h>#define ls rt<&
2020-06-16 19:29:58
113
原创 CodeForces Round #549 U2
考虑每一个点可得 bx+c>=y-xx有左侧直线在点{x,y-xx}上方，维护上凸壳即可#include<bits/stdc++.h>#define ls rt<<1#define rs rt<<1|1#define fi first#define se second#define pb push_backusing namespace std;typedef long long ll;typedef vector<int> VI;
2020-06-16 16:59:55
103
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人