- 博客(88)
- 收藏
- 关注
RSS订阅
原创 组合数学知识点整理
组合数学知识点整理lucas定理 + 组合数计算卡特兰数lucas定理 + 组合数计算链接定理：CnmC_n^mCnm % ppp=Cn/pm/p×Cn%pm%pC_{n/p}^{m/p} \times C_{n\%p}^{m\%p}Cn/pm/p×Cn%pm%p %ppp，其中p为素数卡特兰数链接
2020-06-16 19:47:41
623
原创 codeforces比赛记录
CF比赛记录Educational Codeforces Round 75Educational Codeforces Round 75D. Salary Changing（二分）
2020-04-08 19:33:26
606
原创 线段树提升练习题
习题CF283E. Cow Tennis Tournament （正难则反 + 线段树维护异或）CF283E. Cow Tennis Tournament （正难则反 + 线段树维护异或）链接：https://codeforces.com/contest/283/problem/E题意：有 nnn 个能力值，能力值越大越强。有 mmm 个区间，每个区间代表能力值在 [a,b][a,b][a,b] 内的人的强弱关系翻转，区间外的人对区间内的人的强弱关系不变（没有传递关系）。问有多少个三元组 (p,q,r
2021-07-07 15:55:30
159
原创 线段树基础模板题
练习题HDU - 4027 Can you answer these queries? （同时维护单点更新 + 区间更新）POJ - 2528 D - Mayor’s posters （离散化 + 单点查询）HDU - 1540 Tunnel Warfare （求最大连续区间）HDU - 4027 Can you answer these queries? （同时维护单点更新 + 区间更新）题意：维护两种操作0 a b 代表将区间 [a,b][a,b][a,b] 内的数值，变为自己的平方根1 a
2021-07-07 14:43:14
220
原创 2019牛客暑期多校训练营（第三场）
题目B Crazy Binary String（签到+前缀和）D Big Integer （循环节）F Planting Trees（单调队列）G Removing Stones （分治）H Magic Line （几何思维）I Median （DP求方案数）J LRU management （双向链表）B Crazy Binary String（签到+前缀和）题意：给定一个 01 字符串，求最长的 01数量相等的子串和子序列的长度。思路：前缀和相等的位置累积一下答案即可。#include <
2021-05-26 23:12:50
399
1
原创 2019牛客暑期多校训练营（第二场）
题目A Eddy Walker （概率思维）B Eddy Walker 2 （线性递推）D Kth Minimum Clique （bitset 维护团）E MAZE （线段树上维护矩阵中DP值的转移）F Partition problem （dfs + 优化）H Second Large Rectangle （单调栈）J Subarray （思维 + 抓住小范围）链接：https://ac.nowcoder.com/acm/contest/882A Eddy Walker （概率思维）题意： n 个
2021-05-25 21:59:15
152
原创 2019牛客暑期多校训练营（第一场）
题目A Equivalent Prefixes （二分 + 区间最值查询）E ABBA （DP计数）H XOR （线性基）I Points Division （线段树维护DP）J Fraction Comparision（签到的签到）链接：https://ac.nowcoder.com/acm/contest/881#questionA Equivalent Prefixes （二分 + 区间最值查询）题意：给定两个长度为 n 的数组 a 和 b ，找到一个最大的位置 p ，使得两个组数在 [1,p]
2021-05-23 18:11:31
122
1
原创 第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）
题目B Mine Sweeper IIC Sum of Log （数位DP）D WalkerE The Journey of Geor AutumnG Fibonacci （签到）H Rice ArrangementI Sky GardenL Traveling in the Grid World （待补）M Gitignore链接：https://ac.nowcoder.com/acm/contest/9925B Mine Sweeper II题意：给定一张 n×mn\times mn×m 的扫雷图
2021-05-13 00:45:34
551
1
原创 第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）
题目E Evil CoordinateF FireworksH Harmonious RectangleJ Just Another Game of StonesK K Co-prime Permutation（签到）L Let's Play Curling（签到）M Monster Hunter链接：https://ac.nowcoder.com/acm/contest/10272E Evil Coordinate题意：给定由 U、D、L、R 组成的长度为 n 字符串，问是否存在从 （0,0）开始不
2021-05-12 14:56:04
510
原创 KMP习题
习题POJ - 3461 OulipoPOJ - 3461 Oulipo链接：http://poj.org/problem?id=3461题意：给定字符串 s 和 t ，求 t 在 s 中出现的次数思路：假设模式串当前位置为 j ，当 j 为 1 时，就不用再走到 next[j] 了。因为 next[1]=0，我们需要将模式串指针从 j =1 开始匹配。#include <cstdio>#include <cstring>#define ll long longusi
2021-04-28 20:27:21
89
原创 第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）
题目D Fight against involutionJ Tree ConstructerL Bit Sequence链接：https://ac.nowcoder.com/acm/contest/10662D Fight against involution思路：可以得到几个贪心关系遇到这种左右区间的，可以按右区间排序右区间相同的，左边也得取相同的，否则会不相同。右区间大的，那么贪心的取值，也一定大于右区间小的。J Tree ConstructerL Bit Sequence思路：m
2021-04-15 23:16:50
301
原创 PAT题目集
PAT题目集PAT（甲级）2020年秋季考试PAT（甲级）2020年春季考试PAT（甲级）2019年冬季考试PAT（甲级）2019年秋季考试PAT（甲级）2019年春季考试PAT（甲级）2020年秋季考试PAT（甲级）2020年春季考试PAT（甲级）2019年冬季考试PAT（甲级）2019年秋季考试PAT（甲级）2019年春季考试...
2020-12-04 22:02:49
98
原创 天梯赛 L3 练习题（1）
天梯赛 L3 练习题 1L3-001 凑零钱 (30分) （01背包求方案）L3-002 特殊堆栈 (30分) （线段树或者树状数组求第 k 小）L3-003 社交集群 (30分) （并查集）L3-010 是否完全二叉搜索树 (30分)L3-001 凑零钱 (30分) （01背包求方案）题目链接题意：给定 n 枚硬币的面值，问能否恰好凑成 m 元。输出字典序最小的排列。或者输出“No Solution”。思路：要求字典序最小，那么就贪心地取硬币，从小的开始取。dp 转移的时候记录一下，当前的物品是否
2020-11-26 22:18:06
298
原创 天梯赛 L3 练习题（2）
天梯赛 L3 练习题L3-001 凑零钱 (30分)L3-002 特殊堆栈 (30分)L3-001 凑零钱 (30分)题目链接题意：给定 n 枚硬币的面值，问能否恰好凑成 m 元。输出字典序最小的排列。或者输出“No Solution”。思路：要求字典序最小，那么就贪心地取硬币，从小的开始取。dp 转移的时候记录一下，当前的物品是否会被取。#include <bits/stdc++.h>#define ll long longusing namespace std;const i
2020-11-24 23:21:06
283
原创 天梯赛 L2 练习题
习题L2-001 紧急救援 (25分)L2-004 这是二叉搜索树吗？ (25分)L2-001 紧急救援 (25分)题目链接题意：给定一个 n 个点 m 条边的无向图。给定起点 s 和终点 d 。无向图带有点权和边权。请你输出，从 s 到 d 的最短路径数、最短路中最大的点权和，从 s 到 d 的路径。思路：最短路模板题。用 path 记录路径数，dis 记录最短路，maxval 记录从 s 到当前点的最大点权和，pre 记录路径#include <bits/stdc++.h>#de
2020-11-23 19:03:07
556
1
原创 博弈习题
博弈习题B. MADMAXP2575 高手过招B. MADMAX链接:https://codeforces.com/contest/917/problem/B#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=2e5+10,maxm=1e7+10;int n,m;int sg[110][110][30];vector<pair<int,int> >
2020-10-31 19:29:48
933
原创 思维、模拟、分类讨论习题
习题2020CCPC威海 H Message Bomb2020ICPC沈阳 L-Flowers2020CCPC威海 H Message Bomb题意： n 个群 m 个学生，q 个消息，有 3 种类型1 x y ： 学生 x 加入群 y2 x y ：学生 x 退出群 y3 x y ： 学生 x 在群 y 发送一条消息，其他群里的人都会接收到(1≤n≤1051,≤m≤2×105,1≤q≤106)(1\le n \le 10^5 1,\le m\le 2\times 10^5 ,1\le q\le
2020-10-30 01:10:28
149
原创 DP习题（2）
DP习题2020CCPC威海 L Clock MasterCF1437C. Chef MonocarpC. The Hard Work of Paparazzi2020CCPC威海 L Clock Master题意：给定一个正整数 bbb ，找到一些正整数 (t1,t2,…,tn)(t_1,t_2,\dots,t_n)(t1,t2,…,tn) ，使得 t1+t2+⋯+tn≤bt_1+t_2+\dots+t_n\le bt1+t2+⋯+tn≤b ，并且使得 lcm(t1,t2,…,tn)lcm
2020-10-30 00:57:16
85
原创 The 15th Heilongjiang Provincial Collegiate Programming Contest （A、G、H、L）
The 15th Heilongjiang Provincial Collegiate Programming ContestA. AugustG. GoodbyeL. Let's Get Married链接：https://codeforces.com/gym/102803A. August#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;const doubl
2020-10-29 22:51:04
971
原创 图论习题
习题2020秦皇岛 K. Kingdom's Power2020秦皇岛 K. Kingdom’s Power链接：https://codeforces.com/gym/102769/problem/K题意： n 个城市可以看做一棵以 1 为根的树，在城市 1 有无穷支军队。每天可以派遣一支军队移动一次。问最少需要几天才能使军队走遍所有的城市思路：容易想到直接贪心，在叶节点的位置的军队，要么就是从其他叶节点走过来，要么就是从 1 号节点走过来。首先将每个节点的子节点按照叶节点的深度排序，按贪心的思
2020-10-29 22:37:16
189
原创 树上启发式合并习题
树上启发式合并（dsu on tree）算法流程习题CF600E. Lomsat gelral算法流程首先遍历轻儿子，遍历完之后将数据清空。然后遍历所有重儿子数据不清空此时继续遍历轻儿子，此时就可以统计答案了最后根据：当前 u 是否为 fa 的轻儿子，来决定是否保留数据。如果是轻儿子就清空清空的时候，都是先清空轻儿子的信息，然后会保留重儿子的信息，后面又会重新遍历轻儿子，因而可以保证数据正确。时间发复杂度：一个点距离根节点，最多经过 log2nlog_2nlog2n 条轻边，因此最多被访问
2020-10-26 22:01:31
677
原创 2019 ICPC Asia Xuzhou Regional
2019 ICPC Asia Xuzhou RegionalA. Cat （思维）C. <3<3<3 numbers （素数分布）E. Multiply （大数质因子分解）F. The Answer to the Ultimate Question of Life, The Universe, and Everything. （打表）M. Kill the tree （重心）A. Cat （思维）题意：有 1e18 只猫在排成一列。第 i 只猫的价格为 i 。假设要买区间 [l,r][
2020-10-23 20:43:47
267
原创 The 2019 ICPC Asia Shanghai Regional Contest
The 2019 ICPC Asia Shanghai Regional ContestB. Prefix Code （签到题）D. Spanning Tree Removal （构造题）E. Cave Escape （最大生成树）F. A Simple Problem On A Tree （树链剖分裸题）H. Tree Partition （二分）K. Color Graph （奇环）链接：https://ac.nowcoder.com/acm/contest/4370B. Prefix Code （
2020-10-23 11:58:13
617
原创 概率与期望习题
概率与期望习题P6154 游走P3232 [HNOI2013]游走P6154 游走链接：https://www.luogu.com.cn/problem/P6154题意：B 城可以看作一个有 n 个点 m 条边的有向无环图。可能存在重边。zbw 在 B 城随机游走，他会随机选择一条路径，选择所有路径的概率相等。路径的起点和终点可以相同。定义一条路径的长度为经过的边数，你需要求出 zbw 走的路径长度的期望，答案对 998244353 取模思路：计算出路径的总长度、总路径数，两者相除即可设 g[i
2020-10-12 17:32:33
661
原创 点分治习题
点分治点分治步骤P3806 【模板】点分治1点分治步骤每次找到一个重心，以重心为根开始分治。先 dfs1 拿前面的数据来更新答案，然后 dfs2 将当前子树的数据也更新上去。每次换一个重心的时候，都需要清空 cnt 数组。这些需要重新记录。P3806 【模板】点分治1链接：https://www.luogu.com.cn/problem/P3806题意：给定一棵有 nnn 个点的树， mmm 个询问，询问树上距离为 k 的点对是否存在思路：用 cnt 数组记录一下，当前 点 到根的距离。每
2020-10-05 18:31:21
212
原创 线段树合并
线段树合并P1456 Monkey KingP1456 Monkey King链接：https://www.luogu.com.cn/problem/P1456题意：给定 n 只猴子打 m 次架，每次询问两只猴子，选择它们所在集合中，战斗力最大的两只猴子，将它们的战斗力减半。输出这个减半之后的战斗力，然后将这两个集合合并。如果两只猴子已经在同一个集合，那么就输出 -1.思路：用并查集维护集合关系。然后用 动态开点权值线段树 + 线段树合并来维护操作。每次先查询 u 、v 是否在同一个集合。不在，
2020-10-05 16:06:56
317
原创 可持久化并查集、带删并查集
可持久化并查集P3402 可持久化并查集P3402 可持久化并查集链接：https://www.luogu.com.cn/problem/P3402题意：给定 n 个集合，第 i 个集合内初始状态下只有一个数，为 i。有 m 次操作。操作分为 3 种：1 a b 合并 a,b 所在集合2 k 回到第 k 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态3 a b 询问 a,b 是否属于同一集合，如果是则输出 1 ，否则输出 0思路：可持久化并查集#include &
2020-09-29 11:27:35
763
原创 可持久化 01Trie
01TrieP4551 最长异或路径 （01trie）P4551 最长异或路径 （01trie）链接：https://www.luogu.com.cn/problem/P4551题意：给定一棵 nnn 个点的带权树，结点下标从 1 开始到 n 。寻找树中找两个结点，求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异或。思路： 01trie 模板题从高位开始贪心，每次枚举一个数字时，需要关心与它异或相反的位置。#include <bits/stdc++.h>#
2020-09-27 20:18:04
368
原创 字典树习题
字典树习题POJ - 2418 Hardwood SpeciesPOJ - 2418 Hardwood Species链接：http://poj.org/problem?id=2418题意：给定多个字符串，有些字符串相同，请你统计每种字符串的数量占所有字符串数量的百分比，按字典序输出思路直接拿map 记录一下，然后输出就好了也可以用 set + 字典树 写一下，也不用删除操作。#include <cstdio>#include <string>#include
2020-09-27 20:17:28
130
原创 可持久化数据结构
可持久化数据结构P3919 【模板】可持久化线段树 1（可持久化数组）P1383 高级打字机P3834 【模板】可持久化线段树 2（主席树）P3919 【模板】可持久化线段树 1（可持久化数组）链接：https://www.luogu.com.cn/problem/P3919题意：你需要维护这样的一个长度为 nnn 的数组，支持如下几种操作在某个历史版本上修改某一个位置上的值访问某个历史版本上的某一位置的值，并输出这个值#include <bits/stdc++.h>#defi
2020-09-26 19:15:41
137
1
原创 2019 ICPC Asia-East Continent Final
2019 ICPC Asia-East Continent FinalA. CityE. FlowM. ValueA. City链接：https://codeforces.com/gym/102471/problem/A题意：给定 n×mn\times mn×m 的网格图，有 (n+1)×(m+1)(n+1)\times (m+1)(n+1)×(m+1) 个点，问有多少条线段满足两个端点在网格点上，且中点也在网格点上思路：竖的和横的比较好算，斜着的只需要偶数偶数匹配一下就好了。#include &
2020-09-19 14:02:33
530
原创 贪心
贪心HDU - 2037 今年暑假不ACHDU - Problem BuyerHDU - 1042 Gone FishingPOJ - 1328 Radar InstallationPOJ - 3190 Stall ReservationsPOJ - 3614 SunscreenHDU - 2037 今年暑假不AC链接：http://acm.hdu.edu.cn/showproblem.php?pid=2037题意：给定 n 个区间，问最多能选多少个不相交的区间（端点可重叠）思路：按右区间排序#i
2020-09-19 02:24:11
120
原创 2019 ICPC Asia Nanjing Regional
2019 ICPC Asia Nanjing RegionalA. A Hard ProblemC. Digital PathH. Prince and Princess链接：https://www.jisuanke.com/contest/5528/challengesA. A Hard Problem#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+10;int
2020-09-18 16:26:52
202
原创 2019 ICPC Asia Nanchang Regional
2019 ICPC Asia Nanchang RegionalC. And and PairE. Bob's Problem链接：https://www.jisuanke.com/contest/5530/challengesC. And and Pair#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+10,mod=1e9+7;int t;string n;i
2020-09-18 16:22:56
151
原创 二次剩余
二次剩余二次剩余勒让德符号判别式求解流程模板2019牛客第九场 B Quadratic equation二次剩余定义：对于n、p，若存在x，使得x2≡n(mod p)x^2\equiv n(mod\ p)x2≡n(mod p)，则称n为模p意义下的二次剩余。也就是说，如果n是模p的二次剩余。那么n mod p\sqrt n\ mod\ pn mod p，可以用二次同余方程的解 xxx 来代替n\sqrt nn，暴力地找就是 x2%p==n
2020-09-17 23:44:35
460
原创 积性函数线性筛
积性函数线性筛1、莫比乌斯函数 μ\muμ2、欧拉函数 φ\varphiφ3、约数个数函数d4、约数和函数σσσ5、积性函数1、莫比乌斯函数 μ\muμconst int N=6e6;int visit[N+10],prime[N+10],mu[N+10],cnt;void init(){ cnt=0,mu[1]=1; for(int i=2;i<=N;++i) { if(!visit[i]) prime[++cnt]=i,mu[i]=-1; for(int j=1;j<
2020-09-17 22:39:29
186
1
原创 欧拉降幂
欧拉降幂欧拉降幂bzoj3884. 上帝与集合的正确用法2019ICPC南昌预选赛网络赛 B. super_logCF906D. Power Tower欧拉降幂定理：当b>φ(p)\varphi(p)φ(p) 时，ab≡ab%φ(p)+φ(p)(mod p)a^b\equiv a^{b\%\varphi(p)+\varphi(p)} (\mod p)ab≡ab%φ(p)+φ(p)(modp)细节：每次递归过程中维护的是指数，因此需要在 dfs 出口计算当前的指数，在 qpow 的过程中也通过
2020-09-17 20:51:02
144
原创 数论推式子习题
数论推式子推式子P4213 【模板】杜教筛（Sum）P3327 [SDOI2015]约数个数和2019西安邀请赛 B. Product（杜教筛）HDU - 6706 huntian oy（杜教筛）推式子从枚举因数到枚举倍数，因数不便化简，倍数可以直接靠除法压缩规模遇到 gcd(i,j)gcd(i,j)gcd(i,j) 可以枚举它，遇到 [gcd(i,j)=x][gcd(i,j)=x][gcd(i,j)=x] 可以缩小 iii 、jjj 的规模，变成 [gcd(i,j)=1][gcd(i,j)=1]
2020-09-17 20:14:46
949
1
原创 数论基础知识
数论知识剩余类完全剩余系欧几里得算法扩展欧几里得算法线性同余方程求解同余方程POJ1061 青蛙的约会求解一元线性同余方程组POJ2891 Strange Way to Express Integers剩余类设模为n，则根据余数可将所有的整数分为n类，把所有与整数a模n同余的整数构成的集合叫做模n的一个剩余类，记作[a]。并把a叫作剩余类[a]的一个代表元例如,模3时，[1]=[4]=[7]={1,4,7⋯ }[1]=[4]=[7]={\{1,4,7\cdots\}}[1]=[4]=[7]={1,4,
2020-09-16 00:18:45
760
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人