2024年11月上海月赛丙组题解

· · 个人记录

参赛经历

T1 不难发现在一次操作中我们最多能将 $ x $ 或 $ y $ 的绝对值改变 $ 1 $，于是直接计算起点到终点的 $ x,y $ 绝对值之差，取较大者即可。 T2 直接计算吃了多少包子之后除掉一笼的包子个数即可，结果是向上取整（因为最后一笼可能有剩余）。 T3 记 $ cnt_n $ 代表 $ n $ 在数组中出现的次数，那么对于每次操作我们判断 $ cnt_n $ 的奇偶性就不难判断出这是一个进入操作还是退出操作，然后维护一个当前答案 $ ans $，进入就 $ ans+1 $，反之亦然，然后在计算出的所有 $ ans $ 中取最大值即可。 T4 观察样例，发现最后答案实际上是排序后逆序输出前缀和的结果。 我们不妨考虑最后的操作并倒推，那么我们取出所有前 $ n-m+1 $ 大的值即可。因为最后桶里显然剩下 $ m-1 $ 个元素。 证明：一次放入桶并拿出的操作并不会影响当前桶内的球数量总和。再考虑如何构造出对应的操作，我们每次拿出一个在初始的球里面权值前 $ n-m+1 $ 大的球即可，至于为什么这样的球永远存在，考虑如果桶内没有前 $ n-m+1 $ 大的球，那么桶里至少有 $ m $ 个球，与基本假设矛盾。 于是我们贪心取出前 $ n-m+1 $ 大，然后由于是计算他们的和，先排序之后取前缀和即可。 T5 有时候，手算样例来理解题目甚至发现性质也是很重要的。 我们不难发现把所有数预先对 3 取模之后答案不变，所以以下的讨论中默认数组值域在 $ [0,2] $ 之内。 我们把第二个样例取模之后得到 $ 2,0,1,1,0,1,1,0,1,1 $，根据题目给出的一种示范修改得到 $ 2,0,1,2,0,1,2,0,1,2 $，不难发现最终答案以 $ 3 $ 为循环节。 具体证明，考虑相邻的六个数字 $ a,b,c,d,e,f

在模意义下我们有 a+b+c=b+c+d=0 ，于是有 a=d ，以此类推有 (a,b,c)=(d,e,f) ，得证。

于是我们枚举所有最后答案可能的形态，枚举前两个数字，那么第三个数和之后的序列显然唯一确定。

再考虑如何将初始序列变为目标序列，修改操作对于每个位置是独立的，那么我们每个位置不断加一直到等于目标序列为止。最后在所有答案可能的情况中取最小值。

这样总时间复杂度 \mathcal{O}(27n) ，对于本题来说足以通过。

示例实现：

#include <bits/stdc++.h>
using namespace std;
int f(int l,int r)
{
    if(l<=r)
    return r-l;
    return r+3-l;
}//计算一个位置转移到目标位置的代价
const int maxn=2e6+10;
int a[maxn],a0[maxn],a1[maxn],a012[maxn],a021[maxn],n,a2[maxn];
int comp_012(int del)
{
    int ans=0;
    for(int i=0;i<=n-1;i++)
    ans+=f(a[1+i],a012[1+i+del]);
    return ans;
}//计算总代价
int comp_021(int del)
{
    int ans=0;
    for(int i=0;i<=n-1;i++)
    ans+=f(a[1+i],a021[1+i+del]);
    return ans;
}//同上
int main() 
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i],a[i]%=3;
    int ans=3*n;//答案上界显然是2n
    int minn0=0;
  //为了便于编写，分类讨论简化为000，111，222，012，021五种情况，类似120这些情况用位移的方法消除了，实际上可以枚举前两个数之后统一构造数列
    for(int i=1;i<=n;i++)
    a0[i]=0,minn0+=f(a[i],a0[i]);//处理全0序列
    ans=min(ans,minn0);
    minn0=0;
    for(int i=1;i<=n;i++)
    a1[i]=1,minn0+=f(a[i],a1[i]);//处理全1序列
    ans=min(ans,minn0);
    minn0=0;
    for(int i=1;i<=n;i++)
    a2[i]=2,minn0+=f(a[i],a2[i]);//全2序列
    ans=min(ans,minn0);
    for(int i=1;i<=3*n;i+=3)
    a012[i]=0,a012[i+1]=1,a012[i+2]=2;//形如012的序列
    for(int i=0;i<10;i++)
    ans=min(ans,comp_012(i));//处理循环位移
    for(int i=1;i<=3*n;i+=3)
    a021[i]=0,a021[i+1]=2,a021[i+2]=1;
    for(int i=0;i<10;i++)
    ans=min(ans,comp_021(i));//同上
    cout<<ans<<'\n';
}