蓝桥杯刷题冲刺 | 倒计时27天

作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

1.递增序列

• 题目

  链接：（ 递增序列 - 蓝桥云课 (lanqiao.cn) )

  本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

  对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个字母，它们在同一行，同一列，或者在同一 45 度的斜线上，这两个字母从左向右看、或者从上向下看是递增的。

  例如，如下矩阵中

  LANN
  QIAO
  

  有L N、L N、A N、A N、I O、A O、L Q、A I、N O、N O、A Q、I N、A N 等 13 个 递增序列。注意当两个字母是从左下到右上排列时，从左向右看和从上向下看 是不同的顺序。

  对于下面的 30行 50 列的矩阵，请问总共有多少个递增序列？

  VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
  SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
  ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
  BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
  YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
  ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
  XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
  ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
  MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
  VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
  GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
  EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
  PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
  CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
  RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
  PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
  JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
  YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
  HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
  DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
  LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
  CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
  IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
  ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
  HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
  FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
  VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
  BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
  RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
  ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX
  

• 第一次

  #include<bits/stdc++.h>
  using namespace std;const int N=40,M=60;
  int a[N][M];
  int n=2,m=4;
  char g[N][M];int main()
  {memset(a,-1,sizeof a);for(int i=0;i<n;i++)for(int j=0;j<m;j++){cin>>g[i][j];a[i][j]=g[i][j]-'A'+1;}int cnt=0; for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(a[i][j]<a[i][j+1])cnt++;if(a[i][j]<a[i+1][j])cnt++;if(a[i][j]<a[i+1][j+1])cnt++;if(a[i][j]<a[i+1][j-1])cnt++;}cout<<cnt; return 0;
  }
  

  样例做不出来

  原因：

  • 上面的代码只能计算出来相邻的递增字母，而题目要求的是同一行，不相邻也是可以的
  • 斜上对角线，也没有计算进去，审题，没理解到位

  此外，也可以不用将 字母映射成 数字

• 第二次

  #include<bits/stdc++.h>
  using namespace std;const int N=40,M=60;
  int a[N][M];
  int n=30,m=50;
  char g[N][M];int main()
  {memset(a,-1,sizeof a);for(int i=0;i<n;i++)for(int j=0;j<m;j++){cin>>g[i][j];a[i][j]=g[i][j]-'A'+1;}int cnt=0; for(int i=0;i<n;i++)for(int j=0;j<m;j++){int k;//行 for(k=1;j+k<m;k++)if(a[i][j]<a[i][j+k])cnt++;//列for(k=1;i+k<n;k++)if(a[i][j]<a[i+k][j])cnt++;//右下对角线for(k=1;i+k<n&&j+k<m;k++)if(a[i][j]<a[i+k][j+k])cnt++;//左下对角线if(j>=1){for(k=1;i+k<n&&j-k>=0;k++)if(a[i][j]<a[i+k][j-k])cnt++;}//斜上对角线if(i>=1){for(k=1;i-k>=0&&j+k<m;k++)if(a[i][j]<a[i-k][j+k])cnt++;} }cout<<cnt; return 0;
  }
  

• 反思

  每次都在审题上，绊倒

  每一行，每一列，要十分注意是否是相邻，如果不是，要遍历每一行！！

---

2.等差素数列

• 题目

  链接：( 等差素数列 - 蓝桥云课 (lanqiao.cn) )

  本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

  2,3,5,7,11,13,… 是素数序列。 类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。

  上边的数列公差为 30，长度为 6。

  2004 年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。 这是数论领域一项惊人的成果！

  有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：

  长度为 10 的等差素数列，其公差最小值是多少？

• 我的题解

  #include<bits/stdc++.h>
  using namespace std;int a[10000];bool isPrime(int n)
  {for(int i=2;i<n;i++)if(n%i==0)return false;return true;
  }int main()
  {int k=0;int res[10];for(int i=2;i<10000;i++)//通过题目可以盲目推测出来 素数范围 总不能超过 10000{if(isPrime(i))a[k++]=i;  //这里构造一个素数 表即素数数组}int d=5;int i,j;for(d=5;;d++)  //表d示公差 {for(i=0;i<k-1;i++)  //i表示 数列的第一个数 {int cnt=0;  //数列的长度要求是 10 ，这是用 cnt 来表示 数列的长度for(j=i;j<k-1;j++) // j 表示数列 后面的数 ，遍历完 j cnt 都没有满足10，就换 i 继续遍历{if(cnt<10){if(a[j]==a[i]+d*cnt)   //等差数列的性质{cnt++;}else continue;  //如果 a[j] 不满足，就跳过，找一下 a[j] 满足的}else  //找到 cnt==10，即找到 满足条件的 d 了，输出即可{cout<<d<<endl;return 0;}}}}return 0;
  }
  

• 反思

  写代码的时候，逻辑很乱，条理不清晰，提前没有写注释，后面修改的时候，就很懵

  动手模拟一下，往往会事半功倍

  此外，数据开的范围要足够大

---

3.七段码

• 题目

  链接：( 七段码 - 蓝桥云课 (lanqiao.cn) )

  本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

  小蓝要用七段码数码管来表示一种特殊的文字。

  

  上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二 极管，分别标记为 a,b,c,d,e,f,g。

  小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。

  例如：b 发光，其他二极管不发光可以用来表达一种字符。

  例如 c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上 一行的方案可以用来表示不同的字符，尽管看上去比较相似。

  例如：a,b,c,d,e 发光，f,g 不发光可以用来表达一种字符。

  例如：b,f 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。

  请问，小蓝可以用七段码数码管表达多少种不同的字符？

• 第一次

  emm，没认真看题，直接用的 排列组合公式相加，想的太简单了，果然蓝桥杯没有白给的分

  要求所有的发光二极管是连成一片的，所以我穷举了，还穷举错了

• 第二次

  //准备使用  bfs 和并查集 ，补充知识中
  

4.亲戚

• 题目

  链接：( 1249. 亲戚 - AcWing题库 )

  或许你并不知道，你的某个朋友是你的亲戚。

  他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。

  如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。

  在这种情况下，最好的帮手就是计算机。

  为了将问题简化，你将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。

  从这些信息中，你可以推出Marry和Ben是亲戚。

  请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。

  输入格式

  输入由两部分组成。

  第一部分以 N,M开始。N 为问题涉及的人的个数。这些人的编号为 1,2,3,…,N。下面有 M 行，每行有两个数 $a_i,b_i$ ，表示已知 $a_i$ 和 $b_i$ 是亲戚。

  第二部分以 Q 开始。以下 Q 行有 Q 个询问，每行为 $c_i,d_i$ ，表示询问 $c_i$ 和 $d_i$ 是否为亲戚。

  输出格式

  对于每个询问$c_i,d_i$ ，输出一行：若 $c_i$ 和 $d_i$ 为亲戚，则输出“Yes”，否则输出“No”。

  数据范围

  1≤N≤20000,
  1≤M≤$10^6$ ,
  1≤Q≤$10^6$ .

  输入样例：

  10 7
  2 4
  5 7
  1 3
  8 9
  1 2
  5 6
  2 3
  3
  3 4
  7 10
  8 9
  

  输出样例：

  Yes
  No
  Yes
  

• 我的题解

  #include<bits/stdc++.h>
  using namespace std;const int N=4*1e5+10;
  int p[N];
  int n,m;int find(int x) //查找他的 根节点 路径压缩
  {if(x!=p[x])  p[x]=find(p[x]);return p[x];
  }int main()
  {scanf("%d%d",&n,&m);  //输入输出  cin  cout  不适用while(n--) p[n]=n;  //初始化while(m--){int a,b;scanf("%d%d",&a,&b);p[find(a)]=find(b);  //两个 集合  合并}int q;cin>>q;while(q--){int a,b;scanf("%d%d",&a,&b);find(a)==find(b)?printf("Yes\n"):printf("No\n");  //查找}return 0;
  }
  

• 反思

  • 复习并查集，熟练默写 模板

  • 数据超过 一百万的时候 scanf printf cin cout 之间的差距就会出现

  为避免这种情况发生，考试的时候，一律使用 scanf printf

---

5.连通块中点的数量

• 题目

  链接：( 837. 连通块中点的数量 - AcWing题库 )

  给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。

  现在要进行 m 个操作，操作共有三种：

  1. C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
  2. Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
  3. Q2 a，询问点 a 所在连通块中点的数量；

  输入格式

  第一行输入整数 n 和 m。

  接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

  输出格式

  对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。

  对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量

  每个结果占一行。

  数据范围

  1≤n,m≤$10^5$

  输入样例：

  5 5
  C 1 2
  Q1 1 2
  Q2 1
  C 2 5
  Q2 5
  

  输出样例：

  Yes
  2
  3
  

• 我的代码

  #include<bits/stdc++.h>
  using namespace std;const int N=1e5+10;int p[N];
  int s[N];int find(int x)
  {if(x!=p[x]) p[x]=find(p[x]);return p[x];
  }void add(int a,int b)
  {s[find(b)]+=s[find(a)];p[find(a)]=find(b);   //这个位置 两个语句的顺序是不可以 改变的；
  }int main()
  {int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++) p[i]=i,s[i]=1;char op[3];while(m--){scanf("%s",op);if(op[0]=='C'){int a,b;scanf("%d%d",&a,&b);if(find(a)==find(b)) continue;add(a,b);}else{if(op[1]=='1'){int a,b;scanf("%d%d",&a,&b);find(a)==find(b)?printf("Yes\n"):printf("No\n");}else{int a;scanf("%d",&a);printf("%d\n",s[find(a)]);}}}return 0;
  }
  

• 反思

  • 根据具体的题目在模板上，添加东西，维护，比如这个题，就是加上它的 集合大小，注意它的初始化

  • 要不断地考虑，题目中的逻辑顺序