• 估计也打不了多少 \(qwq\)

\(\Huge终于不垫底了。qwq\)

初三奥赛模拟测试2

T1南

题解

• 一道概率期望。
• 一般都是从 \(n\) 开始递推到 \(0\) 。
• 假设我们现在有 \(i\) 种枪，那么期望次数

• 因为当前有 \(i\) 种可能买到已经买过的枪， \(n-i\) 种可能买到未买过的枪。直接加上即可。
• 期望的价钱就是

• 假如每把枪的价格都是 \(1\) ，显然结果就是期望次数。
• 由于每次购买价格需要 \(+1\) ， 因此也很容易就能得出买到下一把枪的期望价钱就是买到这把枪的期望次数，直接乘起来即可。

代码

#include<bits/stdc++.h>
#define int long long
#define N (1000010)
#define I i
#define J j
#define raed read
#define reaD read
#define reAD read
#define rEAD read
#define READ read
#define REAd read
#define REad read
#define Read read
#define Reda read
#define redA read
#define reDA read
#define redA read
#define itn signed
#define Itn signed
#define ITN signed
#define Int signed
#define INT signed
#define foR for
#define fot for
#define foT for
#define sort stable_sort
using namespace std;
namespace IO
{
    #define ll long long
    const int MAX=1<<6;
    char buf[MAX],*p1=buf,*p2=buf;
    char obuf[MAX],*o=obuf;
    #define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<6,stdin),p1==p2)?EOF:*p1++)
    //template<typename T>
    //inline T read()
    inline int read()
    {
        int x=0;bool f=1;
        char c=gc();
        for(;c<48||c>57;c=gc())if(c=='-')f=0;
        for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
        return f?x:~x+1;
    }
    void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
    void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
    void write(ll x,char ed){pit(x);*o++=ed;}
    void flush(){fwrite(obuf,o-obuf,1,stdout);}
    #undef ll
}
using IO::read;using IO::write;using IO::flush;using std::complex;
inline int min(int x,int y){return y&((y-x)>>31)|x&(~(y-x)>>31);}
inline int max(int x,int y){return x&((y-x)>>31)|y&(~(y-x)>>31);}
inline void swap(int &x,int &y){x^=y^=x^=y;}
long long n,m;
void init_set()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
}
int tot,t,x,y;
int furina,fucaros;
double panzer[10010],nahida[10010];
signed main()
{
    init_set();
    n=read();
    for(int i(n-1);i>=0;--i)
    {
        nahida[i]=1.0*nahida[i+1]+1.0*n/(n-i);
        panzer[i]=1.0*panzer[i+1]+nahida[i]*1.0*n/(n-i);
    }
    printf("%.2f\n",panzer[0]);
    flush();
    return 0;
}

• 由于递推时只需要当前以及上一个状态，因此用四个变量即可替代。

#include<bits/stdc++.h>
#define int long long
#define N (1000010)
#define I i
#define J j
#define raed read
#define reaD read
#define reAD read
#define rEAD read
#define READ read
#define REAd read
#define REad read
#define Read read
#define Reda read
#define redA read
#define reDA read
#define redA read
#define itn signed
#define Itn signed
#define ITN signed
#define Int signed
#define INT signed
#define foR for
#define fot for
#define foT for
#define sort stable_sort
using namespace std;
namespace IO
{
    #define ll long long
    const int MAX=1<<6;
    char buf[MAX],*p1=buf,*p2=buf;
    char obuf[MAX],*o=obuf;
    #define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<6,stdin),p1==p2)?EOF:*p1++)
    //template<typename T>
    //inline T read()
    inline int read()
    {
        int x=0;bool f=1;
        char c=gc();
        for(;c<48||c>57;c=gc())if(c=='-')f=0;
        for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
        return f?x:~x+1;
    }
    void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
    void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
    void write(ll x,char ed){pit(x);*o++=ed;}
    void flush(){fwrite(obuf,o-obuf,1,stdout);}
    #undef ll
}
using IO::read;using IO::write;using IO::flush;using std::complex;
inline int min(int x,int y){return y&((y-x)>>31)|x&(~(y-x)>>31);}
inline int max(int x,int y){return x&((y-x)>>31)|y&(~(y-x)>>31);}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
long long n,m;
void init_set()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
}
int tot,t,x,y;
int furina,fucaros;
double panzer,sumeru,nahida,fontaine;
signed main()
{
    init_set();
    n=read();
    for(int i(n-1);i>=0;--i)
        nahida=fontaine+1.0*n/(n-i),
        panzer=1.0*sumeru+nahida*n/(n-i),
        fontaine=nahida,sumeru=panzer;
    printf("%.2f\n",panzer);
    flush();
    return 0;
}

• 最后发现竟然能优化成这样！

for(int i(n-1);i>=0;--i)
    panzer+=(nahida+=1.0*n/(n-i))*n/(n-i);
printf("%.2f\n",panzer);

• 直接用两个变量不断更新就可以了 \(qwq\) 。

\(\Huge因为根本没打。qwq\)