蓝桥杯c/c++程序设计——接龙数组

问题描述

对于一个长度为 K的整数数列：A1,A2,...,AK我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1的末位数字 (2≤i≤K)。

例如 12,23,35,56,61,1112,23,35,56,61,11 是接龙数列；12,23,34,5612,23,34,56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。

所有长度为 1 的整数数列都是接龙数列。

现在给定一个长度为 N 的数列 A1,A2,...,AN请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 1,2,…,A1​,A2​,…,AN​。

输出格式

一个整数代表答案。

样例输入

5
11 121 22 12 2023

样例输出

1

样例说明

删除 22，剩余 11,121,12,2023是接龙数列。

评测用例规模与约定

对于 2020% 的数据，1≤N≤20。

对于 5050% 的数据，1≤N≤10000。

对于 100100% 的数据，1≤N≤1000000，1≤Ai​≤10^9。所有 Ai​ 保证不包含前导 0

运行限制

#include <iostream>     // 包含输入输出流库
#include <cstring>      // 包含处理字符串的库
#include <algorithm>    // 包含一些算法库函数
using namespace std;

const int N=1e5+10;     // 定义常量 N = 100010

int a[N],b[N],f[N],g[N];    // 声明四个数组a、b、f、g，每个数组大小为 N

int main()
{
  int n;                // 声明变量 n
  cin>>n;               // 输入变量 n，表示接下来会有 n 个数字串

  char s[100];          // 声明字符数组 s，用于存储输入的数字串
  for(int i=0;i<n;i++)  // 循环 n 次，读取 n 个数字串
  {
    cin>>s;             // 输入数字串，将其存储在字符数组 s 中
    a[i]=s[0]-'0';      // 将数字串的首字符转换为整数，存储在数组 a 中
    b[i]=s[strlen(s)-1]-'0';  // 将数字串的末字符转换为整数，存储在数组 b 中
  }

  int mx=0;             // 声明变量 mx，用于记录最大的循环长度，初始化为 0
  for(int i=0;i<n;i++)  // 循环 n 次，处理 n 个数字串
  {
    f[i]=1;             // 将 f 数组的当前元素初始化为 1
    f[i]=max(f[i],g[a[i]]+1); // 更新 f 数组的当前元素，取 f[i] 和 g[a[i]]+1 中的较大值
    g[b[i]]=max(f[i],g[b[i]]);  // 更新 g 数组的当前元素，取 f[i] 和 g[b[i]] 中的较大值

  }

  for(int i=0;i<n;i++)  // 循环 n 次，查找最大的循环长度
  {
    mx=max(mx,f[i]);    // 更新最大循环长度 mx，取 mx 和 f[i] 中的较大值
  }

  cout<<n-mx;          // 输出修改次数，即 n 减去最大的循环长度

  return 0;            // 返回 0，表示程序运行成功
}

根据输入数据分析，输入的第一行是一个数字5，表示接下来要输入的数字个数。接着的一行是以空格分隔的5个数字字符串，分别是11、121、22、12和2023。下面是对这些数据进行处理的解析过程：

首先，我们定义一些变量和数组：

const int N = 100010;
int n;
int f[N], g[N];
int l[N], r[N];

• N 是一个常量，表示数组的最大长度。
• n 是一个整数，用于记录输入数字的个数。
• f 和 g 是两个整数数组，用于存储计算结果。
• l 和 r 是两个整数数组，用于存储输入数字的首位和末位。

然后，我们读取输入的数字个数：

cin >> n;

接下来，我们读取并处理每个数字字符串：

for (int i = 0; i < n; i++) {
    cin >> num;
    l[i] = num[0] - '0';
    r[i] = num[strlen(num) - 1] - '0';
}

在每次循环中，我们首先读取一个数字字符串 num，然后将其首位和末位转换为数字，并分别存储到数组 l 和 r 中。

接下来，我们进行动态规划计算和更新：

int res = 0;
for (int i = 0; i < n; i++) {
    f[i] = 1;
    f[i] = max(f[i], g[l[i]] + 1);
    g[r[i]] = max(f[i], g[r[i]]);
    res = max(res, f[i]);
}

在每次循环中，我们首先将 f[i] 初始化为1，表示以当前数字结尾的最长序列长度至少为1。

然后，我们使用状态转移方程 f[i] = max(f[i], g[l[i]] + 1) 来更新 f[i] 的值。该方程的意思是，如果存在以数字 l[i] 结尾的序列，那么可以将当前数字接在其后形成一个更长的序列。因此，我们将当前 f[i] 和 g[l[i]] + 1 的较大值赋给 f[i]，以记录以当前数字结尾的最长序列长度。

接着，我们使用状态转移方程 g[r[i]] = max(f[i], g[r[i]]) 来更新 g[r[i]] 的值。该方程的意思是，如果存在以数字 r[i] 结尾的序列，那么需要更新 g[r[i]] 的值为当前的最大值，即 f[i] 和当前 g[r[i]] 的较大值。

最后，我们通过比较 res 和 f[i] 的值来更新最终结果 res，以记录整个序列中的最长不符合条件的数字的个数。

最后，我们输出结果 n - res，即不符合条件的数字的个数：

cout << n - res << endl;

以上就是根据输入数据进行解析和处理的过程分析，展示了代码的功能和执行流程。

以下是正确的执行过程：

1. 首先，输入数字序列的长度为 5。
2. 接着，逐个输入每个数字并提取首位数字和末位数字。
   • 对于数字 11，其首位数字和末位数字均为 1，存储在 l[0] 和 r[0] 中。
   • 对于数字 121，其首位数字为 1，末位数字为 1，存储在 l[1] 和 r[1] 中。
   • 对于数字 22，其首位数字和末位数字均为 2，存储在 l[2] 和 r[2] 中。
   • 对于数字 12，其首位数字为 1，末位数字为 2，存储在 l[3] 和 r[3] 中。
   • 最后一个数字是 2023，其首位数字为 2，末位数字为 3，存储在 l[4] 和 r[4] 中。
3. 接着进行动态规划计算，逐个数字计算最长接龙序列长度。
   • 对于数字 11，最长接龙序列长度为 1。
   • 对于数字 121，最长接龙序列长度为 2。
   • 对于数字 22，最长接龙序列长度为 1。
   • 对于数字 12，最长接龙序列长度为 2。
   • 对于数字 2023，最长接龙序列长度为 4。 (1 -> 12 -> 22 -> 2023)
4. 最终，通过计算最少需要删除的数的个数，得到结果为 5 - 4 = 1。