当前位置: 首页 > news >正文

2025.10.3 NOIP 模拟赛

前言

这回一改上次颓势。

T1一眼,T3思考2h+后场切。

但 T2 只有接近正解的 50 pts,T4 常数大挂了 20pts。

A

给定 \(n,k\),对 \([1,n]\) 建线段树后,求线段树上所有节点长度的 \(k\) 次方之和。

Solution

发现线段树上长度不同节点数量不会太大 \((O(\log n) \text{的样子})\)

于是直接 map 存 (长度,出现次数) 的 pair,一层层做即可。

\(O(T\log n\log k\log\log n)\)

B

image

image

发现一个序列经历 \(O(\log \log n)\) 次操作可以被改成第一个数 \(=1\),其余全 \(0\) 的序列。

\(50\) pts 可以对每个前缀离线直接改。

\(100\) pts 加入数字的时候递归更改变化的位置即可。

\(O(n\log^2 n)\)

namespace Subtask2 {int f[20][N],tot,S[20]={0};void Add(int o,int x,int v) {if(o>10) return ;if(f[o][x]) Add(o+1,f[o][x],-1);f[o][x]+=v;S[o]+=v;if(f[o][x]) Add(o+1,f[o][x],1);}void solve() {FOR(i,1,q) {int l=read(),k=read();vec[l].eb(k,i);}FOR(i,1,n) {Add(1,a[i],1);sort(vec[i].begin(),vec[i].end());for(auto p:vec[i]) {int k=p.fr,id=p.se;if(k>10) ans[id]=1;else ans[id]=S[k];}}FOR(i,1,q) printf("%d\n",ans[i]);}
}

C

image

image

Solution

发现当 \(k=1\) 时等价于查询树状数组的那个 \(c\) 数组的第 \(x\) 项。

我们把树状数组那个树建出来。

我们发现,一次查询 \(x\; k\),必定是 \(x\) 的子树中所有点的权值乘上某个系数 \(q_x\) 之和。

\(ans_{x,k}=\displaystyle\sum_{y\in \operatorname{Tree}(x)} a_y\times q_y\)

发现 \(q\) 即相当于初始 \(q_x=1,q_i=0(i\ne x)\),之后在树上对 \(q\)\(k\) 次前缀和。

\(f_{i,j}\) 表示考虑到前缀和第 \(i\) 项,当前是第 \(j\) 次前缀和,\(q_i\) 的值。

\(f_{0,0}=1\)

\[f_{i,j}=f_{i-1,j}+f_{i,j-1} \]

发现这玩意很像网格左上角走到 \((i,j)\) 的方案数转移方程,故 \(f_{i,j}=C_{i+j-2}^{j-1}\)

于是 \(ans_{x,k}=\displaystyle\sum_{y\in \operatorname{Tree(x)}} C_{dep_y+k-2}^{k-1}a_y\)

考虑拆式子。

\[\begin{aligned}&\sum_{y\in \operatorname{Tree(x)}} C_{dep_y+k-2}^{k-1}a_y\\=&\sum_{dp}C_{dp+k-2}^{k-1}\sum_{y\in \operatorname{Tree(x)}} a_y[dep_y=dp]\\\end{aligned} \]

由于树状数组的树深度不超过 \(O(\log n)\),故可以枚举深度,此时前面的组合数为定值。

而后面一项可以预处理。

单点增加直接暴力跳父亲更新即可。\(O((n+m)\log n)\)

赛时代码。

namespace Subtask2 {int fa[N],dep[N];LL power(LL a,LL b) {LL res=1;for(;b;b>>=1) {if(b&1) res=1LL*res*a%Mo;a=a*a%Mo;}return res;}LL s[N][23],Invdp[30];void Add(LL &x,int y) {x+=y;while(x>=Mo) x-=Mo;}void Upt(int x,int v) {int dp=1;while(x) {Add(s[x][dp],v);++dp;x=fa[x];}}LL Ask(int x,int k) {LL Answer=0,C=1;FOR(dp,1,21) {Answer=(Answer+1LL*s[x][dp]%Mo*C%Mo)%Mo;C=C*Invdp[dp]%Mo*(dp+k-1)%Mo;}return Answer;}void solve() {FOR(i,1,21) Invdp[i]=power(i,Mo-2);FOR(i,1,n) if(i+(i&-i)<=n) fa[i]=i+(i&-i);FOR(i,1,n) Upt(i,a[i]);while(m--) {int op=read(),x=read(),v=read();if(op==1) Upt(x,v);if(op==2) printf("%lld\n",Ask(x,v));}}
}
http://www.hskmm.com/?act=detail&tid=24099

相关文章:

  • Python 之操作excel
  • 国家生物信息数据下载
  • linux jenkins服务启动异常等,排查是否日志磁盘空间满 du df命令
  • 详细介绍:LeetCode 391 完美矩形
  • [NOI2025] 集合 题解
  • bi数据报表发送周期,周报和月报获取日期时间
  • 技术Leader的1-3-5沟通法则:向上管理的艺术 - 指南
  • cannot resolve method add in T 及 T 泛型类型生成Excel文件,区别是数据Model不同
  • 测试环境elasticSearch数据泄露排查
  • 深入解析:Spring boot中 限制 Mybatis SQL日志的大字段输出
  • 【AI时代速通QT】第九节:揭秘Qt编译全流程-从.pro材料到可执行程序
  • 考试心得5
  • javascript高级 - Ref
  • Solar9月赛wp - 场
  • 实用指南:深度解析Sora2:技术革命与创意产业的未来图景
  • 自动化安全工具的双刃剑:红队演练揭示安全响应盲区
  • Elastic Search 安装部署最全教程(Docker)
  • 详细介绍:图像分割:PyTorch从零开始实现SegFormer语义分割
  • 深入解析:Playwright同步、异步、并行、串行执行效率比较
  • 2025十一集训——Day2模拟赛
  • 2025十一集训——Day模拟赛
  • Qt纯代码实现智能安防集中管理平台/楼宇对讲管理系统/门禁管理/视频监控
  • 汉文博士词典库源文件已在 github 开放
  • 读人形机器人30未来20年
  • Flutter + Ollama:开启本地AI的全平台新纪元 —— 从零剖析一款现代化AI客户端的技能奥秘
  • 股票资料API接口全解析:从技术原理到多语言实战(含实时行情、MACD、KDJ等技术指标数据与API文档详解)
  • 产业园区招商团队快躺平了 - 智慧园区
  • 洛谷 P3545
  • 题解:AT_wtf22_day2_b The Greatest Two
  • 威胁狩猎实战:终端攻击行为分析与检测