题解 T216141 [WFOI - 01] 硬币（coin

__ex · 2021-12-25 21:21:47 · 题解

\color{orange}\text{前言}

这是蒟蒻的第一篇题解，顺便为AC200做纪念

无耻求管理员通过

话不多说，切入正题

\color{orange}\text{题目大意}

给一些硬币，分为n堆，每一堆有着不同的面值，分别为a_1，a_2，a_3...，a_n任意两堆有着相同的硬币数量。求一个数量，使得每一堆的硬币数量都为这个数时，当前的方差最接近于给定的k。若方差为0，输出"No\ answer!"

\color{orange}\text{正文}

这是一道数数思维题。

因为是月赛，像我这种辣鸡是不可能做出第一题的。所以先想着骗分。所以第一步就是特判方差为0的特殊情况。显然，根据数学书对方差的定义，只当a_1=a_2=a_3...=a_n时，方差为0。

于是就轻而易举骗了0分

因为是月赛，0分未免过于丢脸，于是就有了继续。

根据数学书对方差的定义，我们有一句废话：

而当每一堆硬币的数量为p时，我们有了一句新的废话：

试着化简这句废话，可以得到：

从而得到：

回归本题，S^2可以直接求，要使newS^2最接近k，可以直接计算出期望のp=\sqrt{\dfrac{k}{S^2}}

而此时p不一定是整数，涉及到平方根，也不能直接四舍五入，所以需要计算出p_1=\left\lfloor\sqrt{\dfrac{k}{S^2}}\right\rfloor与p_2=\left\lceil\sqrt{\dfrac{k}{S^2}}\right\rceil两种情况，比较与k更接近的一个。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
using namespace io;
const int mn=7e6+10;
const int mm=1e6+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int fni=0xc0c0c0c0;
int n,k;
bool f0;
int a[mn];
inline void read_init(){
    n=read<int>(),k=read<int>();
    for(int i=1;i<=n;i++){
        a[i]=read<int>();
        if(a[i]!=a[1])f0=1;
    }
}
int main(){
    read_init();
    if(!f0){
        puts("No answer!");
        return 0;
    }
    long double ba=0;
    for(int i=1;i<=n;i++)
        ba+=a[i];
    ba/=n;long double fc=0;
    for(int i=1;i<=n;i++)
        fc+=(a[i]-ba)*(a[i]-ba);
    fc/=n;
    double o=sqrt(k/fc);
    int oo=o,ooo=o+1;
    long double p=oo*oo*fc,pp=ooo*ooo*fc;
    if((p-k)*(p-k)>(pp-k)*(pp-k))write(ooo,1);
    else write(oo,1);
    return 0;
}

此代码已省略快读快写

嗯？别走啊，现在只有20分哦！

因为是月赛，还是要继续写对吧。柿子没推错，只可能爆int了。试着开让无数OIer邂逅祖宗的long long

emm...45分了！

继续开__int128

嗯？怎么还是45分？

至于这种情况，我们得好好读一读题

你需要确定一个\large\color{blue}\text{正整数} x，使得每堆硬币的总金额的 方差 最接近于一个正整数 k。

说句闲话，0\notin N^+

所以...

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
using namespace io;
const int mn=7e4+10;
const int mm=1e6+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int fni=0xc0c0c0c0;
ll n,k;
bool f0;
ll a[mn];
inline void read_init(){
    n=read<ll>(),k=read<ll>();
    for(int i=1;i<=n;i++){
        a[i]=read<ll>();
        if(a[i]!=a[1])f0=1;
    }
}
int mian(){
    read_init();
    if(!f0){
        puts("No anwser!");
        return 0;
    }
    long double ba=0;
    for(ll i=1;i<=n;i++)
        ba+=a[i];
    ba/=n;long doubel fc=0;
    for(ll i=1;i<=n;i++)
        fc+=1.0*(1.0*a[i]-ba)(1.0*a[i]-ba);
    fc/=n;
    long double o=sqrt(1.0*k/fc);
    ll p=o,pp=o+1;
    if(!p && pp==1){
        puts("1");
        return 0;
    }
    if(fabs(1.0*pp*pp-k/fc)<fabs(1.0*p*p-k/fc)){
        write(pp,1);
        return 0;
    }
    write(p,1);
    return 0;
}

此代码已省略快读快写

可能不止改动了快读快写（