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

    给你一个01串,每一次操作,

    第一步:必须先删掉任意一个位置的字符,

    第二步:删除掉最长相同前缀,也就是必须从字符串头部删除连续个1,或者删除连续个0。

    当字符串被删除为空停止,问最多能有多少次这个操作。

    例如: 有一个字符串 \(S = 111010\),进行一次操作可能的情况为:

    选择位置$1$, $111010 → 11010 → 010$;

    选择位置$2$, $111010 → 11010 → 010$;

    选择位置$3$, $111010 → 11010 → 010$;

    选择位置$4$, $111010 → 11110 → 0$;

    选择位置$5$, $111010 → 11100 → 00$;

    选择位置$6$, $111010 → 11101 → 01$;

    输入格式

    第一行一个$t$,表示样例数$( 1 \leqslant t \leqslant 1000)$

    接下来每组样例包含两行数据

    第一行包含一个整数$n$,表示字符串的长度$(1\leqslant k < n \leqslant 2 \cdot 10^5)$

    第二行包含一个长度为$n$的字符串

    输出格式

    每个样例输出一个数,表示答案

    样例输入

    5
    6
    111010
    1
    0
    1
    1
    2
    11
    6
    101010

    样例输出

    3
    1
    1
    1
    3