Codeforces Round 909 (Div. 3) 游祭

· · 个人记录

我不会 F。

A,B 是没脑子题。

C 是 DP（？），判断 a_i 和 a_{i-1} 的奇偶性取最大值就行了。

D 是找性质，推一下等式就可以发现只有 a_i=1/2,a_j=2/1 和 a_i=a_j 的时候才会有 b_i^{b_j}=b_j^{b_i}。套个组合数就行。

E 也是找性质，一开始写了个分块发现搞不出来。后来才看出来在第 1 个最小值之后，序列只要是不增的答案就是第 1 个最小值下标 -1，否则无解。

现在是 0:55，写完上面的之后突然想出来 F 了……

这里应该有一份 WA#2 的赛时没脑子代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline

const int N=1005,M=10;
int n,q;
int dep[N],isleaf[N];
bool vis[N];int ok[N][N];
int fa[N],f[N][M];
int fk[N][N];

il void dfs(int now,int F){
    fa[now]=F;isleaf[now]=0;bool fl=0;
    f[now][0]=F,dep[now]=dep[F]+1;
    for(re int i=1;i<M;++i) f[now][i]=f[f[now][i-1]][i-1];
    for(re int i=1;i<=n;++i){
        if(ok[now][i]&&now!=i&&i!=F){
            dfs(i,now);fl=1;
            for(re int j=0;j<=n;++j){
                fk[now][j+1]=max(fk[now][j+1],fk[i][j]);
            }
        }
    }
    if(!fl) isleaf[now]=1,fk[now][0]=1;
}
il int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(re int i=M-1;i>=0;--i) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(re int i=M-1;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
il int dist(int x,int y){
    int lc=lca(x,y);
    return dep[x]+dep[y]-2*dep[lc];
}
il int up(int x,int dept){
    for(re int i=M-1;i>=0;--i) if(dep[f[x][i]]>=dept) x=f[x][i];
    return x;
}

il void solve(){
    cin>>n>>q;
    for(re int i=1;i<=n;++i)for(re int j=1;j<=n;++j) ok[i][j]=0;
    for(re int i=1;i<=n;++i)for(re int j=0;j<M;++j) f[i][j]=0;
    for(re int i=1;i<n;++i) cout<<i<<" "<<i+1<<"\n",ok[i][i+1]=ok[i+1][i]=1,dep[i]=i,dep[i+1]=i+1;
    isleaf[1]=isleaf[n]=1;
    for(re int k=1;k<=q;++k){for(re int i=0;i<=n;++i) for(re int j=0;j<=n;++j) fk[i][j]=0;
        dfs(1,0);for(re int i=1;i<=n;++i) vis[i]=0;
        isleaf[1]=1;
        int dis;cin>>dis;
        bool fl=0;
        for(re int i=1;i<=n;++i){
            if(!isleaf[i]) continue;
            for(re int j=i+1;j<=n;++j){
                if(isleaf[i]&&isleaf[j]){
                    if(dist(i,j)==dis){fl=1;
                        cout<<"-1 -1 -1\n";break;
                    }
                }
            }
            if(fl) break;
        }
        if(fl) continue;
        int id=0,maxx=0;
        for(re int i=1;i<=n;++i) if(maxx<dep[i]) maxx=dep[i],id=i;
        int noww=id;while(fa[noww]!=1) noww=fa[noww];
        if(dep[id]-dep[1]>dis){
            int kk=up(id,dep[id]-dis+2);
            cout<<kk<<" "<<fa[kk]<<" "<<noww<<"\n";
            ok[kk][fa[kk]]=ok[fa[kk]][kk]=0;
            ok[kk][noww]=ok[noww][kk]=1;
        }
        else{
            int cha=dis-(dep[id]-dep[1]);
            int now=id;
            while(now!=0) vis[now]=1,now=fa[now];
            for(re int i=1;i<=n;++i){
                if(!vis[i]){
                    if(fk[i][cha-1]){
                        cout<<i<<" "<<fa[i]<<" "<<id<<"\n";
                        ok[i][fa[i]]=ok[fa[i]][i]=0;
                        ok[i][id]=ok[id][i]=1;
                        break;
                    }
                }
            }
        }
    }
}

signed main(){
    int t;cin>>t;while(t--)
    solve();
    return 0;
}

F 好像真的很简单。先给构造成链（1 为链头，n 为链尾）。对于询问 d_i，如果某个叶子的深度为 d_i+1，则直接是 -1~-1~-1。否则把 n 移到某个深度为 d_i 的点的下面。因为 d_i-dep_1+1=d_i。可以发现，只要每次移动节点 n，树就最多是个二叉树，且只有一个分支。所以在 0 \le d_i \le n-1 的时候一定有解。啊，最小值只要非负就无所谓。

痛定思痛。

G 现在也没看过。以后再看吧。

好，F 现在又变成 O(q) 的了。什么 lj 数据范围。

好，现在是 1:40。我看懂 G 了。是昨天下午才学的 dsu on tree。输麻了。

考虑离线下来。映射 i 在 p 中的下标 x_i。用 dsu on tree 得到 i 子树中的所有映射下标。使用 set 存储，对于 x=i 的所有询问，二分查找 set 里第一个 \ge l 的地址。判断是否存在就行了。

现在是 2:04，过了。sb F 题毁我 AK div3。