菜菜的秘密花园
Posts Tags Categories Docs About
菜菜的秘密花园

Contents

【蓝桥杯】2022题解

 included in 蓝桥杯刷题记录
   1242 words   6 minutes    views  

⏰总用时：125/240 🎯总分：14.5/150

题号 时间 结果 满分 难度 备注
1 5 ✅ 5 🌕
2 5 ❌ 5 🌓 🔹 博弈论：只能转移到必胜态的，均为必败态。可以转移到必败态的，均为必胜态
🔹 c++中计算字符串中某字符个数：count(s.begin(),s.end(),‘o’)
🔹 DFS：深搜的时候保存已有结果
🔹 二维数组可直接压缩为一维数组
🔹 遍历不连续数组，可把要遍历的索引存储在一个数组中
3 5 30% 10 🌕 🔸 先观察所求式子能否化简，注意超时问题
🔸 注意题目所给数据范围，答案应该用 long long型
4 30 40% 10 🌓 🔹 巧妙构造数组可以简化题目
🔹 若 a ^ b=x，则 a ^ x=b， b ^ x=a。
🔹 可以用 map 来映射一组数和他们的索引
🔹 直接把异或表达式放 if 语句或输出语句中会出错
5 5 ❌ 10 🌑 🔸 【分数取模】、【快速幂】
🔸 注意找递推关系
🔸 加快输入速度：ios::sync_with_stdio(false); cin.tie(0);
🔸 c++自带求最大公约数的函数：__gcd(x,y)
🔸 注意宏定义不能和下面的变量重名
6 15 ❌ 15 🌓 🔹 观察题目的判断结论
🔹 二分查找
7 30 ❌ 20 🌓
8 5 ❌ 20
9 20 10% 25
10 5 ❌ 25

😭😭😭😭好难啊，太多不会的，所以好几题直接放弃了。。。

1 【填空】裁纸刀

题目

小蓝有一个裁纸刀，每次可以将一张纸沿一条直线裁成两半。小蓝用一张纸打印出两行三列共 6 个二维码，至少使用九次裁出来，下图给出了一种裁法。

/img/蓝桥杯/2.png

在上面的例子中，小蓝的打印机没办法打印到边缘，所以边缘至少要裁 4 次。另外，小蓝每次只能裁一张纸，不能重叠或者拼起来裁。如果小蓝要用一张纸打印出 20 行 22 列共 440 个二维码，他至少需要裁多少次？

解析

1

cout<<4+21+22*19;

2 【填空】灭鼠先锋

题目

灭鼠先锋是一个老少咸宜的棋盘小游戏，由两人参与，轮流操作。

灭鼠先锋的棋盘有各种规格，本题中游戏在两行四列的棋盘上进行。游戏的规则为：两人轮流操作，每次可选择在棋盘的一个空位上放置一个棋子，或在同一行的连续两个空位上各放置一个棋子，放下棋子后使棋盘放满的一方输掉游戏。

小蓝和小乔一起玩游戏，小蓝先手，小乔后手。小蓝可以放置棋子的方法很多，通过旋转和翻转可以对应如下四种情况：

/img/蓝桥杯/3.png

其中 O 表示棋盘上的一个方格为空，X 表示该方格已经放置了棋子。

请问，对于以上四种情况，如果小蓝和小乔都是按照对自己最优的策略来玩游戏，小蓝是否能获胜。如果获胜，请用 V 表示，否则用 L 表示。请将四种情况的胜负结果按顺序连接在一起提交。

解析

🟠 【博弈论】当前只能转移到必胜态的，均为必败态。当前可以转移到必败态的，均为必胜态。 仔细观察，本题中的必败态为只剩一个 “o” 的情况。因此要赢，只需要确保 自己放完棋子后一定为【必败态】 。

🟡 c++ 中计算字符串中某个字符个数的函数： count(s.begin(),s.end(),'o') ，需要加头文件 #include <algorithm>

🟢 利用 【DFS】 解决问题，统一考虑问题的视角：自己放完棋子为状态 s 能否赢 ，否则很容易绕晕，到底是返回 true 还是返回 false。 深搜的时候保存结果，遇到已经判断过的状态就直接返回。

🔵 二维数组可以直接压缩成一维数组。

🟣 遍历不连续数组时，可以 把要遍历的索引存储在一个数组中 ，这样遍历时可以连续用下标，简单省事。

 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

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

// 无序映射，键为棋盘状态，值为下完后是这个状态能否赢 
unordered_map<string, bool> mp;

// 用于判断 s 中含有的 'o' 的个数是否为1 
// 个数为 1 则为必败态 
bool check(string s){
	return count(s.begin(),s.end(),'o')==1; 
}

// 利用 dfs 判断自己下完棋后状态为 s 能否赢（是否是必败态） 
bool dfs(string s){			
	if(mp.count(s))				// 若当前状态判断过了，则返回当前状态 
		return mp[s];			// 注意判断 mp 中是否有某个元素的方法！ 
	
	if(check(s))				// 下完棋是必败态，返回 true 
		return mp[s]=true;		// 一定要记得保存 mp[s] 的状态！！！ 
		
	for(int i=0;i<8;i++){		// 放 1 个棋子的所有可能 
		if(s[i]=='x')			// 当前位置已经被放置了 
			continue;
		string t=s;
		t[i]='x';
		if(dfs(t))				// 又走过一步后是必败态 
			return mp[s]=false; // 说明当前这步下完后不能赢。这里一定要返回！！！ 
	}
	
	// 存储放 2 个棋子中的第 1 个的所有可能索引
	int idx[6]={0,1,2,4,5,6};	 
	for(int i=0;i<6;i++){		// 放 2 个棋子的所有可能 
		if(s[idx[i]]=='x' || s[idx[i]+1]=='x')	// 注意索引 idx[i] 在 s 中的下一个元素是 idx[i]+1，不是 idx[i+1]！！！ 
			continue;
		string t=s;
		t[idx[i]]=t[idx[i]+1]='x';				// 注意 i 表示索引的索引，不能直接用 i ！！！ 
		if(dfs(t))
			return mp[s]=false; 
	} 
	
	return mp[s]=true; 			// 对方下一步下完后没出现必败态，说明这步下完能赢 
} 

int main(){
	string s[4]={"xooooooo","xxoooooo","oxoooooo","oxxooooo"};
	for(auto i:s)
		cout << (dfs(i) ? 'V' : 'L');
	return 0;
}

3 求和

题目

给定 n 个整数 $a_1,a_2,…,a_n$ ，求它们两两相乘再相加的和，即：

$S=a_1×a_2+a_1×a_3+…+a_{n-2}×a_{n-1}+a_{n-2}×a_{n}+a_{n-1}×a_n$

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数 $a_1,a_2,…,a_n$ 。

输出格式

输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。

解析

🟠 一开始直接暴力使用 2 个 for 循环，发现超时了，于是开始分析这个式子，发现其实可以化简：

$S=[a_1*(a_2+a_3+…a_n)+a_2*(a_1+a_3+…a_n)…+a_n*(a_1+a_2+…a_{n-1})]/2$

$S=[a_1*(sum-a_1)+a_2*(sum-a_2)…+a_n*(sum-a_n)]/2$

$S=[sum*sum-(a_1^2+a_2^2…+a_n^2)]/2$

🔵 其中 $sum = (a_1+a_2+…a_n)$ 。 要注意题目所给数据范围，应该用 long long，否则无法通过样例。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <bits/stdc++.h>
#include <cmath>
using namespace std;

int main(){
    
    int n,t;
    long long s1=0,s2=0,ans;
    cin>>n;
    for(int i=0;i<n;i++){
    	scanf("%d",&t);
    	s1=s1+t;		// 数字之和
    	s2=s2+t*t; 		// 平方和
	}
	
	ans=(s1*s1-s2)/2;
	cout<<ans;
    return 0;
}

4 选数异或

题目

给定一个长度为 n 的数列 $A_1,A_2,…A_n$ 和一个非负整数 x , 给定 m 次查 询, 每次询问能否从某个区间 [l, r] 中选择两个数使得他们的异或等于 x 。

输入格式

输入的第一行包含三个整数 n, m, x 。

第二行包含 n 个整数 $A_1,A_2,…A_n$ 。

接下来 m 行，每行包含两个整数 $l_i, r_i$ 表示询问区间 [$l_i, r_i$] 。

输出格式

对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出 no。

解析

🟠 构造数组 dp[i] = j ：满足 a[k]^a[j]=x，且 1≤ k ≤ i 的 j 的最大值。由于我们是按索引由小到大遍历的，因此必有 dp[i] ≤ i 。

🟡 构造数组的值和它的索引的映射： map<long long,int> mp

🟢 注意事实：若 a ^ b=x，则 a ^ x=b，且 b ^ x=a。 因此和 t 异或的值为 x 的数是 t^x，它的索引是 mp[t^x]。

🔵 根据以上两点，我们可以这样更新 dp[i]： dp[i]=max(dp[i-1], mp[t^x]);

🟣 要使索引 [l, r] 上的值能两两异或得到 x ，只要保证在 r 之前有一个数，和它异或为 x 的数的索引大于 l，即 dp[r]>=l 。 注意由 dp[i] ≤ i 可知，这个数范围一定在 [l, r] 内。

 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

#include <bits/stdc++.h>
#include <cmath>
using namespace std;

int main(){
	int n,m,l,r;
	int dp[100005]={0};		// dp[i]=j：a[i]^a[j]=x，且 j<=i 
	long long x,t;
	map<long long,int> mp;	// 数列的数和对应的索引 
	cin>>n>>m>>x;
	
	for(int i=1;i<=n;i++){
		scanf("%lld", &t);
		
		dp[i]=max(dp[i-1], mp[t^x]);
		mp[t]=i; 
	}
	
	for(int i=0;i<m;i++){
		scanf("%d %d",&l,&r);
		if(dp[r]>=l)	cout<<"yes"<<endl;
		else cout<<"no"<<endl;
	}
	
	return 0;
	
}

5 爬树的甲壳虫

题目

有一只甲壳虫想要爬上一颗高度为 n 的树，它一开始位于树根，高度为 0，

当它尝试从高度 i-1 爬到高度为 i 的位置时有 $P_i$ 的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。

输入格式

输入第一行包含一个整数 n 表示树的高度。

接下来 n 行每行包含两个整数 $x_i, y_i$ ，用一个空格分隔，表示 $P_i=x_i/y_i$ 。

输出格式

输出一行包含一个整数表示答案, 答案是一个有理数, 请输出答案对质 数 998244353 取模的结果。

其中有理数 a/b 对质数 P 取模的结果是整数 c 满足 0≤c<P 且 c ⋅ b ≡ a(modP) 。

解析

🟠 【分数取模问题】

由费马小定理得：$a^{p-1}=1(mod p)$，其中 p 为质数， a 不为 p 的倍数。

可以推出：$a^{p-2}(mod p)=(a^{p-1}(mod p)*a^{-1}(mod p))(mod p)=a^{-1}(mod p)$。

因此 $a/b(mod p)=(ab^{-1})(mod p)=(a(mod p)*b^{p-2}(mod p))(mod p)$。

🟡 利用快速幂计算 $b^{p-2}(mod p)$。

🟢 【找递推关系】

设 E[i] 为从点 i 到达点 n 的期望时间，则 所求答案为 E[0]，且 E[n]=0。

有递推关系： E[i] = p[i]×(E[0]+1) + (1−p[i])×(E[i+1]+1) 。注意，从 i 无论走到 0 还是走到 i+1，所花费的时间都是1。 很容易可以看出， E[i] 是一个和 E[0] 有关的一次式 ，设 E[i] = a[i]E[0] + b[i] 。

由递推关系得： a[i-1]=p[i-1]+(1-p[i-1])×a[i] ， b[i-1]=(1-p[i-1])×b[i]+1 。

🔵 注意要把 x 和 y 化成最简分数，可用 c++ 自带函数 __gcd(x, y)

 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

#include <bits/stdc++.h>
using namespace std;
#define P 998244353				// 注意宏定义不能和下面的变量重名！！！ 

// 求 a^b(mod p) 
int qm(long long a, long long b, long long p){
	long long c=1;
	while(b){
		if(b&1)
			c=c*a%p;
		a=a*a%p;
		b>>=1;		// 这里忘记加 "="，陷入死循环了！！！ 
	}
	return c;
}

int main()
{
	int n;
    long long x[100005],y[100005];
    cin>>n;
    for(int i=0;i<n;i++){
    	scanf("%d %d",&x[i],&y[i]);
    	int d=__gcd(x[i],y[i]);		// 求最大公约数
		x[i]/=d,y[i]/=d;				// 化简成最简分数 
	}
    
    long long p0,p1,a=0,b=0;
    for(int i=n-1;i>=0;i--){
    	p0=x[i]*qm(y[i],P-2,P)%P;
    	p1=(y[i]-x[i])*qm(y[i],P-2,P)%P;
    	a=(p0+p1*a%P)%P;
    	b=(p1*b%P+1)%P;
	}
	
	long long ans=(-b*qm(a-1,P-2,P)%P+P)%P;
	cout<< ans;
    
    return 0;
}

6 青蛙过河

题目

小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。

河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃 后使石头高度下降到 0 是允许的)。

小青蛙一共需要去学校上 x 天课, 所以它需要往返 2x 次。当小青蛙具有 一个跳跃能力 y 时, 它能跳不超过 y 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。

输入格式

输入的第一行包含两个整数 n,x, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意 2x 才是实际过河的次数。

第二行包含 n-1 个非负整数 $H_1, H_2,…,H_{n-1}$ , 其中 $H_i>0$ 表示在河中与 小青蛙的家相距 i 的地方有一块高度为 $H_i$ 的石头, $H_i=0$ 表示这个位置没有石头。

输出格式

输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。

解析

🟠 当跳跃能力为 y 时，对每个长度为 y-1 的区间 [l, r]，2x 次全程都会经过这个区间 2x 次，因此这个区间的总高度至少为 2x 。 据此我们写出判断函数 check()。

🟡 用 【二分查找】 ，找出最小的 y。注意判断后的转移式 ❗❗❗

 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

#include <bits/stdc++.h>
using namespace std;

int n,x;
int h[100005],s[100005];

// 检查长度为 y-1的闭区间内，总高度是不是都超过 2x
// 若超过则说明跳跃能力可以为 y 
bool check(int y){
	for(int i=1;i<=n-y;i++){
		if(s[i+y-1]-s[i-1]<2*x)	return false;
	}
	return true;
}

 int main(){
 	cin>>n>>x;
 	h[0]=s[0]=0;
 	for(int i=1;i<n;i++){
 		scanf("%d",&h[i]);
 		s[i]=s[i-1]+h[i];
	}
	
	int l=1,r=n;
	while(l!=r){			// 二分法找到最小能符合要求的值 
        // 注意如果符合条件，应该继续找小的！！！
		if(check((l+r)/2))	r=(l+r)/2;
		else	l=(l+r)/2+1;
	}
	
	cout<<r;
	return 0;
 }

7 最长不下降子序列

题目

给定一个长度为 N 的整数序列: $A_1, A_2,…,A_N$ 。现在你有一次机会, 将其 中连续的 K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数 列的最长不下降子序列最长, 请输出这个最长的长度。

最长不下降子序列是指序列中的一个子序列, 子序列中的每个数不小于在 它之前的数。

输入格式

输入第一行包含两个整数 N 和 K 。

第二行包含 N 个整数 $A_1, A_2,…,A_N$ 。

输出格式

输出一行包含一个整数表示答案。

解析

 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
70
71
72
73

#include <iostream>
using namespace std;

const int N=1e5+10;


int n,k,low[N],high[N],nlow,nhigh,a[N],len[N],ans;



int bin(int u,int l,int r)
{
  while(l<r){
    int mid=(l+r)/2;
    if(u<low[mid])r=mid;
    else l=mid+1;
  }
  return l;
}

int binb(int u,int l,int r)
{
  while(l<r){
    int mid=(l+r)/2;
    if(u>high[mid])r=mid;
    else l=mid+1;
  }
  return l;
}

int binc(int u,int l,int r)
{
  while(l<r){
    int mid=(l+r+1)/2;
    if(u<=high[mid])l=mid;
    else r=mid-1;
  }
  return l;
}

int main()
{
  cin>>n>>k;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<=n;i++)low[i]=1e9+7;
  
  for(int i=1;i<=n;i++){
    int x=bin(a[i],1,n);
    low[x]=min(a[i],low[x]);
    nlow=max(nlow,x);
    len[i]=x;//末尾为x
  }

  for(int i=n;i-k>=0;i--){
    int res;
    if(i==n){
      res=len[i-k]+k;
    }
    else if(i-k){
      res=len[i-k]+k+binc(a[i-k],0,nhigh);
    }
    else{
      res=k+nhigh;
    }
    ans=max(ans,res);
    //update
    int x=binb(a[i],1,n);
    high[x]=max(a[i],high[x]);
    nhigh=max(nhigh,x);
  }
  cout<<ans<<endl;
  return 0;
}

8 扫描游戏

9 数的拆分

10 推导部分和

Updated on 2023-03-22
Read Markdown
 蓝桥杯, C++
Back | Home