C. RANDOM
题意：给你两个 01 矩阵 \(S,T\)，问是否可以将 \(S\) 以列为单位重新排列得到 \(T\)。
判断 \(S,T\) 的每列是否可以一一对应即可
做法一
以列为单位提取成字符串，\(S,T\) 分别排序比较即可。
By cxm1024
#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
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
题意：一个小球下落时间为 \(\frac{A}{\sqrt{g}}\)，初始时 \(g=1\)，每次可以花费 \(B\) 的时间将 \(g\) 增加 \(1\)，问最小总时间。
题意转化为求 \(\frac{A}{\sqrt{x+1}}+Bx\) 的最小值。
做法一
容易证明该函数为一个下凸函数，所以可以使用三分法。
By cxm1024
#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;
}
做法二
找最小值相当于这个函数的导数等于 \(0\)，而下凸函数的导函数单调上升，所以可用二分求解。
实际计算中，只需要计算 \(f(x)-f(x-1)\)，粗略地将其作为导数的近似来二分即可。
By Kude
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}')
做法三
考虑答案关于 \(g\) 的函数 \(f(g)=\frac{A}{\sqrt{g}}+B(g-1)\)，由于最小值与常数无关，所以可以看成 \(f(g)=\frac{A}{\sqrt{g}}+Bg\)，则由均值不等式：
\[\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} \]由此可知函数最小值不会小于 \(3\sqrt[3]{\frac{A^2B}{4}}\)，取等条件为 \(\frac{A}{2\sqrt{g}}=Bg\)，即 \(g=(\frac{A}{2B})^\frac{2}{3}\)。
#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;
}