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

近期模拟赛汇总

来让我们看看这个人到底在比赛中能干出什么呢

2025.10.8 国庆模拟赛二

T1

因为每个点只会被覆盖一次,所以倍增跳有标记的父亲然后暴力向下扩展就行。

来让我们看看这个人写的什么:

点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int N = 1e6+10;
int n,k,fa[N];
vector<int> G[N];
struct Q{int id,l,r;
}q[N];
int dep[N],ans=2e9,siz[N],hson[N],dfn[N],dfx,top[N],cnt[N],idfn[N];
void dfs(int u){dep[u]=dep[fa[u]]+1;siz[u]=1;for(int i=0;i<(int )G[u].size();i++){int v=G[u][i];if(v==fa[u]) continue;dfs(v);siz[u]+=siz[v];if(siz[v]>siz[hson[u]]) hson[u]=v;}
}
void dfs2(int u,int tp){top[u]=tp;dfn[u]=++dfx;cnt[tp]++;idfn[dfx]=u;if(hson[u]) dfs2(hson[u],tp);for(int i=0;i<(int)G[u].size();i++){int v=G[u][i];if(v==fa[u] || v==hson[u]) continue;dfs2(v,v);}
}
struct SegTree{
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)ll tr[N<<2],tag[N<<2];void pushup(int u){tr[u]=tr[ls]+tr[rs];}void upd(int u,ll k,int len){tr[u]=k*len;tag[u]=k;}void pushdown(int u,int l,int r){if(!tag[u]) return;upd(ls,tag[u],mid-l+1);upd(rs,tag[u],r-mid);tag[u]=0;}void modify(int u,int l,int r,int x,int y,ll k){if(l>=x && r<=y){upd(u,k,r-l+1);return ;}pushdown(u,l,r);if(x<=mid) modify(ls,l,mid,x,y,k);if(mid<y) modify(rs,mid+1,r,x,y,k);pushup(u);}ll query(int u,int l,int r,int x,int y){if(l>=x && r<=y) return tr[u];pushdown(u,l,r);ll res=0;if(x<=mid) res+=query(ls,l,mid,x,y);if(mid<y) res+=query(rs,mid+1,r,x,y);return res;}
}T;
inline void modify(int x,int y,ll k){while(top[x]!=top[y]){if(dep[x]<dep[y]) swap(x,y);T.modify(1,1,n,dfn[top[x]],dfn[x],k);x=fa[top[x]];}if(dep[x]>dep[y]) swap(x,y);T.modify(1,1,n,dfn[x],dfn[y],k);
}
inline ll query(int x,int y){ll res=0;while(top[x]!=top[y]){if(dep[x]<dep[y]) swap(x,y);res+=T.query(1,1,n,dfn[top[x]],dfn[x]);x=fa[top[x]];}if(dep[x]>dep[y]) swap(x,y);return res+T.query(1,1,n,dfn[x],dfn[y]);
}
inline int ask(int x, int k) {int tmp = dep[x] - k;while (dep[top[x]] > tmp) x = fa[top[x]];tmp = dep[x] - tmp;return idfn[dfn[x] - tmp];
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;for(int i=2;i<=n;i++){cin>>fa[i];G[fa[i]].push_back(i);G[i].push_back(fa[i]);}for(int i=1;i<=k;i++){cin>>q[i].id>>q[i].l>>q[i].r;}dfs(1);dfs2(1,1);for(int i=1;i<=k;i++){int l=q[i].l,r=q[i].r,idx=q[i].id;int tag;tag=query(1,idx);if(r-l+1>=dep[idx]-1-tag){ans=min(max(dep[idx]-1-tag-1,0)+l,ans);break;}else{int id=ask(idx,dep[idx]-(r-l+1)-1-tag);int s=ask(idx,dep[idx]-2-tag);modify(s,id,1);}}cout << (ans==2e9 ? -1 : ans) << '\n';return 0;
}

什么你说你没看懂,没事我给你说。

观察到第一个到达的点一定是最优的,所以考虑依次判断所有点是否可达。

然后发现操作实际上是从某节点向目标节点走若干步对吧。

直接树上链修,然后再链求和,还需要写个树上 k 级祖先。

没了,没有观察到重要性质导致的。

2025.10.13 CSP/NOIP 模拟赛6

T1

这玩意不一眼势能线段树,忘了 pushup 调了一小时。

点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int N = 1e5+10;
constexpr int inf = 2e9;
int T,n,m,a[N];
struct Tree{int fl,fr,cnt;ll mn;
}tr[N<<2];
Tree Merge(const Tree &a,const Tree &b){Tree res={0,0,0,0};res.cnt=a.cnt+b.cnt-(a.fr==1 && b.fl==1);res.fl=a.fl;res.fr=b.fr;res.mn=min(a.mn,b.mn);return res;
}
struct SegTree{#define ls (u<<1)#define rs (u<<1|1)#define mid ((l+r)>>1)int tag[N<<2];inline void pushup(int u){tr[u]=Merge(tr[ls],tr[rs]);}void build(int u,int l,int r){tr[u].mn=2e9;tag[u]=0;if(l==r){tr[u]={1,1,1,a[l]};return ;}build(ls,l,mid);build(rs,mid+1,r);pushup(u);}inline void pushdown(int u){if(!tag[u]) return ;tr[ls].mn-=tag[u];tr[rs].mn-=tag[u];tag[ls]+=tag[u];tag[rs]+=tag[u];tag[u]=0;}Tree query(int u,int l,int r,int x,int y,int k){if(tr[u].mn>=1e9+7){return {0,0,0,inf};}if(l>=x && r<=y && tr[u].mn>k){tr[u].mn-=k,tag[u]+=k;return tr[u];}if(l==r && tr[u].mn<=k){tr[u]={0,0,0,inf};return tr[u];}Tree res={0,0,0,inf};pushdown(u);if(x<=mid) res=query(ls,l,mid,x,y,k);if(mid<y) res=Merge(res,query(rs,mid+1,r,x,y,k));pushup(u);return res;}
}Tr;
void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];int lst=0;Tr.build(1,1,n);for(int i=1,t;i<=m;i++){cin>>t;int tt=t-lst;lst=t;cout << Tr.query(1,1,n,1,n,tt).cnt << ' ';}cout << '\n';
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;while(T--){solve();}return 0;
}

2025.10.15 CSP/NOIP 模拟赛7

T1

这倍增直接把最后的形态整出来,然后直接求最长的被烧过一段的长度-1 就是答案,写个线段树随便维护一下,轻松。

woc怎么调都不过去啊?哦它只会挨着火源放,哦它还只会放在最长的连续0的位置,那不用线段树,把那个位置卡住不倍增它,再扫一遍就行了。

点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int N = 2e5+10;
int T,n,t,a[N],arr[N];
string s;
struct FIRE{int l,r;
}d[N];int pre[N],nxt[N];
void solve() {cin>>n>>t>>s;int tt=t;s=' '+s;for(int i=1; i<=n; i++)a[i]=s[i]-'0';for(int i=n+1; i<=2*n; i++) a[i]=a[i-n];for(int i=1;i<=2*n;i++) d[i]={i,i};int mxd=0,mx=0,sum=0,lst=0;for(int i=1; i<=2*n; i++) {if(a[i]==1) {if(mx<sum) {mx=sum;mxd=lst;}lst=i;sum=0;} else {sum++;}}if(mx<sum) mx=sum,mxd=lst;for(int j=19; j>=0; j--) {if((1<<j)<=tt) {tt-=(1<<j);for(int i=1; i<=2*n; i++) {if(a[i]==1) {d[i].l=max(d[i].l-(1<<j),1);if(i!=mxd && i!=mxd+n)d[i].r=min(d[i].r+(1<<j),2*n);}}}if(tt==0) break;}int tmp=0;for(int i=1; i<=2*n; i++) {if(a[i]==1) pre[i]=tmp,tmp=i;}tmp=2*n+1;for(int i=2*n; i>=1; i--) {if(a[i]==1) nxt[i]=tmp,tmp=i;}for(int i=1; i<=2*n; i++) {if(a[i]==1) d[i].l=max(d[i].l,pre[i]+1),d[i].r=min(d[i].r,nxt[i]-1);}for(int i=1; i<=2*n; i++) {if(a[i]==1) {arr[d[i].l]++;arr[i]--;arr[i+1]++;arr[d[i].r+1]--;}}int ans=0;for(int i=1; i<=2*n; i++) {arr[i]=arr[i-1]+arr[i];}for(int i=1;i<=n;i++){arr[i]|=arr[i+n];if(arr[i]==0 && a[i]==0) ans++;}if(ans==0) cout << ans << '\n';else cout << ans-1 << '\n';memset(arr,0,sizeof(arr));
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;while(T--) {solve();}return 0;
}

T2

怎么有人忘了最短路能拼起来?

怎么有人忘了最短路能拼起来?

怎么有人忘了最短路能拼起来?

怎么有人忘了最短路能拼起来?

怎么有人忘了最短路能拼起来?

怎么有人忘了最短路能拼起来?

T3

我常常追忆过去

我常常追忆过去

我常常追忆过去

我常常追忆过去

我常常追忆过去

我常常追忆过去

http://www.hskmm.com/?act=detail&tid=31801

相关文章:

  • 实用指南:部署Tomcat11.0.11(Kylinv10sp3、Ubuntu2204、Rocky9.3)
  • Hbase的安装与配置
  • 【Azure App Service】App Service是否支持PHP的版本选择呢?
  • OAuth/OpenID Connect 渗透测试完全指南
  • Problem K. 置换环(The ICPC online 2025)思路解析 - tsunchi
  • Go 语言和 Tesseract OCR 识别英文数字验证码
  • Markdown转换为Word:Pandoc模板使用指南 - 实践
  • 2025年10月小程序开发公司最新推荐排行榜,小程序定制开发,电商小程序开发,预订服务小程序开发,活动报名小程序开发!
  • 复习CSharp
  • Rust 和 Tesseract OCR 实现英文数字验证码识别
  • 数据结构-循环队列
  • C语言学习——键盘录入
  • 2025年10月软件开发公司最新推荐,软件定制开发,crm系统定制软件开发,管理系统软件开发,物联网软件开发公司推荐!
  • C语言学习——运算符的学习
  • 第十五篇
  • 数据结构-双向循环链表
  • 数据结构-顺序栈
  • Erlang 的英文数字验证码识别系统设计与实现
  • 使用Django从零开始构建一个个人博客系统 - 实践
  • 2025年磨床厂家TOP企业品牌推荐排行榜,平面磨床,外圆磨床,数控平面磨床,数控外圆磨床,7163平面磨床推荐这十家公司!
  • cifar10
  • [LangChain] 02. 模型接口
  • 摄像头调试
  • C语言学习——字符串数据类型
  • 感知节点@4@ ESP32+arduino+ 第二个程序 LED灯显示
  • WebGL学习及项目实战(第02期:绘制一个点)
  • 2025 年 10 月国内加工中心制造商最新推荐排行榜:涵盖立式、卧式、龙门及多规格型号!
  • display ip routing-table protocol ospf 概念及题目 - 详解
  • C语言学习——小数数据类型
  • 高敏感人应对焦虑