Unsolved --> Solved OJ思路题解
2020-05-30 16:01:13来源：博客园 阅读 ()
Unsolved --> Solved OJ思路题解
目录
- L2-4 部落
- 输入格式：
- 输出格式：
- 输入样例：
- 输出样例：
- 思路
- 并查集
- 题解
- L2-008. 最长对称子串
- 输入格式：
- 输出格式：
- 输入样例：
- 输出样例：
- 思路
- Manacher 算法
- 题解
- B烦人的依赖
- 输入描述:
- 思路
- 题解
- G校车
- 输入描述:
- 思路
- 题解
L2-4 部落
在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。
输入格式：
输入在第一行给出一个正整数N（≤1e4），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：
K P[1] P[2] ? P[K]
其中K是小圈子里的人数，P[i]（i=1,?,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过104。
之后一行给出一个非负整数Q（≤1e4），是查询次数。随后Q行，每行给出一对被查询的人的编号。
输出格式：
首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。
输入样例：
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7
输出样例：
10 2
Y
N
思路
运用 并查集 解决问题
并查集
在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：
Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。Union：将两个子集合并成同一个集合。
由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法，MakeSet，用于创建单元素集合。有了这些方法，许多经典的划分问题可以被解决.
通俗讲,并查集 能够判断判断两个角色在不在一个群组里面 .
const int N = 10010;
//初始化
int fa[N]; //每个结点
int Rank[N]; //树的高度/节点的秩
void MakeSet() //对n个结点初始化
{
for (int i = 0; i < N; i++)
{
fa[i] = i; //每个结点的上级都是自己
Rank[i] = 1; //每个结点构成的树的高度为1
}
}
//改进查找算法：完成路径压缩，将x的上级直接变为根结点，那么树的高度就会大大降低
int Find(int x) //查找结点x的根结点
{
if (fa[x] == x)
{ //递归出口：x的上级为x本身，即x为根结点
return x;
}
return fa[x] = Find(fa[x]); //递归查找 此代码相当于 先找到根结点rootx，然后pre[x]=rootx
}
//判断两个结点是否连通
bool Judge(int x, int y)
{
return Find(x) == Find(y); //判断两个结点的根结点（亦称代表元）是否相同
}
void Union(int x, int y)
{
x = Find(x);
y = Find(y);
if (x == y)
{
return;
}
if (Rank[x] > Rank[y])
{
fa[y] = x; //令y的根结点的上级为x
}
else
{
if (Rank[x] == Rank[y])
{
Rank[y]++;
}
fa[x] = y;
}
}
在算法竞赛的实际代码中，即便不使用启发式合并，代码也往往能够在规定时间内完成任务。因此我们一般情况下无需使用启发式合并（按秩合并）.
题解
C++中库函数大多为下划线命名法,因此自己的函数推荐驼峰命名法.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10010;
//并查集初始化
int fa[MAXN]; //无需按秩合并
void MakeSet()
{
for (int i = 0; i < MAXN; i++)
{
fa[i] = i;
}
}
//查找其父节点
int Find(int x)
{
if (fa[x] == x)
{
return x;
}
else
{
return fa[x] = Find(fa[x]);
}
}
//合并两个节点/集合
void Union(int x, int y)
{
x = Find(x);
y = Find(y);
if (x != y)
{
fa[x] = y;
}
}
//判断两个元素是否有相同的父节点
bool Judge(int x, int y)
{
return Find(x) == Find(y);
}
int main(void)
{
MakeSet();
set<int> member;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int input;
vector<int> temp;
int k;
cin >> k;
for (int j = 0; j < k; j++)
{
cin >> input;
temp.push_back(input);
member.insert(input);
}
for (auto &&j : temp)
{
Union(input, j);
}
temp.clear();
}
int count(0);
cout << member.size() << ' ';
for (auto &&i : member)
{
if (fa[i] == i)
{
count++;
}
}
cout << count << endl;
int k;
cin >> k;
for (int i = 0; i < k; i++)
{
int t1, t2;
cin >> t1 >> t2;
if (Judge(t1, t2))
{
cout << 'Y' << endl;
}
else
{
cout << 'N' << endl;
}
}
return 0;
}
L2-008. 最长对称子串
对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。
输入格式：
输入在一行中给出长度不超过1000的非空字符串。
输出格式：
在一行中输出最长对称子串的长度。
输入样例：
Is PAT&TAP symmetric?
输出样例：
11
思路
Manacher 算法
string Manacher(string ori_s)
{
string s = "#";
for (auto c : ori_s)
{
s += c;
s += "#";
}
int N = s.size(); //N 始终为奇数
vector<int> radius(N, 0); //radius(半径)为N个0
int C = 0;
int R = 0;
int max_center = -1;
int max_radius = 0;
for (int i = 0; i < N; ++i)
{
if (i < R)
{
radius[i] = min(R - i, radius[2 * C - i]);
}
while (i + radius[i] + 1 < N && i - radius[i] - 1 >= 0 &&
s[i + radius[i] + 1] == s[i - radius[i] - 1])
{
++radius[i];
}
if (radius[i] + i > R)
{
R = radius[i] + i;
C = i;
}
if (radius[i] > max_radius)
{
max_radius = radius[i];
max_center = i;
}
}
string res;
for (int i = -max_radius; i <= max_radius; ++i)
{
if (s[i + max_center] != '#')
{
res += s[i + max_center];
}
}
return res;
}
题解
然而我暂时还理解不了马拉车算法 , 所以我这里使用朴素算法给出题解
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string LongestPalindrome(string ori)
{
if (ori.empty())
{
return "";
}
string s;
for (auto &&i : ori)
{
s.push_back('#');
s.push_back(i);
}
s.push_back('#');
vector<int> p;
for (auto i = s.begin(); i != s.end(); i++)
{
int count(1);
for (auto front = i + 1;; front++)
{
auto back = i - (front - i);
if (distance(s.begin(), back) >= 0 && distance(front, s.end()) > 0 && *back == *front)
{
count++;
}
else
{
break;
}
}
p.push_back(count);
}
vector<int>::iterator result = max_element(p.begin(), p.end());
string temp;
int len = *result - 1;
for (auto i = s.begin() + distance(p.begin(), result) - len; i != s.begin() + distance(p.begin(), result) + len; i++)
{
if (*i != '#')
{
temp.push_back(*i);
}
}
return temp;
}
int main()
{
string str;
getline(cin, str);
cout << LongestPalindrome(str).size();
return 0;
}
B烦人的依赖
链接：https://ac.nowcoder.com/acm/contest/5678/B
来源：牛客网
Ubuntu20.04 正式发布了，ZLS 是一个作死小能手，于是他决定尝试一下这个船新版本。好不容易装完系统，ZLS 想要给他的系统装一些常用的软件。众所周知，在 Linux 装软件会遇到各种奇奇怪怪的依赖问题（所谓依赖问题就是若A依赖B，则B要先与A安装）。ZLS 对此不厌其烦，因此他想知道他要用什么顺序安装软件，可以一次安装成功呢?
Tips: ZLS 还有一个癖好，他喜欢先安装字典序小的软件。
输入描述:
第一行包含一个正整数 T 表示数据组数。
每组数据的第一行包 n 和 m， 表示有 n 个软件，m 个依赖关系。
接下来的一行包含 n 个软件名(软件名仅包含小写字母 a-z )
接下来的 m 行每行有两个软件名 s 和 t，表示 t 依赖 s ，即 s 要在 t 之前安装。
数据保证： 1≤T≤51 \le T \le 51≤T≤5
1≤n≤3×104,1≤m≤1051 \le n \le 3 \times 10^{4}, 1 \le m \le 10^{5}1≤n≤3×104,1≤m≤105
1≤∣s∣,∣t∣≤101 \le |s|,|t| \le 101≤∣s∣,∣t∣≤10
输出描述:
共 T 组输出，每组输出先输出一行 Case #%d: ，%d 替换为当前输出的组数。
接下来是 n 行，按照安装的顺序输出。
如果无法进行安装，输出 Impossible (注意大小写)。
示例1
输入
2
4 2
a b c d
a b
b c
3 3
a b c
a b
b c
c a
输出
Case #1:
a
b
c
d
Case #2:
Impossible
思路
软件的依赖关系可以看作一个有向图，而软件安装顺序就是求有向图的一个拓扑排序。注意题目中要求按照字典序排序，因此拓扑排序中要用优先队列。对于字符串的处理，可以先映射成整数，再做拓扑排序。
有的同学反映超时，可以试试看unordered_map，比map要少个log。
先去了解 浅显易懂的拓扑排序
题解
#include <bits/stdc++.h>
#define MAXN 30005
using namespace std;
string soft[MAXN]; // 存所有软件 , 软件名和下表index 一一对应
unordered_map<string, int> _index; // 一一对应 关系
vector<int> edge[MAXN]; // DAG的边, 存的是依赖于它的所有软件
int in_degree[MAXN]; //每一个软件的入度
void DAG_init(const int &n, const int &m)
{
_index.clear();
for (int i = 0; i < n; i++)
{
cin >> soft[i];
//每次进行初始化清空
in_degree[i] = 0;
edge[i].clear();
}
sort(soft, soft + n, greater<string>()); // 字典序排列
for (int i = 0; i < n; ++i)
_index[soft[i]] = i;
for (int i = 0; i < m; i++)
{
string a, b;
cin >> a >> b;
edge[_index[a]].push_back(_index[b]);
++in_degree[_index[b]];
}
}
void TopologicalSort(const int &n)
{
static int num = 0; // Case #%d:
priority_queue<int> q;
for (int i = 0; i < n; i++)
if (in_degree[i] == 0) // 入度=0,入队
q.push(i);
vector<int> ans;
while (!q.empty())
{
int now = q.top();
q.pop();
ans.push_back(now);
for (auto &&i : edge[now])
if (--in_degree[i] == 0)
q.push(i);
}
cout << "Case #" << ++num << ":\n";
if (ans.size() != n) //没有成环
{
cout << "Impossible" << endl;
return;
}
for (auto &&i : ans)
cout << soft[i] << endl;
}
int main(void)
{
ios::sync_with_stdio(0);
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
int n, m;
cin >> n >> m;
DAG_init(n, m);
TopologicalSort(n);
}
return 0;
}
G校车
链接：https://ac.nowcoder.com/acm/contest/5678/G
来源：牛客网
西安邮电大学有一辆从老校区到新校区的校车，总共有 n 个学生乘坐校车，在 aia_{i}ai 站上车，在 bib_{i}bi 站下车。学校打算去除一部分不必要的站点，请问需要保留多少站点，需要安排多少个座位？
输入描述:
输入 T 组数据 (1≤T≤10)(1 \le T \le 10)(1≤T≤10)
输入 n(1≤n≤105)n(1 \le n \le 10^{5})n(1≤n≤105)
输入 n 组 ai,bi(1≤ai，bi≤109)a_{i},b_{i}(1 \le a_{i}，b_{i} \le 10^{9})ai,bi(1≤ai，bi≤109)
输出描述:
输出保留站点数，座位数。
示例1
输入
1
3
1 2
1 3
2 4
输出
4 2
思路
题解
原文链接:https://www.cnblogs.com/Delta2019/p/12995698.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
上一篇：二叉搜索树_BST
下一篇：C++ 模板类array
- Building & Debugging chromium on CLion for Linu 2020-05-19
- 洛谷P1164->小A点菜 2020-05-18
- 表达式·表达式树·表达式求值 2020-04-29
- STL之<string> 2020-04-05
- 2019.3.14解题报告&补题报告 2020-03-22
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
