526互联

Educational Codeforces Round 151 (Div. 2) C

发布时间 2023-07-06 19:50:16作者: wuyoudexian

卡c题了，用双指针做的，赛后发现不用双指针也行。

C. Strong Password

题意

给定1个字符串\(s\)，和两个长度相同的字符串\(l,r\)，字符串的所有元素都在0~9之间。求是否存在一串字符，其中每个数字都在对应位置\(l,r\)的数字之间，且该字符串不能是\(s\)的子序列。

思路

枚举\(l,r\)每个位置数字之间的数字，在字符串\(s\)中从左往右寻找，找到最右边的数字并标记，下次寻找就从标记的位置开始。如此枚举，如果标记到达字符串右端时，还有位置没有枚举，则说明要找的字符串存在，否则不存在。

代码

void solve() {
    int m;
    string s, l, r;
    cin >> s >> m >> l >> r;

    int flag = 0, cnt = 0;
    while(flag < s.size()) {
        int tmp = flag;
        for(char i = l[cnt]; i <= r[cnt]; i++) {
            int pos = s.find(i, flag);
            if(pos == string::npos) {
                cout << "YES\n";
                return;
            }
            tmp = max(tmp, pos);
        }
        cnt++;
        if(cnt >= m) break;
        flag = tmp + 1;
    }

    cout << (flag < s.size() ? "NO\n" : "YES\n");
}