蓝桥杯模拟赛

自用笔记算法

蓝桥杯模拟赛

快速幂

题目要求

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
using namespace std;
long long bigpow1(int a,int b)   //递归实现
{
	if(b==0)
		return 1;
	if(b&1)
		return bigpow1(a,b/2)*bigpow1(a,b/2)*a;
	else
		return bigpow1(a,b/2)*bigpow1(a,b/2);
}
long long bigpow2(int a,int b)    //二分实现
{
	int re=1,base=a;
	while(b!=0)
	{
		if(b&1)
			re*=base;
		base*=base;
		b>>=1;
	}
	return re;
}
long long bigpow3(int a,int b,int p)    //二分取模
{
	int re=1,base=a%p;
	while(b!=0)
	{
		if(b&1)
			re*=base%p;
		base*=base%p;
		b>>=1;
	}
	return re;
}
int main()
{
	int a,b,p;
	cin>>a>>b>>p;
	long long re=bigpow3(a,b,p);
	cout<<re<<endl;
	return 0;
}

注意事项

给出了快速幂的递归实现，二分实现以及二分取模实现。

线段点和

题目要求

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int vis[10050],dian[50050];
struct node
{
	int l,r;
}e[10050];
bool cmp(node x,node y)
{
	if(x.l==y.l)
		return x.r<y.r;
	else
		return x.l<y.l;
}
int main()
{
	int n,m;
	cin>>n>>m;
	memset(vis,0,sizeof(vis));
	memset(dian,0,sizeof(dian));
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		dian[x]=1;
	}
	for(int i=1;i<=m;i++)
		cin>>e[i].l>>e[i].r;
	int ans=0,E;
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int max=-INT_MAX;
		if(!vis[i])
		{
			for(int j=e[i].l;j<=e[i].r;j++)
			{
				if(dian[j])
				{
					int flag=1;
					for(int k=i+1;k<=m;k++)
					{
						if(j>=e[k].l&&j<=e[k].r)
							flag++;
						else
							break;
					}
					if(flag>max)
					{
						max=flag;
						E=j;
					}
				}
			}
			ans++;
			for(int j=i+1;j<=m;j++)
			{
				if(E>=e[j].l&&E<=e[j].r)
					vis[j]=1;
				else
					break;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

思路

对所有区间进行升序排序，若x值一样按y值的升序排列。从第一个区间开始遍历所有给出的点，若满足该区间则判断是否满足下一个区间，直到不满足为止。
计算并保留走的最远的点，把中间经历过的区间的vis至为1，直接从下一个区间开始继续遍历给出的所有的点，直到区间已用完。输出点数即可。

超级玛丽

题目要求

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstring>
using namespace std;
int dp[50],flag[50];
int main()
{
	int n,m;
	cin>>n>>m;
	memset(flag,0,sizeof(flag));
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		flag[x]++;
	}
	if(!flag[1])
		dp[1]=1;
	if(!flag[2])
		dp[2]=1;
	for(int i=3;i<=n;i++)
	{
		if(flag[i])
			continue;
		dp[i]=dp[i-1]+dp[i-2];
	}
	cout<<dp[n]<<endl;
	return 0;
}

思路

不考虑陷进的情况下，满足斐波拉契递推式dp[n]=dp[n-1]+dp[n-2]。dp[1]=dp[2]=1。考虑陷进的情况下只需把陷进处的dp值赋为0即可。

盾神与砝码称重

题目要求

参考AC代码(暴力裸搜)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,w[25];
int dfs(int now,int id)
{
	if(!now)
		return 1;
	if(now&&id==n+1)
		return 0;
	return dfs(now-w[id],id+1)||dfs(now,id+1)||dfs(now+w[id],id+1);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	sort(w+1,w+1+n);
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		if(dfs(x,1))
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	return 0;
}

参考代码(优化剪枝)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,w[25],sum[25];
int dfs(int now,int id)
{
	if(!now)
		return 1;
	if(now&&id==0)
		return 0;
	if(abs(now)>sum[id])
		return 0;
	return dfs(now-w[id],id-1)||dfs(now,id-1)||dfs(now+w[id],id-1);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	sum[0]=0;
	sort(w+1,w+1+n);
	for(int i=1;i<=n;i++) 
		sum[i]=sum[i-1]+w[i];
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		if(dfs(x,n))
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	return 0;
}

思路

暴力裸搜只能得50分，复杂度为3^n（放左 放右 不放）会爆。所以采用优化剪枝的方法，把砝码按质量大小升序排序后求出前缀和。从最大的砝码开始放，
加一个剪枝：若目前物体剩余的质量的绝对值仍大于剩余所有砝码的质量，返回0。

减格子

题目要求

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<string.h>
using namespace std;
#define N 10
int num[N][N];
int tag[N][N] = {0};
int m, n;
int r = 100;
int bad(int i, int j)
{
	if (i < 0 || i >= n || j < 0 || j >= m || tag[i][j] == 1)
        return 1;  
    return 0;
}
void go(int i, int j, int k, int count)
{ 
    if (bad(i, j) || count < num[i][j])
        return;
    k++;
    if (count == num[i][j])
    {
        if (r > k)
            r = k;
        return; 
    }
    tag[i][j] = 1;
    count -= num[i][j];
    go(i - 1, j, k, count); 
    go(i + 1, j, k, count);
    go(i, j - 1, k, count); 
    go(i, j + 1, k, count);
    tag[i][j] = 0;
}
int main()
{
    int i, j;
    int half = 0;
	scanf("%d %d", &m, &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
        {
            scanf("%d", &num[i][j]);
            half += num[i][j];
        }
    if (half % 2 == 0 && half >= num[0][0] * 2)
    {
        half /= 2;
        go(0, 0, 0, half);
    }  
    if (r == 100)
        r = 0;
    printf("%d", r);
    return 0;
}

注意事项

深搜即可。

本文标题:蓝桥杯模拟赛

文章作者:Hippopmonkey

发布时间:2016-11-22, 20:57:59

最后更新:2016-11-24, 12:58:06

原始链接:http://xuboming8.github.io/2016/11/22/蓝桥杯模拟赛/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 蓝桥杯模拟赛
    1. 1.1. 快速幂
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 注意事项
    2. 1.2. 线段点和
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. 超级玛丽
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. 盾神与砝码称重
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码(暴力裸搜)
      3. 1.4.3. 参考代码(优化剪枝)
      4. 1.4.4. 思路
    5. 1.5. 减格子
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 注意事项
|