2023 ICPC网络赛

L. KaChang!

在准备问题时，人们通常会将时间限制至少设定为标准程序运行时间的两倍，但有时参赛者仍会觉得时间限制太紧。

现在你有一个问题的标准程序和另外 $n$ 个被认为 "应该通过这个问题 "的程序。给定每个程序的运行时间，请找出最小的整数 $k\ge 2$ ，使得当时间限制设为标准程序运行时间的 $k$ 倍时，所有提供的程序都能通过。当且仅当一个程序的运行时间小于或等于时间限制时，该程序才能通过。

void solve() {
    int n, t;cin >> n >> t;
    vector<int> a(n);
    for (int i = 0;i < n;i++)cin >> a[i];
    sort(a.begin(), a.end());
    int ans = ceil(a[n - 1] * 1.0 / t);
	cout << max(ans , 2) << '\n';
}

A. Qualifiers Ranking Rules

以下是目前 ICPC 亚洲执委会在线预选赛的排名规则，将有两场在线比赛。

1. 在每场比赛中，只取每所大学排名第一的队伍的名次作为该大学的成绩；

2. 在每次比赛中，参赛大学将根据得分进行排名；

3. 两组大学排名采用合并排序法进行合并。对于在不同比赛中获得相同排名的两所大学，在第一次比赛中获得该排名的大学将被排在第一位。

4. 删除重复的大学，得到所有参赛大学的最终排名（只保留每所大学的最高排名）。

现在假设第一场比赛有 $n$ 支队伍，第二场比赛有 $m$ 支队伍。

在每次比赛中，给定每个参赛队的排名和所属大学，请根据上述规则输出所有参赛大学的最终排名。

void solve() {
    int n, m;cin >> n >> m;
    map<string, int> ss, sss;
    vector<string> s1, s2, ans;
    for (int i = 0;i < n;i++) {
        string s;cin >> s;
        if (!ss.count(s))
            s1.push_back(s);
        ss[s] = 1;
    }
    for (int i = 0;i < m;i++) {
        string s;cin >> s;
        if (!sss.count(s))
            s2.push_back(s);
        sss[s] = 1;
    }
    ss.clear();
    for (int i = 0;i < max(s1.size(), s2.size());i++) {
        if (i < s1.size() && !ss.count(s1[i])) {
            ans.push_back(s1[i]);ss[s1[i]] = 1;
        }

        if (i < s2.size() && !ss.count(s2[i])) {
            ans.push_back(s2[i]);ss[s2[i]] = 1;
        }
    }
    for (auto i : ans)cout << i << '\n';
}

D. Transitivity

给定一个简单的无向图，有 $n$ 个顶点和 $m$ 条边，保证 $m<\frac{n(n-1)}{2}$ .

当且仅当对于任意两个不同的顶点 $u,v$ ：

如果图中存在一条以 $u$ 为起点、以 $v$ 为终点的路径，那么图中应该存在一条连接 $u$ 和 $v$ 的边。

现在，您应该在图中添加一些不定向边（至少添加一条边）。您需要确保添加边后，该图仍然是一个简单的无向图，并且具有传递性。

问题是，至少需要添加多少条边？

回想一下，简单无向图是指任意两个顶点之间没有一条以上的边，并且没有边在同一个顶点开始和结束的无向图。

Solution

当全部连通块都是满的时，需要将两个大小最小的连通块连接在一起, 若这两个联通块顶点个数分别为 $d_1,d_2$，边的个数分别为 $e_1,e_2$,则答案为 $\frac{(d_1+d_2)\times (d_1+d_2-1)}{2}-(e_1+e_2)$
有连通块没满时, 若该连通块的顶点个数为 $d$，边的个数为 $e$，该联通块对答案的贡献为 $\frac{d\times (d-1)}{2}-e$，将所有的贡献加起来即可。

const int N = 1e6 + 10;
vector<int> g[N];
vector<bool> vis(N);
ll e = 0, d = 0;
void dfs(int u) {
    for (auto v : g[u]) {
        e++;
        if (vis[v])continue;
        vis[v] = 1;
        d++;
        dfs(v);
    }
}
void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        int u, v;cin >> u >> v;
        g[u].push_back(v);g[v].push_back(u);
    }
    vector<pair<int, int>> p;

    for (int i = 1;i <= n;i++) {
        if (vis[i])continue;
        vis[i] = 1;
        e = 0, d = 1;
        dfs(i);
        p.push_back({d,e / 2});
    }
    ll ans = 0;
    for (auto [d, e] : p) {
        ans += 1ll * d * (d - 1) / 2 - e;
    }
    if (!ans) {
        sort(p.begin(), p.end());
        ll d = p[0].first + p[1].first, e = p[0].second + p[1].second;
        ans = d * (d - 1) / 2 - e;
    }
    cout << ans << '\n';
}

J. Minimum Manhattan Distance

回顾一下，在二维平面上，两点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 之间的曼哈顿距离为 $|x_1-x_2|+|y_1-y_2|$ 。如果一个点的两个坐标都是整数，那么我们称这个点为整数点。

给定二维平面上的两个圆 $C_1,C_2$ ，并保证 $C_1$ 中任意一点的 $x$ 坐标与 $C_2$ 中任意一点的 $x$ 坐标不同，且 $C_1$ 中任意一点的 $y$ 坐标与 $C_2$ 中任意一点的 $y$ 坐标不同。

每个圆由两个整数点描述，连接两点的线段代表圆的直径。

现在需要在 $C_2$ 内或 $C_2$ 上选取一点 $(x_0,y_0)$ ，使得从 $(x_0,y_0)$ 到 $C_1$ 内一点的曼哈顿距离的期望值最小。如果我们在 $C_1$ 内所有实数坐标点中均匀概率地选择这一点。

Solution

没有看懂题目的意思

答案一定是在以圆心 45 度的边上，取最小即可。答案则为 $\text{Manhattan}(r_1,r_2)-\sqrt{2}{r}_2$

必须用 int 读入，用 double 读入会 TLE
需要开 long long

#define int long long
void solve() {
    int x11, y11, x12, y12;cin >> x11 >> y11 >> x12 >> y12;
    int x21, y21, x22, y22;cin >> x21 >> y21 >> x22 >> y22;
    // double r1 = sqrt((x11 - x12) * (x11 - x12) + (y11 - y12) * (y11 - y12));
    double r2 = sqrt((x21 - x22) * (x21 - x22) + (y21 - y22) * (y21 - y22));
    double x10 = (x11 + x12) / 2.0, y10 = (y11 + y12) / 2.0;
    double x20 = (x21 + x22) / 2.0, y20 = (y21 + y22) / 2.0;
    cout << fixed << setprecision(10) << fabs(y10 - y20) + fabs(x10 - x20) - sqrt(2) * r2 / 2 << '\n';
    // printf("%.10f", fabs(y10 - y20) + fabs(x10 - x20) - sqrt(2) * r2 / 2);
}

I. Pa? sWorD

您需要登录一个神秘的系统，但您发现自己忘记了密码。系统不支持重设密码，所以登录的唯一办法就是不断尝试。

幸运的是，你还记得一些关于密码的信息：

首先，你确定密码的长度是 $n$ 。

那么你记住的信息可以用长度为 $n$ 的字符串 $s$ 来描述。

让 $s_i$ 表示 $s$ 的 $i$ -th 字符：

• 如果 $s_i$ 是大写字母或数字字符，那么密码的 $i$ 个字符必须是 $s_i$ ；
• 如果 $s_i$ 是小写字母，那么密码的 $i$ 个字符可能是 $s_i$ 或 $s_i$ 的大写形式；
• 如果 $s_i$ 是问号'?'，那么密码的 $i$ 个字符可以是任何大写字母、小写字母和数字字符。

可以保证字符串 $s$ 只包含大写字母、小写字母、数字字符和问号"？

此外，系统对密码还有几项要求：

• 密码中至少出现一个大写字母；
• 密码中至少出现一个小写字母；
• 密码中至少有一个数字字符；
• 密码中任何两个相邻字符不能相同。

现在你想知道，有多少种可能的密码？一个可能的密码应该同时符合你的记忆和系统的要求，而且可以保证至少存在一个可能的密码。

你知道这个答案会非常大，所以你只需要计算出模数 $998244353$ 的结果。.

请注意不同寻常的内存限制。memory limit per test 32 megabytes

Solution

容斥/状压 DP
2023 ICPC 网络赛 第一场简要题解 - 知乎
(不懂，待更 $\dots$)