蓝桥杯刷题第二天

题目 3143: 

蓝桥杯2023年第十四届省赛真题-更小的数

题目描述

小蓝有一个长度均为 n 且仅由数字字符 0 ∼ 9 组成的字符串，下标从 0 到 n − 1，你可以将其视作是一个具有 n 位的十进制数字 num，小蓝可以从 num 中选出一段连续的子串并将子串进行反转，最多反转一次。小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 numnew 满足条件 numnew < num，请你帮他计算下一共有多少种不同的子串选择方案，只要两个子串在 num 中的位置不完全相同我们就视作是不同的方案。

注意，我们允许前导零的存在，即数字的最高位可以是 0 ，这是合法的。

输入格式

输入一行包含一个长度为 n 的字符串表示 num（仅包含数字字符 0 ∼ 9），

从左至右下标依次为 0 ∼ n − 1。

输出格式

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

样例输入

210102

样例输出

8

提示

一共有 8 种不同的方案：

1）所选择的子串下标为 0 ∼ 1 ，反转后的 numnew = 120102 < 210102 ；

2）所选择的子串下标为 0 ∼ 2 ，反转后的 numnew = 012102 < 210102 ；

3）所选择的子串下标为 0 ∼ 3 ，反转后的 numnew = 101202 < 210102 ；

4）所选择的子串下标为 0 ∼ 4 ，反转后的 numnew = 010122 < 210102 ；

5）所选择的子串下标为 0 ∼ 5 ，反转后的 numnew = 201012 < 210102 ；

6）所选择的子串下标为 1 ∼ 2 ，反转后的 numnew = 201102 < 210102 ；

7）所选择的子串下标为 1 ∼ 4 ，反转后的 numnew = 201012 < 210102 ；

8）所选择的子串下标为 3 ∼ 4 ，反转后的 numnew = 210012 < 210102 ；

对于 20% 的评测用例，1 ≤ n ≤ 100 ；

对于 40% 的评测用例，1 ≤ n ≤ 1000 ；

对于所有评测用例，1 ≤ n ≤ 5000 。

#include<stdio.h>
 
#include<stdlib.h>
 
#define N 5000 //最长字符串长度为5000
 
int main()
 
{
 
char arr[N];
 
int n = 0;
 
int number = 0;
 
 
 
scanf("%s", arr);
 
n = strlen(arr);
 
 
 
for(int i=0;i<n-1;i++) 
 
{
 
for (int j = i + 1; j < n; j++)
 
{
 
if (arr[i] > arr[j]) 
 
{
 
number++;
 
}
 
else if (arr[i] == arr[j])
 
{
 
int temp1 = i;
 
int temp2 = j;
 
 
 
while (temp1<temp2)
 
{
 
temp1++;
 
temp2--;
 
if (arr[temp1] > arr[temp2])
 
{
 
number++;
 
break;
 
}
 
else if (arr[temp1] < arr[temp2])
 
{
 
break;
 
}
 
}
 
}
 
}
 
}
 
printf("%d", number);
 
return 0;
 
}
 

因为自己太菜了，都是看完了大佬们解完题后写的。