2021 ICPC 上海 M Harmony in Harmony 构造
Published:
题目
题意有点绕，大概意思就是，现在你要将2个完全一样的区域都分成n份，且这n份的面积也都相同，我们将每一份区域定一个id(理解为1-n的排列)，问怎么分使得这俩个区域，相同id的子区域相交之后的共有的面积，n个共有面积的最小值能取到多少。
解法
我们将题意转化一下，把这俩次划分看成一张二分图，在所有可能的排列中，那么第一次划分的第$i$号点和第二次划分的所有可能出现$i$的$n$个位置的面积并之和就是1/n,即它自己面积本身。即这是一个满二分图，其中每一个节点，其所连边的权值和为$1/n$ 那么现在我们就将题意转化成了要求寻找⼀个尽可能⼤的$ans$，使得在任何满⾜上述条件的⼆分图下，都能够找到⼆分图的完美匹配，使得匹配边的权值都不低于$ans$
容易想到一定存在一个$ans=\frac{1}{n^2}$的构造，但这显然不是最优解。官方题解给了一个很巧妙的思路，我们现在取前$t$个白点,将其和前$t-1$个黑点连边，每条边的权值都为$\frac{1}{nt}$,那么显然这$t-1$个黑点的权值已经连完了，而每个白点还剩下$\frac{1}{nt}$的权值可以连给其它黑点，我们将$\frac{1}{nt}$平均分给剩下的$n-t+1$个黑点，然后这些黑点再和剩下的$n-t$个白点连边，可以发现在所有连边中，最小的权值便为$\frac{1}{nt(n-t+1)}$
现在尝试证明$nt(n-t+1)>=n^2$
现在$t$是未知数，进行二次函数展开化简后即证明$-nt^2+(n^2+n)t-n^2>=0$
进行求根后可得$x1=1,x2=2n$,又因为这个函数开口向下，且$t\in[1,n]$，所以证明完毕。
因此对于$nt(n-t+1)$这个函数，所能取到的最大值就是当$t=\frac{n+1}{2}$（对称轴）的时候，因为$t$属于整数域，所以当$t$为偶数的时候，最大值取不到，要取其左右俩边。综上，该函数的最大值就是$n \lfloor \frac{n+1}{2} \rfloor \lfloor \frac{n+2}{2} \rfloor$
对应答案的最小值就是，$\frac{1}{n \lfloor \frac{n+1}{2} \rfloor \lfloor \frac{n+2}{2} \rfloor}$，直接输出即可
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define set9 fixed<<setprecision(9)
#define set12 fixed<<setprecision(12)
#define set2 fixed<<setprecision(2)
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pii pair<int,int>
#define pll pair<long long,long long>
#define db double
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=2e5+5;
const ll mod=1e9+7;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; }
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll Inverse(ll x) { return qpow(x,mod-2);}
int main()
{
int n;
cin>>n;
int t1=(n+1)/2,t2=(n+2)/2;
double val=n*t1*t2;
double ans=(1.000000)/val;
cout<<set9<<ans<<endl;
}