【2020普专提十连测Day7刷题赛】蜂国建设者
10pts
只有 \(9\) 种情况，手玩打表即可
20pts
设所有子六边形个数为 \(ans1\) ，面积之和为 \(ans2\) ，显然 \(ans=\frac{ans2}{ans1}\)
暴力枚举
Task 5 30pts
为方便叙述，本题解中使用 包含的单元格\(-1\) 表示边的长度，即为题目中所述边长 \(-1\)
这种性质下只有形如 \((1,1,x)\) 的子六边形，其面积为 \(3x+4\)
把每个子六边形简化成“中心线”上的一条线段
于是转化到了一维的情况，这个与这道题的简化版 讨论 方法是一样的
\(ans1\) ：枚举端点，$ ans1=\sum\limits_{i=1}^{c}(c-i+1) = c^2-\frac{c(c+1)}{2}+c = \frac{c(c+1)}{2} $
\(ans2\) ：枚举长度，$ ans2=\sum\limits_{i=1}^{c}(c-i+1)(3i+4)$
\(O(c)\) 已经可以轻松通过了
\(ans2\) 的式子可以进一步化开 \(O(1)\) 计算，具体可以参照 讨论 ，这里不过多赘述。最后得到的是 \(ans=c+5\)
结合以上方法可得到 \(40-50pts\)
#include<bits/stdc++.h>
using namespace std;
long long a,b,c;
int main(){
scanf("%lld%lld%lld",&a,&b,&c);
printf("%.3lf",1.0*(c+5));
}
6行代码就有 30pts ，是不是很良心
60pts
先固定三边 \(a\), \(b\), \(c\) ，考虑枚举每种子六边形对应的三边 \(i\), \(j\), \(k\)，计算个数
记边 \(x\) 的对边为 \(x'\) ，比如 \(a\) 的对边就是 \(a'\)
有一种想法是 \(i \leq a\) , \(j \leq b\), \(k \leq c\) ，这显然是错误的，以下是反例
显然正确的是 \(i+j \leq a+b\) , \(i+k \leq a+c\), \(j+k \leq b+c\) （可以补成等边三角形），因此 \(i\), \(j\), \(k\) 的范围不会太大，保证枚举的时间复杂度为 \(O(abc)\)
考虑如何计算一种大小的子六边形的个数 \(cal(i,j,k)\)
首先将它 \(j\) 和 \(k\) 交点放在 \(b\) 和 \(c\) 交点，显然当 \(a \leq b \leq c\) 时是做得到的
考虑一步一步向下移，每一步计算向左下和右下分别能走 \(l\) 和 \(r\) 步
模拟一下发现，前半段 \(l\) 和 \(r\) 是不变的，而后半段它们逐渐减小，直到有一个变为 \(0\)
\(l\) 和 \(r\) 是等价的，先只考虑 \(l\) ，假设移动了 \(t\) 步
记 \(i\) 向左下移动到直线 \(a\) 的距离为 \(b-j\)，
\(k'\) 向下移动到直线 \(c'\) 的距离为 \(a+b-i-j-t\)
显然 \(l=min(b-j,a+b-i-j-t)\)
同理 \(r=min(c-k,a+c-i-k-t)\)
再来考虑 \(t\) 的最大值，即是 **\(k'\) 向下移动到直线 \(c'\) 的距离 \(a+b-i-j\) **和 **\(j'\) 向下移动到直线 \(b'\) 的距离 \(a+c-i-k\) **的最小值
注意到自身的状态也要算，故
\(cal(i,j,k)=\sum\limits_{t=0}^{min(a+b-i-j,a+c-i-k)}(min(b-j,a+b-i-j-t)+min(c-k,a+c-i-k-t)+1)\)
需要注意负数， \(b-j \geq 0\) ， $ c-k \geq 0$ ，可以直接在枚举时剪枝优化（优化 \(1\) ）
前面提到 \(i+j \leq a+b\) , \(i+k \leq a+c\), \(j+k \leq b+c\)
固定 \(i\) 的范围，就可以枚举 \(j \leq a+b-i\) ， \(k \leq a+c-i\) （优化 \(2\) ）
至于计算 \(ans2\) ，分割可知每个子六边形的面积为 \(S(i,j,k)=i(j+1)+j(k+1)+k(i+1)+1\)
时间复杂度 \(O((abc)^2)\)
常数小，可以通过 \(Task \ 1,2,3,5 +Task \ 4_1\) \(75pts\)
还要注意只有当 \(a \leq b \leq c\) 时才能这样做，否则会出现这种情况
显然 \(ans(a,b,c)=ans(a,c,b)\) ，在开始时需要将 \(a,b,c\) 从小到大排序，否则只有 \(50 pts\)
#include<bits/stdc++.h>
using namespace std;
long long a,b,c;
long long ans1,ans2;
long long cal(long long i,long long j,long long k){
long long ans=0;
long long x=a+b-i-j;
long long y=a+c-i-k;
while(x>=0 && y>=0){
ans+=min(x,b-j)+min(y,c-k)+1;
x--;y--;
}
return ans;
}
int main(){
scanf("%lld%lld%lld",&a,&b,&c);
if(a>b) swap(a,b);if(b>c) swap(b,c);if(a>b) swap(a,b);
a--,b--,c--;
for(long long i=1;i<=a+min(b,c);i++)
for(long long j=1;j<=min(b,a+b-i);j++)
for(long long k=1;k<=min(c,a+c-i);k++){
long long t=cal(i,j,k);
ans1+=t;
ans2+=t*(i*(j+1)+j*(k+1)+k*(i+1)+1);
}
printf("%.3lf",1.0*ans2/ans1);
}
85-100pts
考虑优化 \(cal(i,j,k)\)
前提还是有 \(b-j \geq 0\) ， $ c-k \geq 0$ ； \(i+j \leq a+b\) , \(i+k \leq a+c\), \(j+k \leq b+c\)
令 \(lim=min(a+b-i-j,a+c-i-k)\)
\(cal(i,j,k)\)
\(=\sum\limits_{t=0}^{lim}(min(b-j,a+b-i-j-t)+min(c-k,a+c-i-k-t)+1)\)
\(=\sum\limits_{t=0}^{lim}(min(0,a-i-t)+b-j+min(0,a-i-t)+c-k+1)\)
\(=2\sum\limits_{t=0}^{lim}min(0,a-i-t)+(b-j+c-k+1)(lim+1)\)
现在只考虑前面那部分，当 \(t \leq a-i\) 时为 \(0\) ，否则为 \(a-i-t\) ，再令 \(d=max(0,a-i+1)\) ，所以
\(cal(i,j,k)=2\sum\limits_{t=d}^{lim}(a-i-t)+(b-j+c-k+1)(lim+1)\)
若 \(d>lim\) ，则 \(cal(i,j,k)=(b-j+c-k+1)(lim+1)\)
否则，
\(cal(i,j,k)\)
\(=-2\sum\limits_{t=d}^{lim}t+2(a-i)(lim-d+1)+(b-j+c-k+1)(lim+1)\)
\(=-(d+lim)(lim-d+1)+2(a-i)(lim-d+1)+(b-j+c-k+1)(lim+1)\)
\(=(2a-2i-d-lim)(lim-d+1)+(b-j+c-k+1)(lim+1)\)
这个式子已经可以 \(O(1)\) 计算出 \(cal(i,j,k)\) 了
还可以把 \(cal\) 直接搬到主函数来
时间复杂度 \(O(abc)\)
已经可以通过本题
不优化只能得到 \(85pts\)
#include<bits/stdc++.h>
using namespace std;
long long a,b,c;
long long ans1,ans2;
int main(){
scanf("%lld%lld%lld",&a,&b,&c);
a--,b--,c--;
if(a>b) swap(a,b);if(b>c) swap(b,c);if(a>b) swap(a,b);
for(long long i=1;i<=a+min(b,c);i++){
for(long long j=1;j<=min(b,a+b-i);j++){
for(long long k=1;k<=min(c,a+c-i);k++){
long long t=0;
long long lim=min(a+b-i-j,a+c-i-k);
long long d=max(0LL,a-i+1);
if(d<=lim) t=(lim-d+1)*(2*a-2*i-d-lim);
t+=(b-j+c-k+1)*(min(a+b-i-j,a+c-i-k)+1);
ans1+=t;
ans2+=t*(i*(j+1)+j*(k+1)+k*(i+1)+1);
}
}
}
printf("%.3lf",1.0*ans2/ans1);
}