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

NOIP2025模拟赛30

news 2025/10/1 12:47:37

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;
}