31 凯撒加密

解题日期：250218
解题用时：4min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2020，模拟，省模拟赛

题意整理

凯撒加密原版。

解题思路

直接计算推导，注意特判xyz。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main()
{
  string s,s2;
  cin>>s;
  int len=s.length();
  for(int i=0;i<len;i++){
    if(s[i]>='x'){
      s2+=(s[i]+'d'-'a'-26);
    }
    else{
          s2+=(s[i]+'d'-'a');
    }
  }
  cout<<s2;
  return 0;
}

32 最大距离

解题日期：250218
解题用时：5min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2020，模拟，省模拟赛

题意整理

定义两个元素ai和aj之间的距离为|i-j|+|ai-aj|。给定一个数列，找出元素之间最大的元素距离。

解题思路

根据数据范围判断可以直接暴力，而且不需要开longlong

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
#include <iostream>
using namespace std;
int fas(int k){
  if(k<0)return -k;
  return k;
}
int main()
{
  int n;
  cin>>n;
  int a[1010];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  int max=0;
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      int temp=fas(j-i)+fas(a[j]-a[i]);
      if(temp>max){
        max=temp;
      }
    }
  }
  cout<<max;
  return 0;
}

33 最长递增

解题日期：250218
解题用时：13min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2020，模拟，省模拟赛

题意整理

输入一个数列，求其中最长递增序列的长度。

解题思路

可以选一个开头，但是判断的是相邻两个数之间的递增关系。

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>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[1010];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  int max=0;
  int i,j;
  for(i=0;i<n-1;i++){
    int count=1;
    for(j=i;j<n-1;j++){
      if(a[j+1]>a[j]){
        count++;
      }
      else{
        break;
      }
    }
    if(count>max){
      max=count;
    }
  }
  cout<<max;
  return 0;
}

34 字符计数

解题日期：250218
解题用时：3min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2020，暴力，省模拟赛，语法

题意整理

输入一个字符串，输出其中的元音字母和辅音字母个数。

解题思路

遍历字符串，直接判断即可。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  cin>>s;
  int n=s.length();
  int count=0;
  for(int i=0;i<n;i++){
    if(s[i]=='a'||s[i]=='e'||s[i]=='i'||s[i]=='o'||s[i]=='u'){
      count++;
    }
  }
  cout<<count<<endl;
  cout<<n-count<<endl;
  return 0;
}

35

解题日期：250218
解题用时：9min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2018，暴力，省赛

题意整理

x 星球有 26 只球队，分别用 a ~ z 的 26 个字母代表。他们总是不停地比赛。

在某一赛段，哪个球队获胜了，就记录下代表它的字母，这样就形成一个长长的串。

国王总是询问：获胜次数最多的和获胜次数最少的有多大差距？（当然，他不关心那些一次也没获胜的，认为他们在怠工罢了）

解题思路

暴力。使用map进行统计，对于字母使用ASCII对应进行比较即可。

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
  map<int,int> am;
  string s;
  cin>>s;
  int n=s.length();
  int max=0;
  int min=1000;
  for(int i=0;i<n;i++){
    am[s[i]]++;
  }
  for(int i='a';i<='z';i++){
    if(am[i]>max){
      max=am[i];
    }
    if((am[i]<min)&&(am[i]!=0)){
      min=am[i];
    }
  }
  cout<<max-min;
  return 0;
}

36 递增三元组

解题日期：250218
解题用时：12min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2018，暴力，省赛

题意整理

给定三个整数数组，统计有多少个三元组满足Ai < Bj < Ck。

解题思路

直接暴力。在二层循环处可以优化。注意循环里面想清楚break还是continue！（最后有一个样例运行超时了，还是得用技巧。）
看到题解用了一次排序作为预处理，优化时间复杂度。

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
#include <iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a[100005], b[100005], c[100005];
    long long n = 0, ans = 0;
    long long i = 0, s1 = 0, s2 = 0;
    cin >> n;
    for (i = 0; i < n; i++) cin >> a[i];
    for (i = 0; i < n; i++) cin >> b[i];
    for (i = 0; i < n; i++) cin >> c[i];
    sort(a, a + n); sort(b, b + n); sort(c, c + n);

    for (i = 0; i < n; i++)
    {
        //s1 = 0; s2 = 0;
        while (s1 < n && a[s1] < b[i]) s1++;
        while (s2 < n && c[s2] <= b[i]) s2++;
        ans += ((long long)s1 * (n - s2));
    }
    cout << ans << endl;
    return 0;
}

37 螺旋折线

解题日期：250218
解题用时：30min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2018，思维，省赛

题意整理

https://doc.shiyanlou.com/courses/uid1580206-20210202-1612250322579

要算该点到原点的螺旋折线长度。

解题思路

首先确定层数，将图形分成互不相干的层。然后找到每层的一个关键点，再以此点为基准进行计算。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
long long fas(long long m){
  if(m<0)return -m;
  return m;
}
long long max(long long x,long long y){
  if(fas(x)>fas(y))return fas(x);
  return fas(y);
}
int main()
{
  long long x,y,k;
  long long res=0;
  cin>>x>>y;
  k=max(x,y);
  if(x==k) res=4*k*k+(k-y);
  if(x==-k) res=4*k*k-2*k-(k-y);
  if(y==k) res=4*k*k-(k-x);
  if(y==-k) res=4*k*k+2*k+(k-x);
  cout<<res;
  return 0;
}

38 日志统计

解题日期：250218
解题用时：50min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2018，双指针，贪心，省赛

题意整理

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。其中每一行的格式是：ts id

表示在 ts 时刻编号
id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于K 个赞，小明就认为这个帖子曾是”热帖”。

具体来说，如果存在某个时刻 T 满足该帖在
【T,T+D ) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。

给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。

解题思路

预处理之后使用双指针。

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
#include<cstdio>
#include<algorithm>
using namespace std;
int n,d,k;
int nowlike[100005];
struct node{
    int ts;
    int id;
};
node arr[100005];
bool ishot[100005];
bool cmp(node x,node y)
{
    return x.ts<y.ts;
}
int main()
{
    scanf("%d%d%d",&n,&d,&k);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&arr[i].ts,&arr[i].id);
    sort(arr+1,arr+1+n,cmp);
    int l = 1;
    for(int i=1;i<=n;i++)
    {  
            nowlike[arr[i].id]++;
        while(arr[i].ts >= arr[l].ts + d) nowlike[arr[l++].id]--;
        if(nowlike[arr[i].id]>=k) ishot[arr[i].id] = true;
    }
    for(int i=0;i<=100005;i++)
        if(ishot[i])
            printf("%d\n",i);
    return 0;
}

39 缩位求和

解题日期：250218
解题用时：8min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2018，模拟，省赛

题意整理

请你写一个计算机程序，对给定的字符串逐位求和。

解题思路

一定要审题！注意输入进来的是字符串不是数字，而且不能直接转int或者long long因为是1000位数字，要用高精度预处理一波。

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
#include <bits/stdc++.h>
using namespace std;
int countsum(int n){
  int count=0;
  while(n>0){
    count+=n%10;
    n/=10;
  }
  return count;
}
int main()
{
  string s;
  cin>>s;
  int n=s.length();
  int count=0;
  for(int i=0;i<n;i++){
    count+=s[i]-'0';
  }
  int res=countsum(count);
  while(res/10>0){
    res=countsum(res);
  }
  cout<<res;
  return 0;
}

40 小朋友崇拜圈

解题日期：250218
解题用时：60min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2018，省赛，DFS

题意整理

班里 n个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。

在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的右手边。

求满足条件的圈最大多少人？

小朋友编号为 1,2,3,⋯n。

解题思路

DFS，注意每一次dfs结束后需要回溯。

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
#include<stdio.h>
int n;
int a[100001],v[100001];
int max=0;//定义全局变量，方便求最大值
int t;//暂时保存开始位置的小朋友的编号

void dfs(int x,int y)
{
  if(v[x])//只要访问过了已经访问的编号，就是有闭合的圈
  {
    if(a[x]==a[t])//只有满足这个条件，才符合一个真正意义上的圈
    {
      if(y>max)
        max=y;
    }
    return;
  }
  else
  {
    v[x]=1;
    dfs(a[x],y+1);
    v[x]=0;//每次进行一次dfs搜索，回溯，避免影响下一次的搜索
  }
}
int main()
{
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
  scanf("%d",&a[i]);
  for(int i=1;i<=n;i++)//这个开始的编号要从1开始比较方便，因为每个人崇拜的小朋友的编号都是从下标为1开始的
  {
    t=i;//t暂时保存此时的为起点的小盆友的编号
    dfs(i,0);//每个小朋友都进行一次dfs搜索
  }
  printf("%d",max);
  return 0;
}