L2-4 部落 在一個社區里，每個人都有自己的小圈子，還可能同時屬於很多不同的朋友圈。我們認為朋友的朋友都算在一個部落里，於是要請你統計一下，在一個給定社區中，到底有多少個互不相交的部落？並且檢查任意兩個人是否屬於同一個部落。 輸入格式： 輸入在第一行給出一個正整數N（≤1e4），是已知小圈子的個數 ...
目錄
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煩人的依賴
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校車
西安郵電大學有一輛從老校區到新校區的校車，總共有 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
思路
題解
