专栏文章

Atcoder ABC 399

ccompaq
题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mipr84ab
此快照首次捕获于
2025/12/03 16:37
3 个月前
此快照最后确认于
2025/12/03 16:37
3 个月前
查看原文
C - Make it Forest
删除最少的边，使得简单图转为森林
用并查集维护，生成没有环的森林需要的边数ansans，总边数m−ansm - ans即为答案。
CPP
#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)有多少对，使得原本互不相邻的两个aa，原本互不相邻的两个bb， 这四个数可以通过交换位置后，两个aa相邻，两个bb相邻。
首先可以明确，只有相邻的一对数，才有可能成为答案，若后面的某对相邻的数(不分数值大小先后)，在前面出现过，则这四个数通过互换肯定能完成相邻。 还有一个前提是，选出的这对数(a,b)(a,b), 最初需要满足aa与aa不相邻，b与$$b不相邻.
记录每个数出现的第一个位置和第二个位置， 记为p[x][1],p[x][2]p[x][1], p[x][2]
对于第ii个位置和第i+1i+1个位置上的数a[i]a[i]和a[i+1]a[i+1]，需要以下条件：
  • p[a[i]][1]=i,p[a[i+1]][1]=i+1p[a[i]][1] = i, p[a[i+1]][1] = i + 1 ，第一次出现额位置需要相邻
  • p[a[i+1]][2]!=i+2p[a[i + 1]][2] != i + 2， a[i+1][2]a[i + 1][2]不能出现在i+2i+2的位置
  • abs(p[a[i]][2]−p[a[i+1]][2])==1abs(p[a[i]][2] - p[a[i + 1]][2]) == 1, 第二次出现的位置也需相邻
CPP
#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
给出两个小写字母构成的字符串SS和TT, 选择两个小写的英文字符x,yx,y, 将 SS中所有次出现的 xx 替换为 yy
考虑无解的情况：
  1. 如果一个字符需要变成两种或者两种以上的字符，则无解
  2. 如果TT中出现了所有的小写字母，则SS与TT必须相等
有解的情况：
建立S[i]S[i]到T[i]T[i]的有向边，若s[i]==T[i]s[i] == T[i]， 不需要考虑，即不考虑自环，因为已经完成转换。
若这条边已经出现过，则不需要考虑重边。一部分答案就是边的数量的贡献。还有一部分比较特殊。
若这个子图构成纯环，则需要多转换一次（将其中某个字符先转为其他不在环上的字符）。
具体实现：
从入度为00的点开始出发遍历图，能走到的点即是需要转换过程。将遍历到的点都作为标记。
最后未被遍历到的点则为环上，有多少个环，即为多出来的贡献。
USACO出过几乎一模一样的题面，洛谷上P9013 [USACO23JAN] Find and Replace S
CPP
#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;
}

评论

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

正在加载评论...