首页 > 其他分享 >洛谷题单指南-递推与递归-P1928 外星密码

洛谷题单指南-递推与递归-P1928 外星密码

时间:2024-02-18 10:23:45浏览次数:28  
标签:end 递归 int 洛谷题 decode num P1928 指针 外星

原题链接:https://www.luogu.com.cn/problem/P1928

题意解读:要对形如xxx[Nxxx]xxx的字符串进行解码,[]内第一个数表示括号中字符串重复的次数,可以嵌套。

解题思路:

用递归进行处理,设函数decode(start,end)将下标从start到end之间字符串进行解码

递归过程如下:

遍历start~end的每一个字符

1、如果如果不是"[",直接输出

2、如果是"[",则一直找到与之配对的"]",并提取出"["之后的数字num

for 1...num   
    decode(num之后的字符下标,]之前的字符下标)

算法的关键在于利用三个指针i,j,k

i指针用来遍历整个字符串,j指针用来提出"["之后的整数,k指针用来找到与"["配对的"]"

具体实现见代码注释。

100分代码:

#include <bits/stdc++.h>
using namespace std;

string s;

void decode(int l, int r)
{
    int match = 0;
    for(int i = l; i <= r; i++) //遍历l~r之间每一个字符
    {
        if(s[i] != '[') //如果是"["则直接输出
        {
            cout << s[i];
            continue;
        } 

        match++; //用match来寻找与"["配对的"]"",遇到"["match++,遇到"]"match--,match==0则找到

        int num = 0;
        int j = i + 1; //j指针用来提取"["之后的整数
        while(s[j] >= '0' && s[j] <= '9') 
        {
            num = num * 10 + s[j] - '0';
            j++; //循环结束后j的位置即是"[]"中第一个非数字字符的位置
        }

        int k = j - 1; //k指针用来寻找与"["配对的"]"
        while(match)
        {
            char c = s[++k]; //循环结束后,k的位置即是配对的"]"的位置
            if(c == '[') match++;
            else if(c == ']') match--;
        }

        for(int i = 1; i <= num; i++) decode(j, k - 1);

        i = k;
    }
}

int main()
{
    cin >> s;
    decode(0, s.size() - 1);

    return 0;
}

 

标签:end,递归,int,洛谷题,decode,num,P1928,指针,外星
From: https://www.cnblogs.com/jcwy/p/18018845

相关文章

  • 洛谷题单指南-递推与递归-P1464 Function
    原题链接:https://www.luogu.com.cn/problem/P1464题意解读:虽然a、b、c可输入的范围比较大,但是递归中,只会限制在0-20以内,由于递归中有大量的重复计算,因此需要采用记忆化搜索来保存已经计算过的递归函数值。解题思路:定义三位数组LLmem[25][25][25],mem[a][b][c]保存w(a,b,c)的......
  • 洛谷题单指南-递推与递归-P1028 [NOIP2001 普及组] 数的计算
    原题链接:https://www.luogu.com.cn/problem/P1028题意解读:给定n,构造数列,可以用递归或者递推。解题思路:1、递归定义count(n)返回数列的个数  n==1时,count(n)=1  n!=1时,count(n)=1+count(1)+count(2)+...+count(n/2)注意,递归会导致大量重复计算,需要用一个hash......
  • 洛谷题单指南-递推与递归-P1044 [NOIP2003 普及组] 栈
    原题链接:https://www.luogu.com.cn/problem/P1044题意解读:一组数入栈、出栈的方案数,如果了解卡特兰数,此题可以秒杀;如果不了解,也可以通过递归或者递推来解决;最次,可以通过DFS暴搜出方案数,当然对于n个数,一共有n次入栈、n次出栈,一共2n次,每次要么入栈要么出栈,总搜索次数在22n规模,n最......
  • 洛谷题单指南-递推与递归-P1002 [NOIP2002 普及组] 过河卒
    原题链接:https://www.luogu.com.cn/problem/P1002题意解读:从A(0,0)点走到B(n,m)点,只能向右或者向下,C点以及其控制点不能走。解题思路:根据题意,此题要么递归(DFS),要么递推(动态规划)先分析数据规模,最大从起点到终点要走40步,每个步有2种走法,一共240种路径,DFS会超时,且方案数必须用longlong......
  • 洛谷题解-P1194 买礼物
    https://www.luogu.com.cn/problem/P1194题目描述又到了一年一度的明明生日了,明明想要买BBB样东西,巧的是,这BBB样东西价格都是AAA元。但是,商店老板说最近有促销活动,也就是:如果你买了第III样东西,再买第JJJ样,那么就可以只花KI,JK_{I,J}KI,J​元,更巧的是,KI,JK_{I,J}K......
  • P1928 外星密码
    题目链接:本题如果直接模拟去做的话极为繁琐,输入的这个字符串是被多重「压缩」的,所以一重一重地「解压缩」可能会非常非常麻烦(不过应该是可行的),导致代码极其难以理解。所以,我们使用递归算法,在读入这个字符串之后,找出被压缩的内容,再对被压缩的那个字符串实行「解压缩」操作。举个......
  • 洛谷题单指南-暴力枚举-P2392 kkksc03考前临时抱佛脚
    原题链接:https://www.luogu.com.cn/problem/P2392题意解读:由于可以同时计算两道同一科的题目,只需要把某一科题目分两堆,使得两堆总时长之差最小,时长较大的一堆就是完成这一科的最短时间。解题思路:既然直到了要把一科题目分两堆,关键是如何分堆呢?比较容易犯的错是用贪心来解题:把......
  • 洛谷题单指南-暴力枚举-P3799 妖梦拼木棒
    原题链接:https://www.luogu.com.cn/problem/P3799题意解读:要选四根木棒拼成等边三角形,必然有两根长度相等,其余两根长度之和等于前两根解题思路:木棒总数最大100000,每根最长5000,因此通过枚举其中两根木棒的长度,计算出另外两根的长度,通过各个长度的木棒数进行选择。设数组h[n]保......
  • 洛谷题单指南-暴力枚举-P1149 [NOIP2008 提高组] 火柴棒等式
    原题链接:https://www.luogu.com.cn/problem/P1149题意解读:计算符合A+B=C时,火柴棍数量正好等于n,可以采用枚举A、B,然后计算出C,根据A、B、C计算出所有火柴棍数量,再加上4根加号、等号的,如果与n相等,即为一种合法等式。解题思路:题目的关键在于枚举A、B时,最大值的设定,不能超时。分析......
  • 洛谷题单指南-暴力枚举-P1217 [USACO1.5] 回文质数 Prime Palindromes
    原题链接:https://www.luogu.com.cn/problem/P1217题意解读:本题要找[a,b]范围内的所有回文质数,千万不要被题目提示所干扰,如果按照提示先产生各个长度的回文数,再依次判断是否是素数,程序写起来比较繁琐,需要根据a、b的长度,写8个判断是否产生1~8位回文数,最后做素数判断。换一个思路......