Atcoder ABC 399

· · 题解

C - Make it Forest

删除最少的边，使得简单图转为森林

用并查集维护，生成没有环的森林需要的边数ans，总边数m - ans即为答案。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
struct edge{
    int u, v;
};
edge e[N];
int n, m;
int fa[N];

int find(int x){
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= m;i++)
        cin >> e[i].u >> e[i].v;

    for(int i = 1; i <= n;i++)
        fa[i] = i;

    int ans = 0;
    for(int i = 1; i <= m; i++){
        int u = e[i].u, v = e[i].v;
        u = find(u), v = find(v);
        if(u == v)
            continue;   
        ans ++;
        fa[v] = u;
    }
    cout << m - ans;
    return 0;
}

D - Switch Seats

求满足条件的(a,b)有多少对，使得原本互不相邻的两个a，原本互不相邻的两个b， 这四个数可以通过交换位置后，两个a相邻，两个b相邻。

首先可以明确，只有相邻的一对数，才有可能成为答案，若后面的某对相邻的数(不分数值大小先后)，在前面出现过，则这四个数通过互换肯定能完成相邻。 还有一个前提是，选出的这对数(a,b), 最初需要满足a与a不相邻，b与b不相邻.

记录每个数出现的第一个位置和第二个位置， 记为p[x][1], p[x][2]

对于第i个位置和第i+1个位置上的数a[i]和a[i+1]，需要以下条件：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 4e5 + 17;
int t, n;
int a[N], p[N][3];

signed main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) p[i][1] = p[i][2] = 0;
        for (int i = 1; i <= 2 * n; i++) {
            cin >> a[i];
            if (!p[a[i]][1]) p[a[i]][1] = i;
            else p[a[i]][2] = i;
        }
        set<pair<int, int> > se;
        for (int i = 1; i < 2 * n; i++) {
            if(p[a[i]][1] == i && p[a[i + 1]][1] == i + 1 && 
               p[a[i + 1]][2] != i + 2 && abs(p[a[i]][2] - p[a[i + 1]][2]) == 1){
                se.insert({min(a[i], a[i+1]), max(a[i], a[i+1])});
            }
        }
       // for(auto x: se) 
       //   cout << x.first << ' ' << x.second << endl;
        cout << se.size() << "\n";
    }
    return 0;
}

E - Replace

给出两个小写字母构成的字符串S和T, 选择两个小写的英文字符x,y, 将 S中所有次出现的 x 替换为 y

考虑无解的情况：

  1. 如果一个字符需要变成两种或者两种以上的字符，则无解
  2. 如果T中出现了所有的小写字母，则S与T必须相等

有解的情况：

建立S[i]到T[i]的有向边，若s[i] == T[i]， 不需要考虑，即不考虑自环，因为已经完成转换。

若这条边已经出现过，则不需要考虑重边。一部分答案就是边的数量的贡献。还有一部分比较特殊。

若这个子图构成纯环，则需要多转换一次（将其中某个字符先转为其他不在环上的字符）。

具体实现：

从入度为0的点开始出发遍历图，能走到的点即是需要转换过程。将遍历到的点都作为标记。

最后未被遍历到的点则为环上，有多少个环，即为多出来的贡献。

USACO出过几乎一模一样的题面，洛谷上P9013 [USACO23JAN] Find and Replace S

#include<bits/stdc++.h>
using namespace std;
int n, to[300], ans, in[300];
string s,t;
set<int>m;
bool vis[300];
void tope(){//将所有非纯环标记掉 即从入度为0的点出发 把能到达的所有点标记掉
    queue<int>q;
    for(int i = 'a'; i <= 'z'; i++)
        if(!in[i] && to[i])//当然得有后继结点才能扩展
            vis[i] = true, q.push(i);
    while(!q.empty()){
        int u = q.front(); q.pop();
        if(!vis[to[u]]) vis[to[u]] = true, q.push(to[u]); 
    }
}

void dfs(int u){
    vis[u] = true;
    if(!vis[to[u]]) dfs(to[u]);
}
int main(){
    scanf("%d", &n);
    cin >> s >> t;
    bool flag = true;
    for(int i = 0; i < n; i++){
        if(!to[s[i]] || to[s[i]] == t[i])
            to[s[i]] = t[i];
        else flag = false;
        m.insert(t[i]);
    }
    if(flag == false){ // 第一种无解 
        printf("-1");
        return 0;
    }
    if(m.size() == 26&& s != t){// 第二种无解 
        printf("-1");
        return 0;
    }
    memset(to, 0, sizeof(to));
    for(int i = 0; i < n; i++){//建边同时统计边的个数 答案个数等于边的个数加纯环的个数
        if(!to[s[i]] && s[i] != t[i]){//重边和自环不管
            ans++;
            to[s[i]] = t[i];
            in[t[i]]++;//统计入度 为删点做准备
        }
    }
    tope();
    for(int i = 'a'; i <= 'z'; i++){//未被标记且有后继结点的点 一定在纯环内
        if(!vis[i] && to[i]){
            ans++;
            dfs(i);//将这个环内所有点标记掉 避免重复计算
        }
    }
    printf("%d", ans);
    return 0;
}