E. Transitivity
题意：有一张有向图，你需要在其中添加若干条边，满足对于任意 \(a\to b, b\to c\)，都有 \(a\to c\)。求最少的添加边数。\(n,m\le 2000\)。
首先可以转化为最少的总边数，再减去原有的 \(m\) 条边。容易发现新图中存在 \(a\to b\)，当且仅当原图中 \(a\) 能到达 \(b\)。所以问题转化为对每个点求它能到达的点数，\(O(nm)\) 即可。（应该没人像我一样傻地写了个 tarjan+bitset 吧）
By SSRS
#include <bits/stdc++.h>
using namespace std;
int main(){
int N, M;
cin >> N >> M;
vector<vector<int>> E(N);
for (int i = 0; i < M; i++){
int u, v;
cin >> u >> v;
u--;
v--;
E[u].push_back(v);
}
int cnt = 0;
for (int i = 0; i < N; i++){
vector<bool> used(N, false);
used[i] = true;
queue<int> Q;
Q.push(i);
while (!Q.empty()){
int v = Q.front();
Q.pop();
for (int w : E[v]){
if (!used[w]){
used[w] = true;
Q.push(w);
}
}
}
for (int j = 0; j < N; j++){
if (j != i && used[j]){
cnt++;
}
}
}
cout << cnt - M << endl;
}
F. Regular Triangle Inside a Rectangle
题意：一个 \(a\times b\) 的矩形里放正三角形，求最大边长。\(1\le a,b\le 1000\)，精度误差 \(10^{-9}\)。
首先钦定 \(a\ge b\)（否则交换）。
做法一
直接想感觉会有很多分类讨论，所以可以考虑二分答案。
对于一个边长 \(x\)，如果高超过 \(b\)（即 \(\frac{\sqrt{3}}{2}x>b\)）则显然不可行，如果 \(x\le b\)，则显然可行。否则，一定可以将其一个顶点放到一个角上，另一个顶点放到长边上，最后一个顶点悬空。如下图：
于是可以通过勾股定理求出 \(y\)，将 \(x\) 边旋转 \(60^\circ\)，看是否超出矩形即可。
By cxm1024
#include <bits/stdc++.h>
using namespace std;
#define ld long double
const ld eps = 1e-12, sq3 = sqrt((ld)3);
int a, b;
bool check(ld x) {
if (sq3 * x / 2 > b) return 0;
if (x <= b) return 1;
ld y = sqrt(x * x - b * b);
return sq3 * b / 2 + y / 2 <= a;
}
signed main() {
scanf("%d%d", &a, &b);
if (a < b) swap(a, b);
ld l = 0, r = 2000;
while (l + eps <= r) {
ld mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.11Lf\n", (l + r) / 2);
return 0;
}
做法二
上面的做法显然比较麻烦，其实可以不二分答案而很快地求解。
首先容易发现，如果长边过长，超过了短边的 \(\frac{2}{\sqrt{3}}\) 倍，则显然正着放最优，答案为短边的 \(\frac{2}{\sqrt{3}}\)。
否则，参考上面二分答案的过程可以发现，答案的 \(x\) 一定是被长限制住了才不能增长，如下图：
此时便可以直接解出 \(x\)。
By SSRS
（注：这份代码里钦定 \(a\le b\)）
#include <bits/stdc++.h>
using namespace std;
int main(){
cout << fixed << setprecision(20);
int A, B;
cin >> A >> B;
if (A > B){
swap(A, B);
}
if (B > A * 2 / sqrt(3)){
cout << A * 2 / sqrt(3) << endl;
} else {
cout << hypot(B, A * 2 - B * sqrt(3)) << endl;
}
}