20240123 A 组模拟赛 题解
前言
爆零，然后被 OPJ 骂破防。
T1
算是简单题吧。但是赛时以为复杂度假了于是就没写。
首先容易发现数位积的质因数必定只含有 $2,3,5,7$，那么可以数位 DP 求出每个数位积的出现次数。
然后考虑枚举 $\gcd$，容易发现 $a$ 是 $\gcd$ 的倍数当且仅当 $a$ 的四个质因子指数都不大于 $\gcd$ 的对应指数。这个可以四维后缀和求，接着平方后做简单容斥即可求出 $\gcd$ 恰好等于你选的数的数对 $(i,j)$。
然后就过了，因为可以发现可能出现的数位积是不多的。往多了说最多也就 $(18\times 3)\times(18\times 2)\times 18\times 18$ 个数，实际请款肯定远小于它。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=25,inf=0x3f3f3f3f,mod=998244353;
i64 n,m,a[N],cntn,sum[N*3][N*2][N][N],ans;
struct state{
int c2,c3,c5,c7;
bool operator <(const state &r)const{
if(c2!=r.c2) return c2<r.c2;
if(c3!=r.c3) return c3<r.c3;
if(c5!=r.c5) return c5<r.c5;
return c7<r.c7;
}
state operator +(const state &r){
state res=state{0,0,0,0};
res.c2=c2+r.c2;
res.c3=c3+r.c3;
res.c5=c5+r.c5;
res.c7=c7+r.c7;
return res;
}
};
map<state,int> dp[25][2];
state ad[10]={
{0,0,0,0},
{0,0,0,0},
{1,0,0,0},
{0,1,0,0},
{2,0,0,0},
{0,0,1,0},
{1,1,0,0},
{0,0,0,1},
{3,0,0,0},
{0,2,0,0},
};
i64 ksm(i64 a,int b){
i64 c=1;
while(b){
if(b&1) c*=a;
a*=a;
b>>=1;
}
return c;
}
i64 calc(int c2,int c3,int c5,int c7){
return ksm(2,c2)*ksm(3,c3)*ksm(5,c5)*ksm(7,c7);
}
int Get(int i,int j,int k,int l){
i64 res=0;
res=sum[i][j][k][l];
res=((res-sum[i+1][j][k][l]-sum[i][j+1][k][l]-sum[i][j][k+1][l]-sum[i][j][k][l+1])%mod+mod)%mod;
res=(res+sum[i+1][j+1][k][l]+sum[i+1][j][k+1][l]+sum[i+1][j][k][l+1])%mod;
res=(res+sum[i][j+1][k+1][l]+sum[i][j+1][k][l+1])%mod;
res=(res+sum[i][j][k+1][l+1])%mod;
res=((res-sum[i+1][j+1][k+1][l]-sum[i+1][j+1][k][l+1]-sum[i+1][j][k+1][l+1]-sum[i][j+1][k+1][l+1])%mod+mod)%mod;
res=(res+sum[i+1][j+1][k+1][l+1])%mod;
return res;
}
signed main(){
n=read();m=read();
while(n){
a[++cntn]=n%10;
n/=10;
}
dp[cntn][0][state{0,0,0,0}]=1;
fordown(i,cntn-1,1) dp[i][1][state{0,0,0,0}]=1;
fordown(i,cntn,1){
for(auto j:dp[i][0]){
state nw=j.fi;
if(a[i]!=0) (dp[i-1][0][nw+ad[a[i]]]+=j.se)%=mod;
forup(k,1,a[i]-1){
(dp[i-1][1][nw+ad[k]]+=j.se)%=mod;
}
}
for(auto j:dp[i][1]){
state nw=j.fi;
forup(k,1,9){
(dp[i-1][1][nw+ad[k]]+=j.se)%=mod;
}
}
}
for(auto i:dp[0][0]) (sum[i.fi.c2][i.fi.c3][i.fi.c5][i.fi.c7]+=i.se)%=mod;
for(auto i:dp[0][1]) (sum[i.fi.c2][i.fi.c3][i.fi.c5][i.fi.c7]+=i.se)%=mod;
fordown(i,cntn*3,0) fordown(j,(cntn-i/3)*2,0) fordown(k,cntn-i/3-j/2,0) fordown(l,cntn-i/3-j/2-k,0) (sum[i][j][k][l]+=sum[i+1][j][k][l])%=mod;
fordown(i,cntn*3,0) fordown(j,(cntn-i/3)*2,0) fordown(k,cntn-i/3-j/2,0) fordown(l,cntn-i/3-j/2-k,0) (sum[i][j][k][l]+=sum[i][j+1][k][l])%=mod;
fordown(i,cntn*3,0) fordown(j,(cntn-i/3)*2,0) fordown(k,cntn-i/3-j/2,0) fordown(l,cntn-i/3-j/2-k,0) (sum[i][j][k][l]+=sum[i][j][k+1][l])%=mod;
fordown(i,cntn*3,0) fordown(j,(cntn-i/3)*2,0) fordown(k,cntn-i/3-j/2,0) fordown(l,cntn-i/3-j/2-k,0) (sum[i][j][k][l]+=sum[i][j][k][l+1])%=mod;
fordown(i,cntn*3,0) fordown(j,(cntn-i/3)*2,0) fordown(k,cntn-i/3-j/2,0) fordown(l,cntn-i/3-j/2-k,0) sum[i][j][k][l]=1ll*sum[i][j][k][l]*sum[i][j][k][l]%mod;
forup(i,0,cntn*3){
forup(j,0,(cntn-i/3)*2){
forup(k,0,cntn-i/3-j/2){
forup(l,0,cntn-i/3-j/2-k){
if(calc(i,j,k,l)<=m){
(ans+=Get(i,j,k,l))%=mod;
}
}
}
}
}
printf("%lld\n",ans);
}
T2
套路题，会套路就简单，不会就难。
这种元素数量很多，并且有大小关系，让你求第 $k$ 大的题可以考虑随机二分。
考虑二分是每次选中间元素 $a$，然后将所有元素划为严格小于 $a$ 与大于等于 $a$ 两类。判断 $a$ 的排名，然后在答案存在的那一边做子问题。
但是这道题不好找“中间”的一个元素。那么就可以随机一个 $a$，在期望情况下也是 $O(\log n^2)=O(\log n)$ 的。
那么怎么求有多少个区间小于 $a$ 呢？这个可以在值域上开一个线段树维护每个数的出现次数，然后用双指针维护，每次找到第一个出现次数不同的数判断谁更大然后挪动双指针即可。这部分复杂度 $O(n\log n)$。
然后对每个右端点存没被删掉的左端点区间即可。总复杂度 $O(n\log^2 n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1<<17,inf=0x3f3f3f3f;
int n,a[N];
i64 m;
int mark[N<<1];
int L[N],R[N];
mt19937 mr(time(0));
int Rd(int l,int r){
return (unsigned int)mr()%(r-l+1)+l;
}
void Update(int P,int X){
mark[N+P]+=X;
for(int i=(N+P)>>1;i;i>>=1) mark[i]=mark[i<<1]?mark[i<<1]:mark[i<<1|1];
}
set<int> ext;
int al,ar;
vector<int> ans;
signed main(){
n=read();m=read();
forup(i,1,n) a[i]=read();
forup(i,1,n){
ext.insert(i);
L[i]=1;R[i]=i;
}
forup(i,1,60){
int u=Rd(0,ext.size()-1);
set<int>::iterator it=ext.begin();
forup(i,1,u) ++it;
int r=*it,l=Rd(L[r],R[r]);
mem(mark,0);
forup(i,l,r) Update(a[i],1);
int pl=1;
i64 res=0;
forup(pr,1,n){
Update(a[pr],-1);
while(pl<=pr&&mark[1]<0){
Update(a[pl],1);
++pl;
}
res+=pl-1;
}
pl=1;
if(res<m){
al=l,ar=r;
}
mem(mark,0);
forup(i,l,r) Update(a[i],1);
forup(pr,1,n){
Update(a[pr],-1);
while(pl<=pr&&mark[1]<0){
Update(a[pl],1);
++pl;
}
if(L[pr]<=R[pr]){
if(res<m){
L[pr]=max(L[pr],pl);
}else{
R[pr]=min(R[pr],pl-1);
}
if(L[pr]>R[pr]) ext.erase(pr);
}
}
}
forup(i,al,ar){
ans.push_back(a[i]);
}
sort(ans.begin(),ans.end());
for(auto i:ans){
printf("%d ",i);
}
puts("");
}
T3
看起来像数据结构，但是核心更像是模拟题。
考虑有两种情况，一种是占用某一个空行的正中间，另一种是紧靠在某一个用过的点的左边或右边。
第一种容易发现只有两行（上下各一行）是不劣的，这个可以直接维护。
考虑第二种，容易想到在空格长度上开线段树，然后再用线段树维护剩下三个条件最优的情况。
那么如何维护曼哈顿距离和呢？考虑一个完全在中线左侧的区间 $(x,[l,r])$。此时曼哈顿距离和就是 $(x,r)$ 与中点的距离 $dis$ 乘以 $r-l+1$ 再加上一个等差数列。而这个等差数列在固定长度的情况下显然是个定值。那么维护那个距离即可。
然后具体实现可以在线段树叶子上开 set 即可。我代码的实现比较劣，复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=3e5+5;
const i64 inf=1e18;
i64 n,m,w;
i64 mdis(i64 x,i64 y){
return abs(w-x)+abs(w-y);
}
struct Node{
i64 x,y;
bool operator <(const Node &r)const{
if(mdis(x,y)!=mdis(r.x,r.y)) return mdis(x,y)<mdis(r.x,r.y);
if(x!=r.x) return x<r.x;
return y<r.y;
}
};
set<Node> ss[N];
set<i64> ups,dws;
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
Node querymin[N<<2];
void Build(i64 l=1,i64 r=m,i64 id=1){
querymin[id]=Node{inf,inf};
if(l==r) return;
Build(lson);Build(rson);
}
void Update(i64 P,Node X,i64 l=1,i64 r=m,i64 id=1){
if(l==r){
querymin[id]=X;
return;
}
if(P<=mid) Update(P,X,lson);
else Update(P,X,rson);
querymin[id]=min(querymin[id<<1],querymin[id<<1|1]);
}
Node Query(i64 L,i64 R,i64 l=1,i64 r=m,i64 id=1){
if(L<=l&&r<=R){
return querymin[id];
}
Node res=Node{inf,inf};
if(L<=mid) res=min(res,Query(L,R,lson));
if(mid< R) res=min(res,Query(L,R,rson));
return res;
}
}mt;
signed main(){
n=read();m=read();w=(m+1)/2;
forup(i,1,w) ups.insert(i);
forup(i,w+1,m) dws.insert(i);
mt.Build();
forup(i,1,n){
i64 a=read(),r1=ups.size()?*ups.rbegin():inf,r2=dws.size()?*dws.begin():inf;
Node res=mt.Query(a,m);
if(r1==inf&&r2==inf&&res.x==inf){
puts("-1");
continue;
}
i64 pp=a/2*(a/2+1)/2+(a-1)/2*((a-1)/2+1)/2;
i64 v1=(r1==inf?inf:abs(w-r1)*a+pp),v2=(r2==inf?inf:abs(r2-w)*a+pp),v3=(res.x==inf?inf:a*(a-1)/2+a*mdis(res.x,res.y));
bool flag=false;
if(v1>v2){
flag=true;
swap(v1,v2);swap(r1,r2);
}
if(v1<v3||(v1==v3&&r1<res.x)){
if(flag){
dws.erase(dws.begin());
}else{
ups.erase(prev(ups.end()));
}
i64 l=w-a/2,r=w+(a-1)/2;
if(l>1){
ss[l-1].insert(Node{r1,l-1});
mt.Update(l-1,*ss[l-1].begin());
}
if(r<m){
ss[m-r].insert(Node{r1,r+1});
mt.Update(m-r,*ss[m-r].begin());
}
printf("%lld %lld %lld\n",r1,l,r);
}else{
if(res.y<w){
i64 l=res.y-a+1,r=res.y;
ss[r].erase(res);
if(ss[r].size()) mt.Update(r,*ss[r].begin());
else mt.Update(r,Node{inf,inf});
if(l>1){
ss[l-1].insert(Node{res.x,l-1});
mt.Update(l-1,*ss[l-1].begin());
}
printf("%lld %lld %lld\n",res.x,l,r);
}else{
i64 l=res.y,r=res.y+a-1;
ss[m-l+1].erase(res);
if(ss[m-l+1].size()) mt.Update(m-l+1,*ss[m-l+1].begin());
else mt.Update(m-l+1,Node{inf,inf});
if(r<m){
ss[m-r].insert(Node{res.x,r+1});
mt.Update(m-r,*ss[m-r].begin());
}
printf("%lld %lld %lld\n",res.x,l,r);
}
}
}
}