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

NOIP2025模拟赛27

news 2025/10/1 12:47:38

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

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

剧透：有一道小模拟，远小于《梦幻金花》的小模拟。

T1 信道传输【2022NOIP模拟赛T1】

题目传送门

题目难度：\(\color{#FFC116} 普及/提高-\)

算法标签：搜索，枚举，二进制拆分

思路

每次枚举每一个 \(i = 2^k\)，找到它的管理范围，判断是非符合标准，因为最多只错一个，所以如果它和它的管辖范围内的所有数一定是正确的。

所以我们枚举所有的 \(i = 2^k\) 这样我们就能找到不可判断的位置，如果这样我们就能找到不可判断的位置中 \(i = 2^k\) 的数量大于1，则不是 \(i = 2^k\) 的问题，而是所有的 \(i = 2^k\) 的 \(i\) 的异或和（代码中不是这种写法，更复杂一些，也差不多了）。否则就是那个唯一的 \(i = 2^k\) 的问题。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=16;
int T;
int n;
int vis[1<<(maxn+1)],num[1<<(maxn+1)];
string s;signed main(){// freopen("code2.in","r",stdin);// freopen("code.out","w",stdout);ios::sync_with_stdio(false);cin.tie(0);cin>>T>>n;int len=(1<<n)-1;while (T--){for (int i=1;i<=len;i++)    vis[i]=0,num[i]=0;cin>>s;s='0'+s;for (int i=1;i<=len;i<<=1){int sum=0;for (int j=i+1;j<=len;j++){if ((j&i)==i)sum^=(s[j]-'0');}if (sum!=(s[i]-'0')){vis[i]=max(vis[i],0ll);for (int j=i+1;j<=len;j++)if ((j&i)==i)vis[j]=max(vis[j],0ll),num[j]++;}else {vis[i]=1;for (int j=i+1;j<=len;j++)if ((j&i)==i)vis[j]=1;}}int cnt=0;for (int i=1;i<=len;i<<=1)if (vis[i]==0)  cnt++;if (cnt==0){for (int i=1;i<=len;i++){if (vis[i]==0){if (s[i]=='0')    s[i]='1';else    s[i]='0';}}}else if (cnt==1){for (int i=1;i<=len;i<<=1)if (vis[i]==0){if (s[i]=='0')    s[i]='1';else    s[i]='0';}}else {for (int i=1;i<=len;i++)if (vis[i]==0&&num[i]>=cnt){if (s[i]=='0')    s[i]='1';else    s[i]='0';}}for (int i=1;i<=len;i++)    cout<<s[i];cout<<"\n";}return 0;
}

T2 模拟交易【2022NOIP模拟赛T2】

题目传送门

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

算法标签：模拟，优先队列

思路

这就是一道大模拟，结案。

《关于我给 @Sunpicnic 调了一下午代码的事情》

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=1e5+5;
int n,Q;
int cnt;
int las;
int a[maxn],c[maxn];//一开始第i个人手上有a[i]股贵州茅台的股票以及 c[i] 元现金
int vis[maxn];
int op,id,x,y;
struct gmdingdan{int a,x,y,ti;friend bool operator < (const gmdingdan &x,const gmdingdan &y){if (x.x==y.x)   return x.ti>y.ti;return x.x<y.x;}
};
struct smdingdan{int a,x,y,ti;friend bool operator < (const smdingdan &x,const smdingdan &y){if (x.x==y.x)   return x.ti>y.ti;return x.x>y.x;}
};
priority_queue<gmdingdan> gmc;
priority_queue<smdingdan> smc;/*
1 a x y表示第a个人想用x元每股的单价购买y股贵州茅台的股票。此时，如果他手上的钱足够x y，
那么，查找售卖池中是否有卖单，如果有，则将卖价小于等于x的卖单，按照卖价从小到大的顺序取出，
然后依次以卖价交易，直到这笔交易完整完成，或是没有满足条件的卖单。
此时，该笔交易剩余的需求进入购买池中。（购买池就是一堆买单组成的集合）如果他手上的钱不够x×y，或者他已经有一笔买单或者卖单尚未交易完毕，则本次需求被驳回。特别的，如果x=0，则代表购买价为当前交易系统最后一次的成交价格，如果没有成交过，则为0。
*/void goumai(int id,int x,int y,int ti){//表示第a个人想用x元每股的单价购买y股贵州茅台的股票。if (c[id]>=x*y&&vis[id]==0){//此时，如果他手上的钱足够x×yvis[id]=ti;//他有一笔订单int tot=y;while (smc.size()>0&&tot>0){//如果有，则将卖价小于等于x的卖单，按照卖价从小到大的顺序取出，smdingdan t=smc.top();if (t.x>x)  break;//取出卖价小于等于x的卖单smc.pop();if (vis[t.a]!=t.ti)    continue;else {//然后依次以卖价交易，直到这笔交易完整完成，或是没有满足条件的卖单。if (tot>=t.y){vis[t.a]=0;//交易a[id]+=t.y;c[id]-=t.x*t.y;a[t.a]-=t.y;c[t.a]+=t.x*t.y;//交易成功cnt++;las=t.x;tot-=t.y;}else {//这笔交易完整完成//交易a[id]+=tot;c[id]-=t.x*tot;a[t.a]-=tot;c[t.a]+=t.x*tot;//交易成功cnt++;las=t.x;smc.push({t.a,t.x,t.y-tot,t.ti});tot=0;break;}}}if (tot==0){//直到这笔交易完整完成vis[id]=0;return ;}else    gmc.push({id,x,tot,ti});//此时，该笔交易剩余的需求进入购买池中。（购买池就是一堆买单组成的集合）}else {//如果他手上的钱不够x×y，或者他已经有一笔买单或者卖单尚未交易完毕，则本次需求被驳回。return ;}
}/*
2 a x y表示第a个人想用x元每股的单价卖出y股。此时，如果他手上的股票数足够y股，
则，查找购买池中是否有买单，如果有，将买单价格大于等于x的买单，按照买价从大到小的顺序取出，
依次以买价交易，直到这笔交易完整完成，或是没有满足条件的买单。
此时，该笔交易剩余的需求进入售卖池中。如果他手上的股票不够y，或者他已经有一笔买单或者卖单尚未交易完毕，则本次需求被驳回。特别的，如果x=0，则代表售卖价为当前交易系统最后一次的成交价格，如果没有成交过，则为0。
*/void shoumai(int id,int x,int y,int ti){//表示第a个人想用x元每股的单价卖出y股if (a[id]>=y&&vis[id]==0){//此时，如果他手上的股票数足够y股vis[id]=ti;//他有一笔订单int tot=y;while (gmc.size()>0&&tot>0){//如果有，将买单价格大于等于x的买单，按照买价从大到小的顺序取出，gmdingdan t=gmc.top();if (t.x<x)  break;//取出单价大于等于x的买单gmc.pop();if (vis[t.a]!=t.ti)    continue;else {//依次以买价交易，直到这笔交易完整完成，或是没有满足条件的买单if (tot>=t.y){vis[t.a]=0;//交易a[id]-=t.y;c[id]+=t.x*t.y;a[t.a]+=t.y;c[t.a]-=t.x*t.y;//交易成功cnt++;las=t.x;tot-=t.y;}else {//这笔交易完整完成//交易a[id]-=tot;c[id]+=t.x*tot;a[t.a]+=tot;c[t.a]-=t.x*tot;//交易成功cnt++;las=t.x;gmc.push({t.a,t.x,t.y-tot,t.ti});tot=0;break;}}}if (tot==0){//直到这笔交易完整完成vis[id]=0;return ;}else    smc.push({id,x,tot,ti});}else {//如果他手上的股票不够y，或者他已经有一笔买单或者卖单尚未交易完毕，则本次需求被驳回return ;}
}/*
3 a表示第a个人想撤回自己正在交易的需求。
如果他有一笔买单或卖单尚未交易完成，则撤回剩余未交易成功的订单，否则，他的需求被驳回。注意：在交易时，如果有多笔符合条件的订单，则按价格的优先级排序，如果价格一样，则按照订单被生成的时间从小到大排序。
*/void chehui(int id){//如果他有一笔买单或卖单尚未交易完成，则撤回剩余未交易成功的订单vis[id]=0;//否则，他的需求被驳回return ;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>Q;for (int i=1;i<=n;i++)  cin>>a[i];for (int i=1;i<=n;i++)  cin>>c[i];for (int i=1;i<=Q;i++){cin>>op>>id;if (op==1){//表示第a个人想用x元每股的单价购买y股贵州茅台的股票cin>>x>>y;if (x==0)   x=las;goumai(id,x,y,i);}else if (op==2){//表示第a个人想用x元每股的单价卖出y股cin>>x>>y;if (x==0)   x=las;shoumai(id,x,y,i);}else {//表示第a个人想撤回自己正在交易的需求chehui(id);}}cout<<cnt<<"\n";for (int i=1;i<=n;i++)  cout<<a[i]<<" ";cout<<"\n";for (int i=1;i<=n;i++)  cout<<c[i]<<" ";cout<<"\n";return 0;
}