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

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

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

相关阅读

相关 2019 ICPC 徐州网络赛

A.00:45:42(-1) solved by zcz 队友说抄个板子好了，我看了一下板子是扩展中国剩余定理 ![ContractedBlock.gif][]

分手后的思念是犯贱/ 2023年10月11日 13:28/ 0 赞/ 42 阅读

相关分治维护dp——19南昌网络赛C/cf750E

南昌网络赛，是cf的原题第一次做到这种题，所以认真想了下，每次给一个询问\[L，R\],要求出这个区间里有2017子序列，但是不能有2016子序列需要删掉的最少元素个数

桃扇骨/ 2023年10月11日 07:49/ 0 赞/ 12 阅读

相关 2019ICPC 沈阳网络赛

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

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

相关 2019 ICPC 上海网络赛

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

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

相关 2019 ICPC 南京网络赛

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

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

相关 2019 CCPC网络赛

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

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

相关 CCPC2019网络赛

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

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

相关 2019南昌线上选拔赛

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

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

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

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

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

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

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

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