ABC-279解题报告

发表于 更新于 分类于

比赛传送门

C. RANDOM

题意：给你两个 01 矩阵 S,TS,T，问是否可以将 SS 以列为单位重新排列得到 TT。

判断 S,TS,T 的每列是否可以一一对应即可

做法一

以列为单位提取成字符串，S,TS,T 分别排序比较即可。

By cxm1024

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
#include<bits/stdc++.h>
using namespace std;
string s[400010],t[400010];
signed main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        string x;
        cin>>x;
        for(int j=1;j<=m;j++)
            s[j]+=x[j-1];
    }
    for(int i=1;i<=n;i++) {
        string x;
        cin>>x;
        for(int j=1;j<=m;j++)
            t[j]+=x[j-1];
    }
    sort(s+1,s+m+1);
    sort(t+1,t+m+1);
    for(int i=1;i<=m;i++)
        if(s[i]!=t[i]) {
            cout<<"No"<<endl;
            return 0;
        }
    cout<<"Yes"<<endl;
    return 0;
}

做法二

将每列哈希成一个数，排序后比较即可。

By maspy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
  LL(H, W);
  vc<u64> base(H);
  FOR(i, H) base[i] = RNG_64();
  vc<u64> A(W), B(W);

  FOR(i, H) {
    STR(S);
    FOR(j, W) if (S[j] == '#') A[j] += base[i];
  }
  FOR(i, H) {
    STR(S);
    FOR(j, W) if (S[j] == '#') B[j] += base[i];
  }
  sort(all(A));
  sort(all(B));
  Yes(A == B);
}

D. Freefall

题意：一个小球下落时间为 Ag\frac{A}{\sqrt{g}}，初始时 g=1g=1，每次可以花费 BB 的时间将 gg 增加 11，问最小总时间。

题意转化为求 Ax+1+Bx\frac{A}{\sqrt{x+1}}+Bx 的最小值。

做法一

容易证明该函数为一个下凸函数，所以可以使用三分法。

By cxm1024

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
signed main() {
    long long a,b;
    cin>>a>>b;
    long long l=0,r=1e18;
    auto check=[&](long long x) {
        return (long double)a/sqrt(x+1)+x*b;
    };
    while(l+2<r) {
        long long lmid=(l*2+r)/3,rmid=(l+r*2)/3;
        if(check(lmid)>check(rmid)) l=lmid;
        else r=rmid;
    }
    long double ans=1e18;
    for(long long i=l;i<=r;i++)
        ans=min(ans,check(i));
    printf("%.7Lf\n",ans);
    return 0;
}

做法二

找最小值相当于这个函数的导数等于 00，而下凸函数的导函数单调上升，所以可用二分求解。

实际计算中，只需要计算 f(x)−f(x−1)f(x)-f(x-1)，粗略地将其作为导数的近似来二分即可。

By Kude

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
a, b = map(int, input().split())
l = -1
r = 10 ** 18

def f(c):
    return c * b + a / (1 + c) ** 0.5

while r - l > 2:
    c1 = (l + r) // 2
    c2 = c1 + 1
    if f(c1) <= f(c2):
        r = c2
    else:
        l = c1

print(f'{min(f(l + 1), f(l + 2)):.10f}')

做法三

考虑答案关于 gg 的函数 f(g)=Ag+B(g−1)f(g)=\frac{A}{\sqrt{g}}+B(g-1)，由于最小值与常数无关，所以可以看成 f(g)=Ag+Bgf(g)=\frac{A}{\sqrt{g}}+Bg，则由均值不等式：

f(g)=Ag+Bg=A2g+A2g+Bg=3A2g+3A2g+3Bg3≥3A2g⋅3A2g⋅3Bg3=3A2B43\begin{aligned} f(g)&=\frac{A}{\sqrt{g}}+Bg\\ &=\frac{A}{2\sqrt{g}}+\frac{A}{2\sqrt{g}}+Bg\\ &=\frac{\frac{3A}{2\sqrt{g}}+\frac{3A}{2\sqrt{g}}+3Bg}{3}\\ &\ge\sqrt[3]{\frac{3A}{2\sqrt{g}}\cdot \frac{3A}{2\sqrt{g}}\cdot 3Bg}\\ &=3\sqrt[3]{\frac{A^2B}{4}} \end{aligned}

由此可知函数最小值不会小于 3A2B433\sqrt[3]{\frac{A^2B}{4}}，取等条件为 A2g=Bg\frac{A}{2\sqrt{g}}=Bg，即 g=(A2B)23g=(\frac{A}{2B})^\frac{2}{3}。

By EternalAlexander

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
const long double eps = 1e-10;
using ldb = long double;
using ll = long long;
ldb a,b;
long double calc(long double x) {
    return x * b + (long double) a / std::sqrt(1 + x);
}

int main() {
    std::cin >> a >> b;
    long double x = pow( a / (2 * b) , 2.0 / 3 ) - 1;
    ll x1 = x;
    long double ans = a;
    for (ll p = x1 - 10; p <= x1 + 10; ++ p) ans = std::min(ans,calc(p));
    printf("%.10Lf",ans);
    return 0;
}