题目泰国尼添所以暴力挂一点分也能拿到 22/98Rank
A. BA
签到题。
总记得小时候在 《冒险岛数学奇遇记》 的第 28 册左右看到过这道题，关键在于你可以分次烙完一张饼。
举例
2 口锅 5 张饼，5 4 4 3 3，最优策略的一种是先将 5 的那张饼烙 3 单位时间，然后烙一张 4 一张 3；另一口锅先烙一张 4 一张 3，最后烙剩下 5 的那张 2 单位时间。
所以，在面最多的那张饼的面数与其他相差不是很大的情况下，我们可以取到最优结果为 \(\lceil{\frac{总时长}{锅的数量}}\rceil\)。
关键在找如何定义这个相差不大。我们思考一下，可以知道分次烙饼的条件是在烙完最多面饼目标时间（平均值）之内，其他锅都能保证一直在工作，这样我们分次烙饼才有意义。设共 \(n\) 口锅，所有饼的总面数为 \(sum\)，最多面数饼面数为 \(a_{max}\)，这样表示出来符合要求的判断即为 \(a_{max}\times n\le sum\)。
点击查看代码
赛时思路没有如上那么清晰，走了点弯路，但正确性是有的。
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx int
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=1e6+5;
const int mod=10007;
int n,m;
ll a[N];
bool cmp(ll a,ll b){return a>b;}
namespace Wisadel
{
short main()
{
n=qr,m=qr;ll sum=0;
fo(i,1,n) a[i]=qr,sum+=a[i];
sort(a+1,a+1+n,cmp);
ll ans=a[1];
if(a[1]*m<sum) ans+=(sum-a[1]*m+m-1)/m;
printf("%lld\n",ans);
return Ratio;
}
}
int main(){return Wisadel::main();}
B. BB
赛时想到了很接近的思路，但看了题解发现虽然接近但怎么想也想不到。
题意很明确，一个简单的博弈论，找到每个点的贡献值，从大往小选。
证明就很玄学了，如下：
现在突然就理解了 gtm1514 学长，博弈论并没有什么能够一直套用的东西，每道题有自己的结论。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx int
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=2e5+5;
const int mod=10007;
int n;
int hh[N<<1],to[N<<1],ne[N<<1],cnt;
int siz[N],dep[N],w[N];
namespace Wisadel
{
void Wadd(int u,int v)
{
to[++cnt]=v;
ne[cnt]=hh[u];
hh[u]=cnt;
}
void Wdfs(int u,int fa)
{
dep[u]=dep[fa]+1;siz[u]=1;
for(int i=hh[u];i!=-1;i=ne[i])
{
int v=to[i];
if(v==fa) continue;
Wdfs(v,u);
siz[u]+=siz[v];
}
}
short main()
{
memset(hh,-1,sizeof hh);
n=qr;int a;ll ans=0;
fo(i,1,n) w[i]=qr;
fo(i,2,n) a=qr,Wadd(a,i),Wadd(i,a);
Wdfs(1,0);
fo(i,1,n) w[i]=siz[i]-dep[i]-w[i];
sort(w+1,w+1+n);
reverse(w+1,w+1+n);
fo(i,1,n) if(i&1) ans+=w[i];
printf("%lld\n",ans);
return Ratio;
}
}
int main(){return Wisadel::main();}
C. BC
D. BD
末
回来了啊，下半第一场模拟赛，虽然还是被不知姓名的外校人员虐的很惨，但起码稳住了暴力分。
用 Mac 用出习惯了怎么办啊，现在反而觉得 Windows 鸡肋了。
具体如下
Mac 中一些常用快捷键：
复制粘贴是 Command - C 与 Command - V；
End 是 Command - →；
截图是 Command - Shift - 4，录屏是 - 5；
VSCode 中除了 Ctrl - Z 终止程序以外所有 Ctrl 均替换成 Command。
Command 就是 win 键。
除了 Safari 有时候开多了页面会卡死要刷新，别的都挺不错的，尤其是可以下载 VSCode 插件。
总之，回来了就塌下心来，别像上次和昨天某个宿舍一样坠机了。
完结撒花~
Objection！
