Atcoder ABC392游记

Atcoder ABC392游记（A~E）

比赛链接

注：这次比赛因为有事情所以没有打，都是赛后代码，特此说明。

holy shit这次比赛这么简单我怎么没打，qwq

A.Shuffled Equation

题目描述

给你一个整数序列$A=(A_1,A_2,A_3)$。

让$B=(B_1,B_2,B_3)$为A的任意一个排列。

问你有没有可能$B_1*B_2=B_3$

思路

你跑一遍全排列也不是不行，不过我们简单一点可以直接从小到大排序判断就欧克了。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> a(3);
    cin >> a[0] >> a[1] >> a[2];
    sort(a.begin(), a.end());
    cout << (a[0] * a[1] == a[2] ? "Yes" : "No");
    return 0;
}

B.Who is missing

题目描述

给你一个长度为$M$的整数序列$A=(A_1,A_2,...A_M)$

每一个$A$中的元素都在$1$到$N$之间，而且不会有重复的元素。

问你在$1$到$N$之间有哪些元素在$A$中没有出现？按照降序输出。

思路

水题啊，搞一个vis数组就行了。

代码

#include<bits/stdc++.h>
using namespace std;
bool vis[1111];
int n, m;
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        vis[x] = 1;
    }
    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        if (vis[i] == 0) {
            ans.push_back(i);
        }
    }
    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << ' ';
    }
    return 0;
}

C.Bib

题目描述，但是被我乱改了的

有$N$个人，编号为$1,2,...N$。

第$i$个人拿着编号为$Q_i$的桃枝，正在看第$P_i$个人。

对于$i=1,2,...N$，输出拿着编号为$i$的桃枝看的人拿着的桃枝。

（猜猜我为什么要乱翻译）

思路

这一题实现其实焯简单，但是我却读了好久题，尤其是在我没有翻译的时候…

在这种情况下，我们可以借助样例读懂，千万不要在对题意不明不白的时候去写代码。

怎么给你说清楚呢，我也不知道，请务必读懂题之后再继续看。

我们用一个数组把每个桃枝对应的人记录一下，其实就没有那么难了。

代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int idx, look;
}a[333333];
int p[333333], n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].look;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i].idx;
        p[a[i].idx] = i;
    }
    for (int i = 1; i <= n; i++) {
        cout << a[a[p[i]].look].idx << ' ';
    }
    return 0;
}

D.Doubles

题目描述(这个我不会乱翻译)

有$N$个骰子，第$i$个骰子有$K_i$面，对应写的面是$A_{i,1},A_{i,2},...,A_{i,K_i}$。

每一次可以选择两个骰子并丢一次他们，定义$B=$获得的数字正好相同的概率，求你可以得到的$B$的最大值。

答案的精度要保证在$10^{-8}$内。

思路

丢骰子的经历有过吧？

我们得到每一面的概率都是相等的，所以对于一个数字，假设在这个骰子里有$A$个，这个骰子一共有$B$面，可能得到的概率就是$\frac{A}{B}$，其实你的数学老师肯定教过你。

这里，$N$最大到100,所以我们用一个$multiset$来模拟一个骰子，暴力枚举两个骰子算情况就搞定了。

不是，这回$D$这么简单？连double都没有卡（

代码

#include<bits/stdc++.h>
using namespace std;
vector<multiset<int>> vt;
int n;
bool vis[111111];
int main()
{
    cin >> n;
    vt.resize(n);
    for (int i = 0; i < n; i++) {
        int s, x;
        cin >> s;
        while (s--) {
            cin >> x;
            vt[i].insert(x);
        }
    }
    double ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            memset(vis, 0, sizeof(vis));
            double tp = 0;
            for (auto a : vt[i]) {
                if (vis[a]) {
                    continue;
                }
                vis[a] = 1;
                tp += (double)vt[i].count(a) / (double)vt[i].size() * (double)vt[j].count(a) / (double)vt[j].size(); 
            }
            ans = max(ans, tp);
        }
    }
    cout << fixed << setprecision(8) << ans;
    return 0;
}

E.Cables and Servers

题目描述

有$N$个编号为$1,2,...N$的服务器，和$M$个编号为$1,2,...M$的电缆。

第$i$个电缆双向链接$A_i$和$B_i$。

你可以操作以下操作若干次(可能为0)，使所有服务器通过电缆连接。

• 选择一根电缆，把它的一端连接到不同的服务器上。

输出最小的操作次数，并输出达到这个最小次数的操作序列。

思路

花里胡哨的说了一大坨又大又臭（有吗）的东西，其实就是让你把整个图变成连通的。

那既然和连通有关系，我们首先把所有连通块找出来。那并查集就是个不戳的选择。

好了，你找到连通块了，那我们要把它们连起来了，怎么连？

我们起码不能破坏连通块，所以可以找到连通块里修改到其他地方对整个连通块没有影响的边，用他们来当作连通块的桥梁，这样就差不多了。

并查集写着其实我感觉很模板，但这题让我感到没有那么模板了，直接硬控我，条半天，直接给我红温了。

代码

#include<bits/stdc++.h>
using namespace std;
int fa[200005], n, m;
bool can[200005]; // 这条边能不能作为连通块间的桥梁（好像反过来了）
int edges[200005];
void init()
{
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}
int find(int x)
{
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find(fa[x]);
}
bool same(int x, int y)
{
    x = find(x);
    y = find(y);
    return x == y;
}
void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    fa[x] = y;
}
int main()
{
    cin >> n >> m;
    int ans = n - 1;
    init();
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        edges[i] = x;
        if (!same(x, y)) {
            merge(x, y);
            can[i] = 1;
            ans--;
        }
    }
    cout << ans << '\n';
    int cnt = 1;
    for (int i = 1; i <= m; i++) {
        if (can[i]) {
            continue;
        }
        while (same(cnt, edges[i]) && cnt <= n) {
            cnt++;
        }
        if (cnt > n) {
            return 0;
        }
        merge(cnt, edges[i]);
        cout << i << ' ' << edges[i] << ' ' << cnt << '\n';
    }
    return 0;
}

总结

有啥好总结的，就是感觉打着很爽。

其实，比赛这一天有点儿悲伤的一天，因为这个，都怪傻逼的一些xxs。

彩蛋

tqq和mmm的奇妙冒险(从洛谷搬运来的) 我不知道tqq用了什么提示词才能写出这种轻科幻大作，虽然我并不喜欢读（

吐槽：洛谷国际服怎么进不去了