- 博客(76)
- 收藏
- 关注
RSS订阅原创 D. GCD of an Array
线段树维护每个素数区间最小个数，新学了个动态开点。#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef double db;const int mod=1e9+7;const int N=2e7+11;const int maxn=2e5+11;const double eps=0.00000001;int n,q,cnt,a[maxn],ind,x,p[maxn],isp[maxn].
2021-03-09 11:06:39
112
原创 寒假训练1
C. Spelltime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputMaleficent got upset when she could not cancel the spell cast upon Aurora because it’s infinite and unbreakable. Luckily for us it’s not such
2021-01-22 20:12:01
178
原创 POJ1015 Jury Compromise
参考博客#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include <queue>#include <vector>#include <map>using namespace std;typedef long long ll;typedef double
2020-10-28 21:36:53
94
原创 hdoj5542 （树状数组优化dp）
题目链接题目大意：给定一个长度为n特定序列，要求出严格递增的长度为m的子序列的方案数。思路：设dp[i][j]为1-i中，存在长度为j且以a[i]结尾的方案数。方程利用树状数组维护1-i-1中长度为k的方案数即可优化。代码：#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include &
2020-10-23 12:27:05
132
原创 牛客练习赛71 C
链接：https://ac.nowcoder.com/acm/contest/7745/C来源：牛客网牛牛在树剖姐姐的数学考试里出了一个题，但是树剖姐姐不会做，于是她向您求助。求1-n 的排列，有 m 个限制条件，第i个限制条件 Pi，表示前Pi个数不能出现1-Pi 的排列，求符合要求的排列的个数。答案对 20000311 取模。代码：#include <cstdio>#include <cmath>#include <cstring>#include
2020-10-10 00:17:27
113
原创 HDOJ5934(Tarjan缩点)
题目链接：添加链接描述找强连通块，块内选择引爆任意一个都能使整个块引爆，我们只需要把强连通块缩成一个点，然后取入度为0的点引爆，每个点取cost最小即可。代码：#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include <queue>#include <vector>#
2020-09-25 18:40:08
55
原创 613 div2 D
题目链接题目思路：01字典树，当前二进制位置都是1的话，就选择1，都是0就选择0，两种都有就取1<<k+最小值。#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include <queue>#include <vector>#include <map>
2020-09-08 15:33:00
83
原创 RMQ（st算法离线算法）求区间最大值/最小值
定义dp[i][j]为起始位置为i，终点为i+2^j-1的区间的最大值/最小值；转移方程 dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1])具体代码：void st(int n){ for(int i=1;i<=n;++i) dp[i][0]=p[i].w; int len=log(n)/log(2)+1;//区间长度为n的二进制最大数，满足2^len>n for(int i=1;i<len;++i){
2020-09-04 13:17:55
635
原创 div2 649 D. Ehab‘s Last Corollary
题目：给一个连通图，让你找出等于ceil(k/2)的独立点集或者小于等于k的环（按顺序输出），有这么一个存在证明：最小环r>k时，独立集可以在环中找到，r<=k时，直接输出环。当m==n-1时，是树，直接dfs判断奇数偶数层个数，取最大然后输出k个点的独立集即可，m>n-1时，则找出最小环，再判断就好了。代码：#include<bits/stdc++.h>using namespace std;const int maxn=2e5+11;const int mod=
2020-09-01 10:56:17
116
原创 div666 D题
博弈模拟题最优策略就是每次都拿最大堆，用优先队列直接模拟即可代码：#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include <queue>#include <vector>#include <map>using namespace std;typede
2020-08-31 10:57:09
118
原创 权值线段树
（1）.可以计算出整个数组第k大\小（2）.可以计算出i-j在数组中出现的个数。扩展：1.计算逆序对个数，从第一个开始，每次添加一个数，记录前缀中大于a[i]的数的个数即可，利用到了上面的（1）。题目hdoj1394，代码：#include<bits/stdc++.h>using namespace std;const int maxn=5000+11;const int mod=1e9+7;const double eps=0.000001;typedef long long
2020-08-29 12:57:43
81
原创 hdoj4027
线段树题目，区间修改，区间内每个数x->sqrt(x),向下取整，数据不是太大，n=1e5，2^63开根号最大也就8，9次，完全可以暴力，中间可以判断这个区间是否满足 贡献=长度，及sum=r-l+1的话，就不必修改这个区间了。（注意输出格式，还是x和y的大小关系，不一定x小于y的，得判断一下）代码：#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>
2020-08-25 20:04:21
93
原创 202杭电多校第十场1010
题目链接Nim game博弈参考题解：Alice 第一轮取完后，Bob 上来取取同行或者同列必败，因此一定取不同行不同列的。本题性质允许行交换列交换，不妨设 Alice 取 (1, 1), Bob 取 (2, 2)。这样除 (3, 3) 外， 剩下的每个格子都是不论后续局面如何， 谁第一个取最后一颗石子谁必败。 因此 (3, 3) 整堆与其他每堆除一颗石子外的整堆构成一个普通 nim 游戏， 即后手必败当且仅当((1, 2) ) 1) ⊕ ((1, 3) ) 1) ⊕ ((2, 1) ) 1)
2020-08-20 18:16:27
86
原创 2020杭电多校暑假第八场
[hdoj6863](http://acm.hdu.edu.cn/showproblem.php?pid=6863)哈希+暴力做法#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include <queue>#include <vector>#include <map&
2020-08-13 19:12:06
107
原创 2020hdoj暑假多校第六场
1006第i条边的边权是2^i,故可以跑最小生成树，两两之间的距离便是最短路了。计算方面，对于每条边，计算有几个0 1路径经过该边，边权乘以这个个数就可以了。代码：#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include <queue>#include <vector>
2020-08-06 17:11:06
65
原创 hdoj1247
题目链接字典树题目，给定多个单词，如果存在由两个单词构成的单词，就输出，按字典序输出，用字典序，先正序插入，再逆序插入，然后查找就正序查找，逆序查找，找到就标记到vis数组里，最后再遍历一遍vis就好了。用set存答案，方便排序输出。代码：#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include
2020-08-05 21:03:58
91
原创 数论分块
处理Σ[n/i]或Σ[k%i]这种问题的时候用到，https://www.cnblogs.com/henry-1202/p/10121854.htmlhttps://blog.csdn.net/sunmaoxiang/article/details/88958124
2020-08-03 20:18:30
75
原创 2020暑假牛客多校第八场 I
https://ac.nowcoder.com/acm/contest/5673/I思路：并查集来入点，进一个就有ans++，当成环时ans也++，标记，当两个标记的并查集合并时不++，当一个标记一个不标记时，ans++，并且标记新的集合，当两个都不标记的集合合并时，ans++，不标记。代码：#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#includ
2020-08-03 20:13:05
95
原创 牛客暑假多校训练营第二场 C和F
C题目链接代码：#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include <queue>#include <vector>#include <map>using namespace std;typedef long long ll;typedef do
2020-07-14 10:11:34
91
原创 Educational Codeforces Round 87 (Rated for Div. 2) D
Educational Codeforces Round 87 (Rated for Div. 2) D链接#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include <queue>#include <vector>#include <map>using
2020-05-19 10:23:27
100
原创 Ehab and Path-etic MEXs
题目链接思路：看图是否的单链状，如果是单链状，存在max mex为n-1，否则max mex为2；mex(u,v)：表示从u到v这条路径上边权未出现过的数的最小的一个。即找出一个度不小于3的点，使它其中三边权值分别为0，1，2，其他随便。如果不存在度大于等于3的点，可以随便赋值。代码：#include <cstdio>#include <cmath>#incl...
2020-04-05 13:43:54
70
原创 Ehab the Xorcist
题目链接思路：令u=a^b,v=a+b;有a+b=a^b+2a&b->a&b=(v-u)/2;将a+b拆成三个数，(v-u)/2,(v-u)/2,u；再进行组合即可代码：#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>...
2020-04-05 13:40:26
101
原创 个人训练 6 H
H. Ancient Wisdom题目链接题目大意：给出一个式子CD^3 = A^2,1<=c<1e18,求出D的最小值。A和D均为整数。思路：将式子转化为C=A^2/ D^3 = CD^3/ D^3.要令C * D^3的开方是一个整数，即只需算sqrt(CD)是一个整数即可。令X是一个非0正整数，有CD=X^2,已知D的最大值定为C，令D=C，然后对D进行因数分解，能够开...
2020-03-26 13:53:08
122
原创 专题Ⅴ算法优化 C
C - Count Color POJ - 2777题目链接题目大意：一块木板长度为n，有t种颜色颜料，有两种操作(1)涂改区间颜色(2)询问区间有几种颜色。思路：这是一道区间修改的题目，用线段树来维护，但是按平常来算的话，会计算重复，比如左右子树的颜色中有相同的，这样就会重复加了，所以我们可以运用位运算来解决这个问题。在二进制上第i位是1的话，就说明存在这种颜色，push_up的时候也...
2020-03-12 14:04:52
120
1
原创 稀疏图求任意两点最短距离的最大值
参考题目分析：题目中点的个数和边数最大有2000个，如果用floyd肯定不行，因为是无权图，所以就用bfs来算就行了，每个点的搜索最多有O(n)，因此搜索所有点就O(n^2)。代码：#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#inclu...
2020-03-12 13:51:34
434
原创 Count Subrectangles
题目链接题目大意：给出两组整数数组a和b，长度分别为n和m，并且只由0和1构成，存在这么一个矩阵c，c(i,j)=a[i]*b[j],因此矩阵c也是由0和1构成，再给出一个整数k,求c矩阵中仅由k个1组成的子矩阵有多少个。思路：由c组成的性质，可以知道要么一行全为0，要么就等于b，因此可以先算出a和b中连续是1的区间长度有多少个，然后再算出长度从1到n和1到m有多少种即可。代码：#in...
2020-03-10 22:20:31
55
原创 Adding Powers
Adding Powers题目链接题目大意：给出一组n个元素的整数数组，还有k，问这些元素能否由k^i次方相加而成，每个i只能加一次。思路：我们可以将每个转化成k进制，然后用桶存，最后判断k进制下每一位是否存在大于1的即可。代码：#include <cstdio>#include <cmath>#include <cstring>#includ...
2020-03-10 20:16:16
103
原创 2020排位赛Ⅳ（div2）F
F. News Distribution题目链接题目大意：给出两个整数n和m，n代表有n个人，编号1-n，m代表有m个群组，每个群主有一个或多个人，在同一个群组的就是朋友，然后朋友之间可以传递信息，就是比如1得到一个信息，他可以把信息传给他所有的朋友，然后他的朋友可以把信息继续进行传递。思路：用到了并查集，改动一下就好了。代码：#include <cstdio>#incl...
2020-03-09 15:03:37
93
原创 2020排位赛Ⅲ（div2）B
B. Loan Repayment题目链接题目大意：FJ需给贝西Ng牛奶，预计K天给完，但是给的条件不普通，有这么一个Y=（N-G）/x，G是已给贝西的牛奶量，x是一个常数，此外还有一个常数m，如果Y小于m的话，则当天给贝西m g牛奶，否则给贝西Yg牛奶。借鉴大佬的推理：必定存在连续一段时间a给的是y g牛奶。a=⌊r/y−x+1⌋（r=N-G）。代码：在这里插入代码片...
2020-03-09 13:33:40
82
原创 2020排位赛Ⅲ（div2）H
H. Photoshoot题目链接题目大意：就是给出N个整数，1-N，顺序打乱，设为a[n],存在一组b[n+1],使得b[i]+b[i+1]=a[i],要求你按字典序最小输出b[n+1]的所有元素。思路：枚举，第一个元素从小到大开始枚举，直到符合题目就时结果。代码：#include <cstdio>#include <cmath>#include <...
2020-03-09 13:24:33
122
原创 2020排位赛Ⅲ（div2）E
E. Word Processor题目链接题目大意：输入一段标准的英语句子，且包含N个单词，并给出整数K，让你依次输出单词，每一行可能包含多个单词，但单词长度不能超过K。单词用空格隔开，空格不算长度。思路：签到题。#include <cstdio>#include <cmath>#include <cstring>#include <al...
2020-03-09 13:17:02
78
原创 2020排位赛Ⅲ（div2）D
D. Race题目链接题目大意：母牛贝西在比赛跑步，跑道长为N，贝西可以以1m/s的加速度改变自己的速度，但贝西到达终点后速度不能超过x m/s，问贝西到达终点所花最少的时间是多少。思路：采用二分法来计算母牛贝西在跑步期间最高的速度v，然后再计算这个速度是否满足，若满足，就更新结果。代码：#include <cstdio>#include <cmath>#in...
2020-03-09 13:11:34
160
原创 2019_GDUT_新生专题V算法优化 L
L - Feel Good poj2796题目大意：给出一组数字，找出某个l-r区间，则这个区间存在一个值x使所有元素的和sum与最小值a的乘积，求这组数据中x的最大值。思路：我们可以假设第i个元素为最小值，分别求出它左边跟右边的边界就好了，这里可以用单调栈来维护。先算出前缀和，然后用单调栈。单调栈：例如寻找第i个元素的左边界L[i],我们可以这样子，从栈顶开始，如果存在比a[i]大...
2020-03-05 20:11:41
116
原创 2020排位赛I（div2）I
I. Where Am I?题目链接题目大意：FJ迷路了，但他可以根据邮箱颜色来定位，已知每个农田旁有一个邮筒，邮筒有26种颜色，FJ可以通过独特的颜色序列来定位，问FJ最少需要看多少个邮筒才能定位。例如7 ABCDABC，答案不能是1，因为A有重复（即使只有一个D也不行），也不能是2，因为AB重复（即使只有一个CD也不行），可以看出题目是要求出一个最小的邮筒个数k，使得所有k长度的子序列都...
2020-03-05 19:51:56
203
原创 2020排位赛I（div2）G
G. Livestock Lineup题目题目大意：给出N行句子（1<=N<=7),例如Buttercup must be milked beside Bella，意味着Buttercup与Bella相邻。要求你根据这N个句子，输出它们正确的顺序，按字典序输出。思路：数据很小，可以dfs暴力来做。代码：#include <cstdio>#include <...
2020-03-05 19:44:19
139
原创 2020排位赛I（div2）E
E. Milk Visits题目链接题目大意：有个农场，有n处产奶地，能产两种类型的牛奶H和G，每个地方产一种，并且有n-1条路将这些地方连通，某天来了一群客人，他们是从x地到y地，并且给出他们想喝什么类型的牛奶，如果该客人能喝到心仪的牛奶，就输出1，否则输出0.思路：用LCA求两个点的最近公共祖先，然后就可以算出经过几个点，经过H时+1，经过G时-1，通过最终的和可以判断有经过哪种类型的奶...
2020-03-03 20:23:38
131
原创 2020排位赛I（div2）B
B. MooBuzz题目链接题目大意：一群牛玩游戏围成一个圈，从第一头开始数数，当数到3或者5的倍数时，要Moo一声，其余的说出数字，问出现的第n个数字是多少。思路：比如一个数字k，可以计算1到k有几个数是3或5的倍数，然后k再减去这些数，结果是n就行了，由于是递增的，所以可以用二分来做。代码：#include <cstdio>#include <cmath>...
2020-03-03 20:16:02
95
原创 2020排位赛I（div2）A
A. Cow Gymnastics题目链接题目大意：有N头牛pk各种技巧，每种技巧都有排行，如果存在两头牛x和y，x每种技巧都强于y，那么就说明x强于y，问有多少组这种关系。思路：牛很少，只有20头，技巧也只有10中，暴力枚举就完事了。用二维数组记录。代码：#include <cstdio>#include <cmath>#include <cstri...
2020-03-03 20:10:08
185
原创 排位赛Ⅱ H
H. I Would Walk 500 Miles题目链接题目大意：将N头牛分成K组，要求你求出任意两组牛中任意两头牛能相遇的最短距离M。已知两头牛x和y愿意走去看对方的距离是(2019201913x+2019201949y) mod 2019201997（x<y),问M是多少（M尽可能大)。思路：题目意思就是求最小值的最大值。这是有规律可循的，比如编号越小的牛与同一编号的牛...
2020-02-24 11:49:17
81
原创 排位赛Ⅱ G
G. Bucket Brigade题目链接题目大意：在一个10*10的地图上，有一个谷仓和一个湖，有一天谷仓着火了，需要从湖运水到谷仓，这需要一些cows在路上传递水，一个位置站一头牛，牛需要相邻才能传递水，但地图上还有石头，牛不能站在石头上，问最少需要多少头牛就可以灭火。思路：bfs搜索就好了。代码：#include <cstdio>#include <cmat...
2020-02-24 11:37:32
103
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人