多校A层冲刺NOIP2024模拟赛27终结篇
\(T1\) A. 【模板】分治FFT \(0pts\)
-
将式子展开后是一个形如 \(f_{n}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i-1}a_{i,j}\) 的形式。
-
考虑 \(f_{n}\) 如何转移。当我们选出一对 \((i,j)\) 进行合并进入 \(n'=n-1\) 的子问题，故 \(a_{i}a_{j}\) 的系数为 \(f_{n}=f_{n-1}(\dbinom{n}{2}-1)+g_{n-1}\) ，边界为 \(f_{2}=g_{2}=1\) 。其中 \(g_{n-1}\) 表示 \(n-1\) 堆果子有多少种合并方式，即 \(g_{n}=\dbinom{n}{2}g_{n-1}\) 。
- 进一步可以得到 \(f_{n}=g_{n}\) 。
点击查看代码
const ll p=998244353; ll a[100010],sum[100010],f[100010],g[100010]; int main() { freopen("fft.in","r",stdin); freopen("fft.out","w",stdout); ll n,ans=0,i,j; scanf("%lld",&n); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); a[i]%=p; sum[i]=(sum[i-1]+a[i])%p; ans=(ans+a[i]*sum[i-1]%p)%p; } f[2]=g[2]=1; for(i=3;i<=n;i++) { f[i]=((i*(i-1)/2-1)%p*f[i-1]%p+g[i-1])%p; g[i]=i*(i-1)/2%p*g[i-1]%p; } printf("%lld\n",ans*f[n]%p); return 0; }
\(T2\) B. 【模板】最近公共祖先 \(15pts\)
-
通过数学直觉，得到边数为 \(k\) 的连通块的答案为 \(\left\lfloor \frac{k}{2} \right\rfloor\) ，调整法即可证明。
-
当保证连通块是一棵树时，容易得到一种构造方式是从下往上考虑，对于 \(x\) 先尽可能让儿子之间一 \(x\) 为中转点互相连边，如果还有一条剩下的边那就传给 \(fa\) 尝试与 \(fa\) 的其他儿子连边。
-
当不保证连通块是一棵树时，过早地拿走一条边使得图不连通可能会导致不能全部取完，故仍考虑在 \(DFS\) 树上操作并延续树边的构造方式。对于非树边（前向边和返祖边）先进行内部互相连边，然后将余下的扔给 \(DFS\) 树上深度较浅的节点即可。
点击查看代码
struct quality { int u,v,w; }; struct node { int nxt,to,id; }e[600010]; int head[300010],vis[300010],ins[300010],fa[300010],cnt=0; queue<int>q; vector<quality>ans; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(int x) { vis[x]=ins[x]=1; for(int i=head[x];i!=0;i=e[i].nxt) { if(vis[e[i].to]==0) { dfs(e[i].to); } } for(int i=head[x];i!=0;i=e[i].nxt) { if(ins[e[i].to]==0)//非树边 { if(fa[e[i].to]==0)//尝试内部连边 { q.push(e[i].to); } else//直接连上 { ans.push_back((quality){x,e[i].to,fa[e[i].to]}); fa[e[i].to]=0; } } } while(q.size()>=2) { int tmp=q.front(); q.pop(); ans.push_back((quality){tmp,x,q.front()}); q.pop(); } if(q.empty()==0) { fa[x]=q.front(); q.pop(); } ins[x]=0; } int main() { freopen("lca.in","r",stdin); freopen("lca.out","w",stdout); int n,m,u,v,i; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } for(i=1;i<=n;i++) { if(vis[i]==0) { dfs(i); } } printf("%d\n",ans.size()); for(i=0;i<ans.size();i++) { printf("%d %d %d\n",ans[i].u,ans[i].v,ans[i].w); } return 0; }
\(T3\) C. 【模板】普通平衡树 \(45pts\)
-
部分分
- 测试点 \(1 \sim 9\) ：最长锯齿子序列可以 \(O(n^{2})\) 转移。
- 测试点 \(12,13\) ：答案只可能是 \(0/1/2\) 。
点击查看代码
int op[300010],l[300010],r[300010],x[300010],ans[300010]; vector<int>f[300010],g[300010]; void insert(int x,int y) { if(f[x].size()==0) { f[x].push_back(-1044266559); g[x].push_back(0x3f3f3f3f); f[x].push_back(y); g[x].push_back(y); ans[x]=1; } else { f[x].push_back(0x3f3f3f3f); g[x].push_back(-1044266559); for(int i=f[x].size()-1;i>=1;i--) { if(y<g[x][i-1]) { f[x][i]=min(g[x][i-1],y); } if(y>f[x][i-1]) { g[x][i]=max(g[x][i],y); } if(f[x][i]!=0x3f3f3f3f||g[x][i]!=-1044266559) { ans[x]=max(ans[x],i); } } ans[x]=max(ans[x],2); } } struct SMT { struct SegmentTree { int lazy; }tree[1200010]; #define lson(rt) (rt<<1) #define rson(rt) (rt<<1|1) void update(int rt,int l,int r,int x,int y,int val) { if(x<=l&&r<=y) { tree[rt].lazy+=val; return; } int mid=(l+r)/2; if(x<=mid) { update(lson(rt),l,mid,x,y,val); } if(y>mid) { update(rson(rt),mid+1,r,x,y,val); } } int query(int rt,int l,int r,int pos) { if(l==r) { return tree[rt].lazy; } int mid=(l+r)/2; if(pos<=mid) { return query(lson(rt),l,mid,pos)+tree[rt].lazy; } else { return query(rson(rt),mid+1,r,pos)+tree[rt].lazy; } } }T; int main() { freopen("odt.in","r",stdin); freopen("odt.out","w",stdout); int n,m,flag1=1,flag2=1,cnt=0,i,j; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d",&op[i],&l[i]); if(op[i]==1) { scanf("%d%d",&r[i],&x[i]); cnt++; flag1&=(x[i]==cnt); flag2&=(x[i]==1000000000-cnt); } } if(flag1==1||flag2==1) { for(i=1;i<=m;i++) { if(op[i]==1) { T.update(1,1,n,l[i],r[i],1); } else { printf("%d\n",min(T.query(1,1,n,l[i]),2)); } } } else { for(j=1;j<=m;j++) { if(op[j]==1) { for(i=l[j];i<=r[j];i++) { insert(i,x[j]); } } else { printf("%d\n",ans[l[j]]); } } } return 0; } -
正解
- 手摸 \(len \ge 3\) 的情况后发现 \(2+\sum\limits_{i=2}^{len-1}[(a_{i}-a_{i-1})(a_{i+1}-a_{i})<0]\) 即为所求，画在平面直角坐标系上取更新大小关系的截点加入答案即可。
- 线段树
pushdown先天已经维护了时间的先后关系，故可以直接更新。
点击查看代码
int check(int a,int b,int c) { return (a>b&&b<c)||(a<b&&b>c); } struct SMT { struct node { int siz,ans,lc,zlc,rc,zrc; void clear() { siz=ans=lc=zlc=rc=zrc=0; } node operator + (const node &another) { node tmp; if(siz==0){return another;} if(another.siz==0){return *this;} tmp.siz=siz+another.siz; tmp.ans=ans+another.ans+(zrc!=0&&check(zrc,rc,another.lc))+(another.zlc!=0&&check(rc,another.lc,another.zlc)); tmp.lc=lc; tmp.zlc=(zlc!=0)?zlc:another.lc; tmp.rc=another.rc; tmp.zrc=(another.zrc!=0)?another.zrc:rc; return tmp; } }; struct SegmentTree { node lazy; }tree[1200010]; #define lson(rt) (rt<<1) #define rson(rt) (rt<<1|1) void pushdown(int rt) { tree[lson(rt)].lazy=tree[lson(rt)].lazy+tree[rt].lazy; tree[rson(rt)].lazy=tree[rson(rt)].lazy+tree[rt].lazy; tree[rt].lazy.clear(); } void update(int rt,int l,int r,int x,int y,int val) { if(x<=l&&r<=y) { tree[rt].lazy=tree[rt].lazy+(node){1,0,val,0,val,0}; return; } pushdown(rt); int mid=(l+r)/2; if(x<=mid) { update(lson(rt),l,mid,x,y,val); } if(y>mid) { update(rson(rt),mid+1,r,x,y,val); } } int query(int rt,int l,int r,int pos) { if(l==r) { return(tree[rt].lazy.siz>=3)?tree[rt].lazy.ans+2:tree[rt].lazy.siz; } pushdown(rt); int mid=(l+r)/2; if(pos<=mid) { return query(lson(rt),l,mid,pos); } else { return query(rson(rt),mid+1,r,pos); } } }T; int main() { freopen("odt.in","r",stdin); freopen("odt.out","w",stdout); int n,m,pd,l,r,x,i; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d",&pd,&l); if(pd==1) { scanf("%d%d",&r,&x); T.update(1,1,n,l,r,x); } else { printf("%d\n",T.query(1,1,n,l)); } } return 0; }
\(T4\) D. 【模板】平面最近点对 \(20pts\)
-
等价于最小化 \(k\) 维上最大的极差。
-
部分分
- 测试点 \(1,4,8,9\) ：爆搜。
点击查看代码
int a[16010][25],ans=0x7f7f7f7f; vector<int>state; void dfs(int pos,int n,int k) { if(pos==n+1) { int sum=0; for(int i=1;i<=k;i++) { int maxx=0,minn=0x7f7f7f7f; for(int j=0;j<state.size();j++) { maxx=max(maxx,a[state[j]][i]); minn=min(minn,a[state[j]][i]); } sum=max(sum,maxx-minn); } ans=min(ans,sum); } else { state.push_back(pos*2); dfs(pos+1,n,k); state.pop_back(); state.push_back(pos*2+1); dfs(pos+1,n,k); state.pop_back(); } } int main() { freopen("pair.in","r",stdin); freopen("pair.out","w",stdout); int n,k,i,j; scanf("%d%d",&n,&k); for(i=1;i<=n;i++) { for(j=1;j<=k;j++) { scanf("%d",&a[i*2][j]); } for(j=1;j<=k;j++) { scanf("%d",&a[i*2+1][j]); } } dfs(1,n,k); printf("%d\n",ans); return 0; } -
正解
- 等学了 \(2-SAT\) 再来补。
总结
- \(T1\) 误直接把 \(\{ g \}\) 写成了 \(1\) ，挂了 \(100pts\) 。
- \(T2\) 没去想树的部分分，只写了个乱搞做法。
- \(T3\)
- 特殊性质 \(A,B\) 打假了，挂了 \(20pts\) 。
- 赛时以为线段树
pushdown不能很好地维护插入数的先后关系，说明对pushdown更新过程的认识不清。
- \(T4\) 又被卡在对高维空间的理解上，但因为有样例解释很快就理解了。
后记
- \(T2\) 下发了
checker.exe，但 \(Linux\) 下的一开始有点问题，中途又更换了两次。