P3510 [POI2010]JED-Ones

    • 0通过
    • 2提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 单调队列 哈希,HASH 级数 POI 2010 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    本题征求翻译。如果你能提供翻译或者题意简述,请 提交翻译 ,感谢你的贡献。

    题目描述

    Let $x$ be a sequence of zeros and ones.

    An utterly forlorn one (UFO) in $x$ is the extreme (either first or last) one that additionally does not neighbour with any other one.

    For instance, the sequence 10001010 has two UFOs, while the sequence 1101011000 has no UFO, and the sequence 1000 has only one UFO.

    Let us denote the total number of UFOs in the binary representations of the numbers from 1 to $n$ with $sks(n)$.

    For example, $sks(5)=5$, $sks(64)=59$, $sks(128)=122$, $sks(256)=249$.

    We will be working with very large numbers.

    Therefore, we shall represent them in a succinct way.

    Suppose $x$ is a positive integer and $x_2$ is its binary representation (starting with 1). Then the succinct representation of $x$ is the sequence $REP(x)$ consisting of positive integers denoting the lengths of successive blocks of the same digits.

    For example:

    $REP(460\ 288)=REP(1110000011000000000_2)=(3,5,2,9)$ $REP(408)=REP(110011000_2)=(2,2,2,3)$

    Your task is to write a program that finds the sequence $REP(sks(n))$ given $REP(n)$.

    输入输出格式

    输入格式:

    The first line of the standard input holds one integer $k$ ($1\le k\le 1\ 000\ 000$) denoting the length of the succinct representation of a positive integer $n$.

    The second line of the standard input holds $k$ integers $x_1,x_2,\cdots,x_k$ ($0<x_i\le 1\ 000\ 000\ 000$), separated by single spaces.

    The sequence $x_1,x_2,\cdots,x_k$ forms the succinct representation of the number $n$.

    You may assume that $x_1+x_2+\cdots+x_k\le 1\ 000\ 000\ 000$, i.e., $0<n<2^{1\ 000\ 000\ 000}$.

    输出格式:

    Your program is to print out two lines to the standard output.

    The first one should contain a single positive integer $l$.

    The second line should hold $l$ positive integers $y_1,y_2,\cdots,y_l$, separated by single spaces.

    The sequence $y_1,y_2,\cdots,y_l$ is to form the succinct representation of $sks(n)$.

    输入输出样例

    输入样例#1: 复制
    6
    1 1 1 1 1 1
    输出样例#1: 复制
    5
    1 1 2 1 1
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。