CF#1044（Div.2）全解

· · 个人记录

CodeForces Round 1044(Div.2)

完成度：完结。

个人感觉：

A

自评：橙。

出题人试图伪装了，但还是很明显。结论是相同齿数的转速一定相同，然后开个桶或者排序扫一遍看看有没有相同的就行了。

sort(a,a+n);
bool flg=0;
for(int i=1;i<n;i++){
    if(a[i]==a[i-1]){
        flg=1;
        break;
    }
}
if(flg)cout<<"YES";
else cout<<"NO";
cout<<endl;

B

自评：黄。

这个比较降智，我是花了些时间想的。

即使瞪不出来，手玩样例也可以发现，连一条边，边的至少一端会变成 0。

所以直接排个序从大到小每两个一连边就出现了一堆含 0 的连通块，在这些连通块间建边代价显然可以是 0，然后就做完了。

sort(a,a+n);
ll ans=0;
for(int i=n-1;i>=0;i-=2){
    ans+=a[i];
}
cout<<ans<<endl;

C

自评：绿。

首先排着问一遍直接得到起点，此时一共问了 n 次。

然后显然的假设长度为 k，则第二个点的询问结果应该是 k-1，且一条路径不可能经过两个询问结果相同的点（因为否则我可以从其中一个走到另一个使其询问结果变成另一个的询问结果 +1）。

于是把所有询问结果是 k-1 的点全删掉，每次只留一个，如果询问路径上前一个点的结果还是 k 就说明这个点是可以选择的，这样以此类推，一共需要问 n-1 次，我们就只用了 2n-1 次解决了这个问题。

实现时拿 vector 按第一次的询问结果将点分类即可，单组复杂度 O(n^2)。

cin>>n;
ll mx=0;
ans.clear();
for(int i=1;i<=n;i++)a[i].clear();
for(int i=1;i<=n;i++){
    cout<<"? "<<i<<' '<<n;
    for(int i=1;i<=n;i++)cout<<' '<<i;
    cout<<endl;
    ll tmp;
    cin>>tmp;
    a[tmp].push_back(i);
    mx=max(mx,tmp);
}
ans.push_back(a[mx--][0]);
while(mx>0){
    for(int i=0;i<a[mx].size();i++){
        cout<<"? "<<ans[ans.size()-1]<<' '<<n-a[mx].size()+1;
        for(int j=1;j<=n;j++){
            if(j!=mx){
                for(int k=0;k<a[j].size();k++)cout<<' '<<a[j][k];
            }
            else cout<<' '<<a[j][i];
        }
        cout<<endl;
        ll tmp;
        cin>>tmp;
        if(tmp==mx+1){
            ans.push_back(a[mx][i]);
            break;
        }
    }
    mx--;
}
cout<<"! "<<ans.size();
for(int i=0;i<ans.size();i++){
    cout<<' '<<ans[i];
}
cout<<endl;

:::info[额外的挑战（1）] 在不超过 \frac{5}{3}n 次询问内解决本题。 :::success[做法] 做法来自出题人。

我们注意到在找路径的过程中，有一些东西是冗余的。对于每一层，我们可以二分点的集合，每次加入该层二分范围内一半的点，而不是逐个查找，则最坏的情况下该层有 3 个点，我们需要询问至多 2 次，最终只需要 \frac{2}{3}n 次询问找到路径。 :::

:::info[额外的挑战（2）] 在期望 \frac{14}{9}n 次询问内解决本题。 :::success[做法] 做法来自@Maxi135798642，证明是我自己证的，如有问题还请提出。

随机化即可。我们打乱层内所有点，并取前较小的一半进行询问。这样：

D

自评：下位蓝~中位蓝。

没经历过真的体会不到把 Hint 部分的结论光速全观察出来了结果刚了 1h 不会的绝望……

不难注意到每个怪只会受到一次摔伤，且摔伤分为 1 点和大于 1 点，对于后者，显然摔的位置是越高越好的，所以这种情况应该直接在原怪物堆里把它下面那个怪给打死。

于是我们对于第 i(i>1) 个怪有三种选择：

直接对着这个 DP 即可。第二种情况完全包含了第一种，所以可以直接无视第一种。

dp[0]=0;
dp[1]=a[1];
for(int i=2;i<=n;i++){
    dp[i]=min(dp[i-1]+a[i]-1,dp[i-2]+a[i-1]+max(a[i]-i+1,0ll));
}
cout<<dp[n]<<endl;

E

自评：中位蓝~上位蓝。

很显然的，我们需要通过不超过 \left\lfloor\dfrac{n}{4}\right\rfloor 次二操作把树拆成若干条链。首先这个东西的正确性是有的：从树上拆出的三个点的连通块一定是链，所以每四个点只需要一次二操作。接下来考虑怎么操作。

既然我们拆成若干条链，那得知道链是长什么样子的。

随便构造了若干棵树，我们发现如果假定了一个根，则执行完二操作后剩下的链可能是下面两种情况：

而第二种（上图右侧）又是由两个第一种（上图左侧）连到同一个父亲拼出来的。于是断点的策略就十分显然了：

其中有两个儿子的情况注意判断父亲是否已经被其他点断过了，没判会导致 WA on #2 case 652。

然后对于每个链找它的一端把这个链扫一遍就可以了。复杂度线性。

:::info[相似题目推荐]

P11017 Hide And Seek，也有我的题解。赶紧去点赞！

:::

ll T,n,u,v;
bool vis[200010],vis2[200010];
vector<ll> a[200010],ans1,ans2;
void dfs1(ll now,ll lst){
    ll cnt=0;
    for(int i=0;i<a[now].size();i++){
        if(a[now][i]!=lst){
            dfs1(a[now][i],now);
        }
    }
    if(vis[now])return ;
    for(int i=0;i<a[now].size();i++){
        if(a[now][i]!=lst&&!vis[a[now][i]]){
            cnt++;
        }
    }
    if(cnt>2){
        vis[now]=1;
        ans2.push_back(now);
    }
    else if(cnt==2&&now!=lst){
        if(!vis[lst])ans2.push_back(lst);
        vis[lst]=1;
    }
}
void dfs2(ll now,ll lst){
    ans1.push_back(now);
    vis2[now]=1;
    for(int i=0;i<a[now].size();i++){
        if(a[now][i]!=lst&&!vis[a[now][i]]){
            dfs2(a[now][i],now);
        }
    }
}
int main(){
    cin>>T;
    while(T--){
        ans1.clear();
        ans2.clear();
        cin>>n;
        for(int i=1;i<=n;i++){
            a[i].clear();
            vis[i]=0;
            vis2[i]=0;
        }
        for(int i=1;i<n;i++){
            cin>>u>>v;
            a[u].push_back(v);
            a[v].push_back(u);
        }
        dfs1(1,1);
        for(int i=1;i<=n;i++){
            //找链的端点
            if(vis2[i])continue;
            if(vis[i]){
                ans1.push_back(i);
            }
            else{
                ll cnt=0; 
                for(int j=0;j<a[i].size();j++){
                    if(!vis[a[i][j]]){
                        cnt++;
                    }
                }
                if(cnt<=1){
                    dfs2(i,i);//扫链
                }
            }
        }
        cout<<ans1.size()+ans2.size()<<endl;
        for(int i=0;i<ans2.size();i++){
            cout<<"2 "<<ans2[i]<<endl;
        }
        for(int i=0;i<ans1.size();i++){
            cout<<"1 "<<ans1[i]<<endl;
        }
    }
    return 0;
}

F

自评：下位紫~中位紫。

显然，对于两个苦力怕，如果它们的爆炸区间都包含另一个的爆炸点，不能都炸掉（因为无论按什么顺序其中一个都会把另一个的爆炸点给炸死）。

于是有暴力 DP：设 dp_i 表示引爆第 i 个苦力怕且杀死该苦力怕爆炸范围右端点前所有苦力怕的最小操作次数，则对于 j<i，有两种转移到 dp_i 的方式：

于是暴力枚举 j<i 就有了一个 O(n^2) 的暴力 DP。考虑优化。

我们发现转移的过程是个区间最小值，所以我们可以考虑将目前炸死前 i 个苦力怕的最小操作次数挂到线段树上维护，修改就是将爆炸范围的右端点的原有值和当前点的 dp 值取 \min，查询的时候就分别对于两种转移进行查询再取 \min：

然后就可以实现快速的转移了。输出答案的部分就是个普通的 DP 记录路径，维护个前驱数组，转移的同时也把右端点是哪个苦力怕炸的挂到线段树上一起维护，最后按 e_i 升序排序就好了。复杂度单组 O(n\log n)。

虽然只有不到 3KB，但细节真的很多。。。一共用了一下午加一晚上才处理完的。。。

struct node{
    ll ls,rs,mn,lst;
};
struct node2{
    ll mn,lst;
};
bool operator <(node2 x,node2 y){
    return x.mn<y.mn;
}
node t[2000010];//这边稍微开大一点，下标从 0 开始方便处理 
ll T,n,a[500010],dp[500010],lst[500010],rt,p=1;
vector<ll> res[500010],ans;//记录每个位置计算完后要更新的位置 
bool cmp(ll x,ll y){
    return a[x]<a[y];
} 
void build(ll now,ll l,ll r){
    if(l==r){
        if(l==0)t[now].mn=0;
        else t[now].mn=1000000000000000000ll;
        t[now].lst=0;
        return ;
    }
    ll mid=(l+r>>1);
    t[now].ls=p++;
    build(t[now].ls,l,mid);
    t[now].rs=p++;
    build(t[now].rs,mid+1,r);
    t[now].mn=min(t[t[now].ls].mn,t[t[now].rs].mn);
}
void upd(ll now,ll l,ll r,ll pos,ll x,ll y){
    if(l==r){
        if(t[now].mn>x||t[now].mn==x&&t[now].lst>y){
            t[now].mn=x;
            t[now].lst=y;
        }
        return ;
    }
    ll mid=(l+r>>1);
    if(pos<=mid){
        upd(t[now].ls,l,mid,pos,x,y); 
    }
    else{
        upd(t[now].rs,mid+1,r,pos,x,y); 
    }
    if(t[t[now].ls].mn<t[t[now].rs].mn){
        t[now].mn=t[t[now].ls].mn;
        t[now].lst=t[t[now].ls].lst;
    }
    else{
        t[now].mn=t[t[now].rs].mn;
        t[now].lst=t[t[now].rs].lst;
    }
}
node2 query(ll now,ll l,ll r,ll L,ll R){
    if(l>=L&&r<=R){
        return {t[now].mn,t[now].lst};
    }
    ll mid=(l+r>>1);
    if(R<=mid){
        return query(t[now].ls,l,mid,L,R); 
    }
    else if(L>mid){
        return query(t[now].rs,mid+1,r,L,R); 
    }
    else{
        return min(query(t[now].ls,l,mid,L,R),query(t[now].rs,mid+1,r,L,R));
    }
}
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        rt=p++;
        build(rt,0,n);
        for(int i=1;i<=n;i++){
            cin>>a[i];
            res[i].clear();
            if(a[i])res[max(i-a[i],0ll)].push_back(i);
            dp[i]=1000000000000000000ll;
        }
        for(int i=1;i<=n;i++){
            if(a[i]){
                node2 tmp=query(rt,0,n,max(i-a[i],0ll),max(i-1,0));
                if(tmp.mn+1<dp[i]||tmp.mn+1==dp[i]&&tmp.lst<lst[i]){
                    dp[i]=tmp.mn+1;
                    lst[i]=tmp.lst;
                }
                upd(rt,0,n,min(i+a[i]-1,n),dp[i],i);
            }
            for(int j=0;j<res[i].size();j++){
                node2 tmp=query(rt,0,n,max(res[i][j]-a[res[i][j]],0ll),min(res[i][j]+a[res[i][j]]-1,n));
                dp[res[i][j]]=tmp.mn+1;
                lst[res[i][j]]=tmp.lst;
            }
        }
        if(query(rt,0,n,n,n).mn>999999999999999999ll){
            cout<<-1<<endl;
            continue;
        }
        ans.clear();
        ll tmp=query(rt,0,n,n,n).lst;
        while(tmp){
            ans.push_back(tmp);
            tmp=lst[tmp];
        }
        sort(ans.begin(),ans.end(),cmp);
        cout<<ans.size()<<endl;
        for(int i=0;i<ans.size();i++){
            cout<<ans[i]<<' ';
        }
        cout<<endl;
    }
    return 0;
}