- 博客(49)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 《算法竞赛进阶指南》数论篇
下述理论主要参考书目： 电子版pdf:算法竞赛进阶指南(p133-150)文章目录下述理论主要参考书目： [电子版pdf:算法竞赛进阶指南(p133-150)](http://www.j9p.com/down/536233.html)首先补充两个前置知识：约数和最大约数有关性质，可选择性看~有关素数筛的算法 [埃式nlog(n)nlog(n)nlog(n)&欧拉素数筛o(n)o(n)o(n)&大区间素数筛](https://blog.csdn.net/weixin_45819197/art
2023-12-08 11:40:37
1127
原创 《算法竞赛进阶指南》------图论篇
题意：从1到N修一条电缆，有p对电线杆之间是可以连接的，电信公司可以提供k条电缆，其他的由John提供，求john提供的电缆的最长的那根的长度（ret）。留下一个小疑问点： int 和 ll a=0x3f3f3f3f 在这道题中 使用ll a=0x3f3f3f3f 会错。满足d[n]< k ，sum是一个符合的结果。题意：从1到达n号，在沿途中可选一点购买水晶球，在此之后可卖出去水晶球。外层循环k开始，对所以的路径刷新，添上k和步添上k。思路：实则是求最短最长的边。思路：弗洛伊德， 回溯路径。
2023-12-08 11:39:20
1311
原创 《算法竞赛进阶指南》------图论篇3
文章目录0x14 岛屿(基环树直径+拓扑排序+树的直径)0x14 岛屿(基环树直径+拓扑排序+树的直径)岛屿题意：n个岛屿，n座桥。问基环森立直径之和。思路：用BFS遍历，找出每一个基环树，用拓扑排序求出环上的子树的直径，和环上点的集合，顺便得到该环的点为根的树，以根为起点的最长链。再用双指针和优先队列求基环树直径。ACcode详解：#include<bits/stdc++.h>#define ll long long#define ld long double#defin
2021-12-24 17:34:12
744
原创 《算法竞赛进阶指南》------数论习题篇1
文章目录练习9：XOR BZOJ2115 （* 线性基。求图中异或和，可谓经典中的经典）练习10：新Nim游戏 BZOJ3105 （* NIM进阶版 NIM博弈+线性基）练习11：排列计数 BZOJ4517 （* 错位排序）练习12: Sky Code （* 容斥原理$莫比乌斯反演 经典）练习16 魔法珠 CH3B16 （SG博弈）练习17：Georgia and Bob (* NIM博弈三定理)**错误思路**：**NIM博弈三定理**：**正确思路**：练习9：XOR BZOJ2115 （*
2021-12-23 10:53:22
2336
原创 《算法竞赛进阶指南》------图论篇0
文章目录0x01 Telephone Lines POJ - 36620x02 P1073 [NOIP2009 提高组] 最优贸易0x03 道路和航线 BZOJ22000x04 Sorting It All Out POJ - 1094 topo0x05 Sightseeing trip POJ - 1734 最小环问题0x06 Cow Relays POJ - 3613 S到E经过k条边的最短路0x07 走廊泼水节 （Kruskal）0x01 Telephone Lines POJ - 3
2021-12-23 10:39:53
418
原创 《算法竞赛进阶指南》------图论篇2
文章目录0x0E 雨天的尾巴 洛谷p4556(线段树合并+树上差分+树链lca)0x0E 雨天的尾巴 洛谷p4556(线段树合并+树上差分+树链lca)雨天的尾巴详细视频讲解题意：一个由n座房屋形成的树状结构，然后救济粮分 mmm 次发放，每次选择两个房屋 (x,y)(x, y)(x,y)，然后对于 xxx 到 yyy 的路径上(含 xxx 和 yyy)每座房子里发放一袋 zzz 类型的救济粮。然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。输入：输入n−1n
2021-12-21 17:15:29
1241
原创 2021CCPC Jumping Monkey(并查集)
文章目录题意思路官方题解传送门 Jumping Monkey题意在一颗树上，以k节点起始，能跳到v节点，然后接着跳。能跳 需满足条件：在k到v的最短路径上v节点点权最大。问以u节点起始，能跳跃的最多多少个节点。思路并查集， 反向思考，从权值最小的开始枚举。官方题解ACcode#include<bits/stdc++.h>#define ll long long#define ld long double#define ull unsigned long long#de
2021-10-11 00:33:22
194
原创 《算法竞赛进阶指南》------图论篇1
文章目录0x01 Telephone Lines POJ - 36620x01 Telephone Lines POJ - 3662Telephone Lines 题意：从1到N修一条电缆，有p对电线杆之间是可以连接的，电信公司可以提供k条电缆，其他的由John提供，求john提供的电缆的最长的那根的长度（ret）。思路：实则是求最短最长的边。二分结果(sum)。对于 边值>sum, 电信公司需要提供电缆。用djk 计算 1->n 路径上的最短路径。 满足d[n]< k
2021-09-29 18:49:13
330
原创 《算法竞赛进阶指南》------数论习题篇0
文章目录练习1：Gcd练习2 Longge's problem练习3： 青蛙的约会练习1：Gcd传送门题意：给定整数N求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对,N<=1e7题意：给定整数N求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对,N<=1e7题意：给定整数N求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对,N<=1e7.思路：我们可以依次枚举素数，对于一个素数P,如果gc
2021-08-21 16:20:39
266
1
原创 《算法竞赛进阶指南》数论篇(3)-组合计数，Lucas定理,Catalan数列,容斥原理，莫比乌斯反演，概率与数学期望，博弈论之SG函数
组合计数排列数从nnn个不同的元素中依次取出mmm个元素排成一列，产生的不同排列的数量为：AnmA_n^mAnm=n!(n−m)!\frac{n!}{(n-m)!}(n−m)!n!组合数从n个不同的元素中取出m个组成一个集合(不考虑顺序),产生不同集合的数量为：CnmC_n^mCnm=n!(n−m)!m!\frac{n!}{(n-m)!m!}(n−m)!m!n!一些简单性质：1.Cnm=Cnn−mC_n^m=C_n^{n-m}Cnm=Cnn−m2.Cnm=Cn−1m+Cn−1m−
2021-08-20 14:20:37
406
原创 《算法竞赛进阶指南》数论篇(2)-扩展欧几里得，线性同余方程，中国剩余定理，高次同余方程，矩阵乘法,高斯消元，线性空间,线性基
扩展欧几里得对于任意整数a,b,存在一对整数x,y，满足ax+by=gcd(a,b).对于任意整数a,b,存在一对整数x,y，满足ax+by=gcd(a,b).对于任意整数a,b,存在一对整数x,y，满足ax+by=gcd(a,b).证明：代码如下：int exgcd(int a,int b,int &x,int &y){ // a>b a*x+b*y=gcd(a,b); if(b==0){ x=1; y=0; return a;
2021-08-05 00:10:05
225
原创 2021牛客暑期多校训练营5 题解
文章目录King of Range题意：思路：代码如下(详解)King of Range题意：给一数组，问有多少个区间的极差值>k>k>k思路：对于区间[l,r][l,r][l,r]，我们可以先固定右端点rrr,寻找离rrr最近的lll且满足区间[l,r][l,r][l,r]极差值>k>k>k.于是我们用到了两个队列，分别是递增队列和递减队列。队列存放aaa数组的下标。关于递增和递减队列，都有左右端点。两个队列的左端点必定是极差最大值。开始移动两个队列的左
2021-08-01 12:51:12
234
原创 1003 Forgiving Matching
文章目录1003 Forgiving Matching题意思路PS：不太懂FFT，但又想知道原理。传送门 [FFT详解](https://blog.csdn.net/weixin_45819197/article/details/114890441)1003 Forgiving Matching题意给两个字符串s1s2(len1>=len2)s1s2(len1>=len2)s1s2(len1>=len2)问s2s2s2与是s1s1s1的子串进行匹配，在允许出错kkk个字符情况下，最
2021-07-29 11:00:02
108
原创 2021“MINIEYE杯”中国大学生算法设计超级联赛(2)补题
文章目录1010 I love permutation题意：给一个素数p和一个整数a。思路1010 I love permutation题意：给一个素数p和一个整数a。用bx=(a∗x)b_x=(a*x)bx=(a∗x)%p; 构建一个b序列，长度p-1(1<=x<=p−11<=x<=p-11<=x<=p−1)求b序列的逆序对数模2的结果。I love permutation思路结果是对二取余。 说明说明逆序对数要是奇数(输出1)或偶数(输出0)首先观察
2021-07-25 01:32:07
167
原创 《算法竞赛进阶指南》数论篇(1)-最大公约数，素数筛，欧拉函数，同余，欧拉定理，BSGS
下述理论主要参考书目： 电子版pdf:算法竞赛进阶指南(p133-150)文章目录下述理论主要参考书目： [电子版pdf:算法竞赛进阶指南(p133-150)](http://www.j9p.com/down/536233.html)首先补充两个前置知识：约数和最大约数有关性质，可选择性看~有关素数筛的算法 [埃式nlog(n)nlog(n)nlog(n)&欧拉素数筛o(n)o(n)o(n)&大区间素数筛](https://blog.csdn.net/weixin_45819197/art
2021-07-23 14:05:26
525
原创 OS总结!
多道程序设计 传送门多道程序设计：允许多个程序（作业）同时进入一个计算机系统的内存并启动进行交替计算的方法，也就是，计算机中可以同时存放多道程序，从宏观上来看它们是并行的，多道程序都同时处于运行过程中，但都未运行结束，但是微观上是串行的，轮流占用CPU交替执行，引入多道程序设计技术的根本目的是提高CPU的利用率，充分发挥计算机系统部件的并行性。利弊总结：1.提高了CPU的利用率2.提高了内存和I/O设备的利用率3.改进了系统的吞吐率4.充分发挥了系统的并行性5.主要缺点是延长了作业周转时间三
2021-07-17 09:53:50
376
原创 AC自动机(Trie 板子)&后缀数组模板（解决原串与子串问题）
大自然的帮运工使用板子注意事项：注意：1.串是否全是小写字母2.根节点为13.节点数不超过maxn4.多组数据注意 清空5.复杂度嘛。。。。。建树o(n*len)前置知识:Trie树需求：给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。输入n个模式串， 一个原串输出结果： 原串中含有模式串的个数。in：6abcdcdcdcdacaab abcdacout：5#include<bits/stdc++.h>#define maxn
2021-05-26 22:42:41
196
原创 矩阵模板（矩阵快速幂算法用法）
矩阵快速幂算法应用矩阵解线性方程组入门视频在引入矩阵快速幂之前先引入问题：想必大家都不陌生斐波那切数.数字公式表达：f(n)= f(n-1)+ f(n-2) , f(1)=1; f(0)=0; n>=2;嗯很美观~ 然后呢？假如n很大呢， 比如 1e13 呢? 嗯哼? 能在一秒呢计算出吗。显然不可能呢~来–上矩阵，解决。先别急；来个简单例子 温习下线性方程组：2x+3y=zx-y=2z这里x，y，z均是未知数那么用矩阵表示:f(n-1) +f(n-2)=f(n);
2021-05-07 22:31:12
310
原创 【模板】最大流详细证明(Dinic+当前弧优化)(附:题- How Many to Be Happy?)
初识网络流-最大流==最小割什么是网络流网络流(network-flows)是一种类比水流的解决问题方法，与线性规划密切相关。网络流的理论和应用在不断发展。而我们今天要讲的就是网络流里的一种常见问题——最大流问题。如下图：最大流 (Dinic)进而引出了最大流问题：从源点出发到达汇点，所能流入最大的流量。增广路那么我们如何知道S(源点)---->T(汇点)的最大流量呢？我们的思路是：1.先找出一条增广路径，得到这条路径权值的最小值mins，之后该路径边上的流（权值）的值减去min
2021-04-06 21:12:19
1250
原创 题-Slot Machines（KMP, next）
Slot Machines传送门什么是KMP？1.现在我们面临这样一个问题：有一个文本串s和一个模式串p，现在要查找p在s中的位置。朴素算法：o(n2n^2n2)；用KMP算法实现(对next未优化) o(k*n)；在朴素算法中：当s[i]!=a[j]； 直接从i-j的位置开始.这样就很麻烦很重复。引入next数组，存放前缀和后缀的最大长度。怎么求next的数组呢？？两种写法：1.next[i]表示 0~i-1的串中前后缀相同的最大长度。 (初始下标为0)2.next[i]表示1~i的
2021-03-31 14:55:41
217
原创 关于我会不会dfs这档子事（题：Connect,Game Map）
2021年度训练联盟热身训练赛第四场 补题connect:好想难实现Game Map:难想好实现共同点都是dfs。总结1.第一种dfs：常规遍历void dfs(int x,int y,int flag){ a[x][y]=flag; for(){ dfs(i,j,flag); } a[x][y]=0;}2.第二种dfs：满足条件直接退出(不再往下走)后面题目Connect3的下棋：就是这么dfs。如果胜利就结束(当前状态)void dfs(int x,int
2021-03-30 19:54:49
92
原创 题-J. Burnished Security Updates(二分图)
二分图定义与判定在做这道题时，首先我们先了解二分图的基本概念。二分图定义：将图里的顶点分为两个集合，且集合内的点没有直接关联(也就是同一集合里的点不相连).二分图性质上图就是一个二分图,将图的所有顶点分为u,v集合. u,v集合互不相连.我们先从二分图的性质出发：1.能形成回路的：其回路长度必然是偶数。2.不能形成回路的：无要求3.不管从什么点出发必然都是u-v v-u (或者：v-u u-v)这样来回循环。 也就是一个点的左右邻边是与他相对的集合里的点。从上图我可以发现有以下特点:
2021-03-27 11:40:27
139
原创 L. Two Buildings(决策单调性 )详解
2020-2021 ACM-ICPC, Asia Seoul Regional Contest 补题题目传送门朴素算法（爆搜）：o(n2n^2n2)决策单调：o(n*log2n\log_2^nlog2n)题意:给一长度n(n<=1e6)的数组，hih_ihi<=1e6,求max(hih_ihi+hjh_jhj)∗(j−i) 1≤i<j≤n.思路：直接求很难，进行公式变换 ( hjh_jhj - ( hih_ihi ) )∗(j−i) 1≤i<j
2021-03-19 22:37:55
638
3
原创 FFT---（递归版和迭代版）( H. Needleand 和H.Rock Paper Scissors)
FFT快速傅里叶变换(加速多项式乘法)传送门多项式乘多项式 常规想法：时间o(n2n^2n2) FFT时间缩减至o(nlognnlognnlogn);多项式：f(x)=a0x0+a1x1+a2x2+........+anxn;f(x)=a_0x^0+ a_1 x^1 +a_2x^2+........+a_nx^n;f(x)=a0x0+a1x1+a2x2+........+anxn;前置知识1.点值表示法：f(点，点值) 表示一对适用(x0,f(x0)),x1,f(x1)),x2,f(x
2021-03-16 20:39:53
892
原创 D. GCD of an Array(multiset+map)
D. GCD of an Array(multiset+map)D. GCD of an Array总结：1.multiset使用的一些细节2.分解质因数的想法3.(b/a)%mod=( b * a^(mod-2) ) % mod;multisetmultiset是多集合，与set区别在于，它是可以重复插入，就这点区别. 有以下的操作方法： insert（传入数值,插入数值） find（传入数值,寻找值返回最先出现的地址） erase（传入数值,删除一数值，如果有多个同
2021-03-11 18:39:21
99
原创 区间最大公约数（板子）
区间最大公约数(线段树，树状数组，差分)感悟：1.熟练线段树模板: 单点的查询2. gcd(a,b)=gcd(a,b-a); gcd(a,b,c)=gcd(a,b-a,c-b); gcd(a1,a2,a3,a4,a5…an)=gcd(a1,a2-a1,a3-a2,a4-a3,…an-an-1);注意：求区间[l,r]的最大公约数要有个原值保证差分的gcd有效，（后续详细说明）.3.差分,树状数组 总结: 在[l.r]添加值，差分：相对值的不变 添加了值凸起,所以：b[l]加，b[r+1
2021-03-10 18:10:56
450
原创 单源点最短路径-迪杰，优先队列
迪杰特斯拉，优先队列总结：1.图论之一:迪杰特斯拉算法—联想(结构体edge, 结构体node,访问点标记vis,最短距离arr数组).贪心策略:先贪目前的最短的路径，确定下一个点的最短距离，然后再从目前的确定的路径中选出最短路径，依次这样所以用到优先队列.2. 优先队列(priotity_queue)，队头top()， 默认排序从大到小. 参考内容普通队列(queue) 队头front(). 根据先后进队顺序排放。3.结构体内比较在优先队列内比较恰恰相反。单源点最短路径想法,原理：
2021-02-23 17:05:54
333
1
原创 线段树-模板
树状数组and线段树感悟：1.了解线段树2.区间修改，查询 以及建树来一道题目理解理解：洛谷题目链接线段树视频讲解配有代码详解题意：题意很简单，给一a数组，对a数组有两种操作1,和2,输出操作2的结果.1 x y k：将区间 [x, y][x,y] 内每个数加上 k。2 x y：输出区间 [x, y][x,y] 内每个数的和。思路: 线段树的区间修改和区间查询。简单介绍一下线段树：用一tree数组存放每个a数组一个区间和的值。 下面拿一张图直观了解下线段树的大致模样。tr
2020-12-20 16:20:49
53
1
原创 题-芭芭拉冲鸭~(续)(LCA最近公共祖先)
LCA算法求解最近公共祖先北京信息科技大学:J题题目链接树感悟：1.加深dfs的印象2.LCA算法（最近公共祖先）3.倍增4.ar数组的巧妙题意：芭芭拉这次来到了一棵字母树，这同样是一棵无根树，每个节点上面有一个小写字母。芭芭拉想知道，自己从x冲刺到y，从x走到y收集所有字母，选择其中一部分字母组成一个回文串，这个回文串的最大长度是多少？啥意思呢，简单的讲走过的路不能再走的意思咯，而且注意了，从x到y的路径是唯一的，因为是树型结构。（脑海里想象后者画几个树验证一下，就明白是唯一的了
2020-11-25 00:54:08
1133
原创 芭芭拉冲鸭~(dfs树两点最大距离)
树上两节点的最大距离牛客网：题目链接：感悟：1.dfs的再理解，对树的遍历，用深度标记到根节点的距离。2.树两点的最大距离的求解。题意：给定一棵无根树，树上每个节点被染成了红色或绿色或蓝色。（R=红色，G=绿色，B=蓝色）一条边两个节点的颜色不同芭芭拉才能冲刺（即能形成一条边），问芭芭拉在这一颗树上能冲刺的最远距离（不能重复经过一条边） 重点喔思路：实际是求树上两节点的最大距离，由于颜色相同的节点芭芭拉不能通过，就会使得树分割成多颗树，保留根节点和子节点，用dfs遍历树的最大和
2020-11-22 18:33:03
1877
原创 题-宵暗的妖怪（dp）
宵暗的妖怪牛客网：F题目链接题意：给定一数组： 获得的饱食度最大值是多少？ 从数组中选取一个s[i] 那么他的左右都会被暗黑吞噬，意味着不能被选取了。且i能选择首尾（选择了有一部分就不能吞噬了呢）。思路：动态规划,s数组表示每个值。用a数组，表示前i个的饱食度最大值。dp三步走:1.无后效性，嗯。。2.赋初值3.后面结果需要用到前面的结果a[i]=max(a[i-1],a[i-3]+s[i-1]);比较两个数 前一个饱食度的值，和需要添加的饱食度+暗黑吞噬值。代码如下：#i
2020-11-22 17:30:07
176
原创 组合数取模&逆元&Lucas定理
组合数取模(模板)初入数论的萌新分享一下我的组合数取模的想法.感悟：1.运用费马小定理2.分数如何取余。3. lucas定理：*C(n,m)%p=C(n/p,m/p)C(n%p,m%p);主要针对p是较小的数.p必须是素数，p必须是素数，p必须是素数（说三遍）费马小定理如下：(待会组合数取余用得上的)这里是引用费马小定理： p必须是整数( (x)^p ) % p=(x) % p;(x^p)%p=(x)%p; -----1式一式可推出：(x^(p-1))%p=1; //
2020-11-22 17:15:54
263
原创 题—C. Engineer Artem
奇技淫巧篇1题目链接：codeforces：C. Engineer Artem题意：给一数组，可以对该数组的每个值加1或者不加，每个值只能操作一次，问：打印修改后的数组，a[i][j]值与相邻值不一样。相邻位置比如：a[i-1][j],a[i][j-1],a[i+1][j],a[i][j+1].思路： 灵感来自0,1数组。 就比如5x5的数组。5 50 1 0 1 01 0 1 0 10 1 0 1 01 0 1 0 10 1 0 1 0不难发现该就数组就满足上述题意。该值没
2020-11-17 17:01:06
85
原创 题—D. Catching Cheaters（最大子序列问题）
动态规划的新认知（初步了解）心得：一.遇见动态规划的三步走：1.得证当前有最优解（要分析他的可行性）：局部最优解推出整体 最优解2.无效性：博主目前认为：现在的结果不会对之前的结果有影响。部分dp无非是这是三种 dp[i][j],dp[i-1][j],dp[i][j-1]，他们对dp[i][j]的影响。3.初始化初始化初始化（dp数组初始化，重要事情说三遍 ）因题意初始化而不同。二.最大公共子序列的求解问题题目链接题意：给两字符串a，b，已知长度。x是a的子串，
2020-11-16 23:24:10
210
原创 割点（tarjan算法）
割点(无向图).题目链接:洛谷tarjan遍历过程视频链接心得：1.图用dfs的遍历2.Tarjan算法求非强连通图。3.在dfs中如何加东西：dfs（i）后面语句怎么写？每次dfs完成后，就是对前面的影响，像栈一样。割点的定义：在一个无向图里，一个顶点去掉，及其去掉该点的所有边,剩下的图不连通。下图的无向图的割点为：0,3。ps：下图实际是无向图，把指向的箭头去掉哈，就成了无向图。代码如下：#include<iostream>#include<vecto
2020-11-10 16:05:11
7823
1
原创 埃式&欧拉筛&大区间素数筛
埃式素数筛定义：前n个数有多少是素数。并且用prime[]存素数。复杂度O(nloglogn).感悟：任何一个数都可以由若干个素数乘积表示。eg: 100= 2* 2 * 5 * 52.一个数n=a*b.那么a<sqrt(n),b>sqrt(n).#include<iostream>using namespace std;const int maxn=1e7; //仅仅限于1e7，太大就超时。 int prime[maxn]; //存放素数 i
2020-11-07 18:16:51
279
原创 题—Intelligent Warehouse
2020小米选拔赛1 A题题目链接解决思想：dp的优化，线性筛感悟：对dp理解。1.当前dp的改变不重复，每次的改变是独立的。2.当前的dp改变对后续dp的影响。3.dp是套娃，验证dp的正确性。题意：给n个数。特别注意给得数据的取值范围。选出一组满足：任意两个数有倍数关系，eg:可以组成一组 1和2,12,36。 4和12,36,72.不能组成一组： 1和2,12,36,48.输出一组数中最多的个数。思路：可以发现符合的一组数：前一个数是后一个数的倍数就可。不符合的36,4
2020-11-07 15:29:15
133
原创 题-Knapsack
2020小米选拔赛2-H题（背包问题）算法：dp优化。主要解决的问题：一个背包装下的物品价值和最大。背包最大承受量m，每个物品都有重量和对应的价值。怎么装才能使得背包价值最大？题目链接反思：课后补题，没做出来，题目做少了。题意：多组输入，每组n个物品，m的容量。求背包价值最大。思路：测试数据到了1e5级别了，复杂度高，那么就要对动态规划优化主要算法：常规动态规划,时间复杂度（o（n*m））；for(int i=1;i<=n;i++){ for(int j=m;j>=
2020-11-06 20:45:42
151
原创 题—Subsequence Pair
求最大公共子序列数（+dp）题目链接：牛客网小米选拔赛2，I题。最大公共子序列数定义：给两字符串x，y，如果Z既是X的子序列，又是Y的子序列，则称Z为X和Y的公共子序列最大公共子序列数是在所有z中长度最大。eg：x:abcbxyzy:bdcaxyz 最大z: bcxyz 长度5.ps：dp，字符串，卡常。题意：给两字符串x,y：从x，y中分别选出a，b子序列并且字典序:a<b.求len（a+b）之和的最大值。多组数据输入。思路： x的下标 i,(x[i])， y的
2020-11-06 10:58:31
95
原创 题—2020（二分+贪心）
2020牛客网小米选拔1 A题题意：给一只含有2,1,0的字符串，现在要求选出最多子序列为"2020"的个数。思路：二分。每次二分，判断个数是否有。之后贪心：假如该串要你判断是否有5个"2020"，既然要确定有没有5个，那么串只要存在5个"2020"就行了。串的前5个2分别为5个"2020"的第一个2.证实这样贪心是正确的。举个例子：1表示第一个"2020"3表示第三个"2020"判断有没有四个"2020"。串下标: 1 2 3 4 5 6 7 8 9 10 11
2020-11-02 17:03:38
66
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人