这次比赛水题和思维题偏多，没考什么复杂的数据结构，G题一个小细节笔误导致一直TLE，虽然最后还是做出来了，但还是有些郁闷，A、C、L签到水题就不写题解了。

题目链接

C – Save the Queen!（二分答案）

题意

有n个敌人，k个士兵，告诉你每个士兵最大可以战斗的时间，让你安排士兵和敌人战斗，战斗期间可以随意切换战斗对象，问你最多可以让所有敌人同时保持战斗多长时间。

分析

高精度的二分答案，check这样写：对于假设的战斗时间x，若士兵战斗时间超过x则让他全程与一个敌人战斗，否则维护一个战斗时间，将所有战斗时间小于x的士兵的时间存入其中，让他们共同面对剩下的所有敌人，如果可以应付，则返回true，否则false。因为，若一个士兵战斗时间超过了x，则他所能贡献的总时间最多就为x秒，假设他贡献了x+1的时间，则他就算在0时刻就开始战斗则他在x+1秒的时候还在战斗，但是只要求战斗x秒，所以不存在再去帮别人的可能，所以直接将他与一个敌人绑定即可。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double eps = 1e-9;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int a[maxn], n ,k;

bool check(double x) {
    int tot = n;
    double have = 0;
    for(int i = 0; i < k; i++) {
        if(a[i]-x>eps){
            tot--;
            continue;
        }
        else have += a[i];
    }
    if(tot <= 0) return true;
    return ((have/tot)-x) > eps;
}

int main(int argc, char const *argv[]) {
    cin >> n >> k;
    for(int i = 0; i < k; i++) {
        scanf("%d",&a[i]);
    }
    double l = 0.0, r = 1e9;
    int t = 100;
    while(t--) {
        double mid = (l+r)/2.0;
        if(check(mid)) l = mid;
        else r = mid; 
    }
    printf("%.9lf", l);
    return 0;
}

E – Video Conference

题意

给你几个字符串，让你用简写表示每个字符串，规则是不与前面出现过的字符串有相同前缀的最小串（如出第一个串abc，第二个串abcd，则缩写为a和abcd），若前面有相同的字符串，则输出该字符串并在后面加上该字符串出现的次数。

分析

用unordered_map hash每一个字符串的前缀，然后查找前面是否出现过该字符串，暴力循环一遍即可。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;

unordered_map<string,int> mp;

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    while(n--) {
        string s;
        cin >> s;
        int flag = 1;
        for(int i = 1; i <= s.size(); i++) {
            string sub = s.substr(0,i);
            if(mp.find(sub) == mp.end()){
                mp[sub] = 0;
                if(flag == 1) {
                    cout << sub << endl;
                    flag = 0;
                }
            } 
        }
        mp[s]++;
        if(flag == 1) {
            if(mp[s] == 1) cout << s << endl;
            else cout << s << ' ' << mp[s] << endl;
        }
    }
    return 0;
}

G – Array Partition（并查集）

题意

给你n个数字，让你分割成两个集合，每个数字要么属于第一个集合，要么属于第二个集合。要求第一个集合所有元素的乘积与第二个集合所有元素的集合乘积互质，问一共有几种方案。

题目分析

要求A B两个集合元素乘积互质，其实就是要求A B间所有元素的因子互不相同。我们可以求出所有数字的因子，如果两个数字有相同的因子，则说明这两个数属于同一个集合，并且他们的所有因子也属于同一个集合，用并查集维护一下，最后可以得到几个集合，并且这几个集合的元素间没有相同的因子。我们考虑将每个集合是否放入集合A，每个集合有放或者不放两种方案，假设有n个集合，那么方案数就是 $2^n-2$（-2是因为，不存在全部集合都属于A以及全部集合都不属于A的方案）。对于如何求每个数字的因子，可以用素数筛预处理一遍，顺便求因子，比赛的时候就是这里打错了一个字母导致一直T…

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int a[maxn];
vector<int> fact[maxn];
int fa[maxn];
bool is_prime[maxn];
inline int read() {
    int X = 0;
    bool flag = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') flag = 0;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        X = (X << 1) + (X << 3) + ch - '0';
        ch = getchar();
    }
    if (flag) return X;
    return ~(X - 1);
}

void init() {
    for (int i = 2; i < maxn; i++) {
        if (!is_prime[i]) {
            for (int j = i; j < maxn; j += i) {
                is_prime[j] = 1;
                fact[j].push_back(i);
            }
        }
    }
}
LL qmi(int k) {
    LL now = 2;
    LL ans = 1;
    while (k) {
        if (k & 1) ans = (ans * now) % mod;
        now = (now * now) % mod;
        k >>= 1;
    }
    return ans;
}
int f(int x) { return x == fa[x] ? x : fa[x] = f(fa[x]); }

int main(int argc, char const *argv[]) {
    init();
    int t;
    cin >> t;
    while (t--) {
        int cnt = 0;
        for (int i = 0; i < maxn; i++) fa[i] = i;
        map<int, int> all;
        int n = read();
        for (int i = 0; i < n; i++) {
            int x = read();
            if (x == 1)
                cnt++;
            else {
                for (int j : fact[x]) {
                    all[j] = 0;
                    int u = f(j), v = f(fact[x].back());
                    if (u != v) fa[u] = v;
                }
            }
        }
        for (auto i : all) {
            if (i.first == fa[i.first]) cnt++;
        }
        if (cnt == 1)
            puts("0");
        else {
            cout << (qmi(cnt) - 2 + mod) % mod << '\n';
        }
    }
    return 0;
}