2.8 E

E - Cables and Servers

题目：

输入：一张无向图的边（每一条边连接两个节点）。

处理：通过并查集判断哪些边在加入后会形成环（即使图中仍然存在多个连通块）。

输出：输出一组边，这些边被删除后图变成一个树（没有环，且每个连通块只有一棵树）

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int n, m;
int e[N][2], fa[N];
set<int> s; // s集合，保存每个连通块的根节点
vector<int> d; // 存储已经形成环的边的编号
vector<int> u, v, w; // 存储删除的边的信息

int find(int x)
{
	if(fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];	
} 
signed main()
{
	cin >> n >> m;
	//初始化并查集
	for(int i = 1; i <= n; i++) fa[i] = i; 
	for(int i = 1; i <= m; i++)
	{
		cin >> e[i][0] >> e[i][1];//读入边的两个端点
		int x = find(e[i][0]), y = find(e[i][1]);
		if(x == y) d.push_back(i);//说明加上这条线之后可以成环
		else fa[x] = y; 
	}
	for(int i = 1; i <= n; i++)
		if(fa[i] == i) s.insert(i);
	//处理环
	for(int i : d)
	{
		if(s.size() == 1) break;
		int p = *s.begin(), q = find(e[i][0]);
		if(p == q) p = *(++s.begin());
		fa[q] = p;
		s.erase(s.find(q));
		u.push_back(i);
		v.push_back(e[i][0]);
		w.push_back(p);
	}
	cout << u.size() << '\n';
	for(int i = 0; i < u.size(); i++)
	{
		cout << u[i] << " " << v[i] << " " << w[i] << '\n';
	}
	return 0;
}

2.8 F

F - Insert

题目：

给出一个数组a，该数组的第i位应插入到新数组的第a[i]位，请给出最后新数组的结果

解法：

树状数组 + 二分

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
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
class FenwickTree//树状数组，tree的索引从1开始 
{
private:
	 vector<int> tree;
	 int n;
public:
	FenwickTree(int size) : n(size), tree(size + 2, 0) {}
	
	void add(int x, int k = 1)
	{
		while(x <= n)
		{
			tree[x] += k;
			x += x & -x;
		}
	}	
	int ask(int x)
	{
		int sum = 0;
		while(x)
		{
			sum += tree[x];
			x -= x & -x;
		}
		return sum;
	}
}; 
vector<int> insertnum(const vector<int>& a)
{
	vector<int> b(n);//结果数组
	FenwickTree t(n);//树状数组
	
	for(int i = n - 1; i >= 0; i--)//从后往前遍历，防止前面的占了后面的位置 
	{
		int num = i + 1, pos = a[i];
		int l = 1, r = n, mid;
		while(l < r) 
		{
			mid = l + r >> 1;
			int empty = mid - t.ask(mid);
			if(empty < pos) l = mid + 1;
			else  r = mid;
		}
		b[l - 1] = num;//让索引从0开始 
		t.add(l);//树状数组的索引从1开始  
	} 
	return b;
}
signed main()
{
	cin >> n;
	vector<int> p(n);
	for(int i = 0; i < n; i++) cin >> p[i];
	vector<int> result = insertnum(p);
	for(int num: result)
		cout << num << " ";
	return 0;
}

2.15 E

E - GCD of Subset

（待补）

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
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);  // 提高输入输出效率
    cin.tie(nullptr);  // 解除cin与cout的绑定，进一步提高效率

    int N, K;
    cin >> N >> K;  // 读取 N 和 K

    const int MAXVAL = 1000000;  // 假定数组中的最大值为 1000000
    vector<int> A(N);  // 存储 N 个元素的数组 A
    vector<int> freq(MAXVAL + 1, 0);  // 频率数组，记录每个数字在 A 中出现的次数

    // 读取数组 A 的元素，并更新频率数组
    for (int i = 0; i < N; i++) {
        cin >> A[i];  // 读取第 i 个元素
        freq[A[i]]++;  // 增加频率计数
    }

    // 计算每个数 d 能整除多少个不同的数字
    vector<int> cnt(MAXVAL + 1, 0);  // cnt[d] 记录能够被 d 整除的数字在数组 A 中出现的次数
    for (int d = 1; d <= MAXVAL; d++) {  // 遍历 d 从 1 到 MAXVAL
        for (int m = d; m <= MAXVAL; m += d) {  // 遍历 d 的倍数 m (m = d, 2d, 3d, ...)
            cnt[d] += freq[m];  // 对于每个 m，累加 freq[m]，即 m 在 A 中的出现次数
        }
    }

    // 找到每个数字的最佳整除因子
    vector<int> best(MAXVAL + 1, 0);  // best[x] 记录数字 x 最佳的整除因子
    for (int d = MAXVAL; d >= 1; d--) {  // 从大到小遍历 d，找到最大 d
        if (cnt[d] >= K) {  // 如果能整除至少 K 个数字
            for (int x = d; x <= MAXVAL; x += d) {  // 遍历所有能被 d 整除的数字 x (x = d, 2d, 3d, ...)
                if (best[x] == 0) {  // 如果 x 还没有被赋值最佳因子
                    best[x] = d;  // 将最佳因子 d 赋值给 x
                }
            }
        }
    }

    // 输出每个数字的最佳因子
    for (int i = 0; i < N; i++) {
        cout << best[A[i]] << "\n";  // 输出数组 A 中每个元素的最佳整除因子
    }

    return 0;  // 程序结束
}