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

冷不防 2021-12-21 01:07 165阅读 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 条评论，165人围观）

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

相关阅读

相关 2019上海ICPC网络赛 B. Light bulbs【差分+思维】

B. Light bulbs][] 题意： N 个灯泡（编号 0 ~ N-1） M 次操作(初始灯都是关的) 每次操作给 2个数 L, R,把\[L, R\]区...

小鱼儿/ 2024年04月19日 09:48/ 0 赞/ 34 阅读

相关 2019上海ICPC网络赛 B. Light bulbs【差分+思维】

库链接：[https://nanti.jisuanke.com/t/41399][https_nanti.jisuanke.com_t_41399] 题意：n个灯泡，初...

ゞ浴缸里的玫瑰/ 2024年04月19日 09:11/ 0 赞/ 31 阅读

相关 2019ICPC 沈阳网络赛

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

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

相关 2019 ICPC 上海网络赛

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

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

相关 2019 CCPC网络赛

一到网络赛，大家都是东亚之光 1001 00:23:46 solved by hl 签到枚举一下位就行了 ![ContractedBlock.gif][]

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

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

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

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

相关 CCPC2019网络赛

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

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

相关 2019南昌线上选拔赛

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

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

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

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

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

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

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

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