这次的比赛比较简单，题目也不算很难。
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;
}
近期评论