- 博客(30)
- 收藏
- 关注
RSS订阅原创 最短路20题心得
最短路专题最短路的三个算法：dij算法，时间复杂度最低O(nlogm)，能够解决单源最短路径问题 Floyd算法，时间复杂度最高O(n^3)，能够解决多源最短路问题 Spfa算法，时间复杂度O(kE)，k在数据随机的时候只有2，最差的情况k=n技巧：将终点视为起点进行最短路 将u到v的边写成v到u的边...
2019-08-29 17:26:47
366
原创 算法链接
类欧几里得算法：https://www.cnblogs.com/zjp-shadow/p/10601728.html二次剩余：https://www.cnblogs.com/bztMinamoto/p/10664973.html
2019-08-19 20:23:18
171
原创 hdu 6275 Mod, Xor and Everything （类欧几里得）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6275题意：求(nmod1)⊕(nmod2)⊕.......⊕(nmodn)数据范围：n≤1e12思路：首先对于取模操作是可以转化成公式的，,此题因为是异或操作我们可以一位一位的算贡献，对于第k位的贡献可以通过将n个数右移k位以后只看最后一位的异或，又因为只看最后一位的异或...
2019-08-19 20:06:35
594
原创 2019hdu暑假多校训练赛第九场1002 Rikka with Cake hdu6681（树状数组）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6681题意：给定一个n*m的蛋糕，再给出K个操作，每次都是从蛋糕的中间向四个方向中的一个切过去，问最后蛋糕被切成多少块。数据范围：1≤T≤100，1≤n,m≤109,1≤K≤105，1≤xi<n,1≤yi<m，Di∈{'L','R','U','D'}思路：我们发现切的蛋糕块...
2019-08-19 18:28:49
151
原创 2019牛客暑假多校训练赛第六场H Train Driver（bfs思维）
题目链接：https://ac.nowcoder.com/acm/contest/886/H题意：给定n和m代表n个点m条边，每条边的花费时间是1，再给出A集合和B集合，现在有三个人一个人在A集合的任意一个位置，一个人在B集合的任意一个位置，一个人在n个点中的任意一个位置，现在三个人要用最少的时间相遇，问三个人所需时间和的期望是多少。数据范围：1<=n,m<=1e5,1<...
2019-08-18 15:31:58
135
原创 2019牛客暑假多校训练赛第十场F Popping Balloons（优先队列维护）
题目链接：https://ac.nowcoder.com/acm/contest/890/F题意：给定n,r，在一个1e5*1e5的方格图中有n个方格里面有气球，现在让竖向打三枪横向打三枪，必须满足三枪打的位置是x,x+r,x+r+r，问最多能打破多少气球，一枪打一行或列。数据范围：1<=n,r,x,y<=1e5思路：开一个优先队列从大到小排，对于每个气球可以由y，y...
2019-08-18 14:36:24
100
原创 2019牛客暑假多校训练赛第八场 D Distance（定期重构bfs/三维空间，平面bfs/三维树状数组）
题目链接：https://ac.nowcoder.com/acm/contest/888/D题意：给定一个三维空间n,m,h，有两个操作，1是在这个三维空间的某个位置插入一个点，2是访问距离这个点的其余点的最小曼哈顿距离。数据范围：1≤n×m×h,q≤1e5,1≤x≤n,1≤y≤m,1≤z≤h思路1：首先因为n×m×h<=1e5，首先为了表示这个空间我们肯定要开一个数组，所...
2019-08-13 15:15:34
153
原创 2019牛客暑假多校训练赛第七场 I Chessboard（组合数学）
题目链接：https://ac.nowcoder.com/acm/contest/887/I题意：给定n，m要求在一个k*k的正方形内放一些球，正方形里每个1*1的格子至少放m个球，且任意不同行不同列的球的和是相等的且小于等于n，问可行的任意k*k的正方形有多少。数据范围：1<=n,m<=2000思路：我们计“选择大小为k∗k的棋盘，每个方格放的玻璃球数都不小...
2019-08-12 18:56:54
127
原创 2019hdu暑假多校训练赛第七场1006 Final Exam hdu6651（思维）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6651题意：有n道题总分是m，老师要求学生至少做出k道，每道题的复习时间是题目分数+1才能做出这道题，问最少复习多少时间。数据范围：0≤m≤1e9,1≤k≤n≤1e9思路：老师出题要卡掉学生最多的题，那么就把学生复习时间最少的n-k+1道题卡掉那么学生就不能完成任务，那学生就必...
2019-08-12 18:38:16
784
7
原创 2019牛客暑假多校训练赛第七场 E Find the median（权值线段树）
题目链接：https://ac.nowcoder.com/acm/contest/887/E题意：给出一个空集合，每次给出一个l,r的区间将l,r的这些数全部扔进区间内，每次要求输出此时的中位数是多少，若是集合是偶数个数则输出小的那个中位数。数据范围：1<=N,l,r<=4e5思路：首先离散化一下，然后进行类似上一篇博客那样建树，及线段树的每个节点都是一个左闭右...
2019-08-11 15:55:11
196
原创 2019牛客暑假多校训练赛第八场 E Explorer（线段树+并查集）
题目链接：https://ac.nowcoder.com/acm/contest/888/E题意：给定n个点m条无向边，每条边有四个参数，两个端点编号，还有一个size的范围l,r。有多少合法的size可以从1走到n。数据范围：1<=n,m<=1e5,1<=u<v<=n,1<=l<=r<=1e9思路：首先对size离散化左端点...
2019-08-11 15:31:25
269
2
原创 2019牛客暑假多校训练赛第八场 J Just Jump（思维dp）
题目链接：https://ac.nowcoder.com/acm/contest/888/J题意：有一只青蛙在0位置处，他想跳到L位置处，但是路上会受到一些攻击，这只青蛙在出发前就知道自己在跳第几次的时间时哪一个位置会受到攻击，并且青蛙每次跳的距离要大于等于d，问青蛙安全（不受一次攻击）跳到L处的方案数数据范围：1≤d≤L≤1e7,1≤t,p<L,1≤m≤3000，mod=99...
2019-08-11 10:48:38
243
原创 2019牛客暑假多校训练赛第八场A All-one Matrices（单调队列）
题目链接：https://ac.nowcoder.com/acm/contest/888/A题意：给出一个n*m的01矩阵，问用最少能选出多少子矩阵使得这些子矩阵不是其他子矩阵的子矩阵（可以理解成任意个数的必要质蕴涵项有多少）数据范围：1<=n,m<=3000思路：首先我们可以定义一个H二维数组代表向上的最长连续1的个数，再定义一个L数组代表，当前枚举a[i][j]时...
2019-08-10 19:43:33
197
原创 2019牛客暑假多校训练赛第七场H Pair（数位dp）
题目链接：https://ac.nowcoder.com/acm/contest/887/H题意：给定A，B，C问在[1,A]和[1,B]中有多少对x,y满足x&y>C或者x^y<C.数据范围：1<=A,B,C<=1e9思路：数位dp，定义一个dp[len][lim1][lim2][ok1][ok2][za][zb]。len代表当前枚举的二进...
2019-08-09 17:19:48
195
原创 2019牛客暑假多校训练赛第五场E independent set 1（状压dp）
题目链接：https://ac.nowcoder.com/acm/contest/885/E题意：求一个n的点m条边的所有子图的最大独立集的大小之和，子图共有2^n个。数据范围：2<=n<=26,0<=m<=n*(n-1)/2思路：对于此题虽然子图很多但是点数很少，26可以考虑dp的思想来减少复杂度。所以状压一下就好了26位刚好可以代表每一个点是否选...
2019-08-08 20:19:42
304
原创 2019hdu暑假多校训练赛第六场1002 Nonsense Time hdu6635（LIS）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6635题意：给出大小为n的a数组（每一个a[i]都不相同），再给出一个大小为n的b数组，b数组的中的b[i]代表a数组中下标为b[i]的数字可以用，对于每次输入b[i后]求一个新的最长上升子序列的长度，此题数据是随机的。数据范围：1≤T≤3，1≤n≤50000，1≤ai≤n,1<=b...
2019-08-08 19:23:36
276
原创 2019牛客暑假多校训练赛第七场C Governing sand（暴力）
题目链接：https://ac.nowcoder.com/acm/contest/887/C题意：给出n种树和n个h[i],c[i],p[i]代表每种树的高度，砍掉一棵的花费，树的个数。现在要求砍掉一部分树，使得最高的树的个数大于总树木的一半。数据范围：1<=n<=1e5,1<=Hi<=1e9,1<=Ci<=200,1<=Pi<=1e9...
2019-08-08 19:03:35
329
原创 2019hdu暑假多校训练赛第六场1005 Snowy Smile hdu6638（线段树区间连续子段和最大，区间合并）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6638题意：在一个二维平面内给出n个点每个点有权值，要求画一个矩形使得这个矩形内的点的权值和最大。数据范围：1≤T≤100，1≤n≤2000，−1e9≤xi,yi,wi≤1e9,∑n≤10000思路：首先离散化，对于每次点数最多是2000个所以离散化后最大是一个2000*2000...
2019-08-07 19:43:26
219
原创 2019hdu暑假多校训练赛第五场1002 three arrays hdu6625（字典树+贪心）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6625题意：给出两个长度为n的数组a,b，让两个数组中的数字一一匹配做异或运算，形成第三个数组c，就出字典序最小的c数组。数据范围：T≤1000，1≤N≤1e5思路：对于两个数组分别建一棵字典树，字典树上是对于每个数字的二进制串，从高位到低位建，然后对与两棵字典树一直往下找对应二...
2019-08-07 11:59:52
172
原创 hdu 6521 Party （吉司机线段树）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6521题意：给定n,m表示有编号1~n的人，m次询问，每次询问给出l,r问这个区间内的人有多少两两组合在之前没有出现过，对于每次询问输出符合的组数。例如[1,4] 可以有 1-21-3 1-4 2-3 2-4 3-4 6种再给你[2,5] 则只有 2-53-54-5 3种(其余的上面已...
2019-08-07 09:49:58
266
原创 hdu 6252 Subway Chasing (差分约束)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6252题意：给出n个点，i-1到i的距离是不确定的，给出x代表两个人的距离，现在给出m条约束条件，每次给出A，B，C，D代表第一个人在区间（A,B）段，第二个人在区间（C,D）段，两个人的距离始终是x保持不变，求出一组每两个点距离都符合的可行解数据范围：1≤T≤30，1≤N,M≤2000，...
2019-08-06 16:51:22
163
原创 2019牛客暑假多校训练赛第五场F题 maximum clique 1 （最大团，补图最大独立集）
题目链接：https://ac.nowcoder.com/acm/contest/885/F题意：给出n个数，且每个数都不同，要求找出最多的一个子集使得其中任意两个数的二进制位至少有两个不同，并输出这个集合数据范围：1≤N≤5000,1≤ai≤1e9思路:首先把这n个数按照二进制位里1的个数分为奇数个1和偶数个1的集合，对于奇数个1的集合里任意两个数都是满足至少有两位二进制位不...
2019-08-05 22:12:40
128
原创 2019hdu暑假多校训练赛第五场1005 permutation 1 hdu 6628（全排列）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6628题意：给定n和k,要求用1到n求出一个序列使得这个序列后一项减前一项形成的n-1长度的序列的字典序最小。数据范围：1≤T≤40，2≤N≤20，1≤K≤min(1e4,N!)思路：首先字典序最小的序列一定是n,1,2,3.........n-2,n-1这样的。再考虑8的阶乘是40...
2019-08-05 21:23:53
560
6
原创 2019hdu暑假多校训练赛第五场1004 equation hdu 6627（数学思维）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6627题意：给出长度为n的两个序列a[i],b[i]，再给定一个C值，让求出所有满足 的x的解，输出结果为分数形式。数据范围：1≤T≤50，1≤N≤1e5 ，1≤ai≤1000，−1000≤bi≤1000，1≤C≤1e9思路：我们可以设定，此时相当于我们获得了n个带绝对值的...
2019-08-05 18:27:14
643
原创 2019牛客暑假多校训练赛第五场I题 three points 1 （思维）
题目链接：https://ac.nowcoder.com/acm/contest/885/I题意：给定w,h,a,b,c，找到一组点x,y,z在[0,w][0,h]内的矩形里，且满足x和y的距离是a，x和z的距离是b，y和z的距离是c.思路：首先枚举三个点在原点处，然后让剩下两个点任意一个固定在某条边上，算出第三个点的位置看是否合法，暴力枚举一下即可，注意此题要控制好精度。#i...
2019-08-04 14:59:51
369
原创 2019牛客暑假多校训练赛第五场H subsequence 2 （拓扑排序）
题目链接：https://ac.nowcoder.com/acm/contest/885/H题意：给定一个n，问是否存在一个长度为n的字符串满足下面的条件，给定一个m代表此字符串包含的字符是从'a'到‘a’+m-1这些种,后面给出m(m-1)/2个长度为2的不同字符的字符串，再给出由这两个字符组成的字符串。根据这些条件也就是每种字符的个数和字符间的相对位置构造出一个长度为n的子符串，不存在的话...
2019-08-04 13:39:32
178
原创 2019牛客暑假多校训练赛第六场D Move （假二分）
题面链接：https://ac.nowcoder.com/acm/contest/886/D题意：给定n个物品，k个体积相等的盒子，求一个最小体积使得所有的物品都可以装到盒子里。装盒子要满足有大的就装大的，没有大的才能装小的的策略思路：首先本题不符合单调性，对于下面这个样例15 539 39 39 39 39 60 60 60 60 60 100 100 100 100 10...
2019-08-04 10:23:08
238
3
原创 2019牛客暑假多校训练赛第六场G题 Is Today Friday? （全排列）
题目链接：https://ac.nowcoder.com/acm/contest/886/G题意：给定由A到J组成的字符串，A到J唯一代表0到9中的数字（双射），问是否存在一个合法的双射使得所有的给定的字符串都是星期五（现实中的星期五），并且要使得A到J对应的0到9的字典序最小思路：运用蔡勒公式，然后从字典序最小的开始全排列一个一个判断#include <bits/std...
2019-08-04 10:10:46
331
原创 2019hdu暑假多校训练赛第三场1007 Find the answer HDU 6609 （树状数组）
题意：给定一个长度为n的序列，一个k值，要求在从第1项到第i项中选择若干项且必须包括第i项使得选择的项的和<=k,问使得不被选的项最少为多少。思路：贪心的想一下，从第1项到第i项必须选择第i项，其余选的项的数值越小越好，这样我们就可以选择出尽可能多的项，那么如何才能很快的选出这些小的项呢。首先由于a[i]的数据范围是1e9，我们需要先进行离散化一下，离散化不要用unique函数...
2019-08-04 08:53:34
121
原创 2019江西省赛A题 HDU 6567 Cotree 树的重心（树形dp）
题意：给定n的点，n-2条边，也就是给出了两棵树，要求加一条边连接两棵树并使得连接好的这棵树上任意两点距离和最小。思路：先取任意一点bfs来分开两棵树，此时假设第一棵树有n1个点，第二棵树有n2个点，分别对这两棵树进行树形dp，dpsum[i]记录在本棵树上其余点到点i的距离和。分别找出两棵树上的最小的dpsum值，此时连接这两个点就是最优解。此时要统计任意点距离和了(后来发现树的重心的...
2019-08-04 08:52:01
348
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人