前言
一个月前的一场悲剧qwq 传送门
没事干写的qwq
热乎着的一道题，昨晚上刚考完，然而这是一场悲剧。。。。
题解
题目大意
给定 \(a_1 ~ a_n\) 和 \(c\) ，求 \((a_1+2\times w)^2+(a_2+2\times w)^2+...+(a_n+2\times w)^2=c\) 时 \(w\) 的最小值
解析
我们来化简一下这个式子：
\((a_1+2\times w)^2+(a_2+2\times w)^2+...+(a_n+2\times w)^2\)
根据完全平方公式 \((a+b)^2=a^2+b^2+2ab\) （对！初一数学！）可得
原式\(=(a_1)^2+(2\times w)^2+2\times a_1\times (2\times w)+(a_2)^2+(2\times w)^2+2\times a_2\times (2\times w)+...+(a_n)^2+(2\times w)^2+2\times a_n\times (2\times w)\)
\(=\begin{aligned}\sum_{i=1}^{i\le n} (a_i)^2+n(2\times w)^2+(\sum_{i=1}^{i\le n} 2\times a_i)\times (2\times w)\end{aligned}\)
所以预处理出 \(\begin{aligned}\sum_{i=1}^{i\le n} (a_i)^2\end{aligned}\)=sum1，\(\begin{aligned}(\sum_{i=1}^{i\le n} 2\times a_i\end{aligned})\)=sum2 即可。
然后考虑二分 \(w\) ，check 函数这样子写：
inline bool check(ll x){
ll t=x*2;
return sum1+t*t*n+sum2*t<=c;
}
代码
思路很简单，那么就直接给出代码吧qwq！
#include <bits/stdc++.h>
#define i128 __int128 //不开int128见祖宗
using namespace std;
i128 T,n,c,t,sum1,sum2; //sum1 sum2见上
template<typename T> inline void read(T& n){
T x=0;bool f=1; //int128特有的快读快写（悲）
char c=getchar();
while(c<48||c>57)
f=c!=45,c=getchar();
while(c>47&&c<58)
x=(x<<3)+(x<<1)+(c^48),c=getchar();
n=f?x:-x;
}
template<typename T> void write(T x){
if(x<0) putchar(45),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
inline bool check(i128 x){
i128 t=x*2; //check，见上
return sum1+t*t*n+sum2*t<=c;
}
int main(){
ios::sync_with_stdio(0);
read(T);
while(T--){
read(n),read(c),sum1=0,sum2=0;
for(int i=1;i<=n;i++)
read(t),sum1+=t*t,sum2+=2*t; //预处理
i128 l=0,r=1e9,mid;
while(l<=r){ //二分
mid=l+r>>1;
if(check(mid)) l=mid+1;
else r=mid-1;
}
write(r),puts("");
}
return 0;
}
彩蛋
聊聊赛时的一场悲剧：
还剩最后22分钟时，跟 cyh 交流出了解法，她表示：我不想打了，感觉调不出来了。
但是本蒟蒻上次被 Skipped 的Div.4（5.6那次）可是做了 5 道，可不能成为耻辱，上次加了164Rating！
然后就开始调二分了，然而一直卡题，卡了7次到处改都是WA在Test4。
当时打的是：
#define ll __int128 //C++17,GCCmsys2 64bit能过
...
ll l=0,r=c,mid; //r太大了！！！，l=0用不着
while(l<r){ //PS：原版题解里的l<=r是怕玄学，实际上一样的
mid=l+r>>1;
if(check(mid)) l=mid+1;
else r=mid;
}
时间飞逝，比赛结束，最后一次提交依然没过，难绷。
本来想打一个高精度的，但是感觉时间会炸就没打（实际上如果用python一切都能避免只可惜来不及改了）。
比赛完时突然想到 unsigned __int128 ，改了一下: #define ll unsigned __int128
比赛完之后大概 1:39 分时， CF 服务器终于不卡了，于是又提交上去，过了？
还我 T5，unsigned 我*************！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
真蚌埠住了，这场玩飘了。
然后根据 czy 在犇犇里说的 r=1e9 就行，改了一下，换回 signed __int128 就过了。。。。。。。
这份也是题解里面的版本。