A
先构造出(1-8,16)这(9)个数，共需要(17)步
之后按照每四位一个单位构造数(x)，若(x)的末四位(le 8)可以直接加，否则需要在之前(+1)然后减去一个(<8)的数
这样每一个(4)位最多用两步即可解决，一共最多(17+16 imes2+1=50)步
（注意一直进位使得整个数多一位的情况下，中间会有一些(0)，这些(0)节约了步数，使得总步数仍满足要求
#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b))%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void solve(ull x)
{
if(x<16)
{
if(x<=8)
{
puts("p1");x--;
if(x) printf("add %d
",10-x);
}
else printf("dup
sub %d
",10-(16-x));
return ;
}
ull now=x&15;
if(now<=8)
{
solve(x>>4);puts("mul 1");
if(now) printf("add %d
",10-now);
}
else
{
solve((x>>4)+1);puts("mul 1");
printf("sub %d
",10-(16-now));
}
}
int main()
{
ull n;rep(T,1,read())
{
cin>>n;
if(!n) {puts("p1
sub 0
end");continue;}
puts("p1");rep(i,1,7) printf("dup
add %d
",i);
puts("dup
mul 7");solve(n);puts("end");
}
}
B
博弈签到题 咕
C
对于一个数(x)的最大排名来说，需要找到最大的(k)满足较大的(k)个(a_i)与较大的(k)个(b_i)反向相加均大于(a_x+b_n)
因此需要对每一个(a_i)求出最小的(b_j)使(a_i+b_j>a_x+b_n)，将(a)排序后由单调性可以通过简单求出
求出的所有(b)相当于一些限制，找到均满足这些限制的最大(k)即可
最小排名同理
#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b))%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define w first
#define id second
#define pb push_back
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,mn[MAXN],mx[MAXN],b[MAXN];
pii g[MAXN];
int main()
{
int pos,res,cnt;rep(T,1,read())
{
n=read();rep(i,1,n) g[i]={read(),i};
rep(i,1,n) b[i]=read();
sort(g+1,g+n+1);
rep(i,1,n)
{
pos=n-1,res=n-1,cnt=0;dwn(j,n,1) if(i!=j)
{
cnt++;
while(g[j].w+b[pos]<=g[i].w+b[n]&&pos) pos--;
res=min(res,cnt+pos-1);
}
mx[g[i].id]=res+1;
}
rep(i,1,n>>1) swap(b[i],b[n+1-i]);
rep(i,1,n)
{
pos=n-1,res=n-1,cnt=0;rep(j,1,n) if(i!=j)
{
cnt++;
while(g[j].w+b[pos]>g[i].w+b[n]&&pos) pos--;
res=min(res,cnt+pos-1);
}
mn[g[i].id]=n-res;
}
rep(i,1,n) printf("%d %d
",mn[i],mx[i]);
}
}
D
看上去是个推式子概率题 咕
E
可做dp 咕
F
显然可以找到一个分界点，使得该点左侧的贡献为大于(x)的数的个数，右侧为小于
用树状数组直接维护所有数的出现，即可(O(log^2))找到分界点
统计答案可以用线段树分别维护小于/大于每个数的区间和，每次更改为区间加
#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 200100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b))%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int lim=2e5;
int n,q,w[MAXN];
ll pre[MAXN],suf[MAXN];
int sum[MAXN<<2];
ll sl[MAXN<<2],tl[MAXN<<2],sr[MAXN<<2],tr[MAXN<<2];
ll c[MAXN];
inline void addp(int x,int w){for(;x<=lim;x+=x&-x) c[x]+=w;}
inline ll query(int x,ll res=0){for(;x;x-=x&-x) res+=c[x];return res;}
inline ll getpre(int x){return query(x);}
inline ll getsuf(int x){return query(lim)-query(x-1);}
int find()
{
int l=1,r=lim,mid=l+r>>1,res=-1;
for(;l<=r;mid=l+r>>1)
if(getpre(mid-1)<=getsuf(mid+1)) res=mid,l=mid+1;
else r=mid-1;
return res;
}
inline void upd(int k)
{
sl[k]=sl[k<<1]+sl[k<<1|1],sr[k]=sr[k<<1]+sr[k<<1|1];
sum[k]=sum[k<<1]+sum[k<<1|1];
}
inline void Mdfl(int k,int l,int r,int w)
{
sl[k]+=1LL*sum[k]*w,tl[k]+=w;
}
inline void Mdfr(int k,int l,int r,int w)
{
sr[k]+=1LL*sum[k]*w,tr[k]+=w;
}
inline void pshd(int k,int l,int r,int mid)
{
if(tl[k]) Mdfl(k<<1,l,mid,tl[k]),Mdfl(k<<1|1,mid+1,r,tl[k]),tl[k]=0;
if(tr[k]) Mdfr(k<<1,l,mid,tr[k]),Mdfr(k<<1|1,mid+1,r,tr[k]),tr[k]=0;
}
void build(int k,int l,int r)
{
tl[k]=tr[k]=0;
if(l==r)
{
sum[k]=w[l],sl[k]=pre[l-1]*w[l],sr[k]=suf[r+1]*w[l];
return ;
}
int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);
upd(k);
}
void add(int k,int l,int r,int x,int w)
{
if(l==r)
{
sum[k]+=w,sl[k]+=getpre(l-1)*w,sr[k]+=getsuf(r+1)*w;
return ;
}
int mid=l+r>>1;pshd(k,l,r,mid);
if(x<=mid) add(k<<1,l,mid,x,w);
else add(k<<1|1,mid+1,r,x,w);
upd(k);
}
void mdfl(int k,int l,int r,int a,int b,int w)
{
if(a<=l&&r<=b) {Mdfl(k,l,r,w);return ;}
int mid=l+r>>1;pshd(k,l,r,mid);
if(a<=mid) mdfl(k<<1,l,mid,a,b,w);
if(b>mid) mdfl(k<<1|1,mid+1,r,a,b,w);
upd(k);
}
void mdfr(int k,int l,int r,int a,int b,int w)
{
if(a<=l&&r<=b) {Mdfr(k,l,r,w);return ;}
int mid=l+r>>1;pshd(k,l,r,mid);
if(a<=mid) mdfr(k<<1,l,mid,a,b,w);
if(b>mid) mdfr(k<<1|1,mid+1,r,a,b,w);
upd(k);
}
ll qryr(int k,int l,int r,int x)
{
if(l==r) return sr[k];
int mid=l+r>>1;pshd(k,l,r,mid);
return x<=mid?qryr(k<<1,l,mid,x):sr[k<<1]+qryr(k<<1|1,mid+1,r,x);
}
ll qryl(int k,int l,int r,int x)
{
if(l==r) return sl[k];
int mid=l+r>>1;pshd(k,l,r,mid);
return x<=mid?sl[k<<1|1]+qryl(k<<1,l,mid,x):qryl(k<<1|1,mid+1,r,x);
}
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
int main()
{
int las,a,b,now;ll res,tot,g;
rep(T,1,read())
{
n=read(),q=read();
rep(i,1,n) w[read()]++;
rep(i,1,lim) pre[i]=pre[i-1]+w[i];
dwn(i,lim,1) suf[i]=suf[i+1]+w[i];
rep(i,1,lim) if(w[i]) addp(i,w[i]);
build(1,1,lim);
while(q--)
{
a=read();
if(a==2)
{
now=find(),res=qryr(1,1,lim,now);
if(now<lim) res+=qryl(1,1,lim,now+1);
tot=1LL*sum[1]*(sum[1]-1);
g=gcd(res,tot);
printf("%lld/%lld
",res/g,tot/g);
}
else
{
a=read(),b=read();addp(b,a);
add(1,1,lim,b,a);
if(b-1>=1) mdfr(1,1,lim,1,b-1,a);
if(b+1<=lim) mdfl(1,1,lim,b+1,lim,a);
}
}
rep(i,1,lim) w[i]=pre[i]=suf[i]=c[i]=0;
}
}
G
直接维护这个链表，记录一下中点以及中点右侧点的集合。
删除与添加操作分别根据奇偶性讨论即可
#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 10010010
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b))%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int q,pre[MAXN],suf[MAXN],tot,n,ans,now,in[MAXN];
char s[5];
int main()
{
int x,l,r;while(scanf("%d",&q)!=EOF)
{
rep(i,1,q)
{
scanf("%s",s+1);
if(s[1]=='L')
{
tot++,now++;
if(tot==1) pre[now]=suf[now]=0,suf[0]=pre[0]=now,ans=now,in[ans]=1;
else
{
suf[now]=suf[0],pre[suf[0]]=now,pre[now]=0,suf[0]=now;
if(tot&1) ans=pre[ans],in[ans]++;
}
}
else if(s[1]=='R')
{
tot++,now++,in[now]++;
if(tot==1) pre[now]=suf[now]=0,suf[0]=pre[0]=now,ans=now;
else
{
pre[now]=pre[0],suf[pre[0]]=now,suf[now]=0,pre[0]=now;
if(tot%2==0) in[ans]--,ans=suf[ans];
}
}
else if(s[1]=='Q') printf("%d
",ans);
else
{
x=read();l=pre[x],r=suf[x];
suf[l]=r,pre[r]=l;
tot--;
if(x==ans) {if(tot&1) ans=l,in[l]++;else ans=r;}
else if(in[x]) {if(tot&1) ans=pre[ans],in[ans]++;}
else {if(tot%2==0) in[ans]--,ans=suf[ans];}
in[x]=0;
}
}
while(ans) in[ans]=0,ans=suf[ans];tot=now=0;
}
}
H
考虑取(m=2)，则显然有最终答案(ge frac{n}{2})，考虑随机化令一个数在答案集合内
对于已知一个数的情况，朴素的想法是将其他数与这个数作差，想要找到一个质数(m)使得尽可能多的差是(m)的倍数
因为集合内的数较多，可以考虑再进行一次随机化，假定这个差也在集合中
则只需要先预处理出(sqrt{w})内的所有素数，对这个差进行质因数分解，然后(check)所有质因数的贡献
每次错误的概率为((1-frac{1}{4}))，随机化(30)次错误的概率很低
#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 200100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b))%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,ntp[MAXN*10],p[MAXN*10],tot,ans,m;
ll g[MAXN],h[MAXN],f[MAXN];
void mem(int n=2e6)
{
rep(i,2,n)
{
if(!ntp[i]) p[++tot]=i;
rep(j,1,tot) if(i*p[j]>n) break;
else {ntp[i*p[j]]=1;if(i%p[j]==0) break;}
}
}
int solve(int pos,ll diff,int res=0)
{
m=0;rep(i,1,tot)
if(1LL*p[i]*p[i]>diff) break;
else if(diff%p[i]==0)
{h[++m]=p[i];while(diff%p[i]==0) diff/=p[i];}
if(diff>1) h[++m]=diff;int tmp;
rep(i,1,n) f[i]=abs(g[i]-g[pos]);
rep(i,1,m)
{
tmp=0;
rep(j,1,n) tmp+=(f[j]%h[i]==0);
res=max(res,tmp);
}
return res;
}
int main()
{
mem();int x,y;srand(19260817);
rep(T,1,read())
{
n=read(),ans=1;rep(i,1,n) g[i]=read();
rep(t,1,30)
{
x=rand()%n+1,y=rand()%n+1;
while(x==y) y=rand()%n+1;
ans=max(solve(x,abs(g[x]-g[y])),ans);
}
printf("%d
",ans);
}
}
I
奇怪的题 弃了
J
首先可以对(a,b)分别得到一个有效分数的区间，在区间外的贡献为最小值或最大值
有两种显然的情况，即完全不可能或一定可以达到目的
否则显然可以在有效区间内进行合法的选数使得(a)的分数恰好大于(b)，此时的贡献为已有的二者分数之差
考虑能使答案更优的特殊情况，一定是在分数不变的情况下(a_n)更小或(b_n)更大
这两种情况分别发生在区间的左侧与右侧，判断一下二者的左侧区间与右侧区间本身是否合法
#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b))%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll n,a[MAXN],b[MAXN],s,t,h,ans,la,ra,lb,rb,res;
ll sa,sb;
int main()
{
rep(T,1,read())
{
n=read(),s=read(),t=read(),h=read();
rep(i,1,n-1) a[i]=read();rep(i,1,n-1) b[i]=read();
sort(a+1,a+n);sort(b+1,b+n);
ans=inf,sa=sb=0;ll tmp;
rep(i,t+1,n-1-s) sa+=a[i],sb+=b[i];
if(t) la=a[t],lb=b[t];else la=lb=1;
if(s) ra=a[n-s],rb=b[n-s];else ra=rb=h;
if(sa+ra<=sb+lb) {puts("IMPOSSIBLE");continue;}
if(sa+la>sb+rb) {printf("%lld
",1-h);continue;}
res=ans=sb-sa+1;
if(sa+la>sb+lb) ans=min(ans,res-la+1);
if(sa+ra>sb+rb) ans=min(ans,res-h+rb);
printf("%lld
",ans);
}
}
K
看上去可做的虚树+树剖题 咕