P2843 暗杀

    • 50通过
    • 240提交
  • 题目提供者 飞翔
  • 评测方式 云端评测
  • 标签
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    敌方的高级将领都是有很多相同之处的。为了方便找到每名敌将的弱点,我军情报部已经找到了他们的不同点,并将其归纳为K种特性。比如1号特性就代表一个敌将喜欢打人,2号特性就代表一个敌将喜欢吃饭,等等。

    为了方便存储,我军使用特性值来描述一个敌将的特点。特性值是一个位数为K的二进制整数,每一位都可以表示一名敌将的一个特性。1代表具有此特性,0代表没有。

    我军间谍打听到,不久有N个敌方将领会举行一场宴会,而且入场时他们会排成一路纵队入场。如果有连续的M个人的每种特性出现的次数之和是一样的,那么我军间谍就很容易暗杀这M个人。你需要帮助我军算出,间谍最多可以暗杀多少人?

    因为间谍开始攻击后就可能被敌人击毙,所以间谍只能进行一次攻击。

    输入输出格式

    输入格式:

    第一行两个整数N,K

    第二行N个整数,第i个数ai表示第i个敌将的特性值(以十进制的形式输入)

    输出格式:

    最多可以暗杀多少个敌将

    输入输出样例

    输入样例#1: 复制
    7 3
    7 6 7 2 1 4 2
    输出样例#1: 复制
    4

    说明

    样例说明:
    ai         属性           敌将
    7          1 1 1            1
    6          0 1 1            2
    7          1 1 1            3
    2          0 1 0            4
    1          1 0 0            5
    4          0 0 1            6
    2          0 1 0            7
    可以击杀第3人到第6人,共6-3+1=4人

    对于30%的数据,1<=N<=100

    对于50%的数据,1<=N<=1000

    对于100%的数据,1<=N<=100000,1<=K<=30

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