Unsolved --> Solved OJ思路題解

来源:https://www.cnblogs.com/Delta2019/archive/2020/05/30/12995698.html
-Advertisement-
Play Games

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煩人的依賴

鏈接：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

思路

題解

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • position: sticky實現導航欄下滑吸頂效果
    摘要 近期開發中遇到導航欄下滑吸頂的需求，經過方案調研，發現position：sticky可以簡單快捷的實現功能。sticky（粘貼定位）可以被認為是相對定位和固定定位的混合，元素在跨越特定閥值前為相對定位，之後為固定定位。根據sticky的特性，只需要添加簡單的幾行CSS樣式代碼即可實現導航欄吸頂 ...
  • 用node寫個爬蟲？看完這篇新手也會
    從node問世以後，就不斷被JavaScript的忠實追隨者拿來乾一些原來只有php、Python等後端語言才能幹的事情，例如寫個爬蟲之類的。對於前端er來說，用上一些好用的輪子，你可能十幾行代碼就可以寫一個crawler哦~ 爬蟲的思路十分簡單: 按照一定的規律發送 HTTP 請求獲得頁面 HTM ...
  • Nginx 一個牛 X 的功能，流量拷貝！
    1. 需求 將生產環境的流量拷貝到預上線環境或測試環境，這樣做有很多好處，比如： 可以驗證功能是否正常，以及服務的性能； 用真實有效的流量請求去驗證，又不用造數據，不影響線上正常訪問； 這跟灰度發佈還不太一樣，鏡像流量不會影響真實流量； 可以用來排查線上問題； 重構，假如服務做了重構，這也是一種測試 ...
  • 門外漢學習前端開發有前途嗎？現在前端開發行情怎麼樣？
    對於學習前端開發有前途嗎？行情怎麼樣，好就業嗎?這樣的問題相信都看了很多很多，每個人的回答都有些差別。但是唯一的一點肯定的，學習前端的前景是很不錯的。 接下來，小編來跟大家分享一下2020年Web前端的發展趨勢如何?熟悉web的小伙伴們都瞭解，自2018年是前端技術的發展相對穩定的一年，就前端主流技 ...
  • css：chorm調試工具（修改樣式、重置縮放比例、錯誤提示）
    1、打開方式 打開Chrome瀏覽器，按下F12或者右擊空白處然後點擊檢查 最左邊是顯示效果，中間是html代碼，右邊是html樣式。 2、樣式的修改 點擊中間代碼框，左上角的小箭頭，然後點擊css樣式，可以直接修改屬性的值。也可以點擊鍵盤上的上下箭頭，對屬性的值進行修改 需要註意的是，調試工具只是 ...
  • 咕泡三期 Java高級開發 java進階大型互聯網架構師專題
    咕泡三期 Java高級開發|java進階大型互聯網架構師專題 微雲鏈接：鏈接：https://share.weiyun.com/4Ruecunx 密碼：m4xy7s 百度網盤：鏈接: https://pan.baidu.com/s/1UBSJaWNobkTmZ7uTGVMRQg 密碼: 1bpw 如 ...
  • 單例模式，反射破環？
    餓漢式 // 餓漢式單例 public class Hungry { //構造器私有 private Hungry(){ } // 一上來就把這個類載入了 private final static Hungry HUNGRY = new Hungry(); public static Hungry ...
  • PythonのTkinter基本原理 - 小白篇
    本文講解，Python Tkinter 庫，的基本原理，白話講解，面向小白。 Tkinter 是什麼： Tkinter 是 Python 自帶的一個，標準庫，用於快速創造，簡單的 GUI 程式。 為什麼要瞭解 Tkinter： 首先，因為這個庫，是 Python 自帶的，所以非常方便，隨叫隨到的那種 ...
一周排行
    -Advertisement-
    Play Games
  • UOS 開啟 VisualStudio 遠程調試 .NET 應用之旅
    前言 在我們開發過程中基本上不可或缺的用到一些敏感機密數據，比如SQL伺服器的連接串或者是OAuth2的Secret等，這些敏感數據在代碼中是不太安全的，我們不應該在源代碼中存儲密碼和其他的敏感數據，一種推薦的方式是通過Asp.Net Core的機密管理器。 機密管理器 在 ASP.NET Core ...
  • C# - 能否讓 SortedSet.RemoveWhere 內傳入的委托非同步執行
    新改進提供的Taurus Rpc 功能，可以簡化微服務間的調用，同時可以不用再手動輸出模塊名稱，或調用路徑，包括負載均衡，這一切，由框架實現並提供了。新的Taurus Rpc 功能，將使得服務間的調用，更加輕鬆、簡約、高效。 ...
  • 順序棧的介面程式
    順序棧的介面程式 目錄順序棧的介面程式頭文件創建順序棧入棧出棧利用棧將10進位轉16進位數驗證 頭文件 #include <stdio.h> #include <stdbool.h> #include <stdlib.h> 創建順序棧 // 指的是順序棧中的元素的數據類型，用戶可以根據需要進行修改 ...
  • mORMot2 獲取數據集1
    前言 整理這個官方翻譯的系列，原因是網上大部分的 tomcat 版本比較舊，此版本為 v11 最新的版本。 開源項目 從零手寫實現 tomcat minicat 別稱【嗅虎】心有猛虎，輕嗅薔薇。 系列文章 web server apache tomcat11-01-官方文檔入門介紹 web serv ...
  • 萬字長文總結與剖析C語言關鍵字 -- <<C語言深度解剖>>
    C總結與剖析:關鍵字篇 -- <<C語言深度解剖>> 目錄C總結與剖析:關鍵字篇 -- <<C語言深度解剖>>程式的本質:二進位文件變數1.變數:記憶體上的某個位置開闢的空間2.變數的初始化3.為什麼要有變數4.局部變數與全局變數5.變數的大小由類型決定6.任何一個變數,記憶體賦值都是從低地址開始往高地 ...
  • 【Flink入門修煉】2-3 Flink Checkpoint 原理機制
    如果讓你來做一個有狀態流式應用的故障恢復，你會如何來做呢？ 單機和多機會遇到什麼不同的問題？ Flink Checkpoint 是做什麼用的？原理是什麼？ ...
  • C++ 多級繼承與多重繼承：代碼組織與靈活性的平衡
    C++ 多級繼承 多級繼承是一種面向對象編程（OOP）特性，允許一個類從多個基類繼承屬性和方法。它使代碼更易於組織和維護，並促進代碼重用。 多級繼承的語法 在 C++ 中，使用 : 符號來指定繼承關係。多級繼承的語法如下： class DerivedClass : public BaseClass1 ...
  • 圖文結合手把手教你創建SpringCloud項目
    前言 什麼是SpringCloud？ Spring Cloud 是一系列框架的有序集合，它利用 Spring Boot 的開發便利性簡化了分散式系統的開發，比如服務註冊、服務發現、網關、路由、鏈路追蹤等。Spring Cloud 並不是重覆造輪子，而是將市面上開發得比較好的模塊集成進去，進行封裝，從 ...
  • 類模板的常見用法
    class_template 類模板和函數模板的定義和使用類似，我們已經進行了介紹。有時，有兩個或多個類，其功能是相同的，僅僅是數據類型不同。類模板用於實現類所需數據的類型參數化 template<class NameType, class AgeType> class Person { publi ...
  • system-v IPC共用記憶體通信
    目錄system v IPC簡介共用記憶體需要用到的函數介面shmget函數--獲取對象IDshmat函數--獲得映射空間shmctl函數--釋放資源共用記憶體實現思路註意 system v IPC簡介 消息隊列、共用記憶體和信號量統稱為system v IPC(進程間通信機制)，V是羅馬數字5，是UNI ...
所有分類