2019南昌网络赛-M（二分）

冷不防 2021-12-21 01:07 182阅读 0赞

题目链接：https://nanti.jisuanke.com/t/38232

题意：给定字符串s（长度<=1e5)，然后N组样例(N<=1e5)，每组输入一个字符串t判断t是否为s的字串（可以不连续）。

思路：直接暴力判断的话肯定会超时，可以用vector将每个英文字符出现的下标存放。然后对每一组输入，利用函数upper\_bound（原理为二分）来查找，s的长度为m1,t的长度为m2，复杂度为O(N\*m2\*logm1)。

AC代码：

#include<cstdio>
    #include<algorithm>
    #include<vector>
    #include<cstring>
    using namespace std;
    
    char s[100005],t[1005];
    vector<int> v[30];
    int len1,len2,N;
    
    int main(){
        scanf("%s",s);
        len1=strlen(s);
        for(int i=0;i<len1;++i)
            v[s[i]-'a'].push_back(i);
        scanf("%d",&N);
        while(N--){
            scanf("%s",t);
            len2=strlen(t);
            if(v[t[0]-'a'].empty()){
                printf("NO\n");
                continue;
            }
            int p1=v[t[0]-'a'][0],p2,flag=1;
            for(int i=1;i<len2;++i){
                if(v[t[i]-'a'].empty()){
                    flag=0;
                    break;
                }
                int tmp=t[i]-'a';
                p2=upper_bound(v[tmp].begin(),v[tmp].end(),p1)-v[tmp].begin();
                if(p2<v[tmp].size()){
                    p1=v[tmp][p2];
                }
                else{
                    flag=0;
                    break;
                }
            }
            if(flag) printf("YES\n");
            else printf("NO\n");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/FrankChen831X/p/10744273.html

发表评论取消回复

表情：

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

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

相关阅读

相关 2019ICPC 沈阳网络赛

A. 2:40:11(-7) solved by zcz 通过旋转使得抓人的在左下角，逃得在右上角结论是逃得一定在右上或者右下左上被抓住，找到规律枚举一下即可 !

左手的ㄟ右手/ 2023年10月10日 07:52/ 0 赞/ 45 阅读

相关 2019 ICPC 上海网络赛

摸了一整场的鱼，签了个到，做了个FFT还忘记初始化赛后才发现 B.00:16:52 solved by hl 很显然前缀和搞搞就行了，但是卡O(N),要O(M) !

深藏阁楼爱情的钟/ 2023年10月10日 07:51/ 0 赞/ 52 阅读

相关 2019 ICPC 南京网络赛

A. 00:40:35 solved by hl 很显然需要一种方法O(1)定位x,y上的数字，利用矩阵的规律可以找到然后就是一个子矩阵和问题，小范围可以直接二维前

短命女/ 2023年10月10日 07:49/ 0 赞/ 47 阅读

相关 2019ccpc网络赛hdu6705 path

path [题目传送门][Link 1] 解题思路先用vector存图，然后将每个vector按照边的权值从小到大排序。将每个顶点作为起点的边里最短的边存入优先

怼烎@/ 2023年08月17日 17:21/ 0 赞/ 63 阅读

相关 The Nth Item 南昌网络赛（递推数列，分段打表）

The Nth Item \\\[ Time Limit: 1000 ms \\quad Memory Limit: 262144 kB \\\] 题意给出递推

比眉伴天荒/ 2023年08月17日 17:04/ 0 赞/ 98 阅读

相关 Robots 2019南京网络赛（概率dp）

Robots \\\[ Time Limit: 1000 ms \\quad Memory Limit: 262144 kB \\\] 题意有一个机器人要从 \

曾经终败给现在/ 2023年08月17日 17:04/ 0 赞/ 46 阅读

相关 CCPC2019网络赛

1001：输出A&B 特判A&B=0 1007: 思路：按照题意去写，分为四个部分，只有第三部分与第一部分相反，其余都与第一部分相同所以我们以第一部分为基准，去扩

深藏阁楼爱情的钟/ 2023年08月17日 16:26/ 0 赞/ 123 阅读

相关 2019南昌线上选拔赛

[ (打表找规律+前缀异或和)MORE XOR][_MORE XOR] [H.Coloring Game][] > 推出来n大于1时，3^(n-2)\4。 > > 这题让

冷不防/ 2022年04月24日 08:32/ 0 赞/ 164 阅读

相关 2019南昌网络赛-M（二分）

题目链接：https://nanti.jisuanke.com/t/38232 题意：给定字符串s（长度<=1e5)，然后N组样例(N<=1e5)，每组输入一个字符串t判断t

冷不防/ 2021年12月21日 01:07/ 0 赞/ 183 阅读

相关 2019南昌邀请赛网络赛 I.Max answer

单调栈维护左边和右边第一个大于它的位置用ST表维护区间前缀和的最大值和最小值当前点小于0的时候就是后半部分 S m i n − 前半部分 S m a

亦凉/ 2021年09月19日 00:54/ 0 赞/ 321 阅读