牛客周赛 Round 122

A ICPC Problems

略

B Chess

很像周赛120的马，不过这个题是象，但是思路也差不太多

首先 $min(n,m)<3$ 的时候，只能在初始位置，所以只有一个位置

然后考虑 $min(n,m)\geq3$ 的情况，注意到象和马很大一个区别是马由于每次跳 $1*2$ ，棋盘够大时可以跳到任意位置，但象由于每次跳的是 $2*2$ ，所以每次跳动横纵坐标的奇偶性都无法改变，所以我们统计所有横纵坐标都为奇数的位置（数量记为 $num$ ）（因为从 $1$ 开始的奇数的数量一定大于等于偶数）, $num=\lfloor\frac{l}{2}\rfloor * \lfloor\frac{r}{2}\rfloor$

又因为每次跳 $2*2$ 决定了象不能去到距离为 $2$ 的点位，也就是说这 $num$ 个位置中只有一半能取到，因此答案就是 $\lfloor\frac{num}{2}\rfloor$

C Sequence Cost

很典的贪心，主要证明最优策略比较麻烦，但猜个结论还是挺容易猜到的

我们不妨先研究要进行至少一次操作的情况下怎么做最优，这样再跟一次操作都不做（很容易统计答案）比较取最小即可

很容易能想到既然要做操作的话，那么如果能一次性把整个序列全部变为最小值的话，第二步拿走整个序列的时候花费肯定最小，不过这时这一次操作的花费就是整个序列的最大值，这样是不是最优呢？

也就是我们猜测：**只做一次操作：选择区间 $[1,n]$ ，花费最大值（记为 $Max$ ）的代价，将序列中所有数变为最小值（记为 $Min$ ），然后再拿走这个序列，总花费 $Max+n*Min$ **是最优策略，下面来证明这个结论（事实上贪心很多题都是先猜再证的）（下文把此结论简称为结论）

比较同样只做一次操作的情况：

如果选择区间包括 $Max$ 并且不为 $[1,n]$ ，那么第一步操作花费相同，但至少一个数没有被包含在区间里，其中可能存在大于 $Min$ 的数，拿走序列时花费可能更大，所以此方案比结论一定不更优
如果不包括 $Max$ ，我们假设第一步花费为 $x$ ，那么此时总花费至少为 $x+(n-1)*Min+Max$ （最好情况下最大值在边上，这个区间可以最大化，操作后序列为 $n-1$ 个 $Min$ 和 $1$ 个 $Max$ ），而 $x\geq Min$ ，因此此方案依然不比结论优

再考虑做多于一次操作的情况：

如果有至少一次操作选择区间 $[1,n]$ ，显然不如结论
如果没有一次操作选择区间 $[1,n]$ ，那么每一次选择同样有两种可能：包含 $Max$ 和不包含 $Max$ ，而只要包含 $Max$ ，那一定不如把区间扩张到 $[1,n]$ （因为相同的花费能将更多的数变小）
如果没有一次操作包含 $Max$ ，最后拿走序列时的花费一定大于等于 $(n-1)*Min+Max$ ，而操作的花费一定大于等于 $2Min$ （至少两次操作），总花费大于等于 $(n+1)*Min+Max$ ，依然不比结论优

所以我们就证明了如果要操作，结论一定是最优的，因此对每次询问的数列统计一次不操作的结果（ $\sum _{1}^{n}a_i$ ）和按照结论操作的结果（ $n*Min+Max$ ），输出较小即可

D Digital Deletion

算个数学题？不过更像模拟一点

首先搞清楚 $Mex$ 这个东西的定义：集合中没出现过的最小正整数

我们先思考如果我们明确一个集合的所有元素要怎么求这个集合的 $Mex$ ：显然先排序，再用一个指针指向当前没出现过的最小正整数（从 $1$ 开始），接着扫描数列直到出现空缺为止（如指针指向 $3$ 但数列中 $2$ 过了就是 $4$ ）

再来看这个题。本题中集合中元素是由数列的所有子序列的和构成的，显然这个集合元素可能非常多，我们难以直接求这个集合的所有元素，不能用常规方法找 $Mex$

可以明确的是如果一个数 $x$ 已经比 $Mex$ 大，那么比 $x$ 更大的数显然也能被删掉而不受影响。因此我们先把序列从小到大排序，找到能被删掉的边界，后面的就都能被删掉了。而找边界就是在找第一个对 $Mex$ 无贡献的数，所以我们可以先找序列的 $Mex$

怎么求 $Mex$ 呢？我们假设已经求出前 $i-1$ 个数的 $Mex$ ，思考 $a_i$ 对 $Mex$ 的贡献。烧烤一下发现，对于前 $i$ 个数， $[1,Mex-1]$ 一定有至少一种拼凑的方法。所以加上 $a_i$ 后新增的区间就是 $[a_i,a_i+Mex-1]$ ，只要这个区间中出现 $Mex$ ，此时本来没出现过的 $Mex$ 就出现在了集合中，** $a_i$ 成功将 $Mex$ 更新为了 $a_i+Mex$ **（由于 $Mex$ 此前没出现过，而前 $i-1$ 个数也没有比 $a_i$ 更大的，因此 $a_i+Mex$ 必然没出现过）

答案显而易见了，对每一个 $a_i$ ，判断一下前 $i-1$ 个数的 $Mex$ 是否包含在区间 $[a_i,a_i+Mex-1]$ 中，等效于判断 $a_i$ 是否等于 $0$ 或者是否大于 $Mex$ ，如果是的话答案加一，如果不是更新 $Mex$

稍加优化，碰到 $0$ 就统计进答案，之后非 $0$ 的部分一直更新 $Mex$ 直到遇到 $a_i>Mex$ ，那么后面的 $n-i+1$ 个数都能删掉。由于 $0 \leq a_i \leq 10^9$ ，当 $Mex>10^9$ 之后也可以直接停止，因为后面的肯定都比 $Mex$ 小

附个🐎

typedef long long lld;
const int maxn=2e5+5;
int a[maxn];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,ans=0;
        lld now=1;//存储当前Mex的值
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++){
            if(a[i]==0){//0直接累计进答案
                ans++;
                continue;
            }
            if(now>1e9) break;
            else if(a[i]>now){
                ans+=n-i+1;
                break;
            }
            now+=a[i];//更新Mex
        }
        printf("%d\n",ans);
    }
    return 0;
}

E Block Array

算个冻柜吧应该

噼里啪啦写一堆发现样例都过不了，原来连续出现次数可以比元素更大。。。

好数组的基础是块。判断一坨是不是块，直接用一个变量 $len$ 记录当前以 $a_i$ 为止连续出现的相等元素的数目，显然当 $a_i \leq len$ 的时候， $a_i$ 可以作为一个块的终点。

再考虑找到块之后怎么找好数组数量。这里直接用动态规划的思想递推。定义一个数组 $k$ ， $k_i$ 表示以 $a_i$ 结尾的块作为最后一块时有几个好数组。显然结尾块前面有 $n$ 个连续的块时，就有 $n+1$ 个好数组。递推公式 $k_i=k_{i-a_i}+1$ ， $\sum_1^n k_i$ 就是最后的答案。

说实话感觉比D题简单？！！

注意初始化！！！

typedef long long lld;
const int maxn=5e5+5;
int a[maxn],k[maxn];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int now=1,len=1;
        lld ans=0;
        while(now<=n){
            k[now]=0;//初始化
            if(a[now]<=len) k[now]=k[now-a[now]]+1;
            if(a[now]==a[now+1]) len++;
            else len=1;
            now++;
        }
        for(int i=1;i<=n;i++) ans=ans+k[i];
        printf("%lld\n",ans);
    }
    return 0;
}

F Sequence Covering

又是给一个数列，又是一道贪心

首先明确字典序：从前往后依次比较元素，只要一处比出大小关系就停止

显然前面的元素越大越好

我们假设前 $now-1$ 个元素已经搞到最大，现在还剩余 $k$ 的成本。由于前面的越大越好，我们显然就会去找 $[now,now+k]$ 这个区间里的最大值。由于操作区间 $[l,r]$ 花费为 $r-l$ 的神奇特性，如果有多个最大值时分成几段操作能节省成本（比如直接操作 $[1,4]$ 这个区间花费 $3$ ，但是操作 $[1,2]$ 和 $[3,4]$ 两个区间只花费 $2$ ，如果 $a_2$ 和 $a_4$ 都是最大值采取第二种方法更新更优），因此我们定义 $x$ 为区间中第一个最大值。考虑以下情况：

如果 $a_x >a_{now-1}$ ，则 $[now,x]$ 这个区间就都更新为 $a_x$ ，至于 $a_x$ 后面的，由于查找最大值区间变为了 $[x+1,now+k+1]$ ，最大值有可能因此变大，所以我们将 $now$ 更新为 $x+1$ ， $k$ 更新为 $k-(x-now)$
如果 $a_x=a_{now-1}$ ， $[now,x]$ 用 $a_x$ 更新花费 $x-now$ ，用 $a_{now-1}$ 更新花费 $x-1-(now-1)=x-now$ （只需更新到 $a_{x-1}$ ），没区别，因此归入上一种情况
如果 $a_x<a_{now-1}$ ，直接将 $[now-1,now-1+k]$ 这个区间覆盖为 $a_{now-1}$ （因为摸不到后面的更大的数了）， $k$ 直接更新为 $0$ 结束循环

这样基本的思路就确定了，但如果每次通过遍历的方式查找区间最大值，时间效率为 $o(nk)$ ，会超市，因此我们需要优化一下查询区间最大值的方法。当然方法很多，我这里使用了线段树优化。

思路整体比较简单，但前面的题如果没想明白容易时间不够，导致几种情况没想清楚。

代码如下：

const int maxn=2e5+5;
int a[maxn];
int t[maxn<<4],ls[maxn<<4],rs[maxn<<4],cnt,root;//注意线段树空间开销
//t[i]表示编号为i的区间的第一个最大值的下标，ls[i],rs[i]分别表示编号为i的区间的左儿子,右儿子
//cnt用于分配编号，root存根节点（事实上就是1）
void build(int &x,int l,int r){//建树
    x=++cnt;
    if(l==r){
        t[x]=l;
        return ;
    }
    int mid=(l+r)>>1;
    build(ls[x],l,mid);
    build(rs[x],mid+1,r);
    if(a[t[ls[x]]]>=a[t[rs[x]]]) t[x]=t[ls[x]];//左儿子最大值等于右儿子时优先使用左儿子确保t[x]存储第一个最大值
    else t[x]=t[rs[x]];
}
int Query(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R) return t[x];
    int mid=(l+r)>>1,ll=0,rr=0;
    if(L<=mid) ll=Query(ls[x],l,mid,L,R);
    if(R>mid) rr=Query(rs[x],mid+1,r,L,R);
    if(a[ll]>=a[rr]) return ll;
    return rr;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        a[0]=-1e9-5;//注意初始化
        cnt=0;//同上
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        build(root,1,n);
        int now=1;
        while(k&&now<=n){
            int x=Query(1,1,n,now,min(now+k,n));
            if(a[x]<a[now-1]){
                for(int i=now;i<=now+k-1;i++) a[i]=a[now-1];
                k=0;
            }else{
                for(int i=now;i<=x;i++) a[i]=a[x];
                k-=x-now;
                now=x+1;
            }
        }
        for(int i=1;i<=n;i++) printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}