CSDN编程竞赛报名地址：https://edu.csdn.net/contest/detail/23

文章目录

• 第十期竞赛题目
• • 一、熊孩子拜访
  • • 1、题目描述
    • 2、代码实现
  • 二、走楼梯
  • • 1、题目描述
    • 2、代码实现
  • 三、括号上色
  • • 1、题目描述
    • 2、代码实现
  • 四、喜水青蛙
  • • 1、题目描述
    • 2、代码实现

第十期竞赛题目

一、熊孩子拜访

1、题目描述

  已知存在一个长度为 nnn 的整数序列 AAA。AAA中所有元素按照从小到大的顺序进行排序。现在执行操作倒置一段序列。请找到 AAA 序列里的倒置子序列。

• 输入描述： 第一行输入整数 n(1≤n≤1000)n(1≤n≤1000)n(1≤n≤1000)，第二行输入 nnn 个整数 (1≤num≤10000)(1≤num≤10000)(1≤num≤10000)。
• 输出描述： 输出被倒置的数列的左值，右值。如果没有输出0 0。

示例：

输入：4
   1 3 2 4
输出：2 3

2、代码实现

解题步骤如下：

1. 从前往后进行查找，找到第一个比后面一个数大的位置，该位置的数就是被倒置的数列的左值，如果没有找到满足要求的位置，则输出0 0。
2. 继续向后进行查找，找到第一个比后面一个数小的位置，该位置的数就是被倒置的数列的右值。

代码如下：

//熊孩子拜访
#include 
#include 
#include 
#include 
using namespace std;
int main() 
{int n;cin >> n;vector v(n);for (int i = 0; i < n; i++){cin >> v[i];}//1、从前往后进行查找，找到第一个比后面一个数大的位置int index = 1;while (index < n&&v[index - 1] <= v[index]){index++;}if (index == n){//如果没有则输出0 0cout << 0 << " " << 0 << endl;return 0;}//2、继续向后进行查找，找到第一个比后面一个数小的位置int start = index - 1;while (index < n&&v[index - 1] >= v[index]){index++;}int end = index - 1;cout << v[end] << " " << v[start] << endl;return 0;
}

二、走楼梯

1、题目描述

  现在有一截楼梯，根据你的腿长，你一次能走 1 级或 2 级楼梯，已知你要走 nnn 级楼梯才能走到你的目的楼层，请实现一个方法，计算你走到目的楼层的方案数。

• 输入描述： 输入整数 n(1≤n≤50)n(1≤n≤50)n(1≤n≤50)。
• 输出描述： 输出方案数。

示例：

输入：5
输出：8

2、代码实现

解题步骤如下：

1. 走 nnn 级楼梯的方案数等于，走 n−1n-1n−1 级楼梯的方案数和走 n−2n-2n−2 级楼梯的方案数之和，即 f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2)f(n)=f(n−1)+f(n−2)，按照求第 nnn 个斐波那契数的方法进行求解即可。

代码如下：

//走楼梯
#include 
#include 
#include 
#include 
using namespace std;
long long Fibonacci(int n)
{if (n == 1 || n == 2)return n;long long first = 1;long long second = 1;long long third = 2;while (n > 2){first = second;second = third;third = first + second;n--;}return third;
}
int main() 
{int n;cin >> n;cout << Fibonacci(n) << endl;return 0;
}

三、括号上色

1、题目描述

  小艺酱又得到了一堆括号。括号是严格匹配的。现在给括号进行上色。上色有三个要求：1、只有三种上色方案，不上色，上红色，上蓝色。2、每对括号只有一个上色。3、相邻的两个括号不能上相同的颜色。但是可以都不上色。问括号上色有多少种方案？答案对1000000007取模。

• 输入描述： 输入括号序列 s(2≤∣s∣≤700)s(2≤|s|≤700)s(2≤∣s∣≤700)。
• 输出描述： 输出方案数。

示例：

输入：(())
输出：12

2、代码实现

解题步骤如下：

1. 动态规划。

代码如下：

//括号上色
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7, N = 705;
int f[N][N][3][3];
int m[N];
int solution(std::string s) {int n = s.size();vector stk;for (int i = 0; i < n; i++) {//预处理一下括号匹配的位置if (s[i] == '(') stk.push_back(i);else {int u = stk.back();stk.pop_back();m[u] = i;m[i] = u;}}for (int i = 0; i < n; i++) {//状态边界if (m[i] == i + 1) f[i][i + 1][0][1] = f[i][i + 1][0][2] = f[i][i + 1][1][0] = f[i][i + 1][2][0] = 1;}for (int len = 4; len <= n; len += 2) {for (int i = 0, j = i + len - 1; j < n; i++, j++) {if (s[i] != '(' || s[j] != ')') continue;if (m[i] == j) {for (int a = 1; a < 3; a++) {//只枚举需要染色的一端for (int b = 0; b < 3; b++) {if (b == a) continue;//匹配的括号颜色不能相同for (int c = 0; c < 3; c++) {f[i][j][a][0] = (f[i][j][a][0] + f[i + 1][j - 1][b][c]) % MOD;f[i][j][0][a] = (f[i][j][0][a] + f[i + 1][j - 1][c][b]) % MOD;}}}}else {int i1 = m[i], j1 = m[i] + 1;for (int a = 0; a < 3; a++) {for (int b = 0; b < 3; b++) {for (int c = 0; c < 3; c++) {for (int d = 0; d < 3; d++) {if (b == c && b) continue;//相邻括号有颜色不能相同//乘法原理，不用考虑子序列匹配的括号颜色是否相同，相同的话值就是0//这里乘法要加上强转，不然会爆intf[i][j][a][d] = (f[i][j][a][d] + ((ll)f[i][i1][a][b] * f[j1][j][c][d]) % MOD) % MOD;}}}}}}}int res = 0;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {res = (res + f[0][n - 1][i][j]) % MOD;}}return res;
}
int main() {std::string s;std::cin >> s;int result = solution(s);std::cout << result << std::endl;return 0;
}

四、喜水青蛙

1、题目描述

  总数喜欢在水里嬉戏的青蛙，某天要过河拜访一位朋友。
  已知河道中长满了带刺的不知名生物，能通过的路只有一条直线，长度为 LLL。
  直线上随机分布着 mmm 块石头。青蛙的最小跳跃距离是 sss，最大跳跃距离是 ttt。
  青蛙想要尽可能的少踩石头，那么它通过河道最少会踩到多少石头？

• 输入描述： 多组数据输入，其中每组数据：第一行输入1个整数 L(1≤L≤1e9)L(1≤L≤1e9)L(1≤L≤1e9)。第二行输入3个整数：s、t、m(1≤s≤t≤10，1≤m≤100)s、t、m(1≤s≤t≤10，1≤m≤100)s、t、m(1≤s≤t≤10，1≤m≤100)。第三行输入 mmm 个不同的整数，表示 mmm 个石子在数轴上的分布位置。每行所有相邻整数用空格隔开。
• 输出描述： 输出青蛙过河最少会踩到的石子数量，每组输入数据对应的输出结果单独成行。

示例：

输入：10
   2 3 5
   2 3 5 6 7
输出：2

2、代码实现

解题步骤如下：

1. 动态规划。

代码如下：

//喜水青蛙
#include 
#include 
#include 
using namespace std;
const int N = 10100;
int f[N], w[N], stones[105];
int main(){int L, s, t, m;cin >> L >> s >> t >> m;for (int i = 1; i <= m; i++)    cin >> stones[i];int res = 0;if (s == t) {for (int i = 1; i <= m; i++) {if (stones[i] % s == 0)  res++;}cout << res << endl;}else {int last = 0;sort(stones + 1, stones + m + 1);for (int i = 1; i <= m; i++) {int diff = min(stones[i] - last, 100);last = stones[i];stones[i] = stones[i - 1] + diff;}for (int i = 1; i <= m; i++)   w[stones[i]] = 1;memset(f, 0x3f, sizeof f);f[0] = 0;for (int i = s; i <= stones[m] + 10; i++) {for (int j = i - t; j <= i - s; j++) {if (j < 0)   continue;f[i] = min(f[i], f[j] + w[i]);}}res = 100;for (int i = stones[m]; i <= stones[m] + 10; i++)  res = min(res, f[i]);cout << res << endl;}return 0;
}