【luoguP3770】[CTSC2017]密钥

这个题之前想了个非常不正确的贪心,然后一看题解就是……woc……
这个题首先显然我们要考虑每次x向前移动后对答案的影响,那么现在这个题就变成了两个操作
1、将序列最前面的一个b放到最后
2、将序列最前面一串a放在最后
那么我们再将a分成两种情况考虑,一种是没动的a,一种是动了的a
然后我做的时候就想到这里,没有头绪
但事实上我们可以转化成前缀和问题
对于所有的a,只有它前缀和大于0,那么它才会作为答案,所以我们要动态维护一个前缀和
对于没有移动的a,进行2操作,假设有x个a被移动了,那么就是令未移动a的前缀和减少x,进行1操作,就是令所有a的前缀和+1
那么这个东西显然可以线段树/树状数组维护,时间复杂度O(nlogn)
显然过不了100%数据对吧,所以我们需要优化
仔细想一下,每次真正需要修改的只有被移动的a,剩下的我们可以统统用一个标记维护啊,每次我们暴力修改被移动的,然后剩下的修改标记就好啊,总复杂度O(n+n)
第三问看起来和前两问差不多,事实上我们可以和第一第二问一起做的,当强a数目为k-s个的时候,这就是第三问答案
证明也很好证明,我们把问题变换下,当强a数目为s的时候,强b的数目就是k-s个(很显然),而第三问就是将ab互换,因此当求第一位的时候,强a数目为k-s的时候,就相当于第一问强b数目为s,那么就相当于第三问强a数目为s
这个题就这么愉快的解决了,注意细节

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio> 
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

int p[20000005], seed, n, k, S;

int getrand() 
{
    seed = ((seed * 12321) ^ 9999) % 32768;
    return seed;
}

const int N = 10000007;

int a, b, c, add, cnt, num;

void generateData() 
{
    scanf( "%d%d%d", &k, &seed, &S );
    int t = 0;
    n = k * 2 + 1;
    memset(p, 0, sizeof(p));
    for( int i = 1; i <= n; ++i ) {
        p[i] = (getrand() / 128) % 2;
        t += p[i];
    }
    int i = 1;
    while( t > k ) {
        while ( p[i] == 0 ) ++i;
        p[i] = 0;
        --t;
    }
    while( t < k ) {
        while( p[i] == 1 ) ++i;
        p[i] = 1;
        ++t;
    }
}

int ci[20000040];

inline void change(int x)
{
    int na = add - (x - 1);
    for(ri i = 1; i <= x; i ++)
        ci[i - add + N] --;
    /**/for(ri i = -add + 1; i <= -na; i ++)//从-add+1一直到-na,因为add是标记,i-add+1 
        num -= ci[i + N];
    for(ri i = -na + 1; i <= -add; i ++)
        num += ci[i + N];
    for(ri i = 1; i <= x; i ++)
        ci[-x + i - na + N] ++;
    num -= x, add = na; /**/
}

inline void ask1()
{
    int s = 0, pos = 0, cnt = 0;
    for(ri i = 1; i <= n; i ++)
    {
        if(p[i] == 0)
        {
            pos = i; break;
        }
    }
    for(ri i = pos + 1; i <= n; i ++)
    {
        s += p[i] ? 1 : -1;
        if(p[i])
            ci[s + N] ++;
    }
    for(ri i = 1; i < pos; i ++)
    {
        s += p[i] ? 1 : -1;
        if(p[i])
            ci[s + N] ++;
    }
    for(ri i = 1 + N; i <= N + k; i ++)
        num += ci[i];
    if(num == 0)
        a = pos;
    if(num == S)
        b = pos;
    for(ri i = pos + 1; i <= n; i ++)
    {
        if(p[i] == 1)
            cnt ++;
        else
        {
            change(cnt), cnt = 0, pos = i;
            if(num == 0)
                a = pos;
            if(num == S)
                b = pos;
            if(num == k - S)//如果num为k-s,那么就对了 
                c = pos;
            if(a > 0 && b > 0 && c > 0)
                return;
        }
    }
}

int main()
{
    generateData(); ask1();
    printf("%d\n%d\n%d\n", a, b, c);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注