ZZULI (2022河南萌新联赛 四)
2022/7/31 23:43:50
本文主要是介绍ZZULI (2022河南萌新联赛 四),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
分析
读题不认真这个毛病什么时候能改? 我竟然看成最长上升子序列问题了, 而且还把代码写好.......(其实就算看出来是并查集, 我也不会写qwq)赛后借鉴大佬代码, 收获很大
以后看到连通块这个词, 就往并查集的方向想
AC代码
#include <iostream> #include <cstring> using namespace std; const int N = 1000010; int fa[N], sz[N], c[300]; char s[N]; int d[5]; // ***** 表示 Z, U, L, I所代表的连通块的祖宗节点 在 s 数组里的下标 // 并查集 int find(int x) { if(fa[x] != x) fa[x] = find(fa[x]); return fa[x]; } // 合并两个连通块 void merge(int a, int b) { int x = find(a), y = find(b); if(x == y) return ; sz[y] += sz[x]; fa[x] = y; } int main() { scanf("%s", s+1); //字符串长度 int L = strlen(s + 1); // 并查集初始化 for(int i = 1; i <= N; i ++) fa[i] = i, sz[i] = 1; // **** 将字母和数字对应起来, 方便枚举 c['Z'] = 0; c['U'] = 1; c['L'] = 2; c['I'] = 3; // 变量全部字符串 for(int i = 1; i <= L; i ++) { if(s[i] == 'Z' || s[i] == 'U' || s[i] == 'L' || s[i] == 'I') { // k 代表目前找到的字符串是哪一个 0, 1, 2, 3 int k = c[s[i]]; // 如果前面已近已经有和s[i]相同的字符串, 则合并两个连通块 if(d[k]) merge(d[k], i); // d[k] 表示原先那个字符的下标 else d[k] = i; // 依次合并 连通块 for(int j = 0; j < k; j ++) { if(d[j]) merge(d[j], i); } } } int res = 0; for(int i = 1; i <= L; i ++) res = max(res, sz[i]); cout << res << endl; return 0; }
这篇关于ZZULI (2022河南萌新联赛 四)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行
- 2024-05-08阿里云域名注册流程,分享给第一次购买域名的新手站长!