比赛链接

A.中位数 二分+前缀和

题目链接

---

构造一个序列 $B$ 。每次二分一个答案 $ans$，构造 $B$ 序列方法： $$B_i=\{\begin{array}{l}-1A_i<ans\\ 1A_i\ge ans\end{array}$$ 然后维护 $B$ 的前缀和，并记录前缀和的最小值。通过查询是否存在一个长度大于 $len$、区间和大于 $0$ 的区间。这样做时间复杂度是 $O(Nlog{A}_i)$ 的，没有问题。

#include<cstdio> #include<algorithm> using namespace std; const int N=1e5+10; int n,len,a[N],b[N]; bool judge(int mid) { int minn=0x3f3f3f3f; for(int i=1;i<=n;i++) if(a[i]<mid)b[i]=-1; else b[i]=1; for(int i=1;i<=n;i++) { if(i>=len)minn=min(minn,b[i-len]); b[i]+=b[i-1]; if(i>=len&&b[i]-minn>0)return true; } return false; } int main() { //freopen("in.txt","r",stdin); scanf("%d%d",&n,&len); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int l=0,r=1e9; while(l<r) { int mid=(l+r+1)>>1; if(judge(mid))l=mid; else r=mid-1; } printf("%d\n",r); return 0; }

总结

这种题没有秒解是很不应该的。首先对于一个区间，不需要把它排序，只需进行比较就好了；再者我们发现，如果答案太大是找不到这样的区间的，也就是说答案是具有单调性的，应该想到二分答案转化为判定。吸取教训。

---

B.数数字 线性DP

题目链接

---

#include<cstdio> #include<cstring> typedef long long ll; #define _rep(i,a,b) for(int i=(a);i<=(b);i++) #define _for(i,a,b) for(int i=(a);i<(b);i++) int co[10][10]; ll pw[10][100],l,r,l1,r1,ans,g[2][3][2][2],f[2][3][60][38][27][22]; ll nozero(ll x) { if(x<=0)return 0; memset(f,0,sizeof(f)); int cr=0;f[0][1][0][0][0][0]=1; ll ret=0,val; for(;x;x/=10,cr^=1) { int bit=x%10; memset(f[cr^1],0,sizeof(f[cr])); _for(i,0,3)_for(n2,0,60)_for(n3,0,38)_for(n5,0,27)_for(n7,0,22)if(val=f[cr][i][n2][n3][n5][n7]) { ll q1=r1/pw[2][n2]/pw[3][n3]/pw[5][n5]/pw[7][n7]; ll p1=(l1-1)/pw[2][n2]/pw[3][n3]/pw[5][n5]/pw[7][n7]; if(q1>=1&&p1<=0)ret+=val; if(q1<=0)continue; _for(p,1,10) { int ni=(p>bit?2:(p==bit?i:0)); int c2=n2+co[p][2]; int c3=n3+co[p][3]; int c5=n5+co[p][5]; int c7=n7+co[p][7]; if(c2>=60||c3>=38||c5>=27||c7>=22)continue; f[cr^1][ni][c2][c3][c5][c7]+=val; } } } _for(i,0,2)_for(n2,0,60)_for(n3,0,38)_for(n5,0,27)_for(n7,0,22)if(val=f[cr][i][n2][n3][n5][n7]) { ll q1=r1/pw[2][n2]/pw[3][n3]/pw[5][n5]/pw[7][n7]; ll p1=(l1-1)/pw[2][n2]/pw[3][n3]/pw[5][n5]/pw[7][n7]; if(q1>=1&&p1<=0)ret+=val; } return ret; } ll zero(ll x) { if(l1)return 0;//如果含0乘积为0 memset(g,0,sizeof(g)); int cr=0;ll ret=0; g[0][1][0][0]=1; for(;x;x/=10,cr^=1) { int bit=x%10;//取出该位 memset(g[cr^1],0,sizeof(g[cr])); _for(i,0,3)_for(j,0,2)_for(hd,0,2)if(g[cr][i][j][hd]) { if(hd&&j)ret+=g[cr][i][j][hd]; _for(p,0,10) { int ni=(p>bit?2:(p==bit?i:0)); int nj=(j|(p==0)); int hdt=(p>0); g[cr^1][ni][nj][hdt]+=g[cr][i][j][hd]; } } } return ret+g[cr][0][1][1]+g[cr][1][1][1]; } ll calc(ll x) { return zero(x)+nozero(x); } int main() { //freopen("in.txt","r",stdin); _for(i,1,10) { _for(j,2,10) for(int k=i;k%j==0;k/=j) co[i][j]++;//预处理出i有多少个j因子 pw[i][0]=1; for(int j=1;j<=60;j++) pw[i][j]=pw[i][j-1]*i;//预处理出i的次幂 } scanf("%lld%lld%lld%lld",&l,&r,&l1,&r1); if(!l)ans+=(l1==0),l++; if(l<=r)ans+=calc(r)-calc(l-1); printf("%lld\n",ans); return 0; }

总结

线性DP好题，状态定义是关键

---

C.保护 LCA+线段树动态开点+线段树合并

题目链接 ___

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10; int n,m,hd[N],tot,dep[N],fa[N][20],ord[N],cnt,q; struct Edge{ int v,nx; }e[N<<1]; struct SegmentTree{ int l,r,cnt; }c[N*100]; void add(int u,int v) { e[tot].v=v; e[tot].nx=hd[u]; hd[u]=tot++; } void dfs(int u,int f) { dep[u]=dep[f]+1; fa[u][0]=f; for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=hd[u];~i;i=e[i].nx) if(e[i].v!=f)dfs(e[i].v,u); } int lca(int u,int v) { if(dep[u]>dep[v])swap(u,v); for(int i=18;i>=0;i--) if(dep[fa[v][i]]>=dep[u])v=fa[v][i]; if(v==u)return u; for(int i=18;i>=0;i--) if(fa[v][i]!=fa[u][i])u=fa[u][i],v=fa[v][i]; return fa[u][0]; } void update(int l,int r,int p,int &id) { if(!id)id=++cnt; c[id].cnt++; if(l==r)return; int mid=l+r>>1; if(p<=mid)update(l,mid,p,c[id].l); else update(mid+1,r,p,c[id].r); } int merge(int l,int r,int a,int b) { if((!a)||(!b))return a+b; int id=++cnt; c[id].cnt=c[a].cnt+c[b].cnt; if(l==r)return id; int mid=l+r>>1; c[id].l=merge(l,mid,c[a].l,c[b].l); c[id].r=merge(mid+1,r,c[a].r,c[b].r); return id; } void Dfs(int u,int f) { for(int i=hd[u];~i;i=e[i].nx) if(e[i].v!=f) { Dfs(e[i].v,u); ord[u]=merge(1,n,ord[u],ord[e[i].v]); } } int find(int l,int r,int k,int id) { if(c[id].cnt<k)return 0x7fffffff; if(l==r)return l; int mid=l+r>>1; if(c[c[id].l].cnt>=k)return find(l,mid,k,c[id].l); return find(mid+1,r,k-c[c[id].l].cnt,c[id].r); } int main() { //freopen("in.txt","r",stdin); memset(hd,-1,sizeof(hd)); scanf("%d%d",&n,&m); int u,v; for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); add(u,v);add(v,u); } dfs(1,0); for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); int p=lca(u,v); update(1,n,dep[p],ord[u]);update(1,n,dep[p],ord[v]); } Dfs(1,0); scanf("%d",&q); for(int i=1;i<=q;i++) { int k; scanf("%d%d",&u,&k); printf("%d\n",max(0,dep[u]-find(1,n,k,ord[u]))); } return 0; }

总结

线段树高级操作维护信息难题

---

赛后总结

难度挺大的题，很需要一些思维能力。