UOJ Logo Rainbow_sjy的博客

博客

标签
暂无

UOJ 940 黑桃国王 题解

2025-02-09 21:15:51 By Rainbow_sjy

曾经有人反映说看不懂这题题解,我来写一个(

一些基础观察

首先可以只保留强连通分量里的边,考察每个强连通分量,可能有几种情况:

  1. 是一个“循环”,存在一个 $k$ 使得距离 $\bmod k$ 相同的点字符相同。此时生成的字符串数量是有限的 $k$ 个。
  2. 包含至少两个“循环” $A$ 和 $B$,可以生成 $A^{\infty},(AB)^{\infty},(AAB)^{\infty},(AAAB)^{\infty},\cdots$,此时有一个在集合中的下界 $A^{\infty}$。
  3. 可以生成 $(ABC)^{\infty},(ABBC)^{\infty},(ABBBC)^{\infty},\cdots$,此时有一个不在集合里的下界 $(AB^{\infty}C)^{\infty}$。

假设我们已经特判掉了第 1 种情况,考虑 2 和 3,我们可以求出一个最终集合的“上界”,再把情况 1 的串判断能否小于上界。

为了求出 2 和 3 的最小字符串,想做的是求出每个点开始,走一个字典序最小的无限环 是什么样的路径。

设 $f(u,i)$ 表示 $u$ 开始,走 $i$ 步得到的字符串,最小是什么。这里只记所有 $f(u,i)$ 之间的大小关系。

转移每步从 $i\to i+1$ 可以递推,并且只要做 $O(n)$ 轮,直到 $f(u,i)$ 不再变化。

然后建一张新的有向图,图上的每个点表示一个 $f(u,i)$ 的值,每个点仅有一条出边,指向它在原图中最小的出边的 $f$ 值。

考虑一个强连通分量中的最小字符串:

  1. 如果走的是一个 $\rho$ 形,对应情况 3。
  2. 如果走的是一个 $o$ 形,且一个强连通分量中有 $\ge 2$ 个不同的环,对应情况 2。
  3. 否则,对应情况 1。

这样可以得到 $O(nm)$ 做法。

这里看似需要一些后缀数据结构来比较,但实际上,我们可以把所有点一起做这个过程,这样就同时维护了所有点 $f$ 的值的大小关系。

优化

下面考虑优化求出 $f$ 的过程。

我们不再考虑一轮一轮递推出 $f$,而是维护当前所有点 $f$ 的相对大小关系。此时所有点会根据 $f$ 分为若干等价类,同时维护每个等价类的最小出边。

考虑一个“等价类分裂”操作:假设一开始某个集合 $S$ 中所有点的 $f$ 是相等的,现在把集合 $S$ 分成两个集合 $S_0,S_1$,其中 $f(u) < f(v) (u\in S_0,v\in S_1)$。

这会造成 $S$ 中所有点的前驱的 $f$ 值可能发生变化。从而发生更多的“等价类分裂”的连锁反应。

初始把所有点当成一个等价类,然后每次把最小的字母分裂出去,并且处理所有“等价类分裂”的连锁反应。

如果每次暴力处理分裂,直到不再分裂,能求出所有点的 $f$。时间复杂度仍为 $O(nm)$。

但是这里可以“启发式分裂”:选择 $S_0,S_1$ 中 size 更小的那一边,遍历 $S_i$ 的所有前驱,只考虑这些前驱的等价类的变化。

具体过程如下:

  • 维护一个队列,存储所有分裂操作 $S\to S_0,S_1$。
  • 一开始插入所有“分裂一个最小字母”的操作,这部分大小 $\le n$ 个。
  • 若 $|S_0| \le |S_1|$:
    • 遍历所有 $u\in S_0$ 的入边。
    • 假设有 $x\to u,x\in T$,且 $T\to S$,则 $T$ 的出边可能会修改。
    • 由于 $S_0$ 更小,对于所有 $x$,等价类都会修改为 $T_0$,其中 $T_0 < T$。
  • 若 $|S_0| > |S_1|$:
    • 若对于 $x$,所有 $x$ 向 $S$ 的出边都指向 $S_1$,则等价类会修改为 $T_1$,其中 $T_1 > T$。
  • 遍历所有被影响的等价类 $T$,可能被分裂成两个集合 $\{T_0,T\}$ 或 $\{T,T_1\}$。若两个集合都不为空,则需要分裂。
    • 取出两个集合中更小的那一个,建立一个新的等价类。
    • 以分成 $\{T_0,T\}$ 为例:
      • $|T_0| \le |T|$:建立一个 $T_0$ 的等价类。
      • $|T_0| > |T|$:遍历整个 $T$,求出 $T\setminus T_0$,建立 $T\setminus T_0$ 的等价类。此时原来的 $T$ 大小减半。
    • 然后在队列中 push 一个分裂操作。

时间复杂度 $O(m\log n)$。

UOJ Round #29 公告

2025-02-09 13:02:04 By Rainbow_sjy

UOJ Round #29 将于 2 月 16 日星期日晚上 18:00 举行!比赛将进行 4 个小时,共三道题。

这是 UOJ 第二十九场 UOJ Round,还是一如既往的省选及以上难度,欢迎大家来玩!

公元 2024 年 2 月 8 日,小青鱼越过高高的龙门,成为大青龙。而一年后,公元 2025 年 2 月 8 日,跳蚤王国的一社区由于龙太唐而倒闭。

面对这一突如其来的变故,跳蚤国王决定建立一个全新的“多元、开放与包容”的学术讨论社区“跳蚤宇宙”,让所有热爱编程与竞赛的跳蚤们继续在这里交流思想、碰撞智慧、共同进步。

然而,在建设社区的过程中,伏特遇到了一些技术难题。你能否帮助伏特攻克技术难关,共同打造跳蚤王国新的学术讨论社区?

比赛链接:https://uoj.ac/contest/94

出题人:GeZhiyuan, zhoukangyang, dead_X, xyf007

参加本次比赛将有机会获得 UOJ 抱枕!获奖条件的 SHA256 码是 622bf5d6173d427945b34efba3b00589b8b93525d703294f81441be508611bdd。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD: 恭喜前5名的选手!

  1. liuhengxi
  2. hhoppitree
  3. lgvc
  4. zjy0001
  5. cmk666
输入要计算 SHA-256 的字符串: 最后一发使得得分变高的提交的时间减去第一发使得得分变高的提交的时间最大的(精确到秒),若有多个相同的则取排名最高的。
SHA-256 哈希值: 622bf5d6173d427945b34efba3b00589b8b93525d703294f81441be508611bdd

恭喜 hhoppitree(3:40:24, 18:08:06 ~ 21:48:30) 获得 UOJ 抱枕!

双极定向的构造

2025-01-27 21:27:48 By Rainbow_sjy

双极定向 - 方法 1

以 $s$ 为根求出 dfs 树,求出每个点的 $fa(u)$ 和 $low(u)$(最浅能到达的祖先)。

在每个点开一个列表,每次剥掉一个叶子,把该叶子加入 $fa(u)$ 和 $low(u)$ 的列表末尾,表示染黑了 $fa(u)$ 或 $low(u)$ 后就可以染黑 $u$。这样若一个点染黑,则可以将其列表里的点依次染黑,不断递归下去。

假设要求 $s\to t$ 的双极定向。提取 $s\to t$ 的路径,在剥叶子的过程中,不剥掉这条路径上的点。然后将路径从 $s\to t$ 依次染黑,并且递归染黑其列表。

这个做法的本质是:

对于叶子节点,只保留了 $u-fa(u)$ 和 $u-low(u)$ 的边,这样并不改变点连通性。

此时叶子节点度数为 2,进行缩二度点操作:

若 $fa(u)$ 或 $low(u)$ 中有某一个染黑,则立刻染黑 $u$。这样操作,黑与白连通块仍然连通。

https://qoj.ac/submission/521207

int dfn[maxn],low[maxn],fa[maxn],idx,que[maxn],on[maxn];
vi e[maxn],p[maxn];
int cut[maxn];
bool vis[maxn];
void tar(int u,int pa){
    fa[u]=pa;
    dfn[u]=low[u]=++idx,que[idx]=u;
    int ch=0;
    for(auto v:e[u]){
        if(v==pa)continue;
        if(!dfn[v]){
            tar(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u] && pa) cut[u]=1;
            ++ch;
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(!pa && ch>1) cut[u]=1;
}

int q[maxn],len,tim[maxn];
void dfs(int u){
    vis[u]=1;
    q[++len]=u,tim[u]=len;
    for(int v:p[u]) if(!vis[v]) dfs(v);
}
void bipolar(int n,int s,int t){
//    cout<<"bipolar "<<n<<" "<<s<<" "<<t<<"\n";
    For(i,0,n) dfn[i]=low[i]=fa[i]=cut[i]=vis[i]=on[i]=0,p[i].clear(); 
    idx=0,len=0;
    tar(s,0);
    vi path;
    for(int x=t;x;x=fa[x]) on[x]=1,path.pb(x);
    reverse(ALL(path));
    Rep(i,n,1){
        int u=que[i];
        if(!on[u]) p[fa[u]].pb(u),p[que[low[u]]].pb(u);
    }
    for(int x:path) dfs(x);
}

双极定向 - 方法 2

这里考虑将所有边定向。

先以 $s$ 为根求出 dfs 树,然后将 $s\to t$ 的路径定向成“向下”。

我们先把 $t$ 推进队列里,并把它标记为“向下”(向队列中加入 $(t,\downarrow)$)。

从队列里取出一个点 $t$,然后不断向上爬祖先,把 $t$ 到某个祖先都标记成相应的方向,直到碰到一个标记过的祖先边结束。

假设我们当前定向了 $(x,y)$ 这条边。这时碰到一条返祖边 $(x,u)$ 且 $u$ 在 $y$ 的子树中(重要细节:不要考虑 $u$ 不在 $y$ 子树中的返祖边)。此时需要给这条返祖边 $(x,u)$ 定向成 $(x,y)$ 相同的方向,然后将 $u$ 向上的一段树边路径定向成 $(x,y)$ 相反的方向。

把 $u$ 和这个对应方向推进队列里(比如下图就是加入 $(u,\uparrow)$),不断 bfs 即可。

我们发现这个过程相当于加入了一个“耳”。

具体实现的话,假设返祖边 $(x,u)$ 对应路径 $x\to y\to \dots \to u$,将这条返祖边加入 $y$ 的列表。定向树边 $(x,y)$ 时遍历一下 $y$ 的列表即可。

https://codeforces.com/contest/730/submission/257809370

int n,m,s,t;
vector<pii>e[maxn],et[maxn];
int fa[maxn],fe[maxn],dep[maxn];
int eu[maxn],ev[maxn];
int to[maxn];

void dfs(int u){
//    cout<<"dfs "<<u<<" "<<fa[u]<<" "<<dep[fa[u]]+1<<"\n";
    dep[u]=dep[fa[u]]+1;
    for(auto [v,i]:e[u]){
        if(i==fe[u])continue;
        if(!dep[v]){
            fa[v]=u,fe[v]=i;
            to[u]=v;
            dfs(v);
        }
        else if(dep[v]<dep[u]) et[to[v]].pb(mkp(u,i));
    }
}

pii q[maxn];
int hd,tl;
bool vis[maxn];
bool ve[maxn];

void go(int i,int d){
    ve[i]=1;
    if(dep[eu[i]]>dep[ev[i]]) swap(eu[i],ev[i]);
    if(d) swap(eu[i],ev[i]);
}
void decomp(){
    hd=1,tl=0;
    q[++tl]=mkp(t,0); // 0:dw 1:up
    while(hd<=tl){
        auto [u,d]=q[hd++];
        if(vis[u])continue;
        while(!vis[u]){
            vis[u]=1;
            if(u==s)break;
            go(fe[u],d);
        //    if(!vis[u]) q[++tl]=mkp(u,d);
            for(auto [v,j]:et[u]){
                go(j,d);
                if(!vis[v]) q[++tl]=mkp(v,!d);
            }
            u=fa[u];
        }
    }
}

UNR #8 D2T2 hack

2024-07-15 13:51:03 By Rainbow_sjy

膜拜传奇特级大师周康阳大佬

2023-04-22 17:21:51 By Rainbow_sjy

0: zhoukangyang

50: zhoukangyang

100: zhoukangyang

150: zhoukangyang

200: zhoukangyang

250: zhoukangyang

300: zhoukangyang

350: zhoukangyang

400: zhoukangyang

450: zhoukangyang

500: zhoukangyang

550: zhoukangyang

600: zhoukangyang

650: zhoukangyang

700: zhoukangyang

750: zhoukangyang

800: zhoukangyang

850: zhoukangyang

900: zhoukangyang

950: zhoukangyang

1000: zhoukangyang

1050: zhoukangyang

1100: zhoukangyang

1150: zhoukangyang

1200: zhoukangyang

1250: zhoukangyang

1300: zhoukangyang

1350: zhoukangyang

1400: zhoukangyang

1450: zhoukangyang

1500: zhoukangyang

1550: zhoukangyang

1600: zhoukangyang

1650: zhoukangyang

1700: zhoukangyang

1750: zhoukangyang

1800: zhoukangyang

1850: zhoukangyang

1900: zhoukangyang

1950: zhoukangyang

2000: zhoukangyang

2050: zhoukangyang

2100: zhoukangyang

2150: zhoukangyang

2200: zhoukangyang

2250: zhoukangyang

2300: zhoukangyang

2350: zhoukangyang

2400: zhoukangyang

2450: zhoukangyang

2500: zhoukangyang

2550: zhoukangyang

2600: zhoukangyang

2650: zhoukangyang

2700: zhoukangyang

2750: zhoukangyang

2800: zhoukangyang

2850: zhoukangyang

2900: zhoukangyang

2950: zhoukangyang

3000: zhoukangyang

zhoukangyang

zhoukangyang

@zhoukangyang

偷吃蛋糕

共 15 篇博客