专栏文章

ICPC 2023 Online I vp记录（题解）

mminstdfx风神少女
生活·游记参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mio11sg4
此快照首次捕获于
2025/12/02 11:37
3 个月前
此快照最后确认于
2025/12/02 11:37
3 个月前
查看原文

A

根据题意模拟即可。
CPP
void solve() {
    int n,m; cin>>n>>m; vector<string> s,t;
    set<string> se,te; string tmp;
    for(int i=0;i<n;++i) {
        cin>>tmp;
        if(!se.count(tmp)) s.push_back(tmp);
        se.insert(tmp);
    }
    for(int i=0;i<m;++i) {
        cin>>tmp;
        if(!te.count(tmp)) t.push_back(tmp);
        te.insert(tmp);
    }

    map<string,pii> rk;
    for(int i=0;i<int(s.size());++i) {
        if(!rk.count(s[i])) rk[s[i]]={i,1};
        else chkmin(rk[s[i]],{i,1});
    }
    for(int i=0;i<int(t.size());++i) {
        if(!rk.count(t[i])) rk[t[i]]={i,2};
        else chkmin(rk[t[i]],{i,2});
    }
    vector<string> S; for(auto&[s,y]:rk) S.push_back(s);
    sort(S.begin(),S.end(),[&](const string &s,const string &t) {
        return rk[s]<rk[t];
    });
    for(auto &s:S) cout<<s<<"\n";
}

L

直接输出 max⁡{2,⌈max⁡tiT⌉}\max\{2,\lceil\frac{\max t_i}{T}\rceil\}。
CPP
void solve() {
    int n,T,t; cin>>n>>T;
    int ans=2;
    while(n--) {
        cin>>t;
        chkmax(ans,(t+T-1)/T);
    }
    cout<<ans<<"\n";
}

D

注意到条件等价于所有连通块是完全子图。若当前所有的连通块已经是完全子图，则找两个最小的合并，否则补全。
CPP
void solve() {
    int n,m; cin>>n>>m; dsu_t dsu(n);
    for(int i=1,u,v;i<=m;++i) {
        cin>>u>>v; dsu.merge(u,v);
    }
    ll needadd=0;
    vector<int> tuan;
    for(int i=1;i<=n;++i) {
        if(i!=dsu.findfa(i)) continue;
        if(1ll*dsu.sz[i]*(dsu.sz[i]-1)/2>dsu.ecnt[i]) {
            needadd+=1ll*dsu.sz[i]*(dsu.sz[i]-1)/2;
            needadd-=dsu.ecnt[i];
        } else tuan.push_back(dsu.sz[i]);
    }
    if(!needadd) {
        sort(tuan.begin(),tuan.end());
        cout<<tuan[0]*1ll*tuan[1]<<"\n";
    } else {
        cout<<needadd<<"\n";
    }
}

I

先写出一个简单的 dp，dpi,j,maskdp_{i,j,mask} 表示填好前 ii 个字符，最后一个是 jj，三种字符分别有没有出现。首先滚一下数组，然后发现转移的一项和可以记一下，然后做完了。
CPP
void solve() {
    int n; string tmpl; cin>>n>>tmpl; tmpl="&"+tmpl;
    Z dp[2][64][8],f[2][8];
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;f[0][0]=1;
    auto toc=[](int c) ->int {
        if('a'<=c && c<='z') return c-'a'+1;
        if('A'<=c && c<='Z') return c-'A'+27;
        if(isdigit(c)) return c-'0'+53;
        return -1;
    };
    auto getmask=[](int c) {
        if(c<=0) return 0;
        if(c<=26) return 1;
        if(c<=52) return 2;
        if(c<=62) return 4;
        return 0;
    };
    for(int i=1,k=1;i<=n;++i,k^=1) {
        vector<int> fillin;
        if(tmpl[i]=='?') {
            fillin.assign(62,0);
            iota(fillin.begin(),fillin.end(),1);
        } else if('a'<=tmpl[i] && tmpl[i]<='z') {
            fillin={toc(tmpl[i]),toc(tmpl[i]-'a'+'A')};
        } else fillin.push_back(toc(tmpl[i]));
        memset(dp[k],0,sizeof(dp[k]));
        memset(f[k],0,sizeof(f[k]));
        for(int ch:fillin) {
            for(int stat=0;stat<8;++stat) {
                int nxt=stat|getmask(ch);
                dp[k][ch][nxt]+=f[k^1][stat];
                dp[k][ch][nxt]-=dp[k^1][ch][stat];
                f[k][nxt]+=f[k^1][stat];
                f[k][nxt]-=dp[k^1][ch][stat];
            }
        }
    }
    Z ans=0;
    for(int i=1;i<63;++i)
        ans+=dp[n&1][i][7];
    cout<<ans.raw()<<"\n";
}

J

因为圆的坐标不交，所以把图画出来，发现对于一条和对角线平行的直径对称的两段测度相同的圆弧平均一下对称一下相当于最后所有的点都在那条直径上，而且这条直径到另一个圆所在的四分之一平面的所有点的曼哈顿距离完全一致。接下来就是找另一个圆上的一个点离那条直径的曼哈顿距离最近。直接画一条平行切线即可，答案即为 ∣O1O2∣−2r2|O_1O_2|-\sqrt 2 r_2。
CPP
void solve() {
    long double x1,y1,x2,y2;
    long double xl,xr,yl,yr;
    cin>>xl>>yl>>xr>>yr;
    x1=(xl+xr)/2; y1=(yl+yr)/2;
    cin>>xl>>yl>>xr>>yr;
    x2=(xl+xr)/2; y2=(yl+yr)/2;
    auto myabs=[](long double x) {
        return x<0?-x:x;
    };
    long double D=sqrt((xr-xl)*(xr-xl)+(yr-yl)*(yr-yl));
    printf("%.6Lf\n",abs(x1-x2)+abs(y1-y2)-D/sqrt((long double)2));
}

G

首先因为生成过程中每条边独立选取，因此如果树合法答案一定是总方案数的倒数。总方案数量显然在合并过程中累乘两个连通块大小的积即可。如何判断合法呢？只需要在给定的树上模拟过程，维护每个连通块的根，判断每次合并不在同一个连通块且其中一个连通块的根的父亲在另一个指定的连通块里面即可。
CPP
void solve() {
    int n; cin>>n; vector<pii> mgt(n-1);
    Z res=1; dsu_t dsu(n+1);
    for(auto &[u,v]:mgt)cin>>u>>v,res*=dsu.merge(u,v);
    res=res.inv();
    vector<pii> tree(n-1); int flag=1;
    for(auto &[u,v]:tree) cin>>u>>v;
    vector<int> dep(n+1,0),fa(n+1),tfa(n+1);
    vector<vector<int>> e(n+1);
    for(auto[u,v]:tree) {
        e[u].push_back(v);
        e[v].push_back(u);
    }
    iota(fa.begin(),fa.end(),0);
    auto findfa=[&fa](this auto &&dfs,int u) -> int {
        return fa[u]==u?u:fa[u]=dfs(fa[u]);
    };
    auto dfs=[&](this auto &&dfs,int u,int ft) -> void {
        tfa[u]=ft; dep[u]=dep[ft]+1;
        for(int v:e[u]) if(v!=ft) {
            dfs(v,u);
        }
    }; dfs(1,0);
    for(auto[mu,mv]:mgt) {
        int tu=findfa(mu),tv=findfa(mv);
        if(tu==tv) { flag=0; break; }
        if(findfa(tfa[tu])==tv) {
            fa[tu]=tv;
        } else if(findfa(tfa[tv])==tu) {
            fa[tv]=tu;
        } else { flag=0; break; }
    }
    if(flag) cout<<res.raw()<<"\n";
    else cout<<"0\n";
}

K

引理

给圆盘内等概率随机点 XX（均匀分布在半径为 rr 的圆内），取一个定点 AA，记圆心为 OO，且 d=∣OA∣d=|OA|。要证
E ∣AX∣2=r22+d2.\mathbb E\,|AX|^2=\frac{r^2}{2}+d^2 .
以圆心为原点，把 XX 看作二维随机向量，AA 的向量记为 aa，则
∣AX∣2=∥X−a∥2=∥X∥2−2a⋅X+∥a∥2.|AX|^2=\|X-a\|^2=\|X\|^2-2a\cdot X+\|a\|^2 .
对期望取值并用线性性：
E∥X−a∥2=E∥X∥2−2a⋅EX+∥a∥2.\mathbb E\|X-a\|^2=\mathbb E\|X\|^2-2a\cdot \mathbb E X+\|a\|^2.
圆盘关于原点对称，故 EX=0\mathbb E X=0，于是
E∥X−a∥2=E∥X∥2+∥a∥2.\mathbb E\|X-a\|^2=\mathbb E\|X\|^2+\|a\|^2.
接下来算 E∥X∥2\mathbb E\|X\|^2。均匀圆盘在极坐标 (ρ,θ)(\rho,\theta) 下的径向密度为
fρ(ρ)=2ρr2(0≤ρ≤r),f_\rho(\rho)=\frac{2\rho}{r^2}\quad(0\le \rho\le r),
于是
E∥X∥2=E[ρ2]=∫0rρ22ρr2 dρ=2r2⋅r44=r22.\mathbb E\|X\|^2=\mathbb E[\rho^2]=\int_0^r \rho^2 \frac{2\rho}{r^2}\,d\rho =\frac{2}{r^2}\cdot \frac{r^4}{4}=\frac{r^2}{2}.
又 ∥a∥=∣OA∣=d\|a\|=|OA|=d，故
E ∣AX∣2=r22+d2.\mathbb E\,|AX|^2=\frac{r^2}{2}+d^2.
证毕。

解法

转化为最小化 dd。只需要先判断是否在凸包内，然后遍历所有凸包边，求最短距离即可。
CPP
void solve() {
    int n,q; cin>>n>>q;
    vector<Point> convex(n);
    for(auto &[x,y]:convex) cin>>x>>y;
    convex=ConvexHull(convex);
    double x1,y1,x2,y2;
    for(int i=1;i<=q;++i) {
        cin>>x1>>y1>>x2>>y2;
        double x=(x1+x2)/2.0,y=(y1+y2)/2.0;
        double R=sqrtl((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))*0.5;
        Point pos{x,y};
        if(inConvex(pos,convex)!=-1) {
            printf("%6Lf\n",0.5*R*R);
            continue;
        }
        double mindis=1e12;
        for(int i=0;i<n;++i) {
            int j=(i+1)%n;
            auto kk=Line(convex[i],convex[j]);
            auto p=NearestPointToLineSeg(pos,kk);
            chkmin(mindis,sqrtl((p.x-pos.x)*(p.x-pos.x)+(p.y-pos.y)*(p.y-pos.y)));
        }
        printf("%.6Lf\n",0.5*R*R+mindis*mindis);
    }
}

F

先打表。得出结论：后手必胜，当且仅当三个数完全相同，或两个数相同，且不同数的差的 lowbit 为 2 的某个偶数幂。

证明

我们不妨考虑状态的本质：两个相邻项的差 (a,b)(a,b)，满足 a<ba<b。
在接下来的表示中，我们认为 (b,a)(b,a) 和 (a,b)(a,b) 代表同一个状态。对于一切 a>0a>0 的状态，我们总能一步到达它的某个后继状态 (0,b−a)(0,b-a) 的所有后继状态 (i,b−a−2i)∀0<i≤b−a2(i,b-a-2i)\forall 0<i\le\frac {b-a} 2 或 (b−a−i,2i−b−a)∀b−a2<i<b−a(b-a-i,2i-b-a)\forall \frac{b-a} 2<i<b-a，因此无论该后继状态是必胜还是必败，原状态总是存在一个后继必败态。因此对于所有的 a>0a>0，一定是先手必胜态。
对于一个状态 (0,b)(0,b)，考虑数学归纳法。如果 lowbit⁡(b)=1\operatorname{lowbit}(b)=1，说明 bb 是奇数，则下一个状态必然有三个数各不相同，因此为必胜态。对于 lowbit⁡(b)=2k(k>0)\operatorname{lowbit}(b)=2^k(k>0)，其除 (0,b/2)(0,b/2) 以外的后继状态均为必胜态。因此其胜败性完全取决于这一个后继态，且与其相反。

维护

正难则反。考虑统计先手必败的方案数。对于三个数完全相同的方案，是简单的；对于两个数相同的情况，每次我们在添加一个数之前，我们需要知道这个数之前出现的次数 cc，和这个数异或后的 lowbit 为 2 的偶数幂的所有数的个数 s1s_1 和相同的对数 s2s_2。和这个新加的数形成非法三元组的数量为 c⋅s1+s2c\cdot s_1+s_2。cc 可以用 map 维护，ss 可以简单地使用反转后的 trie 进行维护和查询。
CPP
struct trienode {
    ll samepairs,szcnt;
    int ch[2];
};
trienode trie[40000009];
int rt=1,nodeptr=1;
void insert(int u,ll val,ll dep,ll thiscnt,ll &res) {
    if(dep==63) {
        trie[u].samepairs+=trie[u].szcnt;
        ++trie[u].szcnt;
        return;
    }
    int b=(val>>dep)&1;
    if(dep%2==0) {
        res+=thiscnt*(trie[trie[u].ch[b^1]].szcnt);
        res+=trie[trie[u].ch[b^1]].samepairs;
    }
    if(!trie[u].ch[b]) {
        trie[u].ch[b]=++nodeptr;
        trie[nodeptr]={0,0,0,0};
    }
    insert(trie[u].ch[b],val,dep+1,thiscnt,res);
    trie[u].samepairs=trie[trie[u].ch[0]].samepairs;
    trie[u].samepairs+=trie[trie[u].ch[1]].samepairs;
    trie[u].szcnt=trie[trie[u].ch[0]].szcnt;
    trie[u].szcnt+=trie[trie[u].ch[1]].szcnt;
}
void solve() {
    int n; cin>>n; vector<ll> a(n);
    nodeptr=1;
    trie[1]={0,0,0,0};
    for(ll &v:a) cin>>v;
    map<ll,ll> m_cnt;
    for(ll v:a) m_cnt[v]++;
    ll ans=0;
    for(auto[_,c]:m_cnt) ans+=1ll*c*(c-1)*(c-2)/6;
    map<ll,ll> now_cnt;
    for(ll v:a) {
        insert(rt,v,0,now_cnt[v],ans);
        now_cnt[v]+=1;
    }
    cout<<1ll*n*(n-1)*(n-2)/6-ans<<"\n";
}
附打表代码
CPP
int iswin[401][401];
int dfs(int x,int y,int fl=0) {
    // 本质上只需确定两个值，即排序后两两的差：
    // 不妨设左侧差小，我们可以表示为 a a+x a+2x+y
    // printf("%d %d(actually 0 %d %d)\n",x,y,x,2*x+y);
    if(iswin[x][y]>-1) return iswin[x][y];
    // operation on a and a+x
    for(int i=1;i<x;++i) {
        // 0 x 2x+y \to i x-i 2x+y
        array<int,3> qwq={i,x-i,2*x+y};
        sort(qwq.begin(),qwq.end());
        pii delt={qwq[1]-qwq[0],qwq[2]-qwq[1]};
        if(delt.first>delt.second) swap(delt.first,delt.second);
        if(!dfs(delt.first,delt.second-delt.first,fl)) return iswin[x][y]=1;
    }
    // operation on a and a+2x+y
    for(int i=1;i<2*x+y;++i) {
        array<int,3> qwq={i,x,2*x+y-i};
        sort(qwq.begin(),qwq.end());
        pii delt={qwq[1]-qwq[0],qwq[2]-qwq[1]};
        if(delt.first>delt.second) swap(delt.first,delt.second);
        if(!dfs(delt.first,delt.second-delt.first,fl)) return iswin[x][y]=1;
    }
    // operation on a+x and a+2x+y
    for(int i=1;i<x+y;++i) {
        array<int,3> qwq={0,x+i,2*x+y-i};
        sort(qwq.begin(),qwq.end());
        pii delt={qwq[1]-qwq[0],qwq[2]-qwq[1]};
        if(delt.first>delt.second) swap(delt.first,delt.second);
        if(!dfs(delt.first,delt.second-delt.first,fl)) return iswin[x][y]=1;
    }
    return iswin[x][y]=0;
}

H

对于一个确定的周期长度 kk，对于所有的 i≥ki\ge k，sis_i 是否具有 kk 的周期这一条件具有单调性，可以二分出 maxposkmaxpos_k 表示 kk 是 sk,⋯ ,smaxposks_k,\cdots,s_{maxpos_k} 的周期，但不是 smaxposk+1s_{maxpos_k+1} 的周期。预处理出 sns_n，所有的 sis_i 都是它的一个子串。判断子串周期可以使用 SA+rmq、哈希或是任何你喜欢的算法。
考察询问其实就是问 min⁡l≤i≤r,k≤maxpospipi\min_{l\le i\le r,k\le maxpos_{p_i}} p_i 扫描线维护即可。若答案 >i>i 则说明无解。
CPP
constexpr int maxn=5e5+9;
void get_sa(const char s[],int n,int sa[],int rk[],int he[])
{
    static int buc[maxn],id[maxn],p[maxn],t[maxn];
    int m=300;
    for(int i=1;i<=n;++i) buc[rk[i]=s[i]]++;
    for(int i=1;i<=m;++i) buc[i]+=buc[i-1];
    for(int i=n;i;--i) sa[buc[rk[i]]--]=i;
    memset(buc,0,sizeof(int)*(m+1));
    for(int k=1,cc=0;cc!=n;k<<=1,m=cc)
    {
        cc=0;
        for(int i=n;i>n-k;--i) id[++cc]=i;
        for(int i=1;i<=n;++i)
            if(sa[i]>k) id[++cc]=sa[i]-k;
        for(int i=1;i<=n;++i) buc[p[i]=rk[id[i]]]++;
        for(int i=1;i<=m;++i) buc[i]+=buc[i-1];
        for(int i=n;i;--i) sa[buc[p[i]]--]=id[i];
        memset(buc,0,sizeof(int)*(m+1));
        memcpy(t,rk,sizeof(int)*(n+1));
        t[n+1]=0;
        cc=0;
        for(int i=1;i<=n;++i)
        {
            if(t[sa[i]]!=t[sa[i-1]] || t[sa[i]+k]!=t[sa[i-1]+k]) ++cc;
            rk[sa[i]]=cc;
        }
    }
    for(int i=1;i<=n;++i) sa[rk[i]]=i;
    for(int i=1,k=0;i<=n;++i)
    {
        if(k) --k;
        if(rk[i]>1) while(sa[rk[i]-1]+k<=n && 
            s[i+k]==s[sa[rk[i]-1]+k]) ++k;
        he[rk[i]]=k;
    }
}
int stb[21][maxn],mylg[maxn];
int P[maxn];
int st[maxn<<2];
inline void pushup(int rt) {
    st[rt]=min(st[rt<<1],st[rt<<1|1]);
}
void build(int l,int r,int rt) {
    if(l==r) {
        st[rt]=INT_MAX;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void upd(int p,int x,int l,int r,int rt) {
    if(l==r) return void(st[rt]=x);
    int mid=(l+r)>>1;
    if(p<=mid) upd(p,x,l,mid,rt<<1);
    else upd(p,x,mid+1,r,rt<<1|1);
    pushup(rt);
}
int qry(int ql,int qr,int l,int r,int rt) {
    if(ql<=l && r<=qr) return st[rt];
    int mid=(l+r)>>1,ans=INT_MAX;
    if(ql<=mid) chkmin(ans,qry(ql,qr,l,mid,rt<<1));
    if(qr>mid)  chkmin(ans,qry(ql,qr,mid+1,r,rt<<1|1));
    return ans;
}
void solve() {
    int n,m,q; string D,str;
    cin>>n>>D; str.assign(n+1,'*');
    vector<pii> views(n+1);
    views[n]={1,n};
    int pp=n;
    for(auto ch:D|std::views::reverse) {
        views[pp-1]=views[pp];
        if(islower(ch)) {
            str[views[pp-1].second--]=ch;
        } else {
            str[views[pp-1].first++]=tolower(ch);
        }
        --pp;
    }
    vector<int> sa(n+1),rk(n+1),height(n+1);
    get_sa(str.c_str(),n,&sa[0],&rk[0],&height[0]);
    mylg[0]=-1;
    for(int i=1;i<=n;++i) mylg[i]=mylg[i>>1]+1;
    for(int i=1;i<=n;++i) stb[0][i]=height[i];
    for(int j=1;(1<<j)<=n;++j) {
        for(int i=1;i+(1<<j)-1<=n;++i)
            stb[j][i]=min(stb[j-1][i],stb[j-1][i+(1<<(j-1))]);
    }
    auto getmin=[&](int l,int r) -> int {
        if(l>r) return INT_MAX;
        int k=mylg[r-l+1];
        return min(stb[k][l],stb[k][r-(1<<k)+1]);
    };
    auto getlcp=[&](int i,int j) -> int {
        if(i==j) return n-i+1;
        i=rk[i]; j=rk[j];
        if(i>j) swap(i,j);
        return getmin(i+1,j);
    };
    auto checkperiod=[&](int l,int r,int k) {
        int len=r-l+1;
        if(k<1||k>len) return false;
        if(len==k) return true;
        return getlcp(l,l+k)>=len-k;
    };
    int maxpos[maxn];
    for(int i=1;i<=n;++i) {
        maxpos[i]=-1;
        int l=i,r=n,mid;
        while(l<=r) {
            mid=(l+r)>>1;
            if(checkperiod(views[mid].first,views[mid].second,i)) {
                maxpos[i]=mid;
                l=mid+1;
            } else r=mid-1;
        }
    }
    cin>>m;
    vector<vector<pair<pii,int>>> qs(n+1);
    vector<vector<int>> upds(n+1);
    for(int i=1;i<=m;++i) cin>>P[i];
    for(int i=1;i<=m;++i) {
        upds[maxpos[P[i]]].push_back(i);
    }
    build(1,m,1);
    cin>>q; vector<int> ans(q,INT_MAX);
    for(int i=0,k,l,r;i<q;++i) {
        cin>>k>>l>>r;
        qs[k].push_back({{l,r},i});
    }
    for(int i=n;i;--i) {
        for(auto pos:upds[i]) {
            upd(pos,P[pos],1,m,1);
        }
        for(auto[range,id]:qs[i]) {
            auto[ql,qr]=range;
            ans[id]=qry(ql,qr,1,m,1);
            int ans2=INT_MAX;
            if(ans[id]>i) ans[id]=INT_MAX;
        }
    }
    for(int i=0;i<q;++i)
        cout<<(ans[i]==INT_MAX?-1:ans[i])<<"\n";
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...