本文共 3846 字，大约阅读时间需要 12 分钟。

0x01

猿辅导APP需要下发一些宣传文本给学生，工程师使用了一种字符压缩算法，为简单起见，假设被压缩的字符全部为大写字母序列，规则如下：

• AAAB可以压缩为A3B（单字符压缩不加括号）
• ABABA可以压缩为(AB)2A（多字符压缩才加括号）

输入数据保证不会出现冗余括号，且表示重复的数字一定合法且大于1，即不会出现：

• (A)2B
• ((AB))2C
• (A)B
• A1B
• (AB)1B

注意：数字可能出现多位数即A11B或者(AB)10C或者A02这种情况。

输入描述：

第一行是正整数C(C <= 100)，表示下面有C组数据。之后C行，每行为一组数据，每组数据为一个字符串。每个字符串由A-Z，数字0-9和()组成表示一个压缩后的串，保证输入数据一定合法且字符串长度小于50。

输出描述：

输出C行，每行对应一个数据的输出结果，表示压缩后的字符串，保证每个字符串展开后的长度不超过10^6。

示例：

5A11B(AA)2A((A2B)2)2G(YUANFUDAO)2JIAYOUA2BC4D2

输出：

AAAAAAAAAAABAAAAAAABAABAABAABGYUANFUDAOYUANFUDAOJIAYOUAABCCCCDD

解题思路

这个问题和之前的非常类似，使用递归调用即可。

• 如果碰到数字，我们需要继续遍历找到所有数字构成的数是多少，然后我们的结果字符串res添加string(num-1,res.back())
• 如果碰到字母，直接将字母添加到结果串中
• 如果碰到'('，我们需要将递归加过添加到结果串中res+=dfs()
• 如果碰到')'，我们需要将')'后面的所有数字都找到，然后结果字符串中添加(num-1)*res。

#include 
   
    using namespace std;int c, n, u;string str;string dfs() {
       int num = 0;    string res;    while (u < n) {
           if (str[u] >= '0' && str[u] <= '9') {
               num = num * 10 + str[u++] - '0';            while (u < n && str[u] >= '0' && str[u] <= '9') {
                   num = num * 10 + str[u++] - '0';            }            res += string(num - 1, res.back());            num = 0; --u;        } else if (str[u] == '(') {
               ++u;            res += dfs();        } else if (str[u] == ')') {
               ++u;            while (u < n && str[u] >= '0' && str[u] <= '9') {
                   num = num * 10 + str[u++] - '0';            }            --u;            string t;            for (int i = 0; i < num; ++i) t += res;            return t;        } else res += str[u];        u++;    }    return res;}int main(){
       cin >> c;    for (int i = 0; i < c; ++i) {
           cin >> str;        n = str.size(), u = 0;        cout << dfs() << endl;    }}
   

0x02

有一个N*M大小的迷宫矩阵，迷宫的每一个格子有一个数值（a[i][j]<10^9）。小猿在迷宫中发现，它只能朝着上下左右四个方向的相邻格子前进，并且只能进入比当前位置数值更大的格子。但是小猿有个紧急呼救按钮，他可以通过按下按钮，强行进入到不满足条件的相邻格子，可惜按钮只能按K次。请问小猿从这个迷宫任选一个格子出发，在紧急呼救按钮的帮助下，最多可以走多少步（开始位置计入步数，即站在起点是步数为1）。

输入描述：

第一行输入三个数N,M,K。接下来N行，每行M个数，表示迷宫中每个格子的值。1<=N<=5001<=M<=5000<=K<=10

输出描述：

输出小猿在迷宫中能走的最大步数

示例1：

3 3 11 3 32 4 68 9 2

输出：

6

说明：其中一种方案是(0,0)(0,1)(0,0)(1,0)(2,0)(2,1)

解题思路

显然这是一个dfs加记忆化搜索的问题，这种问题使用python写会简洁一些。

from functools import lru_cachen, m, k = list(map(int, input().split()))data = []for _ in range(n):    data.append(list(map(int, input().split())))@lru_cache(None)def dfs(x, y, k):    res = 0    for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:        nx, ny = i + x, j + y        if nx >= 0 and nx < n and ny >= 0 and ny < m:            if data[x][y] < data[nx][ny]:                res = max(res, dfs(nx, ny, k) + 1)            elif data[x][y] >= data[nx][ny] and k > 0:                res = max(res, dfs(nx, ny, k - 1) + 1)    return resres = 0for i in range(n):    for j in range(m):        res = max(res, dfs(i, j, k))print(res + 1)

0x03

K(K>=3)个猿辅导的老师们在玩一个击鼓传花的小游戏，每击一次鼓，拿着花的老师要将花交给别人，不能留在自己手中。游戏开始前花在小猿手中，求击鼓N次后，这朵花又回到小猿手中的方案数，请输出这个数的模1e9+7。

输入描述：

输入两个数N, K。3 <= N <= 1e9  3 <= K <= 1e9

输出描述：

输出方案数模1e9+7后的结果

示例1：

3 3

输出：

2

解题思路

经典的动态规划问题，我们可以定义函数$f(i,p)$表示击鼓i次后是不是在手里，p==0表示在手里，p==1不在手里。那么

• $f(i,0)=f(i-1,1)$
• $f(i,1)=f(i-1,1)\ast (k-2)+f(i-1,0)\ast (k-1)$

说明一下上面的式子，当$f(i,0)$表示第$i$个状态的时候在手里，那么$i-1$状态的时候一定不在手里。如果$f(i,1)$表示第$i$个状态不在手里，那么$i-1$状态的时候可以在手里，也可以不在手里，在手里有$k-1$种情况（即，将自己手里的花传给其他人），不在手里有$k-2$种情况（即，既不在自己手里也不在上一轮的人手里）。

考虑边界问题，当n==1的时候，此时只能在手中，也就是$f(0,0)=1,f(0,1)=0$。

n, k = list(map(int, input().split()))MOD = 10**9 + 7mem = [[1, 0] for _ in range(n)]for i in range(1, n):    mem[i][0] = mem[i-1][1]%MOD    mem[i][1] = (mem[i-1][1]*(k - 2)%MOD + mem[i-1][0]*(k - 1))%MODprint(mem[n-1][0])

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/98597843 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！