luogu P4403 [BJWC2008]秦腾与教学评估

题目

一道神奇的题qwq

首先看题很容易想到把所有的点存下来然后暴力枚举...于是RE 20分

所以要找一种不用开那么大的数组的解法（然而我自己是不可能想出来的qwq

注意一个地方，人数为奇数的位置“最多也仅有一个”，说明奇偶性只根据这一个点改变

……也就是说，用前缀和的方法表示的时候，奇数点之前都是偶数，之后都是奇数

所以正解是二分答案qwq

对于某个点，用一个cal函数判断这一点是否为偶数，如果是说明这个点在后面，否则在前面（或者就是这一点）

——二分的这个地方WA了5次！

这是原来写的

        while(l <= r) {

            mid = (l+r)/;

            if (cal(mid)% == )l = mid+;

            else r = mid-;

        }

        cnt = cal(mid)-cal(mid-);

        printf("%lld %lld\n",mid,cnt);

为什么会WA呢... 举个例子，

当正确答案为3，l = 2, r = 4, mid = 3；

r = mid -1 = 2；l = mid +1 = 3

这时候就把3跳过去了qwq

所以要改成这样↓

        while(l < r) {

            mid = (l+r)/;

            if (cal(mid)% == ) l = mid+;

            else r = mid;

        }

        cnt = cal(l)-cal(l - );

        printf("%lld %lld\n",l,cnt);

就可以啦w（感谢mrclr学长和jlSsy）

哦还有...bin哥说不放心的话可以用一个ans min来每次把它记下来qwq

以下是完整代码

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

long long s[],e[],d[];

long long t,n,l,r,mid,maxe,cnt;

long long cal(long long p) {

    long long sum = ;

    for(long long j = ; j <= n; j++) {

        if(p>=s[j])

            sum += (min(p,e[j])-s[j])/d[j]+;

    }

    return sum;

}

int main() {

    scanf("%lld",&t);

    for(long long i = ; i <= t; i++) {

        maxe = ;

        cnt = ;

        scanf("%lld",&n);

        for(long long j = ; j <= n; j++) {

            scanf("%lld%lld%lld",&s[j],&e[j],&d[j]);

            maxe = max(maxe,e[j]);

        }

        if (cal(maxe)% == ) {

            printf("Poor QIN Teng:(\n");

            continue;

        }

        l = ;

        r = maxe;

        while(l < r) {

            mid = (l+r)/;

            //printf("%lld    %lld    \n",mid,cal(mid));

            if (cal(mid)% == ) l = mid+;

            else r = mid;

        }

        /*for(long long j = 1; j <= n; j++) {

            if(mid>=s[j]&&mid<=e[j]&&((mid-s[j])%d[j]==0))

                cnt++;

        }*/

        cnt = cal(l)-cal(l - );

        printf("%lld %lld\n",l,cnt);

    }

    return ;

}

巴特西

luogu P4403 [BJWC2008]秦腾与教学评估

最新文章

热门文章