2022-10-20总结

最短子列

Description

对于一个字符串 $S=S_1S_2\dots S_n$ ，定义它的一个子序列是任意满足 $1 \le i_1 < i_2 < \dots < i_k \le n$ 的字符串 $S_{i_1}S_{i_2} \dots S_{i_k}$ 。字符串 $S$ 的非子序列即不是 $S$ 的子序列的字符串。

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

这里 $S,Y$ 仅由 $0$ 和 $1$ 构成。现在请你求出字典序最小的最短公共非子序列。

Input

第一行两个正整数 $n, m$ ，表示两个字符串 $S,T$ 的长度。

第二行一个长度为 $n$ 的、仅由 $0,1$ 组成的字符串 $S$ ，表示第一个字符串。

第三行一个长度为 $m$ 的、仅由 $0,1$ 组成的字符串 $T$ ，表示第二个字符串。

Output

输出一行一个字符串，表示字典序最小的最短公共非子序列。

HINT

$1 \le n,m \le 4000$

Solution

考虑子序列的匹配过程，设当前子序列匹配到 $i$ , 若添加一个字符，则下一步应匹配到 $i$ 后面的第一个这个字符，如果没有则代表是非子序列。

然后就可以 DP 了，然而我直接建边跑了个 bfs, 本质上是一样的.

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("str.in", "r", stdin);
        freopen("str.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

#define int short

struct pir { int x, y; };
const int N = 4005;

int n, m;
pir pre[N][N];
int ver1[N][2];
int ver2[N][2];
bool vis[N][N];
char s[N], type[N];

void prework(char *s, int n, int ver[N][2]);
void bfs();
void print(int x, int y);

signed main()
{
    cin >> n >> m;
    cin >> (s+1) >> (type+1);
    prework(s, n, ver1);
    prework(type, m, ver2);
    bfs();
    print(n+1, m+1);
}

void bfs()
{
    queue<pair<int,int>> q;
    q.push({0, 0});
    vis[0][0] = true;
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if(x == n+1 and y == m+1)
            return void();
        for(int i = 0; i <= 1; i++)
        {
            int nx = ver1[x][i], ny = ver2[y][i];
            if(!vis[nx][ny])
            {
                q.push({nx, ny});
                vis[nx][ny] = true;
                pre[nx][ny] = {x, y};
            }
        }
    }
}
void prework(char *s, int n, int ver[N][2])
{
    for(int i = 0; i <= n+1; i++)
    {
        ver[i][0] = ver[i][1] = n+1;
        for(int j = i+1; j <= n; j++)
            if(s[j] == '0'){ ver[i][0] = j; break; }
        for(int j = i+1; j <= n; j++)
            if(s[j] == '1'){ ver[i][1] = j; break; }
    }
}
void print(int x, int y)
{
    if(x == 0 and y == 0) return;
    int px = pre[x][y].x;
    int py = pre[x][y].y;
    print(px, py);
    if(x == ver1[px][0] and y == ver2[py][0])
        cout << 0;
    else
        cout << 1;
}

树上深搜

Description

有份 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);
}

这个代码表示对一个点数为 $n$ 的无向连通图进行遍历。

其中 g[][] 是一个布尔数组，如果图有边 $(x,y)$ 则 g[x][y]=g[y][x]=true，否则 g[x][y]=g[y][x]=false 。特别地，对于任意的 $1 \le x \le n$ 都有 g[x][x]=false。

link(x,y) 表示在另一个点数为 $n$ 的图 $T$ 上连边。注意，初始时 $T$ 中只有 $n$ 个点而没有任何边。容易得到，执行 dfs(1) 之后 $T$ 将会是一棵树。

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

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

Input

第一行一个正整数 $n$ ，表示树 $T$ 的点数，也是无向连通图的点数。

接下来的 $n-1$ 行，每行两个正整数 $x,y$ ，表示树 $T$ 上有边 $(x,y)$ 。

Output

输出一个整数表示答案。由于答案可能很大，你只要输出其对 $10^9+7$ 取模后的结果。

HINT

$n \le 2 \times 10^5$

Solution

考虑哪些边连不连无影响，对于一个节点 $x$ ，如果 $x$ 的祖先中有比 $x$ 编号小的节点 $y$ ，则 $(x,fa_y)$ 这条边可连可不连，问题就变成了统计一个点的祖先中有多少点比它编号小，因为 $1$ 号点没有父节点所以 $1$ 不能算上，这个可以 dfs 时维护一个 bit 实现。

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("dfs.in", "r", stdin);
        freopen("dfs.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

typedef long long ll;
const int N = 2e5+10;
const int P = 1e9+7;

struct bit_array {
    #define lowbit(i) (i&-i)
    int a[N], lim;
    void add(int pos, int val)
    {
        for(; pos <= lim; pos += lowbit(pos))
            a[pos] += val;
    }
    int query(int pos)
    {
        int ans = 0;
        for(; pos >= 1; pos -= lowbit(pos))
            ans += a[pos];
        return ans;
    }
} bit;

int n; ll ans;
vector<int> ver[N];

ll qpow(ll a, ll b);
void dfs(int x, int fa);

int main()
{
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int x, y; cin >> x >> y;
        ver[x].push_back(y);
        ver[y].push_back(x);
    }
    bit.lim = n;
    dfs(1, 1919810);
    ans -= n-1;
    ans = qpow(2, ans);
    cout << ans << "\n";
}


void dfs(int x, int fa)
{
    ans += bit.query(x);
    bit.add(x, 1);
    for(auto y : ver[x])
        if(y != fa) dfs(y, x);
    bit.add(x, -1);
}

ll qpow(ll a, ll b)
{
    ll ans = 1;
    for(; b; b >>= 1, a = a*a%P)
        if(b&1) ans = ans*a%P;
    return ans;
}

五彩斑斓

Description

小 L 想要粉刷一块 $n \times m$ 的木板，现在他手上有 $c$ 桶不同颜色的油漆。

小 L 是一个很怕麻烦的人，他每次只会粉刷完整的一行或一列，并且他希望粉刷的次数尽量少。

现在给你小 L 的粉刷方案，即粉刷完成之后，每个小方格应该是什么颜色的。

请你给出一个粉刷方案，使得粉刷次数最少。

当然，也可能不存在任何合法方案，这时请你告诉小 L 他的设计不合法。

Input

输入的第一行包含三个整数 $n, m, c$ ，含义如题所示。

接下来的 $n$ 行，每行包含 $m$ 个整数。令第 $i$ 行的第 $j$ 个数字为 $col_{i,j}$ ，满足 $0 \le col_{i,j} \le c$ 。如果 $col_{i,j}=0$ ，则说明格子 $(i,j)$ 不应该被粉刷，否则说明格子 $(i,j)$ 应该被粉刷成颜色 $col_{i,j}$ 。

Output

如果不存在合法方案，仅输出一行，包含一个整数 $-1$ 。

否则，输出的第一行包含一个整数 $t$ ，表示最少的粉刷次数。

接下来的 $t$ 行，按照顺序输出 $t$ 次粉刷操作。第 $i$ 行描述第 $i$ 次操作，包括空格隔开的一个字符 $opt_i$ 以及两个数字 $num_i$ 和 $col_i$ 。

$opt_i$ 为 R 或 C，分别代表粉刷一行或者一列。
$num_i$ 为粉刷的列或行的编号。
$col_i$ 为粉刷的颜色。

如果存在多种合法且操作次数最少的方案，输出任意一种即可。

HINT

$1 \le n,m \le 50, \, c\le 100$

评分程序将对选手输出按照如下标准评分：

如果不存在输出文件，或者输出不符合规范，得分。
如果最少的粉刷次数不正确，且方案不合法，得分。
如果最少的粉刷次数不正确，但方案合法，可以获得的分数。
如果最少的粉刷次数正确，但方案不合法，可以获得的分数。
如果最少的粉刷次数正确，且方案合法，可以获得的分数。

这里方案合法是指方案行数等于，且按照方案粉刷可以得到给定的设计。

注意获得的分数的条件是方案格式正确，即按要求输出行。当然这个操作可以完全乱来，不过还是得符合操作的格式。

Solution

首先粉刷次数的上界是 $n+m-1$ ，因为如果刷了 $n+m$ 次的话，第一次刷的颜色会全部被覆盖掉，那么第一次的操作就没用了。

这样的话我们知道至少有一行或者一列没有粉刷颜色，那么我们就枚举没有刷颜色的这一行 (列的话把矩阵转置一下就行)，因为这一行没有刷颜色，所以可以通过这一行唯一确定每一列刷的颜色，然后就可以确定一些行刷的颜色和刷的顺序了(确定不了的视为没刷颜色就行)。方案的话用拓扑排序处理一遍就行了。

#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("iridescent.in", "r", stdin);
        freopen("iridescent.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

const int N = 105;

bool flag;
int n, m, c;
int deg[N], ci[N], cj[N];
int col[N][N], tmp[N][N];
int type;

struct point {
    int col, id, opt;
    point(int col, int id, int opt):
        col(col), id(id), opt(opt) {}
};

vector<point> ans, now;
vector<int> ver[N];

void check(int id);
void toposort();

int main()
{
    cin >> n >> m >> c;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> col[i][j];
    
    type = 0;
    for(int i = 1; i <= n; ++i)
        check(i);
    
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            tmp[j][i] = col[i][j];
    swap(n, m);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)    
            col[i][j] = tmp[i][j];
    
	type = 1;
    for(int i = 1; i <= n; ++i)
        check(i);
    
    if(!flag)
        cout << "-1";
    else 
    {
        cout << ans.size() << "\n";
        for(int i = 0, im = ans.size(); i < im; ++i)
        {
            cout << (ans[i].opt == 0 ? 'R' : 'C') << " ";
            cout << ans[i].id << " " << ans[i].col << "\n";
        }
    } 
}

void check(int id)
{
    for(int j = 1; j <= m; ++j)
        cj[j] = col[id][j];
    for(int i = 1; i <= n; ++i)
        ci[i] = -1;
    ci[id] = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(id == i) continue;
        for(int j = 1; j <= m; ++j)
            if(col[i][j] != cj[j])
            {
                if(col[i][j] == 0) return void();
                if(ci[i] == -1) ci[i] = col[i][j];
                else if(ci[i] != col[i][j]) return void();
            }
        if(ci[i] == -1) ci[i] = 0;
    }
    
    for(int i = 1; i <= n+m; ++i)
        ver[i].clear(), deg[i] = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(!ci[i]) continue;
        for(int j = 1; j <= m; ++j)
            if(cj[j] and ci[i] != cj[j])
            {
                if(col[i][j] == ci[i])
                    ver[j+n].push_back(i), deg[i]++;
                else
                    ver[i].push_back(j+n), deg[j+n]++;
            }
    }
    
    toposort();
}


void toposort()
{
    now.clear();
    queue<int> q;
    for(int i = 1; i <= n; ++i)
        if(ci[i] > 0 and deg[i] == 0) q.push(i);
    for(int j = 1; j <= m; ++j)
        if(cj[j] > 0 and deg[j+n] == 0) q.push(j+n);
    
    while(!q.empty())
    {
        int x = q.front(); q.pop();
        
        if(x <= n)
            now.emplace_back(ci[x], x, type);
        else
            now.emplace_back(cj[x-n], x-n, type^1);
        
        for(auto y : ver[x])
            if(--deg[y] == 0) q.push(y);
                
    }
    
    for(int i = 1; i <= n+m; ++i)
        if(deg[i]) return void();
    
    if(!flag or now.size() < ans.size())
        ans = now, flag = true;
}