A.Array—构造+思维

题意：给出一个包含 n 个元素的序列，将它们满足下列条件的三个集合：

  • 第一个集合里所有元素的乘积小于 0
  • 第二个集合里所有元素的乘积大于 0
  • 第三个集合里所有元素的乘积等于 0

求出任意一个满足条件的方案并输出集合中组成的元素，题目保证答案存在

思维：第一个集合就放一个负数，第二个集合放两个负数或者一个正数，剩余的元素都放在第三个集合，这样构造最简单

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    int a[100] = {};
    vector<int> vec;
    int flag = 0;   //记录是否存在一个正数
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x > 0 && !flag)
            flag = x;
        else
            vec.push_back(x);
    }
    sort(vec.begin(), vec.end());   //排序使负数在容器前面
    int p = 0;  //遍历指针
    cout << 1 << ' ' << vec[p++] << endl;
    if (flag)   //存在一个正数
        cout << 1 << ' ' << flag << endl;
    else        //否则第二个集合放两个负数
        cout << 2 << ' ' << vec[p++] << ' ' << vec[p++] << endl;
    cout << vec.size() - p; //第三个集合的元素
    for (; p < vec.size(); ++p)
        cout << ' ' << vec[p];
    cout << endl;
    // system("pause");
    return 0;
}

B.Coach—带权并查集+思维

题意：教练有 n 名学生，n 保证能被 3 整除。他想要将学生们分成三人一组去打 ACM，学生们有 m 个条件，形如学生 i 和学生 j 想要分到一组，求一种满足所有要求的方案，如果不存在输出 -1，否则则每行输出三哥学生的序号代表三人一组

思路：不难想要肯定要借助并查集先确定条件限制形成的点集的大小，如果存在一个点集的大小大于 3 那么肯定是输出 -1，否则点集的大小都是 1 或者 2。因为还需要输出学生序号所以对于每个点集我们让另开一个容器帮助根节点记录该集合内部的序号成员。对于大小为 3 的点集直接输出，对于大小为 2 的点集跟它在找一个大小为 1的点集，剩余的大小为 1的点集自行组队。但是需要注意如果大小为 2 的点集多余大小为 1 的点集也是不能成功组队的例如 6 被分成 3 个大小为 2 的点集，所以还需要在组队前判断一下

细节多码量也不小，比赛时好像过 C 的比过 B 的要多

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*带权并查集按秩合并,将节点记录点集大小的负数,其他节点记录父节点*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 55;

int n, m;
int fa[maxn];
vector<int> se[maxn];  //记录并查集头部节点为集合的点集

int find(int x) {
    if (fa[x] < 0) return x;
    fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    if (fa[fx] < fa[fy]) {
        fa[fx] += fa[fy];
        fa[fy] = fx;
        for (int i = 0; i < se[fy].size(); ++i)
            se[fx].push_back(se[fy][i]);
        se[fy].clear();
    } else {
        fa[fy] += fa[fx];
        fa[fx] = fy;
        for (int i = 0; i < se[fx].size(); ++i)
            se[fy].push_back(se[fx][i]);
        se[fx].clear();
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    while (cin >> n >> m) {
        for (int i = 1; i <= n; ++i) {
            fa[i] = -1;
            se[i].push_back(i);
        }
        while (m--) {
            int x, y;
            cin >> x >> y;
            merge(x, y);
        }
        vector<int> vec1, vec2, vec3;
        for (int i = 1; i <= n; ++i) {
            if (fa[i] < -3) {
                cout << -1 << endl;
                return 0;
            }
            if (fa[i] == -1)
                vec1.push_back(i);
            else if (fa[i] == -2)
                vec2.push_back(i);
            else if (fa[i] == -3)
                vec3.push_back(i);
        }
        if (vec2.size() > vec1.size()) {  //只有大小为2的集合小于大小为1的集合才可以：例如6个人分成3个大小为2的集合
            cout << -1 << endl;
            return 0;
        }
        for (int i = 0; i < vec3.size(); ++i) {  //输出大小为3的点集
            for (auto e : se[vec3[i]])
                cout << e << ' ';
            cout << endl;
        }
        for (int i = 0; i < vec2.size(); ++i) {  //大小为1的和大小为2的点集各一个
            for (auto e : se[vec1[i]])
                cout << e << ' ';
            for (auto e : se[vec2[i]])
                cout << e << ' ';
            cout << endl;
        }
        for (int i = vec2.size(); i < vec1.size(); i += 3)  //剩余的大小为1的点集每三个一组
            cout << se[vec1[i]][0] << ' ' << se[vec1[i + 1]][0] << ' ' << se[vec1[i + 2]][0] << endl;
    }
    // system("pause");
    return 0;
}

C.Beautiful Numbers—组合数+快速幂+逆元+思维

题意：给出一个长度为 n 的数 x，如果 x 本身由 a 和 b 两个数构成并且 x 中每个位置上的数的加和还是只由 a 和 b 构成我们就成它为优秀的数，请确定这个 x 是优秀的数有几种构造方法，答案对 1e9+7 取模

思路：如果 x 中有 cnta 个 a，那么就有 n-cnta 个 b，然后我们判断这样所有的数的加和时候还是只由 a 和 b 构成，是的话 x 就多了 C(n,cnta) 种构造方法，cnta的取值无疑是 [0,n]，所以就枚举 a 的个数判断构成的 x 是否为优秀的数，是的话就算上新增加的构造方法，中间环节注意取模

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll a, b, n;

ll quick_pow(ll a, ll b) {
    ll ans = 1, base = a;
    while (b) {
        if (b & 1) ans = ans * base % mod;
        base = base * base % mod;
        b >>= 1;
    }
    return ans;
}

ll factorial(ll n) {  //阶乘
    ll fc = 1;
    for (int i = 1; i <= n; ++i) fc = (fc * i) % mod;
    return fc % mod;
}

ll inv(ll a) {  //求逆元
    return quick_pow(a, mod - 2) % mod; 
}

ll combo(ll n, ll m) {  //逆元组合数
    ll com = factorial(n) * inv((factorial(m) * factorial(n - m)) % mod) % mod;
    return com % mod;
}

bool check(ll x, ll y, ll s) {
    while (s) {
        int x = s % 10;
        s /= 10;
        if (x != a && x != b) return 0;
    }
    return 1;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    while (cin >> a >> b >> n) {
        ll ans = 0;
        for (ll cnta = 0; cnta <= n; ++cnta) {
            ll cntb = n - cnta;
            ll sum = a * cnta + b * cntb;
            if (check(cnta, cntb, sum))	//判断是否是优秀的数
                ans = (ans + combo(n, cnta)) % mod;
        }
        cout << ans << endl;
    }
    // system("pause");
    return 0;
}