首页 > 其他分享 >Strong Password(贪心思想)

Strong Password(贪心思想)

时间:2023-07-12 15:57:02浏览次数:39  
标签:digits Strong string Password testcase only criteria password 贪心

Strong Password time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Monocarp finally got the courage to register on ForceCoders. He came up with a handle but is still thinking about the password.

He wants his password to be as strong as possible, so he came up with the following criteria:

  • the length of the password should be exactly m;
  • the password should only consist of digits from 00 to 99;
  • the password should not appear in the password database (given as a string s) as a subsequence (not necessarily contiguous).

Monocarp also came up with two strings of length m: l and r, both consisting only of digits from 00 to 99. He wants the i-th digit of his password to be between li and ri, inclusive.

Does there exist a password that fits all criteria?

Input

The first line contains a single integer t (1≤t≤1041≤≤104) — the number of testcases.

The first line of each testcase contains a string s (1≤|s|≤3⋅1051≤||≤3⋅105), consisting only of digits from 00 to 99 — the password database.

The second line contains a single integer m (1≤m≤101≤≤10) — the required length of the password.

The third line contains a string l (|l|=m||=), consisting only of digits from 00 to 99 — the lower restriction on each digit.

The fourth line contains a string r (|r|=m||=), consisting only of digits from 00 to 99 — the upper restriction on each digit. li≤ri≤ for all i from 11 to m.

The sum of lengths of s over all testcases doesn't exceed 3⋅1053⋅105.

Output

For each testcase, print "YES" if there exists a password that fits all criteria. Print "NO" otherwise.

Example input Copy 5 88005553535123456 2 50 56 123412341234 3 111 444 1234 4 4321 4321 459 2 49 59 00010 2 10 11 output Copy
YES
NO
YES
NO
YES
Note

In the first testcase, Monocarp can choose password "50". It doesn't appear in s as a subsequence.

In the second testcase, all combinations of three digits, each of them being from 11 to 44, fit the criteria on l and r. However, all of them appear in s as subsequences. For example, "314" appears at positions [3,5,12][3,5,12] and "222" appears at positions [2,6,10][2,6,10].

In the third testcase, Monocarp can choose password "4321". Actually, that is the only password that fits the criteria on l and r. Luckily, it doesn't appear in s as a subsequence.

In the fourth testcase, only "49" and "59" fit the criteria on l and r. Both of them appear in s as subsequences.

In the fifth testcase, Monocarp can choose password "11".

//Strong Password
//贪心的想,每次寻找字母都找在字符串中位置最靠后的,这样出现密码的范围才会变小
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
int n,t,a[N],f[N],res,num,ans,m;
bool vis[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        res=0;
        string s,l,r;
        cin>>s>>n>>l>>r;
        for(int i=0;i<n;i++){
            int pos=0;
            for(int j=l[i];j<=r[i];j++){
                int x=s.find(j,res);//找到这个字母
                if(x==-1){//如果没有,那就直接判断为可以
                    cout<<"YES"<<endl;
                    goto nexts;
                }
                pos=max(pos,x+1);//如果这个数字位置靠后就更新
            }
            res=max(pos,res);//找到目前位数最靠后的数字
        }
        cout<<"NO"<<endl;
        nexts:;
    }
    return 0;
}

 

 

标签:digits,Strong,string,Password,testcase,only,criteria,password,贪心
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17547698.html

相关文章

  • SMU 2023 Spring 题单 第二周 贪心
    Saruman'sArmy首先对序列排序,然后逐个考虑覆盖,如果要覆盖当前的点,则标记点越靠后越好,所有向后找\(R\),选择最靠后的标记,然后从标记点开始在向后找\(R\)也是被标记过的,直接跳过#include<cstdio>#include<algorithm>usingnamespacestd;intread(){intx=0,f=1......
  • 第二节 贪心
    引入贪心算法(英语:greedyalgorithm),是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪,每一步行动总是按某种指标选取最优的操作。而且他目光短浅,总是只看眼前,并不考虑以后可能造成的影响。可想而知,并不是所有的时候贪心法都能获得最优解,所以一般使用贪心法的时候......
  • abc065d <贪心+最小生成树> [lambda表达式]
    D-Built?//https://atcoder.jp/contests/abc065/tasks/arc076_b//贪心+最小生成树//关键在于意识到,连接x或y相邻的边代价最小,因而无需考虑全部的边,仅需考虑这些相邻边即可(贪心)//学习://1.lambda写法https://www.cnblogs.com/yaya12138/p/11815475.html//......
  • abc064d <贪心/前缀和>
    D-Insertion另一种做法,注意这两种写法:max_elementstring(个数,字符)//https://atcoder.jp/contests/abc064/tasks/abc064_d//贪心//要求答案为字典序最小,因而补充的'('都放在最前面,')'都放在最后面//从左到右遍历,记录未匹配的左括号个数cntl,//当......
  • 贪心&&模拟&&搜索
    贪心基于微扰证明但关系不具有传递性的贪心感觉起了个离谱的标题先看题:P2123皇后游戏既然这题像国王游戏就顺着考虑微扰贪心,对于两个大臣\(i,j=i+1\),假设现在的顺序是最优顺序,那么记\(last=c_{i-1},sum=\sum_{k=1}^{i-1}a_k\)有:\[cost_1=max\{last+b_i,sum......
  • 5944: 小船过河 经典贪心
    描述  N个人要过河,但只有一条小船,每次只能坐2人,每个人有不同的划船速度,而两个人一起过河时小船速度由最慢的人的速度决定。请设计一个过河方案,使得所有人均过河,且所用总时间最少。   输入  第一行为正整数N(N<=1000),表示人数,第二行为N个正整数,表示每个人的速度(......
  • Educational Codeforces Round 151 (Rated for Div. 2) C. Strong Password
    题目翻译,给定t组数据,每组数据包含一个字符串s,两个长度为m的字符串l和r,要求判断是否存在一个长度为m的字符串res,满足l[i]<=res[i]<=r[i](i->0~m)且不是s的子序列贪心首先对于所有满足l<res<r的字符串,我们只需判断是否存在一个字符串不是子序列即可,那么我们让res成为子序列的可能......
  • CodeForces 1845C Strong Password
    洛谷传送门CF传送门我怎么这么多天没写题解了,快来水一篇。考虑对\(s\)串建子序列自动机后dp。设\(n=|s|\)。建子序列自动机,就是求出\(nxt_{i,j}\)为\([i,n]\)中第一个等于\(j\)的位置,不存在则\(nxt_{i,j}=n+1\)。然后我们设\(f_{i,j}\)为填到密码的......
  • CF1845C Strong Password
    思路这场edu爆炸了,特此记录。由于\(m\le10\),因此可以直接考虑搜索。对于定义状态为\((idx,cur)\),表示当前在填密码的第\(idx\)位,且使用了\(s\)中的前\(cur\)个字符。首先注意到对于同一个数字,如果其在\(s\)中出现了不止一次,那么出现在前边的显然比出现在后边的潜......
  • mysql: [Warning] Using a password on the command line interface can be insecure.
      https://zhuanlan.zhihu.com/p/542166965 ......