精华内容
下载资源
问答
  • 蓝桥杯算法竞赛试题.

    2013-11-22 15:11:11
    蓝桥杯算法竞赛试题,不多说,对你竞赛一定会有好处的,这是一些训练逻辑思维的算法试题,希望对你有所帮助!
  • 蓝桥杯算法竞赛专题优质解析:KMP算法(搜索匹配优化) 如有建议,请联系:(1)QQ 群,849225619;(2)作者QQ,987599519 #------------------------------------------------------------ #作者:肖念昕 #时间:...

    蓝桥杯算法竞赛专题优质解析:KMP算法(搜索匹配优化)

    1.情境引入

    KMP本身不复杂,但网上绝大部分的文章较混乱。下面,从暴力匹配算法讲起,随后阐述KMP的流程 步骤

    next 数组的简单求解
    递推原理
    代码求解
    接着基于next 数组匹配
    谈到有限状态自动机
    next 数组的优化
    KMP的时间复杂度分析,
    最后简要介绍两个KMP的扩展算法。

    给大家一个清晰的KMP,希望更多的人不再被KMP折磨或纠缠。有何疑问,欢迎随时留言评论,thanks。
    


    2. 暴力匹配算法

    假设现在我们面临这样一个问题:有一个文本串S,和一个模式串P,现在要查找P在S中的位置,怎么查找呢?

    如果用暴力匹配的思路,并假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置,则有:

    • [1 ] 如果当前字符匹配成功(即S[i] == P[j]),则i++,j++,继续匹配下一个字符;

    • [ 2] 如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯,j 被置为0。

    int baoli(string s,string p) 
    {
    	int sLen = strlen(s);
    	int pLen = strlen(p);
    	int i = 0;
    	int j = 0;
    	while (i < sLen && j < pLen) {
    		if (s[i] == p[j]) { //①如果当前字符匹配成功(即S[i] == P[j]),则i++,j++
    			i++;
    			j++;
    		} else { //②如果错误(即S[i]! = P[j]),令i = i - (j - 1),j = 0
    			i = i - j + 1;
    			j = 0;
    		}
    	}
    	//匹配成功,返回模式串p在文本串s中的位置,否则返回-1
    	if (j == pLen)
    		return i - j;
    	else
    		return -1;
    }
    }
    

    举个例子,如果给定文本串S“BBC ABCDAB ABCDABCDABDE”,和模式串P“ABCDABD”,现在要拿模式串P去跟文本串S匹配,整个过程如下所示:

    1. S[0]为B,P[0]为A,不匹配,执行第②条指令:“如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0”,S[1]跟P[0]匹配,相当于模式串要往右移动一位(i=1,j=0)

    2. S[1]跟P[0]还是不匹配,继续执行第②条指令:“如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0”,S[2]跟P[0]匹配(i=2,j=0),从而模式串不断的向右移动一位(不断的执行“令i = i - (j - 1),j = 0”,i从2变到4,j一直为0)

    在这里插入图片描述

    1. 直到S[4]跟P[0]匹配成功(i=4,j=0),此时按照上面的暴力匹配算法的思路,转而执行第①条指令:“如果当前字符匹配成功(即S[i] == P[j]),则i++,j++”,可得S[i]为S[5],P[j]为P[1],即接下来S[5]跟P[1]匹配(i=5,j=1)

    1. S[5]跟P[1]匹配成功,继续执行第①条指令:“如果当前字符匹配成功(即S[i] == P[j]),则i++,j++”,得到S[6]跟P[2]匹配(i=6,j=2),如此进行下去

    1. 直到S[10]为空格字符,P[6]为字符D(i=10,j=6),因为不匹配,重新执行第②条指令:“如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0”,相当于S[5]跟P[0]匹配(i=5,j=0)

    1. 至此,我们可以看到,如果按照暴力匹配算法的思路,尽管之前文本串和模式串已经分别匹配到了S[9]、P[5],但因为S[10]跟P[6]不匹配,所以文本串回溯到S[5],模式串回溯到P[0],从而让S[5]跟P[0]匹配。

    而S[5]肯定跟P[0]失配。为什么呢?因为在之前第4步匹配中,我们已经得知S[5] = P[1] = B,而P[0] = A,即P[1] != P[0],故S[5]必定不等于P[0],所以回溯过去必然会导致失配。那有没有一种算法,让i 不往回退,只需要移动j 即可呢?

    答案是肯定的。这种算法就是本文的主旨KMP算法,它利用之前已经部分匹配这个有效信息,保持i 不回溯,通过修改j 的位置,让模式串尽量地移动到有效的位置。
    

    题解:

    #include<bits/stdc++.h>
    using namespace std;
    int baoli(string s,string p) 
    {
    	int sLen = s.size();
    	int pLen = p.size();
    	int i = 0,j =0 ;
    
    	while (i < sLen && j < pLen) {
    		if (s[i] == p[j]) { 
    			i++;
    			j++;
    		} else { 
    			i = i - j + 1;
    			j = 0;
    		}
    	}
    	if (j == pLen)
    		return i - j;
    	else
    		return -1;
    }
    
    int main()
    {
    	string s="BBC ABCDAB ABCDABCDABDE",p="ABCDABD";
    	cout<<baoli(s,p); 
    	return 0;
    }
    

    3.KMP算法

    3.1入门

    下面先直接给出KMP的算法流程(如果感到一点点不适,没关系,坚持下,稍后会有具体步骤及解释,越往后看越会柳暗明):

    • 假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置

    • 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;

    • 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移- 动了j - next [j] 位。

    换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值(next 数组的求解会在下文的
    3.3.3节中详细阐述),即移动的实际位数为:j - next[j],且此值大于等于1

    在某个字符失配时,该字符对应的next 值会告诉你下一步匹配中,模式串应该跳到哪个位置(跳到next [j] 的位置)。如果next [j] 等于0或-1,则跳到模式串的开头字符,若next [j] = k 且 k > 0,代表下次匹配跳到j 之前的某个字符,而不是跳到开头,且具体跳过了k 个字符

    • KMP算法
    int Kmp(string s,string p)
    {
    	int i = 0,j = 0;
    	int sLen = s.size();
    	int pLen = p.size();
    	while (i < sLen && j < pLen) {
    		if (j == -1 || s[i] == p[j]) {
    			i++;
    			j++;
    		} else {
    			j = next[j];
    		}
    	}
    	if (j == pLen)
    		return i - j;
    	else
    		return -1;
    }
    

    3.2next[]求法

    void GetNext(string p,int next[])
    {
    	int pLen = p.size();
    	next[0] = -1;
    	int k = -1;
    	int j = 0;
    	while (j < pLen - 1)
    	{
    		//p[k]表示前缀,p[j]表示后缀
    		if (k == -1 || p[j] == p[k]) 
    		{
    			++k;
    			++j;
    			next[j] = k;
    		}
    		else 
    		{
    			k = next[k];
    		}
    	}
    }
    

    逐步优化中!

    展开全文
  • 蓝桥杯算法竞赛专题优质解析:二分法、三分法 肖念昕 . 尊重原创 转载注明 . 如有建议,请联系:(1)QQ 群,849225619;(2)作者QQ,987599519 #------------------------------------------------------------ #...

    蓝桥杯算法竞赛专题优质解析:二分法、三分法

    .
    尊重原创 转载注明
    .
    如有建议,请联系:(1)QQ 群,849225619;(2)作者QQ,78983438
    #------------------------------------------------------------

    #作者:新零云
    #时间:2020-3-18日初稿(日后会维护内容)

    #------------------------------------------------------------

    1.1整数二分模板 - 普通

    在有序数列a[]中查找某个数x;如果数列中没有x,找它的后继。
    二分

    int sec(int a[],int n,int x)
    {
    	int left=0,right=n;   //这里是n  非n-1
    	while(left<right)
    	{
    		int mid=(right-left)/2+left;
    		if(a[mid]>=x) right=mid;
    		else left=mid+1;
    	}
    	return left;	
    } 
    

    .

    1.2整数二分模板 - STL - lower_bound()

    #include <bits/stdc++.h>
    using namespace std;
    int a[8]={1,2,3,5,6,7,9,10};
    int main()
    {
    	cout<<lower_bound(a,a+8,7)-a;
    	return 0;
    }
    

    .


    2.1简单例题

    ∎问题描述:
    输入n ( n≤100,000)个整数,找出其中的两个数,它们之和等于整数m(假定肯定有解)。题中所有整数都能用int 表示。

    #include <bits/stdc++.h>
    using namespace std;
    int a[100010];
    void sec(int a[],int n,int m)    //二分思想 核心
    {
    	int left=0,right=n-1;
    	while(left<right)
    	{
    		int sum=a[left]+a[right];
    		if(sum>m) right--;
    		if(sum<m) left++;
    		if(sum==m) 
    		{
    			cout<<a[left]<<"+"<<a[right]<<"="<<m<<endl;
    			left++;
    		}
    	}
    }
    int main()
    {
    	for(int i=1;i<=100000;i++) a[i]=i;
    	sec(a,100000,1587);
    	return 0;
    }
    
    

    .
    二分法的典型应用有:最小化最大值最大化最小值

    2.2进阶例题 - 最小值最大化(最小值尽量大)

    ∎问题描述:“进击的奶牛” - 洛谷
    在一条很长的直线上,指定n个坐标点(x1, …, xn)。有c头牛,安排每头牛站在其中一个点(牛棚)上。这些牛喜欢打架,所以尽量距离远一些。问最近的两头牛之间距离的最大值可以是多少。
    这个题目里,所有的牛棚两两之间的距离有个最小值,题目要求使得这个最小值最大化。
    .
    ∎题解
    二分思想:分析从小到大检查dis的过程,发现可以用二分的方法找这个dis。这个dis符合二分法:它有上下边界、它是单调递增的。

    .
    不知道为啥有三个测试点没通过

    #include <bits/stdc++.h>
    using namespace std;
    int n,c,x[10005]; //牛棚数量,牛数量,牛棚坐标
    
    bool check(int dis)  //当牛之间距离为dis时,检查牛棚够不够
    {
    	int cn=1,place=0;
    	for(int i=1;i<n;i++)
    	{
    		if(x[i]-x[place]>=dis)
    		{
    			cn++;
    			place=i;
    		}
    	}
    	if(cn>=c) return true;
    	else return false;
    }
    
    int main()
    {
    	scanf("%d%d",&n, &c);
    	for(int i=0;i<n;i++)   scanf("%d",&x[i]);
    	sort(x,x+n);
    	int l=0,r=x[n-1]-x[0];
    	int ans=0;
    	while(l<r)
    	{
    		int mid=(r-l)/2+l;
    		if(check(mid))  //当牛之间距离最小为mid时,牛棚够不够?
    		{
    			ans=mid;  //牛棚够,先记录mid
    			l=mid+1;   //扩大距离
    		}
    		else r=mid;  //牛棚不够,缩小距离
    	}
    	cout<<ans;
    	return 0;
    }
    
    

    .

    3.1实数二分模板

    const double eps =1e-7;        //精度
    while(right - left > eps){   
          double mid = left+(right-left)/2;
          if (条件) right=mid;  //判定,然后继续二分
          else  left  = mid;
    }
    

    .

    3.2实数二分例题

    ∎题目描述
    主人过生日,m个人来庆生,有n块半径不同的圆形蛋糕,由m+1个人(加上主人)分,每人的蛋糕必须一样重,而且是一整块(不能是几个蛋糕碎块,也就是说,每个人的蛋糕都是从一块圆蛋糕中切下来的完整一块)。问每个人能分到的最大蛋糕是多大。
    ∎题解
    最小值最大化问题。设每人能分到的蛋糕大小是x,用二分法枚举x。

    自己有点晕

    #include <bits/stdc++.h>
    using namespace std;
    double PI=acos(-1.0);  //3.141592653589793;
    const double eps=1e-7;
    double area[10010];
    int n,m;
    bool check(double mid)
    {
    	int sum=0;
    	for(int i=0;i<n;i++)
    	{
    		sum+=(int)(area[i]/mid);   //把每个圆蛋糕都按大小mid分开。统计总数
    	}
    	if(sum>=m) return true;
    	else return false;
    }
    int main()
    {
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		cin>>n>>m;
    		m++;
    		double maxx=0;
    		for(int i=0;i<n;i++)
    		{
    			int r; cin>>r;
    			area[i]=r*r*PI;
    			if(maxx<area[i])	maxx=area[i];  //最大的一块蛋糕
    		}	
    		double l=0,r=maxx;
    		while(r-l>eps)
    		{
    			double mid=(r-l)/2+l;
    			if(check(mid)) l=mid;
    			else r=mid;
    		}
    		cout<<l<<endl;
    	} 
    	return 0;
    }
    
    

    .

    4.二分法精选例题

    饥饿的奶牛  https://www.luogu.org/problem/P1868
    寻找段落   https://www.luogu.org/problem/P1419
    小车问题   https://www.luogu.org/problem/P1258
    借教室    https://www.luogu.org/problem/P1083
    跳石头    https://www.luogu.org/problem/P2678
    聪明的质监员 https://www.luogu.org/problem/P1314
    分梨子    https://www.luogu.org/problem/P1493
    第 k大     http://acm.hdu.edu.cn/showproblem.php?pid=6231


    .

    5.1三分法模板

    今天有点累,过几天在更新!

    展开全文
  • 试题A:组队 问题描述: 作为篮球队教练,你需要从以下名单中选出 1 号位至 5 号位各一名球员, 组成球队的首发阵容。 每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1 号位至 5 号位的评分...

    试题A:组队

     问题描述:

    作为篮球队教练,你需要从以下名单中选出 1 号位至 5 号位各一名球员, 组成球队的首发阵容。

    每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1 号位至 5 号位的评分之和最大可能是多少?

     


    试题B:不同子串

    问题描述:

    一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成 的串。例如,字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab,一共 7 个。 注意在计算时,只算本质不同的串的个数。 请问,字符串0100110001010001 有多少个不同的非空子串?

    import java.util.ArrayList;
    
    public class Main {
    	public static void main(String[] args) {
    		ArrayList<String> list = new ArrayList<>();
            //首先使用题目给定的条件进行测试
    //		String string = "aaab";
    		String string = "0100110001010001";
    		String subString = null;
    		int size = string.length();
    		for (int length = 1; length <= size; length++) {
    			for (int index = 0; index <= (size - length); index++) {
    				subString = string.substring(index, index + length);
    				if (!list.contains(subString)) {
    					list.add(subString);
    				}
    			}
    		}
    		System.out.println(list.size());
    		System.out.println(list.toString());
    	}
    }
    

    试题C:数列求和

    问题描述:

    给定数列 1, 1, 1, 3, 5, 9, 17, …,从第 4 项开始,每项都是前 3 项的和。求 第 20190324 项的最后 4 位数字。

    public class Main {
    	public static void main(String[] args) {
    		int number = 20190324;
    		
    		long num1 = 1;
    		long num2 = 1;
    		long num3 = 1;
    		long temp = 0;
    		
    		// 首先使用较小的项数测试完整的数字,与下面截取的结果进行比较
    //		for (long i = 4; i <= 50; i++) {
    //			temp = num3;
    //			num3 = (num1 + num2 + num3);
    //			num1 = num2;
    //			num2 = temp;
    //		}
    		
    		for (long i = 4; i <= number; i++) {
    			temp = num3 % 10000;
    			num3 = (num1 + num2 + num3) % 10000;
    			num1 = num2 % 10000;
    			num2 = temp;
    		}
    		System.out.println(num3);
    	}
    }

     当时试过用递归,但是对于20190324这样的项数,直接就报了栈溢出。所以试验了上面代码中注释掉的部分,直接使用了20190324跑的结果5268603393216230115,这个结果看上去还可以,但唯独千位数是0,很郁闷,用20190325跑了一次发现数值越界了(结果是-94021825125598091),当时自作聪明地以为20190324就是临界值。/泪奔


     试题D:数的分解

    问题描述:

    把 2019 分解成 3 个各不相同的正整数之和,并且要求每个正整数都不包 含数字 2 和 4,一共有多少种不同的分解方法? 注意交换 3 个整数的顺序被视为同一种方法,例如 1000+1001+18 和 1001+1000+18 被视为同一种。

    展开全文
  • 算法
  • 蓝桥备考基础算法归纳 暴力、贪心 递归、递推 二分、快排 深度优先搜索、广度优先搜索、回溯 字符串处理 双指针 动态规划 各类背包问题 数论 全排列、组合 素数、最大公约数、最小公倍数、欧几里得gcd 海伦公式...

    蓝桥备考基础算法归纳

    暴力、贪心
    递归、递推
    二分、快排
    深度优先搜索、广度优先搜索、回溯
    字符串处理
    • 双指针
    动态规划
    • 各类背包问题
    数论
    • 全排列、组合
    • 素数、最大公约数、最小公倍数、欧几里得gcd
    • 海伦公式、斐波那契、杨辉三角
    • 大整数
    图论
    C++ STL类库使用

    一些小点

    scanf("%[^\n]", &ch);

    scanf中正则表达式的输入格式
    接收除了回车以外的所有字符

    展开全文
  • 蓝桥杯2016算法竞赛a题代码。
  • 蓝桥杯算法全家桶(终极完结版)

    千次阅读 多人点赞 2020-06-11 23:34:52
    蓝桥杯算法合集这个系列包括: 蓝桥杯常用算法系列 蓝桥杯五年真题两次模拟系列 算法竞赛Java常用API总结 以及 常用数据结构 这四个模块,里面的算法题目大多是蓝桥杯历届真题。文章都是是自己备战学习过程中总结...
  • 备战蓝桥杯算法整合

    千次阅读 多人点赞 2020-09-25 17:57:29
    整合这一段时间备战蓝桥杯学习的算法,方便复习!!向国一冲刺 算法目录 整合这一段时间备战蓝桥杯学习的算法,方便复习!!向国一冲刺 六倍法判断素数 欧拉筛 01背包 完全背包 多重度背包 Floyd-Warshall(多源最...
  • 蓝桥杯算法学习(1)

    2021-04-11 19:56:30
    蓝桥杯算法学习(1)00 学习建议01 位运算的奇巧淫技1 相关基础2 用处3 相关题解题1:找出唯一成对的数题2:找出落单的那个数题3:二进制中1的个数题4:是不是2的整数次方题5:将整数的奇偶位互换题6:0~1间浮点实数的二...
  • 资源限制 时间限制:1.0s 内存限制:512.0MB 问题描述  编写一个程序,首先输入一个整数,例如5,然后在屏幕上显示如下的图形(5表示行数):  * * * * *  * * * *  * * *  * *  *  C语言代码: ...
  • Java实现 蓝桥杯 算法提高 判断名次

    万次阅读 多人点赞 2019-06-13 12:39:47
    算法提高 判断名次 时间限制:1.0s 内存限制:256.0MB 问题描述  某场比赛过后,你想要知道A~E五个人的排名是什么,于是要求他们每个人说了一句话。(经典的开头……-_-!)得了第1名的人23,说了假话;得了第5名...
  • 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述  编写一函数lcm,求两个正整数的最小公倍数。 样例输入 3 5 样例输出 15 数据规模和约定  输入数据中每一个数的范围。... 例:两个数都小于65536。...
  • 算法训练 调和数列问题  时间限制:1.0s 内存限制:512.0MB  提交此题  问题描述   输入一个实数x,求最小的n使得,1/2+1/3+1/4+…+1/(n+1)&gt;=x。  输入的实数x保证大于等于0.01,小于等于5.20,并且...
  • 蓝桥杯练习】 算法提高 八数码问题 输入格式  输入两个3*3表格  第一个为目标表格  第二个为检索表格 ...代码参考:《算法竞赛入门到进阶》 满分代码: #include <iostream> #include <cstdio> #inc
  • C++ 蓝桥杯题目讲解汇总(持续更新) VIP试题 结点选择 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 有一棵 n 个节点的树,树上每个节点都有一个正整数权值。如果一个点被选择了,那么在树上和它相邻的点都...
  • 蓝桥杯算法题——搭积木

    千次阅读 2018-03-12 23:52:57
    搭积木小明最近喜欢搭数字积木,一共有10块积木,每个积木上有一个数字,0~9。搭积木规则:每个积木放到其它两个积木的上面,并且一定比下面的两个积木数字小。最后搭成4层的金字塔形,必须用完所有的积木。...
  • 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述  输入正整数n,判断从1到n之中,数字1一共要出现几次。例如1123这个数,则出现了两次1。例如15,那么从1到15之中,一共出现了8个1。   输入格式 ...
  • 题目描述 使用Switch语句编写一个模拟简单计算器的程序。依次输入两个整数和一个字符,并用空格隔开。如果该字 符是一个“+”,则打印和;如果该字符是一个“-”,则打印差;如果该字符是一个“*”,则打印积;...
  • 题目描述 编写程序实现“剪刀,石头,布”游戏。在这个游戏中,两个人同时说“剪刀”,“石头”或“布”,压过另一方的为胜者。规则是:“布”胜过“石头”,“石头”胜过“剪刀”,“剪刀”胜过“布”。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,591
精华内容 636
关键字:

蓝桥杯算法竞赛