- 博客(112)
- 收藏
- 关注
RSS订阅原创 2019 ICPC 南昌 K. Tree（dsu on tree + 动态开点线段树）
传送门dsu on tree 模板题，就是统计贡献时需要n颗线段树，好在能用到点的不是很多，所以动态开点空间能接受。ps：两点之间距离小于等于k#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=200010;int n,m,k,a[N],idx;struct node{ int ls,rs; ll sum;}tr[N*50];struct seg{ int
2021-03-22 20:29:53
226
原创 2021年度训练联盟热身训练赛第一场
A Weird Flecks, But OK最小圆覆盖模板题，大部分都是用的板子吧，来个三分套三分吧。（跑得比较慢）#include <bits/stdc++.h>using namespace std;typedef long long ll;const int mod=1e9+7;const double eps=1e-6;const int N = 5010, M = 1e6+10;int n,k;double x[N],y[N],z[N];double check3
2021-03-07 22:13:52
1665
1
原创 牛客练习赛75
A 费马小定理：p为质数时，ap−1≡1a^{p-1}≡1ap−1≡1(mod p)。#include <bits/stdc++.h>using namespace std;typedef long long ll;const int mod=1e9+7;const int N = 1e6+9, M = 4e5+10;int a,b,m,n;ll ksm(ll a,ll b){ ll res=1; while(b){ if(b&1) res
2021-03-02 21:56:03
235
原创 牛客练习赛77
[传送门](https://ac.nowcoder.com/acm/contest/11160#question)小G的约数思路：每一个小于等于$\sqrt{n}$的i都会对
2021-02-28 17:12:33
147
原创 AtCoder Beginner Contest 190
传送门D n的奇因子个数的二倍。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod=10+7; typedef pair<int,int> pii;const double eps=1e-6;const int inf=0x3f3f3f3f;#define fi first#define se secondconst int N=200010;ll n;
2021-02-01 17:27:54
142
原创 P2762 太空飞行计划问题（最大权闭合子图）
对每一个实验从源点连一条权值为收益的边，每一个仪器向汇点连一条权值为花费的边，实验到仪器连一条边权为inf的边（确保这条边不会被割掉），最终答案就是所有实验的收益和减最小割。在最后一次跑dinic时没有找到一条从源点到汇点的增广路就是说整个图已经被割成两部分了，这时与源点相连的这个图就是我们需要的实验和仪器了，此时与源点相连的实验的边的容量和就是最大收益。#include<bits/stdc++.h>using namespace std;typedef long long ll;c..
2021-01-25 16:08:30
145
原创 CF 1446 C Xor Tree （分治）
可以对所有数建一个01字典树，然后可以发现每个点找最小的异或值就是在字典树中离它最近的点（可以把整个二叉树都画出来会更好看一点），对于每一个非叶子结点它的两个子树中的点如果想成为连通图的话，只能是两个子节点中数量都不能超过两个，不然就是两个连通图了，所以保留两个中的最大值另一个删得只剩一个值就好。对所有的非叶子结点都做这样的操作后就是最优结果了，将空节点减掉时间复杂度就能接受了。可以发现每个节点的子树会表示一个数的范围，所以不用建字典树就可以。#include<bits/stdc++.h>..
2021-01-21 11:10:58
171
原创 CF 1470B Strange Definition （hash）
首先定义一种关系就叫相关吧（相邻与传统观念太冲突了），如果lcm(x,y)gcd(x,y)\frac{lcm(x,y)}{gcd(x,y)}gcd(x,y)lcm(x,y)是完全平方数那么x和y就是相关的。暂且定义 [x] 表示 x 是完全平方数化简一下可以得到x∗ygcd2\frac{x*y}{gcd^2}gcd2x∗y 所以如果 [xy] 那么x和y就相关。相关性具有传递性：如果[xyxyxy]且[yzyzyz]相关，那么[xy2zxy^2zxy2z],所以[xzxzxz]。所以d数组..
2021-01-17 13:06:46
182
原创 Codeforces Round #693 (Div. 3)
传送门E ：首先维护hi>=wi(小于也没问题），然后h作为第一关键字递增排序。然后遍历这个数组，维护一个最小的w的位置，还要保证该位置的h严格小于当前点的h，双指针扫一遍即可。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=1000100;typedef pair<int,int> pii;#define fi first#define se secon
2021-01-17 12:40:56
101
原创 CF 1473E Minimum Path
如果没有最大值和最小值就是最短路模板了，如果在跑图过程中同时维护最大值最小值就太麻烦了，可以对每一条边都当做最大值最小值去试一试，状态表示为dist[i][0/1][0/1]，第二维表示是否减过边权，第三维表示是否加过边权。这样就可以跑迪杰斯特拉了。也可理解为分层图最短路。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=1000010;int t;int n,m;ll di..
2021-01-17 12:17:48
205
原创 CF 1288D Minimax Problem（二分+状压）
最大化最小值很容易想到二分，但是怎么check是个问题，check（ans）是否成立时需要找到两个行使得每一位的最大值都大于等于ans，也就是说每一位至少存在一个数大于等于ans，可以观察到m<=8,所以可以状压，将每一行大于等于ans的位置1，小于的位置0.最后判断是否存在两行状态或之后二进制位都为1即可。#include<bits/stdc++.h> using namespace std;typedef long long ll;const int N=300010;i.
2021-01-15 14:05:58
228
1
原创 CF 1453D Checkpoints （期望+构造）
构造一个这样的游戏关卡使得玩家通过全部关卡的期望步数等于k。首先肯定是分块的，每个1以及后面的连续0是同一块。先计算一下每一种块的的期望：1 ： E = 12\frac{1}{2}21 * 1 + 12\frac{1}{2}21 * (1+E) (没通过返回1之后又是独立重复实验期望不变） 解得 e[1] = 2 ;10 ： E = 14\frac{1}{4}41 * 2 + 12\frac{1}{2}21 * (1+E) + 14\frac{1}{4}41 * (..
2021-01-13 15:13:18
194
原创 Acwing 218. 扑克牌 （期望dp）
很明显可以期望dp，状态表示为 f[a][b][c][d][x][y]（abcd表示四种花色牌的数量，x和y表示大小王，如果不记录大小王翻开后充当了那个花色太容易出错，所以用四种状态表示充当了那个花色，所以x和y取值0到4）需要注意的是牌的数量是可以大于A,B,C,D的。还有翻到大小王之后具体是充当哪个花色是由你自己决定的，和概率无关，既然要求最小的期望值就选择期望值最小的状态转移即可。#include<bits/stdc++.h>using namespace std;typedef.
2021-01-12 21:49:52
532
原创 Widget Factory（高斯消元）
题目链接已知m个含n个变元同余方程式，求是否有解。先将增广矩阵化为行阶梯型矩阵，如果系数矩阵的秩不等于增广矩阵矩阵的秩就是无解，如果相等但是秩比n小，就是有无数解，否则就是唯一解ps：比较系数矩阵和增广矩阵的秩时要比较m个方程组，不只是比较n个！#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include&
2021-01-11 17:08:24
138
原创 Codeforces Round #686 （E，F）
E 一直一颗基环树，问有多少种简单路径。先找到这个环，然后环上每个点为根连接的环外的点会构成一个树，这棵树内两两构成一条路径，与每个树外节点都构成两条路径（分别走环的两端）。#include<iostream>#include<cstring>#include<cstdio> using namespace std;typedef long long ll;const int N=200010; int n,m,t;int h[N],e[N<&
2020-11-27 17:53:52
979
5
原创 AtCoder Beginner Contest 184
C - Super Ryuma每个点可以到的区域可以分为两种情况：方式1.以起点为原点直线 y=x 和 直线 y=-x 上的点；方式2.与起点曼哈顿距离小于等于3的点，任意两点之间至多需要移动三次，过起点做斜率为1的直线，以重点做斜率为-1的直线（交换一下也可以），一定有交点，如果交点坐标都为整数，则两次就可以，否则就要三次（偏移一个单位即可移动两次）。#include<iostream>#include<cstdio>#include<cstring>
2020-11-23 21:51:40
202
原创 P3380 【模板】二逼平衡树（树套树）
排名，修改，前驱和后继通过平衡树都很好实现，查询排名为k的值不是很好实现，因为这个区间可能在线段树的多个区间内，就需要在多棵平衡树中找，合并也不太现实，换个思路：二分值，找到排名小于k的最大值，然后在对它求一个后继就好了。#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cstdlib>using namespace std;
2020-11-17 19:33:08
771
原创 Tree Requests [CodeForces - 570D]
传送门dsu on tree 的经典题能组成回文串的前提是至多有一种字符是奇数个，统计同一深度下各种字符个数即可。启发式合并即可优雅的暴力统计。ps：一直wa41，也找不到错误，看了样例才发现输入中多了一个空行，我是单个字符读入的。又发现一个新的wa题方法。。。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>
2020-11-11 17:32:05
145
原创 2020 ccpc长春 F Strange Memory （树上启发式合并）
直接暴力每颗子树复杂度是O(n2n^2n2)的，树上启发式算法是可以将复杂度优化到O(nlogn)的。启发式算法是基于人类的经验和直观感觉，对一些算法的优化。举个栗子：并查集的按秩合并，合并时将秩（集合的高度）小的集合合并到秩大集合上去。对于树来说也是可以的，不过合并树的话就不能看高度了，而要看树的节点数量，沿用树链剖分的轻重儿子的概念，就是将轻儿子的子树的贡献合并到重儿子的子树上去。#include<iostream>#include<cstdio>#include&.
2020-11-11 10:54:13
733
原创 区间的连续段 (倍增）
f[i][j]表示：以i为起点跳过2j2^j2j个区间后最远能跳到的点（该点不在区间）。j>0时 f[i][j]=f[f[i][j-1][j-1];j=0时就得令外找了，双指针扫一遍就好。最终要找区间[l,r]的值，从l出发一直向后跳，最后一个区间不一定最大，所以一直跳到离r最近的点即可。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#incl.
2020-11-06 10:37:14
186
原创 P1503 鬼子进村（平衡树）
传送门第一次写fhq平衡树，写个博客纪念一下，附全部模板#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cstdlib>using namespace std;typedef long long ll;const int N=500010;int n,m,cnt,root;struct node{ int l,r,
2020-10-22 16:59:30
120
原创 SP10707 COT2 - Count on a tree II （树上莫队）
传送门普通莫队是对一段一维的序列上操作的算法，即使带修莫队也是增加一个时间轴修改的序列也是一维的，如果对于一个树能否操作呢？可以将对树处理成一个欧拉序来实现，欧拉序是在dfs序的基础上在绕回每个点时将这个点填进去的序列。举个例子：dfs序：12345678欧拉序：1233445526778861定义：s[i]表示节点i入栈的时间戳，t[i]表示节点i出栈的时间戳。所以欧拉序的长度是2n的，对树上两点u和v之间的路径有两种情况（假设u的深度比v小）：u是v的祖先：那么s[u]到s[v]之间的点（
2020-10-21 22:37:48
164
原创 P2051 [AHOI2009]中国象棋 （dp）
传送门n和m太大了，状压dp不行。换一种方式：定义f[i][j][k]为前i行中有就 j 列放了一个，k列放了2个的方案数。总共有m列，什么也没放的有 s=m-j-k 列。第 i 行有三种选择不放，放一个（放s或j中，k已经放不下了），放两个（全放s，一个s一个j，两个j），需要注意一直保持 s+j+k=m。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=110;const
2020-10-10 23:08:13
101
原创 2019 蓝桥杯省赛 B 组模拟赛（一）
传送门D. 结果填空：马的管辖爆搜，总的状态只有2252^{25}225个，判断每个状态是否成立。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;#define rint register int const int N=200010;#define fi first
2020-10-10 22:25:31
197
原创 P1505 [国家集训队]旅游 （树链剖分）
传送门很明显是树链剖分，因为是边权，所以将每个边权给深度大的那个点可以了，根节点不用赋值，要求最大值和最小值，所以线段树不包含根节点。因为点是从0编号的，所以父节点和重儿子数组要初始化。#include<iostream>#include<cstring>#include<cstdio>using namespace std;const int N=200010,inf=0x3f3f3f3f;int n,m,a[N],b[N],c[N],h[N],e[N&l
2020-10-09 23:54:54
2038
原创 P3293 [SCOI2016]美味 （主席树）
传送门要求最大的异或值，最先想到的就是tire树了，又有区间的限制，就试了试可持久化tire树，然后发现+x没办法处理，遂自闭。题解的思路真是妙啊，还是借助tire的思想，假设 b 的第 i 位是0，那么就找 a[j]+x是否存在第 i 位是1 的数，反之亦然，要保证异或值最大嘛。怎么去找呢，定义一个变量num表示第 i 位之前使异或值最大的那个数（仅考虑第i位之前的 a[j]+x），第 i 位如果是0，a[j]+x的第 i 位就尽量填1，就是a[j]+x要属于区间 [ 2i2^i2i,2i+1−12^
2020-10-09 10:48:53
106
原创 SUM OF SUB RECTANGLE AREAS （矩阵快速幂+高精度+压位）
题目链接打表可以发现ans[n]是完全平方数，令f[n]=sqrt(ans[n])可以求得 f]n]=3 * f[n-1] - 3 * f[n-2] + f[n-3] + 1;所以可以用矩阵快速幂求得，答案爆ll，还得套高精度模板，如果高精度每一位都存个位数还是会超时，所以还得压位。#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<
2020-10-02 21:32:47
154
原创 数颜色
题目链接查询某种颜色c在区间[l,r]有几个，可以直接把每种颜色出现的位置保存并递增排列，然后计算有几个位置是在区间[l,r]内的，二分就可以了。如果a[x]==a[x+1]那么就不用交换，否则 对颜色a[x]来说，下一个同颜色的位置一定大于x+1，所以可以直接用交换后的位置x+1覆盖交换之前的位置x；颜色a[x+1]同理。所以交换操作就处理好了。#include<bits/stdc++.h>using namespace std;typedef long long ll;const
2020-09-24 23:22:14
310
原创 HH的项链
题目链接既然要统计区间[l,r]内不同的数字，那么相同的数字只保存最后一个，对最后一个数字赋值1，其余数字赋值0，这样可以通过前缀和求得区间[1,r]内的不同数字，那么区间[1,l-1]内赋为1数字是什么意思呢？这些数字最后一个位置在[1,l-1]内，就是说区间[l,r]内没有这些数字，所以两个区间前缀和的差即为[l,r]的答案。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=100
2020-09-24 22:48:02
104
原创 第K小数 （主席树）
第k小数主席树本名可持久化线段树，也就是说，主席树是基于线段树发展而来的一种数据结构。其前缀"可持久化"意在给线段树增加一些历史点来维护历史数据，构成多个版本的主席树，使得我们能在较短时间内查询历史数据可以对于每个点i都建一棵权值线段树，维护1~i这些数，每个不同的数出现的个数（权值线段树以值域作为区间）对于第i个点a[i]，将它属于的权值线段树添加进主席树，该权值线段树相比于前i-1个点构成的第i-1版本的主席树只有log（n）个点是不同的，其余的点都是相同的，将不同的这些点新建一个分支并与主席树链
2020-09-23 23:19:39
217
原创 Codeforces Round #671 (Div. 2)
A 如果n是奇数 最终剩下的一定是奇数位的值，判断奇数位是否有奇数即可；如果n是偶数最终剩下的一定是偶数位的值，判断偶数位是否有偶数即可。ps：&运算比 == 优先级低！！！ 因为这个被hack了。哭辽。。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=200010;typedef pair<int,int> pii;#define fi first#de
2020-09-20 20:01:20
208
原创 Candies POJ - 3159 （差分约束）
题目链接题意：已知n个点和m条关系，每条关系包含a,b,c三个整数，表示：d[b]-d[a]<=c，求d[n]-d[1]的最大值。如若一个系统由n个变量和m个不等式组成，并且这m个不等式对应的系数矩阵中每一行有且仅有一个1和-1，其它的都为0，这样的系统称为差分约束系统。说人话：关系式都是 d[i]-d[j]<=a[k]的形式。令 w(j,i)=a[k]，再移项可以得到 d[j]+w(j,i)>=d[i],是不是感觉似曾相识，迪杰斯特拉算法的松弛操作：if(d[u]+w(u,v
2020-09-06 17:33:31
67
原创 2020 杭电多校第6场
1009 Divisibility题意：十进制下判断一个数n能否被3整除的方法是 判断n的各位数的和能否被3整除，现给你一个b和x，判断再b进制下能否用这种方法判断所有数能否整除x。打表可以找规律。#include<bits/stdc++.h>using namespace std;typedef long long ll;int t;ll b,x;int main(){ cin>>t; while(t--) { cin&g
2020-08-09 16:27:59
115
原创 2020杭电多校第5场
1001 Tetrahedron直角三棱锥有一个性质：底面面积的平方等于三个侧面面积的平方和。然后根据体积可以算出来h，1/(h^2)= (a ^ 2 * b ^ 2+a ^ 2 * c ^ 2+b ^ 2 * c ^2) / ( a ^ 2 * b ^ 2 * c ^ 2)再往下化简就可以得到 1/(h^2)= 1/( a ^ 2 )+ 1/(b ^ 2 )+1/(c ^ 2)根据 E（x+y）= E (x)+ E(y) 可得 E(1/(h ^ 2))=3*E(1/(a ^ 2))所以求1到n
2020-08-09 11:13:32
211
原创 2020 杭电多校4 1007 Go Running
题目链接以x与t为轴建立直角坐标系，可以发现向右跑的同一个人在 x=t+b这条直线上，向左跑的同一个人在x=-t+b这条直线线上，肯定是让同一条直线上人算做一个人才会最少，但是直线的交点怎么算是个问题。当时还真想不到怎么建图跑网络流太菜了。对于每个点都会有一个 xi+ti 和一个 xi-ti,在他们之间连一条有向边，最终就会建成一个二分图，问题就变成了求最小点覆盖。对于有向图最小点覆盖等于最大匹配，对于无向图还要除以二。再建造一个超级源点和一个超级汇点可以跑网络流了。xi和ti的值太大还要离散化一下。
2020-07-31 21:20:53
140
原创 2020杭电多校第三场
1004 Tokitsukaze and Multiple思路：合并尽量多的p的倍数，假设[l,r]的和模p等0，就可以合并这个区间，需要得到尽量多，对于每一个r选择最近的l，想要快速寻找这个 l 可以借助前缀和的性质，如果[l,r]的和模p等0，那么sum[r]%p==sum[l]%p，所以记录前缀和的模数的位置即可。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=100010;
2020-07-29 10:33:31
354
原创 2020 杭电多校第二场
1010 Lead of Wisdom剪枝：预处理每一行每个位置最大值，搜到第i行时如果后面几行全部取最大值（这种情况都不一定存在）的结果还是比ans小就没必要再搜了。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=55;int t,n,k,s[N][N][5],sz[N];int suf[N][5],m[N][5];ll ans;void dfs(int x,int a,i
2020-07-27 08:45:38
263
4
原创 2020杭电多校第一场
Problem DescriptionThe Fibonacci numbers are defined as below:Given three integers N, C and K, calculate the following summation:Since the answer can be huge, output it modulo 1000000009 (109+9).InputThe first line contains an integer T (1≤T≤200), d
2020-07-23 09:38:13
359
原创 最小割边与最小割点
最小割边思路：将1到n的所有最短路都切断，求最小代价。先跑一遍迪杰斯特拉，然后再在最短路径上重新建图，就变成了在新图上将1到n的所有路径全部切断的最小代价，也就是最小割（边）。根据最大流最小割定理：最大流等于最小割，所以求最大流即可。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=200500;const ll inf=0x3f3f3f3f3f3f3f3f;#define fi
2020-07-15 13:14:29
644
原创 P2055 [ZJOI2009]假期的宿舍（匈牙利算法或者最大流）
题目链接题意：学校放假了，一部分学生回家一部分留校，然后有一些外校生来找他们的朋友玩。怎么安排住宿是个问题，他们所有人都有一个毛病只想睡朋友或者自己的床。问是否有一个合理的住宿方案？看到这个很容易会想到二分图最大匹配，先将整个图分成两部分：人和床，求人和床的最大匹配。首先是本校生他才会有床，床的编号就是他的编号，然后对于每一个外校生找最大匹配。对于留校的本校生先让他睡他自己的床，还需要给他与他的床之间连一条边，刚开始想着留校生已经匹配好床了就没连结果wa了一个点，可能会存在留校生先把床让给了朋友，然后
2020-07-11 11:33:34
152
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人