【思维-桶记录数组动态滚动】Encrypted Password UVALive - 6320

男娘i 2022-06-08 00:50 27阅读 0赞

Think:  
1知识点：桶记录数组动态滚动  
2题意：输入字符串1和字符串2，询问字符串1是否可能由字符串2经过3种操作得到，a操作：交换任意两个字符（可交换大于等于0次）；b操作：输出字符串2时在其之前提前输出一个字符串；c操作：输出字符串2之后再输出一个字符串  
3错误反思：注意控制长度  
4方法：桶记录数组动态滚动

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    char st1[101400], st2[101400];
    int a[40], b[40];
    
    int main(){
        int T, i, j, flag;
        scanf("%d", &T);
        while(T--){
            flag = 0;
            memset(a, 0, sizeof(a));
            memset(b, 0, sizeof(b));
            scanf("%s %s", st1, st2);
            int len1 = strlen(st1);
            int len2 = strlen(st2);
            for(i = 0; i < len2-1; i++){
                a[st1[i]-'a']++, b[st2[i]-'a']++;
            }
            b[st2[len2-1]-'a']++;
            for(i = len2-1; i < len1; i++){
                a[st1[i]-'a']++;/*向下滚动*/
                for(j = 0; j < 26; j++){
                    if(a[j] != b[j]){
                        break;
                    }
                }
                if(j == 26){
                    flag = 1;
                    break;
                }
                a[st1[i-(len2-1)]-'a']--;/*状态更新*/
            }
            printf("%s\n", flag == 1? "YES": "NO");
        }
        return 0;
    }

[vjudge]: https://vjudge.net/problem/UVALive-6320

发表评论取消回复

表情：

评论列表（有 0 条评论，27人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVALive - 4329 树状数组

题意：一条大街上住着n个乒乓球爱好者，经常组织比赛。每个人都有一个技能值ai，每场比赛需要3个人：两名选手和一名裁判。规定裁判位置必须在两个选手的中间，而且技能值也必

约定不等于承诺〃/ 2024年02月17日 21:40/ 0 赞/ 25 阅读

相关算法基础：动态规划数组中滚动数组的使用

这篇文章继续在前一篇文章的基础上介绍动态规划数组的优化方式。很多基础算法本来都是写给我家的小少年看的，结果发现后浪学习的速度远远超出我的想象，在一个周末用这篇文章来纪念一下吧。

男娘i/ 2022年11月21日 09:53/ 0 赞/ 30 阅读

相关思维私塾——动态规划

在刷剑指offer和LeetCode中发现，动态规划是经常出现的一类题目，那么接下来我们就来仔细分析和总结下其中的套路。介绍动态规划（DP）说白了其实就是一种求解最

浅浅的花香味﹌/ 2022年10月25日 14:00/ 0 赞/ 137 阅读

相关 UVALive 2197

题意：n个点，m条边，还有一个k，给出每条边的信息，让你选择一些边，使得这些边组成的图里面，每个点只属于k个回路上，问最小的费用。分析：如果每个点都只在k个回路上，那

布满荆棘的人生/ 2022年10月02日 12:00/ 0 赞/ 52 阅读

相关 UVALive 5881 Unique Encryption Keys【线段树】

题目：[UVALive 5881 Unique Encryption Keys][] 分类：线段树，想法题题意：给出n个数，然后有q次查询，每次查询

快来打我*/ 2022年08月10日 13:45/ 0 赞/ 17 阅读

相关关于滚动数组

Minimum Path Sum Given a m x n grid filled with non-negative numbers, find a path fro

小咪咪/ 2022年07月15日 11:16/ 0 赞/ 149 阅读

相关关于滚动数组

Minimum Path Sum Given a m x n grid filled with non-negative numbers, find a path fro

﹏ヽ暗。殇╰゛Y/ 2022年07月15日 11:16/ 0 赞/ 172 阅读

相关 G - Meeting Room Arrangement UVALive - 6606——动态规划

Think: 1知识点：动态规划 2题目分析：会议室0~10时可开会，输入最多20组开会起止时间，询问可安排的最大开会数量 3思路： 1>动态规划——线性时间规

忘是亡心i/ 2022年06月11日 05:47/ 0 赞/ 43 阅读

相关【思维-桶记录数组动态滚动】Encrypted Password UVALive - 6320

Think: 1知识点：桶记录数组动态滚动 2题意：输入字符串1和字符串2，询问字符串1是否可能由字符串2经过3种操作得到，a操作：交换任意两个字符（可交换大于等于0次

男娘i/ 2022年06月08日 00:50/ 0 赞/ 28 阅读

相关 PBE（Password Based Encryption）基于口令加密

基于口令加密是一种根据口令生成密钥并用该密钥进行加密的方法其中的加密解密使用的是同一个密钥 -------------------- 问题的产生：想要保证文件

小鱼儿/ 2022年05月09日 15:48/ 0 赞/ 135 阅读