题解：P10402 「XSOI-R1」凑点

· · 题解

写一篇不用二分的题解。

思路

首先我们发现，题目中可以这么修改：

pow f，将计数器 x 变为 x^f，f 可以为浮点数。

我们可以观察下幂函数 y=2^x 的图像：

在 x \ge 0 时，值域为 [1,\infty)。也就是说，我们可以直接执行一次 pow 操作，使其变成任何大于等于 1 的数。接着发现 \sum_{i=1}^n a_i\le10^{10}。我们可以直接花 n 次操作把 x 变为 \sum_{i=1}^n a_i。

接着就是这个式子：

x^p=c\\p=\log_xc

根据换底公式用 c++ 自带的 \log 函数即可，操作次数 n+1。

注意 c 可能为 0，当 c=0 时方法就不多说了，操作次数 n。

代码

#include<bits/stdc++.h>
#define int long long
int n,x,y,X;
signed main(){
    scanf("%lld%lld%lld",&n,&x,&y),x=0;
    if(y==0){
        printf("%lld\n",n);
        for(int i=1;i<=n;i++)scanf("%lld",&X),printf("mul %lld\n",i);
        return 0;
    }
    printf("%lld\n",n+1);
    for(int i=1;i<=n;i++)scanf("%lld",&X),x+=X,printf("add %lld\n",i);
    long double ans=log10(y)*1.0000/log10(x),s=pow(x,ans);//此处用 log,log2都行
    if(fabs(s-y)>1e-4)while(printf("sto wmr orz"));
    printf("pow %.114510Lf",ans);
    return 0;
}