前言

传送门 :

这场好难的样子,难指的是(会写,但是写不出来

A. Array Balancing

给定两个数组,完成多次操作操作后使得

$\sum_{i=1}^{n-1}(|a_i-a_{i+1}|+|b_i-b_{i+ 1}|)$ 最小

操作描述 :
- 选择一个下标$i$
- 交换$a_i$ 和 $b_i$

看着像$dp$,对于每个位置有交换和不交换两种选择

其实我们只需要模拟的时候 直接取 $min$即可

$abs(a[i]-b[i-1])+abs(b[i] - a[i-1]))$表示前面的数进行了交换

Mycode

void solve(){
    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    ll sum = 0;
    for(int i=2;i<=n;i++){
        sum += min(abs(a[i] - a[i-1]) + abs(b[i]-b[i-1]),
        abs(a[i]-b[i-1])+abs(b[i] - a[i-1]));
    }

     cout<<sum<<endl;
}

B. Getting Zero

给定一个数$v$,询问最少的操作次数变为$0$
操作描述如下 :
- $v=(v+1)\ mod\ 32768$
- $v=(2*v)\ mod\ 32768$

网上有很多$bfs$和$dfs$大佬在乱飞,所以我们考虑$dp$

状态表示 :

$dp[i]$表示当前这个点到$0$的最小次数

状态转移 :
$dp[j] = min(dp[(j+1)\%N],dp[(j*2)\%N])+1;$

Mycode

void solve(){
    memset(dp,0x3f,sizeof dp);
    dp[0] = 0 ;


    for(int i=N-1; i >  0;  i -- ){
            for(int j = i ;j>0; j --  ){
                dp[j] = min(dp[(j+1)%N],dp[(j*2)%N])+1;
            }
    }

    cin >> n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        cout<<dp[x]<<" ";
    }

}

C. Water the Trees

有$n$棵树,每个数有一个高度$h[i]$,询问最少操作使得所有树的高度相同

操作如下 :
- 如果是奇数天,可以给树浇水使得树$h[i]+1$
- 如果是偶数天,可以给树浇水使得树$h[i]+2$
- 你也可以不浇水
- 一天只能浇一颗

看到这种最小的… 考虑直接 二分天数

首先所有数至少都要加到$maxn$里面

但是加到$maxn$不一定最优,因此我们还需要考虑$maxn+1$,$maxn+2$

我们如何$check$呢 ?

首先 :
能$+2$的次数$mid/2$
能$+1$的次数$mid-mid/2$

然后我们计算每个$h[i]$,需要加多少次$2$
然后再用计算出来的$tt2$，计算出需要$1$的次数,即不足用$1$补
‘
最后判断是否能补上即可

Mycode

const int N = 3e5+10;
ll a[N],n;
ll maxn ;

bool check(ll x,ll h){
    ll t2 =  x/2;
    ll t1 =  x - t2;

    for(ll i = 1;i<=n;i++){
        ll d =  h - a[i];
        ll tt2 = min(d/2,t2);

        d -= tt2*2;
        t2-= tt2;
        t1-=d;
    }
    return t1>=0;
}
void solve(){
    cin>>n;
    maxn = 0 ;

    for(ll i=1;i<=n;i++)cin>>a[i],maxn=max(a[i],maxn);


    ll l = 0 , r = 1e9*maxn;
    ll ans = 0  ;

    while(l <=r ){
        ll mid = (l+r)>>1;
        if(check(mid,maxn)||check(mid,maxn+1)||check(mid,maxn+2)){
            ans = mid;
            r = mid-1;
        }else l = mid+1;
    }
    cout<<ans<<endl;


}

D.Progressions Covering

给定$n$和$k$,以及数组$b[]$

对空数组$a[]$进行最少次操作使得$a[i]>=b[i]$

操作描述如下 :
选择长度为$k$的区间,使得
$a[1]+1,a[2]+2,…,a[k]+k$

我们可以把$a[]=b[]$问题转换为 把$a[]$中长度为$k$ 的序列减去一个$1.2.3..k$的等差序列,询问最少减去多少次使得所有数都$<=0$

对于每次做减去的操作,减去大于$0$的数总是最优的,因此我们可以使用线段树维护一个差分序列即可

吐槽一下这题竟然有1000人过,感觉现在蓝名真的不配了QAQ

code

const int N = 3e5+10 ;
int n,k;

ll b[N];

struct node{
    int l,r;
    ll sum,add;
}tr[N*4];

void pushup(int u){
    tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}
void pushdown(int u){
    auto &root = tr[u];
    auto &left  = tr[u<<1];
    auto &right = tr[u<<1|1];

    if(root.add){
        left.add += root.add;
        left.sum += root.add*(left.r - left.l +1 );
        right.add+=root.add;
        right.sum+=root.add*(right.r - right.l +1);
        root.add = 0;

    }
}

void build(int u,int l,int r){
    if(l == r){
        tr[u] = {l,r,b[r] - b[r-1],0};
        return;
    }

    tr[u] = {l,r};
    int mid =(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify(int u,int l,int r,ll d){
    if(tr[u].l>=l && tr[u].r <= r){
        tr[u].sum += (ll)(tr[u].r - tr[u].l + 1)*d;
        tr[u].add +=d;
    }else{
        pushdown(u);
        int mid = (tr[u].l + tr[u].r)>>1;
        if(l<=mid)modify(u<<1,l,r,d);
        if(r>mid) modify(u<<1|1,l,r,d);
        pushup(u);
    }
}

ll query(int u, int l, int r){
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    ll sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);
    if (r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}

void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>b[i];
    build(1,1,n);
    ll res = 0 ;

    for(int i=n;i;i -- ){
        ll t = query(1,1,i);
        if(t<=0)continue;
        int last = min(k,i);
        ll add = (t+last-1)/last;
        res += add;
        modify(1,i-last+1,i,-add);
    }
    cout<<res<<endl;

}