Educational Codeforces Round 151 (Rated for Div. 2)

A.Forbidden Integer

算法本质

分类讨论

题目大意

给定n k x三个数字，需要你用任意个1~k中除去x的的数相加为n。

输出方案。

思路推演

显然，当x不为1时，直接用n个1即可。

当x为1时，考虑大部分情况，有2、3就可以处理所有n非1的情况。
再考虑只有2的情况。

• x!=1
  可行，全用1

• x==1

  • k==1
    不可行
  • k==2
    若n为偶数可行
  • k>=3
    若n为>1的数可行

B.Come Together

算法本质

思维

题目大意

在方格地图上给定3个点，其中Alice和Bob从点1出发，分别以最短路径走向点2、点3。

输出最大化的重叠路径。

思路推演

显然，这与点的绝对坐标无关，点2、点3减去点1得到相对位置。

方格地图，走只能是水平或者竖直。
若x方向上，点2、点3方向一致，则可以一起走$min(|x2|, |x3|)$，y同理。

C.Strong Password

算法本质

思维

题目大意

是否存在一个长度m由数字组成的密码ans[]，满足下列条件：

• l[i] < ans[i] < r[i]
• ans[]不能是s[]的子序列

思路推演

需要玩家在满足l[] r[]条件的同时，跳出s[]。

对于ans[i]，有r[i]-l[i]+1种字符可能：

• 若s[]对某个字符无法匹配，判断可行
• 若s[]对所有字符匹配，以步步最优解的思想来看，我们应该选择第一次匹配下标靠后的字符

ac核心代码

int f(int pos, char cl, char cr)
{
    set<char> st;
    for (int i=pos; i<s.length(); i++)
    {
        if (s[i]<cl || s[i]>cr)        continue;
        st.insert(s[i]);
        if (st.size()==cr-cl+1)
            return i;
    }
    return -1;
}
inline void solve()
{
    string l, r;
    cin>>s>>n>>l>>r;
    int last=0;
    flag=0;
    for (int i=0; i<n; i++)
    {
        last = f(last, l[i], r[i]);
        if (last==-1)
            flag=1;
        last++;
    }
    cout<<(flag ? "YES" : "NO")<<endl;
    return;
}

D.Rating System

算法本质

思维

题目大意

现在存在n个有序的加分a[]，你需要设定一个k，依次加分满足下列规则：

• 若当前得分>=k，则会永久获得保护机制，每次加分下限得分为k

输出可以最大化最终得分的k值。

思路推演

简单画一个图可以发现，所有的k值都是基于点来设置的——即k可以设定为某个前缀和，并假设前面的加分都不受影响。
反向思考可以发现，加分都是一致的，核心在于如何让k值尽可能地去“捞分”——找到最小字段和。

然后为了保证最小字段的分都可以捞上来，k值设为前缀和即可。

思路推演2

另外一种思考方式，首先仍是可以退出k为某个前缀和。

考虑画图，图像应该类似于：先上升、走平、（上升、有限下降、走平）、上升
先上升这部分可以用前缀和搞定，我们需要找到最后一次走平后的上升值。

这其实就是后缀最大值，遍历前缀和结合后缀最大值即可得到答案。

不过再结合图像观察，其实2个思路是一致的，反过来看就是找最小字段和。

ac核心代码

int a[maxn], dp[maxn];
inline void solve()
{
    cin>>n;
    for (int i=1; i<=n; i++)
        cin>>a[i];
    dp[n+1] = 0;
    for (int i=n; i>=1; i--)
        dp[i] = min(dp[i+1]+a[i], a[i]);
    int p = min_element(dp+1, dp+1+n) - dp;        // 最小子段和的左端点
    int ans = accumulate(a+1, a+p, 0ll);        // 前缀和求值
    cout<<ans<<endl;
    return;
}

E.Boxes and Balls](https://codeforces.com/contest/1841/problem/E)

算法本质

思维

题目大意

在一个[1,n]的一维方格地图中，存在若干空格、石头，分别用01表示。
操控每个石头移动到相邻空格为一次操作。

输出k次操作后的情况数。（mod 1e9+7）

n k <= 1500
保证有方格为空、有方格存在石头、至少2方格

思路推演

容易发现的2个性质：

• 石头的相对顺序固定
  符合dp性质，可以用下标特定指代某个石头
• 可以来回空走石头
  这意味在处理中可以保证不空走石头，最后答案为与k同奇偶性的所有答案之和

这道题的数据范围、性质都说明dp是较好解法，所以先思考dp。

为了方便转移，我们规定

其中当前占位置、石头数、操作次数都是必须的，所以先假设一个：
dp[a][b][c] = num表示前a个方格、存在b个石头、使用了c次操作（无空走）的方案数num。
转移方程如下：

• 当前a方格存在石头
  dp[a][b][c] = dp[a-1][b-1][c-第b个石头到a的代价]
• a方格不存在石头
  dp[a][b][c] = dp[a-1][b][c]

但是显然，这样是O(n^2^k)的复杂度，无法过题。

考虑优化会发现，k的数目限制在1500，但想要能达到任意的情况，其实操作数最多需要n^2^左右。
这时就可以反过来思考，当初始状态前a个方格存在x石头时，我们最终b的探索范围其实局限于$x\pm\sqrt{k}$，并非最初考虑的0~a。

至此，复杂度优化至O(nk^1.5^)。

同时，我们需要针对空间复杂度进行优化，使用滚动数组优化第一维度。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
const int M=40;
int a[maxn], pre[maxn], dp[maxn][maxn];

inline void solve()
{
    cin>>n>>k;
    int num=0;        // 记录石头的个数
    map<int, int> pos;        // 记录每个石头的位置
    for (int i=1; i<=n; i++)
    {
        cin>>a[i];
        pre[i] = pre[i-1] + a[i];        // 前缀和，记录左边有多少个石头，同时可以计算出右边的石头数目
        if (a[i]==1)
            pos[++num] = i;        // 每个石头的位置
    }

    dp[0][0] = 1;        // dp[a][b][c]被滚动数组压缩为dp[b]][c]：前a个方格有b个石头、用了c次操作的情况数
    for (int i=1; i<=n; i++)    // i表示前i个方格的情况
    {
        int l = max(1ll, pre[i]-M);        // k次操作最多可以从这个区间撤走M个石头，计算最少的数目可能
        int r = min(num, pre[i]+M);        // 可以给这个区间带来至多M个石头，计算最多数目可能
        for (int j=r; j>=l; j--)        // 滚动数组优化，需要从右往左
        {
            int cost = abs(pos[j]-i);        // 第j个石头移动到位置i需要的操作数
            for (int t=cost; t<=k; t++)
                dp[j][t] += dp[j-1][t-cost], dp[j][t]%=mod;        // 方程转移（2个转移方程，但是因为使用滚动数组优化后，刚好可以省略1个）
        }
    }
    
    int ans=0;
    for (int i=k; i>=0; i-=2)
        ans += dp[num][i], ans%=mod;
    cout<<ans<<endl;
    
    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。