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

NOIP2025模拟赛30

T1 T2 T3 T4
\(\color{#52C41A} 普及+/提高\) \(\color{#52C41A} 普及+/提高\) \(\color{#9D3DCF} 省选/NOI-\) \(\color{#9D3DCF} 省选/NOI-\)

参赛网址:https://oj.33dai.cn/d/TYOI/contest/68abe2d6c5d9c2f14c2cd7d2

因为今天高一同学去报道,所以难度有所下降。

T1 黑白棋【2022NOIP模拟赛T1】

题目传送门

题目难度:\(\color{#52C41A} 普及+/提高\)

算法标签:数据结构,树状数组,结论题

思路

AC Code

#include <bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;const int maxn=2e5+5;
int n,Q;
int op,x;
struct seg_tree{int t[maxn<<2],lazy[maxn<<2];void build(int p,int l,int r){if (l==r){t[p]=n;return ;}build(ls,l,mid);build(rs,mid+1,r);t[p]=min(t[ls],t[rs]);}void push_down(int p){if (lazy[p]){t[ls]=min(t[ls],lazy[p]);t[rs]=min(t[rs],lazy[p]);if (lazy[ls]==0)   lazy[ls]=lazy[p];else    lazy[ls]=min(lazy[p],lazy[ls]);if (lazy[rs]==0)   lazy[rs]=lazy[p];else    lazy[rs]=min(lazy[p],lazy[rs]);lazy[p]=0;}}void update(int p,int l,int r,int x,int y,int k){if (x>r||y<l)   return ;if (x<=l&&r<=y){t[p]=min(t[p],k);if (lazy[p]==0)   lazy[p]=k;else    lazy[p]=min(lazy[p],k);return ;}push_down(p);if (x<=mid)   update(ls,l,mid,x,y,k);if (y>mid)   update(rs,mid+1,r,x,y,k);t[p]=min(t[ls],t[rs]);}int query(int p,int l,int r,int x){if (l==r)   return t[p];push_down(p);if (x<=mid) return query(ls,l,mid,x);else    return query(rs,mid+1,r,x);}
}tx,ty;signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>Q;int ans=(n-2)*(n-2);tx.build(1,1,n);ty.build(1,1,n);while (Q--){cin>>op>>x;if (op==1){int pos=tx.query(1,1,n,x);ans-=(pos-2);ty.update(1,1,n,1,pos-1,x);}else {int pos=ty.query(1,1,n,x);ans-=(pos-2);tx.update(1,1,n,1,pos-1,x);}}cout<<ans;return 0;
}

T2 寻找车位【2022NOIP模拟赛】

题目传送门

题目难度:\(\color{#52C41A} 普及+/提高\)

算法标签:贪心,优先队列

思路

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=1e6+5;
int n,m;
int ans;
int a[maxn];
int d[maxn];
struct node{int l,r;int sum;friend bool operator < (const node &x,const node &y){if (x.sum==y.sum)   return x.l>y.l;return x.sum<y.sum;}
};
vector<pair<int,int> > G;
priority_queue<node> Q;signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>m>>n;for (int i=1;i<=n;i++)  cin>>a[i];Q.push({0,m+1,m});for (int i=1;i<=n;i++){node t=Q.top();Q.pop();int mid=((t.l+t.r)>>1);Q.push({t.l,mid,mid-t.l-1});Q.push({mid,t.r,t.r-mid-1});G.push_back({mid,i});d[i]=mid;}G.push_back({0,0});G.push_back({m+1,n+1});sort(G.begin(),G.end());for (int i=1;i<=n;i++){int l=0,r=G.size()-1,pre=0,las=0;while (l<=r){int mid=((l+r)>>1);if (G[mid].first<d[i]){pre=mid;l=mid+1;}else    r=mid-1;}l=0,r=G.size()-1;while (l<=r){int mid=((l+r)>>1);if (G[mid].first>d[i]){las=mid;r=mid-1;}else    l=mid+1;}int qian=d[i]-G[pre].first;int hou=G[las].first-d[i];int tot=0;if (qian<=a[i]&&G[pre].second!=0)    tot=max(a[i]-qian+1,tot);if (hou<=a[i]&&G[las].second!=n+1)    tot=max(a[i]-hou+1,tot);ans+=tot;}cout<<ans;return 0;
}

T3 染色【NOIP2022模拟赛T3】

题目传送门

题目难度:\(\color{#9D3DCF} 省选/NOI-\)

算法标签:DP,带悔贪心

T4 激光【NOIP2025模拟赛T4】

题目传送门

题目难度:\(\color{#9D3DCF} 省选/NOI-\)

算法标签:二分,结论题

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

相关文章:

  • 2025西安品牌新房,西安刚需新房,陕西优质新房住宅推荐,地建嘉信臻境,超2000㎡高端会所,满足多元化生活需求
  • 2025年未央区高端楼盘,西咸新区品质楼盘,西安高新品牌楼盘住宅口碑推荐,地建嘉信臻境周边配套丰富,教育医疗商业齐全
  • 2025西安高端新房,西安优质新房,西安品牌新房住宅推荐,地建嘉信臻境,沣东文商板块门户,享双地铁便利
  • 2025年西安洋房楼盘,陕西优质楼盘,西咸新区现房楼盘住宅口碑推荐,地建嘉信臻境超2000㎡高端会所,功能多样
  • Python 闭包的应用场景与实战案例
  • input() 函数
  • 如何确保CMS系统能够飞快响应用户请求?全面性能优化指南
  • 近期
  • Playwright MCP 的使用与调试技巧
  • 实用指南:零基础学AI大模型之LangChain-PromptTemplate
  • 文件上传攻击全面指南:从侦察到防御
  • 2025年陕西洋房楼盘,西安城西品质楼盘,沣东品牌楼盘住宅口碑推荐,地建嘉信臻境户型多元布局,满足全周期生活需求
  • asus nuc15 pro ultra7 255H 外接 fevm 雷电5显卡坞 BIOS设置
  • P11529 [THUPC 2025 初赛] 辞甲猾扎
  • 2025年陕西品牌楼盘,西安城西优质楼盘,西咸新区核心楼盘住宅口碑推荐,地建嘉信臻境距吾悦广场一路之隔,商业配套完善
  • ARC113E Rvom and Rsrev
  • 2025年西咸新区高端楼盘,西安刚需楼盘,沣东改善楼盘住宅口碑推荐,地建嘉信臻境3分钟通达高新,区位优势明显
  • P12704 Retribution
  • Sunny Pro 网络验证- 仅需一键,即可为您的exe添加高强度防破加密!
  • 一条mysql数据库更新语句
  • 浅谈递归入门(1) - 指南
  • python+uniapp基于微信小工具的医院陪诊预约系统
  • [深度学习] 大模型学习5-高效微调框架Unsloth使用指北
  • 【APK安全】组件安全核心风险与防御指南 - 详解
  • 前端-JavaScript简介JavaScript模块化 - 努力-
  • 基本地址变换机构
  • 2025工业网线厂家权威推荐榜:千兆/拖链/高柔/网线/六类/超五类/6类/超5类/千兆/超六类/8芯/4芯/成品/相机/视觉数据工业网线高强屏蔽与稳定传输实力之选
  • gitee 使用安装教程
  • VisualMimic——基于视觉的人形行走-操作控制:低层策略负责平衡控制且跟踪高层下发的指令、高层策略则基于自我中心视觉输入生成任务跟踪指令 - 实践
  • 基本分页存储管理的基本概念