这次的比赛比较简单，题目也不算很难。

A

题目原文

题意

给定一个数列 $a$ 的首项 $a _ 1(1\leq a _ 1\leq 10^{18})$ 和 $k(1\leq k\leq 10^{16})$，求 $a _ k$。多组数据，数据组数为 $t(1\leq t\leq 10^3)$。

数列 $a$ 的递推公式为：

$$a _ {n+1}=a _ n+\operatorname{minDigit}(a _ n)\cdot \operatorname{maxDigit}(a _ n)$$

题解

思路

很简单的一道题目，显然发现递推的次数很少，递推了几项之后就会有 $\operatorname{minDigit}(a _ n)=0$，这个时候就可以直接跳出循环了。

代码

很简短。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline ll read(void){
    reg char ch=getchar();
    reg ll res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

inline ll Get(reg ll a){
    int Min=10,Max=0;
    while(a){
        Max=max(Max,(int)(a%10)),
        Min=min(Min,(int)(a%10));
        a/=10;
    }
    return Max*Min;
}

int main(void){
    reg int T=read();
    while(T--){
        reg ll a=read(),K=read();
        while(--K){
            reg ll sum=Get(a);
            if(!sum)
                break;
            else
                a+=sum;
        }
        printf("%lld\n",a);
    }
    return 0;
}

B

题目原文

题意

总共 $n(1\leq n\leq 2\times 10^5)$ 个人，每个人有一个属性 $e _ i(1\leq e _ i\leq n)$，每个人只能在人数大于等于 $e _ i$ 的队伍中，问最多能有多少支队伍。多组数据，数据组数为 $T(1\leq T\leq 2\times 10^5)$，保证 $\sum n\leq 3\times 10^5$。

题解

思路

解法显然是贪心。

先对每个人按照 $e$ 排个序，然后对于每个人，如果到他这里刚刚好满足条件，就组成一个队伍，以节省剩下的人数。显然正确。

代码

这种做法的时间复杂度为 $\Theta(\sum n\log _ 2n)$。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXN=200000+5;

int n;
int a[MAXN];

int main(void){
    reg int T=read();
    while(T--){
        n=read();
        for(reg int i=1;i<=n;++i)
            a[i]=read();
        sort(a+1,a+n+1);
        reg int cnt=0,ans=0;
        for(reg int i=1;i<=n;++i){
            ++cnt;
            if(a[i]==cnt){
                cnt=0;
                ++ans;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

C

题目原文

题意

给定四个数 $a,b,c,d(1\leq A\leq B\leq C\leq D\leq 5\times 10^5)$，求满足三条边长为 $x,y,z$ 且 $A\leq x\leq B\leq y\leq C\leq z\leq D$ 的三角形的个数。

题解

思路

考虑枚举，然后这道题就做完了。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

int a,b,c,d;

int main(void){
    a=read(),b=read(),c=read(),d=read();
    reg ll ans=0;
    for(reg int i=a;i<=b;++i){
        ll Min=b+i-1,Max=c+i-1;
        if(Min>=d)
            ans+=(ll)(d-c+1)*(c-b+1);
        else{
            reg ll l=max(c,b+i-1),r=min(d,c+i-1);
            ans+=((ll)(r-l+1)*(l-c+1+r-c+1)>>1);
            if(Max>d)
                ans+=(ll)(Max-d)*(d-c+1);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

D

题目原文

题解

思路

构造一种解法，数列 $a _ n$ 中有 $n-1$ 个 $1$ 和 $1$ 个 $s-n+1$，判定条件是 $2n<s$。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

int n,s;

int main(void){
    n=read(),s=read();
    if((n<<1)>s)
        puts("NO");
    else{
        puts("YES");
        for(reg int i=1;i<=n;++i)
            printf("%d%c",i==n?(s-(n-1)):1,i==n?'\n':' ');
        printf("%d\n",n);
    }
    return 0;
}

E

题目原文

题解

思路

首先先考虑把 $c$ 换成 $\min(c,a+b)$，然后再用三分求函数极小值即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXN=100000+5;

ll n,a,b,c;
ll h[MAXN];
ll sum[MAXN];

inline ll check(int mid){
    reg int before=upper_bound(h+1,h+n+1,mid)-(h+1),after=n-before;
    reg ll sum1=sum[before],sum2=sum[n]-sum1;
    ll up=sum2-(ll)after*mid,down=(ll)mid*before-sum1;
    reg ll Min=min(down,up);
    return min(down*a+up*b,Min*c+(up-Min)*b+(down-Min)*a);
}

int main(void){
    n=read(),a=read(),b=read(),c=read();
    c=min(c,a+b);
    for(reg int i=1;i<=n;++i)
        h[i]=read();
    sort(h+1,h+n+1);
    for(reg int i=1;i<=n;++i)
        sum[i]=sum[i-1]+h[i];
    reg int l=0,r=1e9,mid;
    ll ans=3e18;
    while(r-l>1){
        mid=(l+r)>>1;
        ll val1=check(mid),val2=check(mid+1);
        ans=min(ans,min(val1,val2));
        if(!ans){
            puts("0");
            return 0;
        }
        if(val1<val2)
            r=mid-1;
        else
            l=mid+1;
    }
    for(reg int i=l-1;i<=r+1;++i)
        ans=min(ans,check(i));
    printf("%lld\n",ans);
    return 0;
}

F

题目原文

题解

思路

还是比较好做的一道题目。

考虑到

$$x=\prod p _ i^{c _ i}$$

$$\sigma _ 0(x)=\prod (c _ i+1)$$

首先考虑减少查询操作，不难发现，$Q$ 总应该是一个质数的幂积的形式，这样可以最快得到答案。

考虑到 $x\leq 10^9$，假设 $x=x _ 1x _ 2$，其中 $x _ 1$ 我们已经知道而 $x _ 2$ 我们不知道但可以确定的是它没有多于 $t$ 个质因子（包括幂）。那么 $\sigma _ 0(x _ 1)\leq \sigma _ 0(x)\leq\sigma _ 0(x _ 1)\sigma _ 0(x _ 2)\leq\sigma _ 0(x _ 1)2^t$。

经过分析不难发现，答案已经近在眼前，还是看看代码吧。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

const ll p[17]={19634730635520000ll,67665248476907597ll,877779077635511999ll,15031861979012587ll,239868713978954299ll,8100049778130103ll,32826117705688133ll,96265407405451883ll,260006624961107813ll,707992818804600227ll,3676594834162829ll,6402204344683229ll,9797084445859807ll,15916020492768661ll,27616086651273059ll,41286304414422503ll,229580147ll};

int T;

int main(void){
    scanf("%d",&T);
    while(T--){
        reg ll x=1;
        for(reg int i=0;i<17;++i){
            static ll y;
            cout<<"? "<<p[i]<<endl;
            cin>>y;
            x*=y;
        }
        reg ll ans=1;
        for(reg int i=2;i<=800;++i){
            reg int c=0;
            while(x%i==0){
                x/=i;
                ++c;
            }
            ans*=c+1;
        }
        cout<<"! "<<max(8ll,ans<<1)<<endl;
    }
    return 0;
}