牛客练习赛109 B D

﹏ヽ暗。殇╰゛Y 2024-03-26 17:19 79阅读 0赞

浅浅vp了一下

[牛客练习赛109\_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛\_牛客竞赛OJ (nowcoder.com)][109_ACM_NOI_CSP_CCPC_ICPC_OJ _nowcoder.com]

题意：

![d45dbf1104e24b6aa2a11d62c2ca1b3a.png][]

思路：

考虑尺取法找出最长的超现实子串

当右边一直满足条件的时候就r++，然后条件用k维护就行，统计最大值

Code：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    #include <map>
    #define int long long
    using namespace std;
    using i64 = long long;
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    
    int n;
    int a[mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        int r=1,ans=0;
        for(int l=1;l<=n;l++){
            int k=1;
            r=l+1;
            while(r<=n&&a[r]==a[l]+k){
                r++;
                if(k>0) k=-k;
                else k--,k=-k;
            }
            r--;
            ans=max(ans,r-l+1);
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

题意：

![ff55426f4d038edd4665f7c902aeadeb.png][]

思路：

贪心，直接从贡献入手，去计算贡献

设未知数 x,y

不妨设x<y，此时贡献为x\*y

然后x+m，y-m，此时贡献为 xy+(y-x)\*m-m\*m

那么去考虑 (y-x)\*m-m\*m和0比较

y>x+m时贡献为正，否则就是负

因此策略就是每次拿出最大值和最小值操作，操作k次

我赛时思考止步于次，想用优先队列维护但是失败了

线段树维护很妙啊

这道题里我们需要维护区间最小/大值下标和**整个区间**的积

因为是整个区间，因此直接修改a数组里面的值就行了

那只需要写区间最值下标就行

当我们在确定我们需要什么数据结构时，先去确定我们需要维护的是哪些量

Code：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    #include <map>
    #include <queue>
    #define int long long
    using namespace std;
    using i64 = long long;
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    struct ty{
        int mx,mi;
    }tree[mxe<<2];
    
    int n,m,k;
    int a[mxn];
    void pushup(int rt){
        tree[rt].mi=(a[tree[rt<<1].mi]<a[tree[rt<<1|1].mi])?tree[rt<<1].mi:tree[rt<<1|1].mi;
        tree[rt].mx=(a[tree[rt<<1].mx]>a[tree[rt<<1|1].mx])?tree[rt<<1].mx:tree[rt<<1|1].mx;
    }
    void modify(int rt,int l,int r,int x,int cmd){
        if(l==r) return;
        int mid=l+r>>1;
        if(x<=mid) modify(rt<<1,l,mid,x,cmd);
        else modify(rt<<1|1,mid+1,r,x,cmd);
        pushup(rt);
    }
    void build(int rt,int l,int r){
        if(l==r){
            tree[rt].mi=tree[rt].mx=l;
            return;
        }
        int mid=l+r>>1;
        build(rt<<1,l,mid);
        build(rt<<1|1,mid+1,r);
        pushup(rt);
    }
    void solve(){
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        build(1,1,n);
        while(k--){
            if(a[tree[1].mx]-a[tree[1].mi]<=m) break;
            a[tree[1].mx]-=m,modify(1,1,n,tree[1].mx,1);
            a[tree[1].mi]+=m,modify(1,1,n,tree[1].mi,-1);
        }
        int ans=1;
        for(int i=1;i<=n;i++) ans=(ans*a[i])%mod;
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[109_ACM_NOI_CSP_CCPC_ICPC_OJ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/51721#question
[d45dbf1104e24b6aa2a11d62c2ca1b3a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d0514d8afe6a43ee80ab05ff6c0e2b15.png
[ff55426f4d038edd4665f7c902aeadeb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4857cc141de74860a91765265cbcd7e9.png