CF Round 1060 题解

· · 个人记录

血的教训：不要在xcpc正式赛前一天晚上试图三人vp速通 cf div2

很难认为神·fisher 第二天状态不佳没有带飞全队拿Au和这场的C题无关

不过题还是得补

A

懒得看了

B

显然先做操作Ⅰ，再做操作Ⅱ。

显然操作Ⅰ只会让元素变大，所以仅对偶数的位置使用操作Ⅰ，且操作后偶数位置上的数越大越好。

不难得出操作思路为让偶数位置的数变为前缀最大值，奇数位置上的数不变。

int T,n,a[N];

signed main(){
    read(T);
    while(T--){
        read(n);
        for(int i=1;i<=n;i++)
            read(a[i]);
        int s=a[1];
        for(int i=1;i<=n;i++){
            s=max(s,a[i]);
            if(!(i&1)) a[i]=s;
        }
        ll ans=0;
        a[0]=a[n+1]=1e9+5;
        for(int i=1;i<=n;i++)
            if(i&1) ans+=max(0,a[i]-min(a[i-1],a[i+1])+1);
        printf("%lld\n",ans);
    }
    return 0;
}

C

对 b_i 最小与次小的两个位置的奇偶性简单讨论可知，除 b_i 最小的位置外，其余位置最多被操作一次，否则必定不优。

进一步讨论后可将答案归为以下几类：

1、初始序列中已有两个不互质的数，答案为 0 。

2、选取满足 a_i 为奇数的 b_i 最小值与次小值，制造两个偶数。

3、对 b_i 最小的 a_i 重复操作若干次，使其与另一数不互质。

4、对某 a_i(1 \leq i \leq n) 操作一次，使其与另一数不互质。

具体实现中需要进行质因数分解以达到 O(n\sqrt{n}) 的时间复杂度。

int T,n,a[N],b[N];

int p[N],cnt;
bool vis[N];
void get_prime(){
    vis[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i]){
           p[++cnt]=i;
        }
        for(int j=1;j<=cnt&&p[j]*i<N;j++){
                vis[i*p[j]]=1;
                if(!(i%p[j])) break;
        }
    }
}

int sum[N],tim[N];

signed main(){
    scanf("%d",&T);
    get_prime();
    while(T){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        bool flag=0;
        int mn1=inff,mmn1=inff;
        for(int i=1;i<=n;i++){
                if(a[i]&1){
                    if(b[i]<mn1) mmn1=mn1,mn1=b[i];
                    else mmn1=min(mmn1,b[i]);
                }
                int tmp=a[i];
                for(int j=1;j<=cnt&&p[j]*p[j]<=tmp;j++){
                    if(!(tmp%p[j])){
                        if(tim[p[j]]!=T) tim[p[j]]=T,sum[p[j]]=0;
                        sum[p[j]]++;
                        while(!(tmp%p[j])) tmp/=p[j];
                        if(sum[p[j]]>1) flag=1;
                    }
                }
                if(!vis[tmp]){
                    if(tim[tmp]!=T) tim[tmp]=T,sum[tmp]=0;
                    sum[tmp]++;
                    if(sum[tmp]>1) flag=1;
                }
        }
        if(flag) printf("0\n");
        else{
            ll ans=mn1+mmn1;
            int cur=1;
            for(int i=2;i<=n;i++)
                if(b[i]<b[cur]) cur=i;
            for(int j=1;j<=cnt;j++){
                    if(a[cur]%p[j]&&sum[p[j]]&&tim[p[j]]==T){
                        ans=min(ans,1ll*(p[j]-a[cur]%p[j])*b[cur]);
                    }
            }
            for(int i=1;i<=n;i++){
                int tmp=a[i]+1;
                bool have=0;
                for(int j=1;j<=cnt&&p[j]*p[j]<=tmp;j++){
                    if(!(tmp%p[j])){
                        while(!(tmp%p[j])) tmp/=p[j];
                        if(sum[p[j]]&&tim[p[j]]==T) have=1;
                    }
                }
                if(!vis[tmp]){
                    if(sum[tmp]&&tim[tmp]==T) have=1;
                }
                if(have) ans=min(ans,1ll*b[i]);
            }
            printf("%lld\n",ans);
        }
        T--;
    }

D

把猫“误杀”了的情况有两种：猫在当前节点上、猫在当前节点子树内。

对于第一种情况，易知猫每走一步，所在节点深度的奇偶性改变一次，所以猫不在当前节点上的一个充分条件是猫走过总距离的奇偶性与删除节点深度的奇偶性不同（根节点深度按 0 计算），如果相同让猫多走一步即可。

对于第二种情况，保证每次删除的为叶子节点即可避免。先不断删除叶子节点直至只剩下端点为 1 和 n 的链，再从 1 往下删即可满足要求。

顺便吐槽一句要求输出步数是真的难受

struct edge{
    int next,to;
}e[N<<1];
int head[N],cnt;
void add(int x,int y){
    e[++cnt].next=head[x];
    e[cnt].to=y,head[x]=cnt;
}

int fa[N],inde[N],dep[N];
void prework(int x){
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==fa[x]) continue;
        fa[y]=x,inde[x]++,dep[y]=dep[x]+1;
        prework(y);
    }
}

queue<int>q;
bool era[N];

int num[N<<2],tot;

void endwork(int x,int step){
    if(x==n) return ;
    if((step-dep[x])%2==0)
        num[++tot]=0,step++;
    num[++tot]=x,era[x]=1;
    num[++tot]=0,step++;
    for(int i =head[x];i;i=e[i].next){
        int y=e[i].to;
        if(!era[y]) endwork(y,step);
    }
}

void init(){
    cnt=tot=0;
    for(int i=1;i<=n;i++)
        fa[i]=inde[i]=head[i]=0,era[i]=0;
}

void print(){
    printf("%d\n",tot);
    for(int i=1;i<=tot;i++){
        if(!num[i]) printf("1\n");
        else printf("2 %d\n",num[i]);
    }
    //printf("\n");
}

void work(){
    read(n);
    init();
    for(int i=1;i<n;i++){
        read(x),read(y);
        add(x,y),add(y,x);
    }
    prework(1);
    for(int i=1;i<n;i++){
        if(!inde[i]) q.push(i);
    }
    int step=0;
    while(!q.empty()){
        int x=q.front();
        //if(x==n) printf("???\n");
        q.pop();
        if(x==n) continue;
        if((step-dep[x])%2==0)
            num[++tot]=0,step++;
        num[++tot]=x,era[x]=1;
        inde[fa[x]]--;
        if(!inde[fa[x]]) q.push(fa[x]);
        num[++tot]=0,step++;
    }
    endwork(1,step);
    print();
}

signed main(){
    //freopen("D.in","r",stdin);
    read(T);
    while(T--) work();
    return 0;
}

E

可以发现，若操作序列长度为 x ，记 t=\lfloor \frac{x}{2} \rfloor 。任取某序列操作一次后，假设中位数为 s ，则出现 t+1 个 s ，如果后续要将别的数变为 s ，取已有的 t+1 个 s 操作必定是最优的，因为不会再导致任何元素减小。因此中位数相同的一系列操作可视作对某数 s 操作。即用 t 个数减小为 s 的代价，将至多 k \times t 个数增大为 s 。

对数列从小到大排序，可以发现，若对 a_i 操作，将 a_{i+1} \sim a_{i+t} 减小为 a_i ，将 a_1 \sim a_{i-1} 的一段前缀增大为 a_i 是最优的。

进而可证最优方案中只会对一个 a_i 操作，若操作了多个 a_i ，将所有被变大的数均改为用最大的 a_i 操作是更优的。

因此当 k , x (等价于 t ) 均给定时，若 a_1 \sim a_{t \times x} 均被操作，我们可以 O(1) 计算对某 a_i 操作产生的贡献：

对序列排序并求前缀和 pre 后，贡献为

pre_n+(-pre_{i+t}+pre_i+t \times a_i)+(t \times k \times a_i - pre_{t \times k})

整理得 (pre_n-pre_{i+t}+pre_i- pre_{t \times k})+t \times (k+1) \times a_i

现在我们要把对 t 的枚举优化掉，注意到：

令 f(i,t)=(pre_n-pre_{i+t}+pre_i- pre_{t \times k})+t \times (k+1) \times a_i

则 f(i,t)-f(i,t-1)=(k+1) \times a_i -(a_{i+t}+pre_{t \times k}-pre_{(t-1) \times k})

这个式子中第一项在 i 固定时为常数，第二个括号里的和是递增的，因此式子整体是递减的，可以二分找到最优决策点。

余下一种边角情况：把 a_1 \sim a_{i-1} 都变了还没用满 k 次的情况，特殊处理即可。

注意 t 的最大取值受到右边界影响。

int T,n,k;
ll a[N];

ll sum[N];
ll calc(int i,int x,int k){
    return  sum[i]-sum[i+x]+1ll*(k+1)*x*a[i]-sum[k*x];
}

signed main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&k);
        for(int i=1;i<=n;i++)
           scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++)
            sum[i]=sum[i-1]+a[i];
        ll ans=sum[n];
        for(int i=2;i<n;i++){
            int l=1,r=min(n-i,(i-2)/k);
            if(i+(i-2)/k+1<=n)
                ans=max(ans,sum[n]+sum[i]-sum[i+(i-2)/k+1]+1ll*((i-2)/k+1)*a[i]+1ll*(i-1)*a[i]-sum[i-1]);
           while(l<=r){
                int mid=l+r>>1;
                if(calc(i,mid,k)-calc(i,mid-1,k)>0) l=mid+1;
                else r=mid-1;
           }
           ans=max(ans,sum[n]+calc(i,r,k));
        }
        printf("%lld\n",ans);
    }
    return 0;
}

F1

考虑如何求以 k 作为分界点的符合要求的排列。

将序列看作 1 \sim k 与 k+1 \sim n 两个子序列，则任何一个均需在排列中顺序出现。

可以发现，若序列中某个位置已知，则可确定它所属的序列在它前面的元素个数；且只要确定某序列中所有元素在排列中位置的集合，则每个元素在排列中的位置都能唯一确定。

因此，对于第一个已知元素，若它所在位置为 i ，它所属的序列在它前面有 j 个元素。则它所属的序列在 1 \sim i-1 中需要占有 j 个位置，而另一序列占有 i-1-j 个位置，共有 C(i-1,j) 种位置分配方式。

进而，对于某个已知元素，若它所在位置为 i ，它上一个已知元素所在位置为 las 它所属的序列在它和 las 之间需要填入 j 个元素。则它所属的序列在 las+1 \sim i-1 中需要占有 j 个位置，而另一序列占有 i-1-las-j 个位置，共有 C(i-1-las,j) 种位置分配方式，而 j 可以通过记录每个序列已填入元素个数，再与当前元素比对得到。如此依次对于每两个已知元素间的空位分配位置。

最后一段位置的分配同理。

在这一过程中判断不合法情况也是容易的，包括：

当前序列已填入的上一个数比已知数更大

某段可供已知元素所在序列填入的位置数小于填入的元素个数

最后一段元素个数之和不对（即前面某段填多了或填少了，但由于出错的不是已知元素所在序列，没有被判断）

分别判断即可

那么对于 k 不同的情况，会不会重复计算同一序列呢？有以下结论。

结论：

若 a_i 为顺序排列，则 1,2 \ldots n 均可作为分界点 k ;否则分界点 k 唯一。

证明：

前半句显然。

若 k_1 与 k_2 （ k_1 < k_2 ）均为某一序列的分段点，由 k_1 可知 1 \sim k_1 顺序出现，k_1+1 \sim n 顺序出现，由 k_2 可知，k_1+1 在 k_1 后出现，得到排列为顺序排列，矛盾。

所以只需特判顺序序列的情况即可

int T,n,a[N];

ll frac[N],inv[N],finv[N];
void init(){
    frac[0]=finv[0]=finv[1]=inv[1]=frac[1]=1;
    for(int i=2;i<N;i++){
        frac[i]=frac[i-1]*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}
ll C(int n,int m){
    return frac[n]*finv[n-m]%mod*finv[m]%mod;
}

bool check1(){
    bool res=1;
    for(int i=1;i<=n;i++){
        if(a[i]>0) res&=(a[i]==i);
    }
    return res;
}

int calc(int k){
    int las=0,cur1=0,cur2=k;
    ll res=1;
    for(int i=1;i<=n;i++){
        if(a[i]>0){
            if(a[i]<=k){
                if(cur1>a[i]||i-las-1<a[i]-cur1-1) return 0;
                res=res*C(i-las-1,a[i]-cur1-1)%mod;
                cur2+=(i-las-1-(a[i]-cur1-1));
                cur1=a[i],las=i;
            }
            else{
                if(cur2>a[i]||i-las-1<a[i]-cur2-1) return 0;
                res=res*C(i-las-1,a[i]-cur2-1)%mod;
                cur1+=(i-las-1-(a[i]-cur2-1));
                cur2=a[i],las=i;
            }
            //cout<<cur1<<" "<<cur2<<" "<<k<<endl;
        }
    }
    if(cur1>k||cur2>n) return 0;
    else if((k-cur1)+(n-cur2)!=n-las) return 0;
    else{
        //cout<<"res="<<res<<endl;
        return res*C(n-las,k-cur1)%mod;
    }
}

signed main(){
    scanf("%d",&T);
    init();
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int flag=check1();
        ll ans=0;
        for(int k=1;k<=n;k++)
            ans=(ans+calc(k)-flag)%mod;
        printf("%lld\n",((ans+flag)%mod+mod)%mod);
    }
    return 0;
}