Home

# 最短子列

# 题目描述

对于一个字符串 S=S1S2...S3S = S_1 S_2 ... S_3，定义它的一个子序列是任意满足 1≤i1<i2<...<ik≤n1 \le i_1 < i_2 <...< i_k \le n 的字符串 Si1Si2...SikS_{i_1} S_{i_2} ... S_{i_k}。字符串 SS 的非子序列即不是 SS 的子序列的字符串。

对于两个字符串 SS， TT 我们定义它们的最短公共非子序列为一个最短的字符串，使得它既是 SS 的非子序列，也是 TT 的非子序列。

这里 SS,TT 仅由 00 和 11 构成。现在请你求出字典序最小的最短公共非子序列。

# 解题思路

  1. 即依次考虑 TT 中的每个字符，记录在 𝑆𝑆 中匹配到的位置，每次贪⼼地找下⼀个字符出现的最早位置，如果失配就跳到 ∣𝑆∣+1|𝑆|+1。
    为了⽅便输出最⼩字典序，我们倒过来设计 DP：
    设 f(𝑖,𝑗)f(𝑖,𝑗) 表示按照上述匹配规则，在第⼀个字符串中匹配到 𝑖𝑖、在第⼆个字符串中匹配到 𝑗𝑗 时要使其成功到达 (𝒏+1,𝒎+1)(𝒏+1, 𝒎+1) 后⾯还需要的字符串的最短⻓度，这⾥ 𝑓(n+1,m+1)=0𝑓(n+1,m+1) = 0 就表示在两个字符串中都失配。
    转移时，设 𝑎Si,0/1𝑎_{S_{i, 0/1}} , 𝑎Ti,0/1𝑎_{T_{i, 0/1}} 表示分别在字符串 𝑆𝑆, 𝑇𝑇 中从 𝑖𝑖 开始的下⼀个 0,10,1 位置在哪，失配 就跳到 𝑛+1𝑛+1 𝑜𝑟 𝑚+1𝑚+1。需要顺便记录是从哪⾥转移的，从后往前转移的时候尽量尝试取 00。
    f(i,j)=min⁡{f(aSi,0,aTi,0),f(aSi,1,aTi,1)}f(i,j) = \min { \{f(a_{S_{i,0}},a_{T_{i,0}}), f(a_{S_{i,1}},a_{T_{i,1}})\} }
    最后答案取 f(0,0)f(0,0)，表示⽬前在两个字符串中都还没有开始匹配。输出⽅案的时候根据记
    录的来源倒推回去即可

  2. 答案一定是一个 SS 和 TT 的公共子序列拼接上一个 00 或 11 形成都不包含的字串。
    预处理出 SS ， TT 每个位置下一个 00，11 出现的位置（没有则设为 len+1len+1），直接跑 bfs, 然后记录转移时的前驱，先 00 后 11，最后输出答案即可。

# Code

#include<iostream>
#include<utility>
#include<cstdio>
#include<queue>
#define Pair pair<int, int>
using namespace std;
const int N = 4e3+10;
int n, m, len, vis[N][N];
int snxt[N][2], tnxt[N][2];
char s[N], t[N], ans[N]; 
Pair pre[N][N];
auto bfs() -> void;
auto print() -> void;
auto prework() -> void;
int main()
{
    freopen("str.in", "r", stdin);
    freopen("str.out", "w", stdout);
    scanf("%d%d", &n, &m);
    scanf("%s%s", s+1, t+1);
    prework(); bfs(); print();
    return 0;
}
auto prework() -> void
{
    for(int i = 0; i <= n; i += 1)
    {
        int pos = i+1;
        while(pos <= n and s[pos] != '0') pos += 1;
        snxt[i][0] = pos;
        pos = i+1;
        while(pos <= n and s[pos] != '1') pos += 1;
        snxt[i][1] = pos;
    }
    for(int i = 0; i <= m; i += 1)
    {
        int pos = i+1;
        while(pos <= m and t[pos] != '0') pos += 1;
        tnxt[i][0] = pos;
        pos = i+1;
        while(pos <= m and t[pos] != '1') pos += 1;
        tnxt[i][1] = pos;
    }
    snxt[n+1][0] = snxt[n+1][1] = n+1;
    tnxt[m+1][0] = tnxt[m+1][1] = m+1;
}
auto bfs() -> void
{
    queue<Pair> q; q.push({0, 0}); 
    int x, y, nx, ny; 
    vis[0][0] = 1;
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second; q.pop();
        if(x == n+1 and y == m+1) return;
        nx = snxt[x][0]; ny = tnxt[y][0];
        if(!vis[nx][ny])
        {
            vis[nx][ny] = 1;
            pre[nx][ny] = {x, y};
            q.push({nx, ny});
        }
        nx = snxt[x][1]; ny = tnxt[y][1];
        if(!vis[nx][ny])
        {
            vis[nx][ny] = 1;
            pre[nx][ny] = {x, y};
            q.push({nx, ny});
        }
    }
    
}
auto print() -> void
{
    int x = n+1, y = m+1, nx, ny;
    while(x and y)
    {
        nx = pre[x][y].first;
        ny = pre[x][y].second;
        if(snxt[nx][0] == x and tnxt[ny][0] == y)
            ans[++len] = '0', x = nx, y = ny;
        if(snxt[nx][1] == x and tnxt[ny][1] == y)
            ans[++len] = '1', x = nx, y = ny;
    }
    for(int i = len; i >= 1; i -= 1)
        printf("%c", ans[i]);
}

# 树上深搜

# 题目描述

有份 DFS 代码：

void dfs(int u)
{
	vis[u] = true;
	for (int v = 1; v <= n; v++)
		if (g[u][v] == true && vis[v] == false)
			dfs(v), link(u, v);
}

这个代码表示对一个点数为 nn 的无向连通图进行遍历。
其中 g[u][v]g[u][v] 是一个布尔数组，如果图有边(u,v)(u,v), 则g[u][v]=g[v][u]=1g[u][v] = g[v][u] = 1，否则 g[u][v]=g[v][u]=0g[u][v] = g[v][u] = 0。图没有自环。
link(x,y)link(x,y) 表示在另一个点数为 nn 的图 TT 上连边 (x,y)(x,y)。注意，初始时 TT 中只有 nn 个点而没有任何边。容易得到，执行 dfs(1)dfs(1) 之后 TT 将会是一棵树。

​求对于给定的树 TT ，有多少个没有重边和自环的无向连通图 % G% 满足对 GG 执行 dfs(1)dfs(1) 之后得到的树 TT 与给定的树完全一样？

​两个图完全一样，当且仅当这两个图的节点数相同并且对于第一个图的任意一条边 (u,v)(u,v) ，第二个图中都有边 (u,v)(u,v) 存在。

# 解题思路

一定有的边是原树边，一条非树边要么不能加，要么加不加都可以，而且能加的非树边互不影响，因为一定不会遍历到。所以答案是 2cnt2^{cnt}，cntcnt 为可以加的非树边的数量。
一条非树边 (u,fa(v))(u,fa(v)) 可以连的条件为 vv 为 uu 的祖先，vv 的权值 小于 uu。所以直接在 dfs 的时候用树状数组统计路径上权值的前缀和即可。

# Code

#include<iostream>
#include<cstdio>
#define lowbit(i) (i&-i)
using namespace std;
typedef long long ll;
const int N = 2e5+10;
const int mod = 1e9+7;
struct edge{
    int from, to;
    int next;
}a[N<<1];
int n, tr[N];
int head[N], cnt; ll sum;
auto query(int x) -> int;
auto ksm(ll a, ll b) -> ll;
auto add(int x, int k) -> void;
auto dfs(int x, int fa) -> void;
auto add_edge(int from, int to) -> void;
int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1, x, y; i < n; i += 1)
    {
        scanf("%d%d", &x, &y);
        add_edge(x, y);
        add_edge(y, x);
    }
    dfs(1, 0);
    printf("%lld", ksm(2, sum+1));
    return 0;
}
auto dfs(int x, int fa) -> void
{
    add(x, 1); sum += query(x-1)-1;
    for(int i = head[x], y; i; i = a[i].next)
    {
        if((y = a[i].to) == fa) continue;
        dfs(y, x);
    }
    add(x, -1);
}
auto add(int x, int k) -> void
{
    for(; x <= n; x += lowbit(x))
        tr[x] += k;
}
auto query(int x) -> int
{
    int ans = 0;
    for(; x; x -= lowbit(x))
        ans += tr[x];
    return ans;
}
auto add_edge(int from, int to) -> void
{
    cnt += 1;
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].next = head[from];
    head[from] = cnt;
}
auto ksm(ll a, ll b) -> ll
{
    ll ans = 1;
    for(; b; (a *= a) %= mod, b >>= 1)
        if(b&1) (ans *= a) %= mod;
    return ans;
}