CF750E New Year and Old Subsequence

    • 25通过
    • 34提交
  • 题目来源 CodeForces 750E
  • 评测方式 RemoteJudge
  • 标签
  • 难度 省选/NOI-
  • 时空限制 3000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述

    定义一个数字串满足性质$nice$当且仅当:该串包含子串$2017$,且不包含子串$2016$。

    定义一个数字串的函数$ugliness$为:该串至少删去几个字符,可以使得剩余串满足性质$nice$;如果该串没有满足性质$nice$的子串,则该串的$ugliness$是$-1$。

    给定一个长度为$n$的字符串$t$,和$q$次询问,每次询问用$(l,r)$表示。对于每次询问,回答$ugliness(t[l,r])$。

    输入输出格式

    输入格式:

    第一行输入两个整数$n,q$ ,其中$n$是字符串$s$的长度,$q$是询问的个数。

    第二行输入完全由十进制数字组成的字符串$s$。

    接下来的$n$行,每行输入两个整数$l,r$,描述一个询问。

    输出格式:

    对于每个询问,输出一行答案。

    数据范围:

    $$ 4 \leq n \leq 200000,1 \leq q \leq 200000,1 \leq l \leq r \leq n $$

    题目描述

    A string $ t $ is called nice if a string "2017" occurs in $ t $ as a subsequence but a string "2016" doesn't occur in $ t $ as a subsequence. For example, strings "203434107" and "9220617" are nice, while strings "20016", "1234" and "20167" aren't nice.

    The ugliness of a string is the minimum possible number of characters to remove, in order to obtain a nice string. If it's impossible to make a string nice by removing characters, its ugliness is $ -1 $ .

    Limak has a string $ s $ of length $ n $ , with characters indexed $ 1 $ through $ n $ . He asks you $ q $ queries. In the $ i $ -th query you should compute and print the ugliness of a substring (continuous subsequence) of $ s $ starting at the index $ a_{i} $ and ending at the index $ b_{i} $ (inclusive).

    输入输出格式

    输入格式:

    The first line of the input contains two integers $ n $ and $ q $ ( $ 4<=n<=200000 $ , $ 1<=q<=200000 $ ) — the length of the string $ s $ and the number of queries respectively.

    The second line contains a string $ s $ of length $ n $ . Every character is one of digits '0'–'9'.

    The $ i $ -th of next $ q $ lines contains two integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i}<=b_{i}<=n $ ), describing a substring in the $ i $ -th query.

    输出格式:

    For each query print the ugliness of the given substring.

    输入输出样例

    输入样例#1: 复制
    8 3
    20166766
    1 8
    1 7
    2 8
    
    输出样例#1: 复制
    4
    3
    -1
    
    输入样例#2: 复制
    15 5
    012016662091670
    3 4
    1 14
    4 15
    1 13
    10 15
    
    输出样例#2: 复制
    -1
    2
    1
    -1
    -1
    
    输入样例#3: 复制
    4 2
    1234
    2 4
    1 2
    
    输出样例#3: 复制
    -1
    -1
    

    说明

    In the first sample:

    • In the first query, $ ugliness( $ "20166766" $ )=4 $ because all four sixes must be removed.
    • In the second query, $ ugliness( $ "2016676" $ )=3 $ because all three sixes must be removed.
    • In the third query, $ ugliness( $ "0166766" $ )=-1 $ because it's impossible to remove some digits to get a nice string.

    In the second sample:

    • In the second query, $ ugliness( $ "01201666209167" $ )=2 $ . It's optimal to remove the first digit '2' and the last digit '6', what gives a string "010166620917", which is nice.
    • In the third query, $ ugliness( $ "016662091670" $ )=1 $ . It's optimal to remove the last digit '6', what gives a nice string "01666209170".
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。