POJ 2018 Best Cow Fences （二分答案构造新权值 or 斜率优化）

$ POJ~2018~Best~Cow~ Fences $（二分答案构造新权值）

$ solution: $

题目大意：

给定正整数数列 $ A $ ，求一个平均数最大的长度不小于 $ L $ 的子段

1. 这道题首先我们如果没有长度限制，直接扫一遍数组即可
2. 而有了长度限制之后我们的候选集合发生改变，很容让我们想到DP
3. 事实上这一道题可以DP，用斜率优化复杂度极小，就是有点常数（事实上最优）
4. 但是我们可以参考类似01规划的做法，因为答案具有单调行。
5. 我们让数组中每一个数都减去我们二分答案枚举的值，然后求前缀和，我们只要扫描一遍即可
6. 因为我们们可以从后往前，求出以每一个数为左端点的最大字段和，然后我们只需要知道将后面离它距离大于\(L\)的最大值即可，这个可以边扫描边维护（就是更新最大值）。

$ code: $

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

#define ll long long
#define db double
#define rg register int

using namespace std;

const int mod=9901;

int n,m,ans;

inline int qr(){
    register char ch; register bool sign=0; rg res=0;
    while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
    while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
    if(sign)return -res; else return res;
}

inline int ksm(ll x,int y){
    ll res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod; y>>=1;
    }return res;
}

inline int ask(int x,int y){
    if(y==1)return x;
    if(y&1) return ((ll)ask(x,y>>1)*(ksm(x,y>>1)+1)%mod+ksm(x,y)%mod)%mod;
    else return (ll)ask(x,y>>1)*(ksm(x,y>>1)+1)%mod;
}

int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    while(~scanf("%d%d",&n,&m)){
        if(m==0){puts("1");continue;}
        ans=1;
        for(rg i=2;i*i<=n;++i){
            if(n%i)continue;
            rg x=0; while(!(n%i))++x,n/=i;
            ans=(ll)ans*(ask(i%mod,x*m)+1)%mod;
        }if(n!=1)ans=(ll)ans*(ask(n%mod,m)+1)%mod;
        printf("%d\n",ans);
    }
    return 0;
}

POJ 2018 Best Cow Fences （二分答案构造新权值 or 斜率优化）

原文：https://www.cnblogs.com/812-xiao-wen/p/11248810.html