目录

  1. 题目一
    1. 题目描述
    2. 分析
  2. 题目二
    1. 题目描述
    2. 输入描述
    3. 输出描述
    4. 分析

题目一

题目描述

求最大非递减子序列。

分析

直接用动态规划求解会超时，所以得用到贪心+二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int biSearch(const vector<int>& a, int w) {
    int l = 0;
    int r = a.size() - 1;
    while (l <= r) {
        mid = (left + right) / 2;
        if (a[mid] > w)
            right = mid - 1;
        else if (a[mid] < w)
            left = mid + 1;
        else
            return mid;
    }
    return left;
}

int getRes(const vector<int>& num) {
    vector<int> dp(num.size());
    int res = 1;
    dp[0] = num[0];
    int pos = 0;
    for (int i = 1; i < num.size(); ++i) {
        // 如果大于等于dp中最大元素，则直接插入到dp末尾
        if (num[i] >= dp[res - 1]) {
            dp[res++] = num[i];
        }
        else {
            pos = biSearch(dp, num[i]); // 否则进行二分查找，插入到dp数组中，覆盖掉之前的值。
            dp[pos] = num[i];
        }
    }
    return res;
}

int main() {
    int n;
    while (cin >> n) {
        vector<int> num(n);
        for (int i = 0; i < n; ++i) {
            cin >> num[i];
        }
        cout << getRes(num) << endl;
    }
    return 0;
}

题目二

题目描述

某学术会议上，一共有n个人参加，现在已知每个人会的语言（一个人可能不会任何语言）。现在有一种学习机，每一个学习机可以在会议期间使一个人暂时掌握一种自己不会的语言，问要使得任意两人都能直接或间接的交流，至少准备多少个学习机？
间接交流的意思是：可以通过其他参加会议的人翻译（可能会出现很多人一起帮忙翻译的情况）进行交流。如第一个人和第二个人会第一种语言，第二个人和第三个人会第二种语言，那么第一个人可以和第三个人进行交流。

输入描述

第一行3个数n、m、k，代表人数、语言数、已知的信息数。接下来k行，每行两个数u，v，代表第u个人会第v种语言。

输出描述

输出需要准备的学习机的个数

分析

  • 考察并查集知识。即求图中连通团数减1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
void dfs(int idx, int res, vector<bool>& visited, vector<set<int> >& group, 
         const vector<vector<int> >& vp, const vector<vector<int> >& vl) {
    visited[idx] = true;
    int len = vp[idx].size();
    for (int i = 0; i < len; ++i) {
        int lan = vp[idx][i];   // 第idx个人会的第i门语言lan
        group[res].insert(lan); // 在第res组中插入lan语言
        // 遍历所有会lan语言的所有人
        for (int j = 0; j < vl[lan].size(); ++j) {
            int p = vl[lan][j];
            if (visited[p] == 0)
                dfs(p, res, visited, group, vp, vl);
        }
    }
}


int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int> > vp(n+1); // 人->语言
    vector<vector<int> > vl(m+1); // 语言->人
    vector<bool> visited(n+1, false);  // 记录访问过的人
    vector<set<int> > group(n+1); // 记录连通域内的语言  
    int res = 0;
    for (int i = 0; i < k; ++i) {
        int t1, t2;
        cin >> t1 >> t2;
        vp[t1].push_back(t2);
        vl[t2].push_back(t1);
    }
    
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs(i, res, visited, group, vp, vl);
            ++res;
        }
    }
    
    for (int i = 0; i < res; ++i) {
        if (group[i].size() == 0)
            ++cnt;
    }
    if (cnt == res)
        ++res;
        
    cout << res - 1 << endl;
    return 0;
}