TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7727
  • 题目
  • P77272020
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    果老师有一个长度为 \(n\) 且只由数字$0, 1, 2$组成的字符串$s_1...s_n$,现在果老师想从字符串中取出尽可能多的不相交子序列,并且所有序列都等于$2020$。

    更形式化的表达,果老师希望能找出 \(k\) 个四元组 $(a_1, b_1, c_1, d_1),...,(a_k,b_k,c_k,d_k)$满足:

    • $1 \leq a_i < b_i < c_i < d_i \leq n$
    • \(s_{a_i}s_{b_i}s_{c_i}s_{d_i} = 2020\)
    • 对于$i \neq j, \{a_i, b_i, c_i, d_i\} \cap \{ a_j, b_j, c_j, d_j \} = \varnothing$

    请你求出最大的 \(k\)

    输入格式

    输入的第一行包括正整数$T$,表示测试用例数

    输入的第一行为一个正整数$n(1 \leq n \leq 10^{5}), \sum n \leq 10^6$

    第二行为字符串$s_1...s_n$

    输出格式

    对于每个字符串输出结果。

    样例输入

    3
    4
    2222
    7
    2101210
    8
    22002200

    样例输出

    0
    1
    2