视频题解

---

A

先将 $x$ 转为相应的三进制，发现第 $i$ 位若为 $0,2$，则说明 $±i$ 位只能都为白，红，否则要混合出粉红色，则可一红一白、一白一红两种情况。

注意 $x$ 的最高位为 $1$ 时，表示第 $0$ 位自己与自己重叠出粉红色，是不可能的情况。

#include <iostream>
using namespace std;
int main()
{

    long long x;
    cin >> x;

    long long result = 1;
    int h = 0;
    while (x > 0)
    {
        if ((h = x % 3) == 1)
            result *= 2;
        x /= 3;
    }

    cout << (h != 1 ? result : 0);

    return 0;
}

B

对任意正整数 $n$，先对其进行质因数分解：

$$n = p_1^{k_1} p_2^{k_2} \dots p_m^{k_m}$$

其中 $p_1,p_2,\dots,p_m$ 是 $n$ 的不同质因数，$k_1,k_2,\dots,k_m$ 是对应的指数。

则欧拉函数的通项公式为：

$$\varphi(n) = p_1^{k_1-1}(p_1-1)\cdot p_2^{k_2-1}(p_2-1)...p_m^{k_m-1}(p_m-1)$$

题目中所求的“孤单值”即为欧拉函数，即所求为欧拉函数为质数的情况。

对于 $>2$ 的质因数都是奇数，所以 $p_i-1$ 一定是偶数，导致最后 $\varphi(n)$ 一定不为质数。因此 $n$ 只能含有 $2,3$ 两种质因数。即要使 $2^{a}\cdot 3^{b}, a,b\geq 0$ 为质数，仅当其为 $2,3$ 时可为质数。此时对应的 $n$ 为 $3, 4,6$

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, Q;
	cin >> N;
	vector<int> a(N+1, 0);
	for(int i = 1; i <= N; ++i) {
		cin >> a[i];
		if(a[i] == 3 || a[i] == 4 || a[i] == 6) a[i] = a[i-1]+1;
		else a[i] = a[i-1];
	}
    cin >> Q;
    vector<pair<int, int>> ans;
	for(int i = 1; i <= Q; i++) {
		int l, r;
		cin >> l >> r;
		ans.push_back( {a[r] - a[l-1], i} );
	}
    sort(ans.begin(), ans.end(), [](const pair<int, int> m, const pair<int, int> n) {
        if(m.first != n.first) return m.first > n.first;
        else                   return m.second < n.second;
    });
    cout << ans[0].second;
	return 0;
}

C

$a_i<b_i$ 的人必选，接下来考虑在剩下的 $a_i\ge b_i$ 的人中如何选择。

因为最后所有人 $a_i\ge b_i$，也就是 $a_i\ge b_{max}$，所以将 $b_i$ 按照由小到大的顺序排序，逐一枚举 $b_{max}$，再考虑删除过小的 $a_i$，使用优先队列完成。

#include <bits/stdc++.h>
using namespace std;

struct node
{
    long long a, b;
} v[1000010];

priority_queue<long long, vector<long long>, greater<long long>> p;

bool cmp(node v1, node v2)
{
    return v1.b < v2.b;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        long long bmax = 0, sum_r = 0, cnt_r = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> v[i].a >> v[i].b;
            if (v[i].a < v[i].b)
            {
                sum_r += v[i].a;
                cnt_r++;
                bmax = max(bmax, v[i].b);
            }
        }

        if (cnt_r == 0)
        {
            cout << "YES\n";
            continue;
        }

        sort(v + 1, v + n + 1, cmp);

        long long sum_h = 0, cnt_h = 0;
        int flag = 0;

        for (int i = 1; i <= n; i++)
        {
            bmax = max(bmax, v[i].b);

            if (v[i].a >= v[i].b)
            {
                p.push(v[i].a);
                sum_h += v[i].a;
                cnt_h++;
            }

            long long total_sum = sum_r + sum_h;
            long long total_cnt = cnt_r + cnt_h;

            // 如果平均值不够大，就移除 a_i 最小的可选成员
            while (!p.empty() && p.top() < bmax)
            {
                long long tp = p.top();
                p.pop();
                sum_h -= tp;
                cnt_h--;

                total_sum = sum_r + sum_h;
                total_cnt = cnt_r + cnt_h;
            }

            if (total_sum * 1.0 / total_cnt >= bmax)
            {
                flag = 1;
                break;
            }
        }

        if (flag == 1)
            cout << "YES\n";
        else
            cout << "NO\n";

        while (!p.empty())
            p.pop();
    }
    return 0;
}

D

- 30pts

按照题意，模拟每天的 MST 即可，$O(mk)$

- 100pts

定义 $k$ 个并查集，表示每一天的城市道路修建与联通情况。将所有道路按照 $w_i$ 由小到大进行排序，对于每一条边，二分查找出第一个 $u_i,v_i$ 还没有联通的天数 $t$，说明该条边会在第 $t$ 天修建。$O(mlogk)$

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> fa;

    DSU(int n) : fa(n + 1) {
        for (int i = 0; i <= n; ++i) {
            fa[i] = i;
        }
    }

    int find(int u) {
        if (fa[u] != u) fa[u] = find(fa[u]); 
        return fa[u];
    }

    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        fa[v] = u; 
    }
};

struct Edge {
    int u, v, w, idx;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, K;
    cin >> N >> M >> K;

    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].idx = i + 1;
    }
    sort(edges.begin(), edges.end());

    vector<DSU> dsus(K + 1, DSU(N));
    vector<int> ans(M + 1, -1);

    for (const Edge& e : edges) {
        int u = e.u;
        int v = e.v;
        if (dsus[K].find(u) == dsus[K].find(v)) continue;
        int left = 1;
        int right = K;
        int day;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (dsus[mid].find(u) != dsus[mid].find(v)) {
                day = mid; 
                right = mid - 1; 
            } else left = mid + 1; 
        }
        ans[e.idx] = day;
        dsus[day].merge(u, v);     
    }

    for (int i = 1; i <= M; i++)  cout << ans[i] << '\n';

    return 0;
}