Educational Codeforces Round 151 (Rated for Div. 2)

D. Rating System

题意

给出一个得分序列。可以设定一个 $k$，使得分数到达 $k$ 后不会再低于 $k$。求一个 $k$ 使得最终得分最大。

题解

显然 $k$ 应该为得分序列前缀和中的一个。对于给定的 $k=sum_i$，必然存在一个位置 $j\in[i,n]$，使得从该位置往后得分不再小于 $k$。所以我们直接维护后缀最大值即可（即假定从每个位置开始，得分不再小于 $k$ ，如果真实情况会出现小于 $k$ ，答案只会更差）。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
int a[maxn];
ll pre[maxn],suf[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],pre[i]=pre[i-1]+a[i];
        suf[n+1]=0;
        for(int i=n;i;i--) suf[i]=suf[i+1]+a[i];
        for(int i=n;i;i--) suf[i]=max(suf[i],suf[i+1]);
        ll idx=-0x3f3f3f3f3f3f3f3f,mx=-0x3f3f3f3f3f3f3f3f;
        for(int i=0;i<=n;i++)
        {
            ll ans=pre[i]+suf[i+1];
            if(ans>mx) idx=pre[i],mx=ans;
        }
        cout<<idx<<'\n';
    }
    return 0;
}

E. Boxes and Balls

题意

给出 $n$ 个盒子，有些装有一个球，有些没有装球。每次操作可以选择相邻的两个盒子且一个为空，一个不为空，将球从不为空的盒子移动到为空的盒子。求 $k$ 次操作后有多少种可能的情况。

题解

先考虑一个子问题，对于两种情况如何用最少的操作次数从一种变成另一种，答案很显然，每个球对应地移动。即第一个球对应移动到第一个球的位置，以此类推。

这类计数问题自然想到dp。令 $f_{i,j,k}$ 表示前 $i$ 个位置有 $j$ 个 $1$ 用了 $k$ 次操作的方案数。那么有转移 $f_{i,j,k}=f_{i-1,j-1,k-cost}$，其中 $cost$ 为将第 $j$ 个 $1$ 移动到 $i$ 的代价。但复杂度为 $O(n^2k)$，还需要优化。

将 $k$ 个 $1$ 移出某个区间或移入的代价是 $O(k^2)$ 的，所以当前位置前缀和的变化不会超过 $\sqrt{k}$。这样时间复杂度就降到 $O(nk\sqrt{k})$ 了。

注意，统计答案的时候需要统计与 $k$ 奇偶性相同的所有操作次数。因为可以通过两次连续的交换令 $k$ 减少 $2$ 而不产生影响。

代码

#include <bits/stdc++.h>
using namespace std;
const int p=1e9+7;
const int B=40;
int a[1505],s[1505],f[1505][1505];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    vector<int> pos;
    for(int i=1;i<=n;i++)
        if(a[i]) pos.push_back(i);
    int S=(int)pos.size();
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        int r=min(min(i,S),s[i]+B);
        int l=max(1,s[i]-B);
        for(int j=r;j>=l;j--)
        {
            int cost=abs(pos[j-1]-i);
            for(int t=k;t>=cost;t--)
                f[j][t]=(f[j][t]+f[j-1][t-cost])%p;
        }
    }
    int ans=0;
    for(int i=k;i>=0;i-=2) ans=(ans+f[S][i])%p;
    cout<<ans<<'\n';
    return 0;
}