NFLSPC #1 C题 Balance 题解

2018-12-02 11:33:39 By skyline

首先我们考虑2种特殊情况

第一种特殊情况 什么时候输出yjztxdy (杨骏昭天下第一)呢?

如果所有蒟蒻崇拜同一个神犇 显然应该输出yjztxdy

如果不是所有蒟蒻崇拜同一个神犇 一定有相邻2个蒟蒻不崇拜同一个神犇 这2个蒟蒻构成平衡区间

第二种特殊情况 如果整个长度为n的区间是平衡区间 显然它是唯一最长的

我们考虑一般情况

考虑任一个最长平衡区间 它可以由整个长度为n的区间每次去掉一个数得到

由于它是最长平衡区间 所以这个过程中的所有区间都是不平衡的

设整个长度为n的区间中最多的数为x x的出现次数超过一半

每次去掉一个数的过程中 如果x的出现次数变为不超过一半 那它的出现次数一定恰好为一半

如果某一个数在一个平衡区间内出现恰好一半次 显然这是平衡区间

于是我们得到:过程中的区间x的出现都超过一半 最长的那个区间中x出现恰好一半

故x出现一半为区间为最长平衡区间的必要条件 而x出现一半为区间为平衡区间的充分条件

我们把所有x变为1 所以其它数变为-1 找最长的和为0的区间的长度和个数即可

我们可以用前缀和来实现这一想法

std https://acm.nflsoj.com/submission/9697

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。