CF 记录

cqbzlzh / 2023-08-16 / 原文

CF1858B The Walkway

降智题，但是这种题放B着实有点恶心
考虑每两个相邻点对\(x\),\(y\)对于答案的贡献，显然是\(\frac{s_y-s_x-1}{d}\)
然后每次枚举删除的点\(i\)，减去\((i-1,i)\),\((i+1,i)\)的贡献，再加上\((i-1,i+1)\)的贡献就是可能的答案
但是实现的时候细节很多，主要是两个端点不好处理，一种比较简单的实现方法是将\(1-d\)和\(n+1\)加入点集再特判即可

\(code\):

点击查看代码

#include<bits/stdc++.h>
 
using namespace std;
 
template <class T>
void read(T &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f=c=='-',c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    x=f? (-x):x;
}
#define ll long long
 
const int MAXN=2e5+5;
 
int T,n,m,d,s[MAXN];
 
int calc(int x,int y){
    return (s[y]-s[x]-1)/d;
}
 
int main(){
    read(T);
    while(T--){
        read(n);read(m);read(d);
        for (int i=1;i<=m;i++) read(s[i]);
        s[++m]=1-d,s[++m]=n+1;
        sort(s+1,s+1+m);
        int ans=0;
        for (int i=2;i<=m;i++){
            ans+=(s[i]-s[i-1]-1)/d;
        }
        ans+=m-2;
        int mn=0x3f3f3f3f;
        int cnt=0;
        for (int i=2;i<m;i++){
            int cur=calc(i-1,i+1)-calc(i-1,i)-calc(i,i+1);
            if (cur<mn){
                mn=cur;
                cnt=1;
            }
            else if (cur==mn) cnt++;
        }
        printf("%d %d\n",ans+mn-1,cnt);
    }
}

CF1858 E1. Rollbacks (Easy Version)

赛后听神加哥讲完后还是感觉非常套路的。。。
对于这种带有回退的问题，考虑建出树形结构，每次加入一个点时直接新建节点往下走并预处理\(k\)级祖先，删除时直接往上跳\(k\)级祖先，回退时用之前加入和删除时栈中记录的在树中的位置回溯，询问直接挂在树上。最后一次\(dfs\)即是答案。

对于\(E2\)强制在线，发现对每个询问其实能产生贡献的只有它到根节点的一条链，直接维护这条链上的信息即可。~~但是懒得写了~~

点击查看代码

#include<bits/stdc++.h>

using namespace std;

template <class T>
void read(T &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f=c=='-',c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    x=f? (-x):x;
}

const int MAXN=1e6+5;

int m,qcnt;
int ans[MAXN];
struct Query{
    char op;
    int x,id;
}q[MAXN];

vector <int> G[MAXN];
vector <int> Q[MAXN];

int tot,u,a[MAXN],fa[MAXN][24];

void init(int u,int f){
    fa[u][0]=f;
    for (int i=1;i<24;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
}

int kth(int u,int k){
    for (int i=0;i<24;i++){
        if (k&(1<<i)) u=fa[u][i];
    }
    return u;
}

int st[MAXN],top;

int bucket[MAXN],res;

void dfs(int u){
    for (const auto &x:Q[u]) ans[x]=res;
    for (const auto &v:G[u]){
        if (++bucket[a[v]]==1) res++;
        dfs(v);
        if (--bucket[a[v]]==0) res--;
    }
}

void solve(){
    u=1;tot=1;
    for (int i=1;i<=m;i++){
        if (q[i].op=='+'){
            st[++top]=u;
            ++tot;
            G[u].push_back(tot);
            a[tot]=q[i].x;
            init(tot,u);
            u=tot;
        }
        else if (q[i].op=='-'){
            st[++top]=u;
            u=kth(u,q[i].x);
        }
        else if (q[i].op=='!'){
            u=st[top--];
        }
        else Q[u].push_back(q[i].id);
    }
    dfs(1);
}

int main(){
    read(m);
    for (int i=1;i<=m;i++){
        char op[5];
        scanf("%s",(op+1));
        q[i].op=op[1];
        if (op[1]=='+'||op[1]=='-') read(q[i].x);
        if (op[1]=='?') ++qcnt,q[i].id=qcnt;       
    }
    solve();
    for (int i=1;i<=qcnt;i++) printf("%d\n",ans[i]);
}