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

【比赛记录】2025CSP+NOIP 冲刺模拟赛合集Ⅱ

2025CSP-S模拟赛65(HZOJ CSP-S模拟37)

A B C D Sum Rank
100 40 15 - 155 7/12

HZOJ 上也有这场比赛,但我没看见。放过去大概是个 14/24 左右吧。

A. gcd&xor (gcdxor)

首先打表,发现对于所有合法的 \((x,y)\),都满足 \(y-x|x\)。于是有 \(O(n\log^2n)\) 的做法,枚举 \(y-x\),再枚举 \(x\),暴力判断合不合法。\(10^7\) 跑不过去,但 \(10^5\) 能跑过。考虑以 \(10^5\) 分块,将每个块前缀的答案打表出来,然后再用上面那个做法处理散块即可。

Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define gcd __gcd
using namespace std;
namespace asbt{
const int B=1e5;
const ll pre[]={0,173407,347890,522448,696846,871744,1046284,1220431,1395236,1570280,1745100,1919875,2093695,2267837,2442059,2617018,2791283,2966683,3141146,3315871,3490365,3666781,3839968,4013813,4188010,4362066,4536292,4710801,4884960,5060158,5234883,5408205,5583629,5758317,5933666,6107019,6282382,6458098,6631521,6804281,6980543,7155409,7332425,7505250,7678957,7852680,8026427,8200183,8374902,8548938,8723182,8897288,9071582,9246092,9420147,9594727,9768429,9942808,10117875,10291162,10467026,10640553,10813783,10989926,11164092,11338740,11513448,11687394,11863511,12037297,12210785,12385489,12560986,12736987,12911711,13084959,13258776,13431315,13604565,13779830,13956088,14130677,14305355,14480650,14657932,14830769,15004603,15178361,15352044,15525831,15699840,15873481,16047556,16221400,16395321,16570018,16744419,16919172,17092225,17266746,17440305};
int n;
int main(){freopen("gcdxor.in","r",stdin);freopen("gcdxor.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0);cin>>n;int id=n/B;ll ans=pre[id];
//	cout<<ans<<'\n';
//	cout<<n/B;for(int i=1;i<=n;i++){
//		cout<<i<<' '<<(id*B+i)/i*i-i<<'\n';for(int j=max((id*B+i)/i*i-i,i);j+i<=n;j+=i){if((j^(i+j))==gcd(j,i+j)){
//				cout<<j<<' '<<i+j<<'\n';ans++;}}}cout<<ans;return 0;
}
}
int main(){return asbt::main();}

B. 异或树 (xortree)

因为树始终是完全二叉树,所以除了叶子节点之外的店的子树异或和是不会改变的。用维护每种叶子节点的数量,修改时维护答案即可。

Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e4+5,mod=998244353;
int m,kk,ans[maxn],a[maxn],b[maxn];
int main(){freopen("xortree.in","r",stdin);freopen("xortree.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0);cin>>kk>>m;ans[kk]=1,a[kk]=1;while(m--){int opt,x;cin>>opt>>x;if(opt==1){for(int i=0;i<1<<13;i++){b[i]=0;}for(int i=0;i<1<<13;i++){(ans[i]+=mod-a[i])%=mod;(ans[i^x]+=a[i])%=mod;(b[i]+=a[i])%=mod;(b[i^x]+=a[i])%=mod;}for(int i=0;i<1<<13;i++){a[i]=b[i];(ans[i]+=a[i])%=mod;}}else{cout<<ans[x]<<'\n';}}return 0;
}
}
int main(){return asbt::main();}

C. 符文石 (stone)

我们需要点 \(u\) 能走到的所有权值,考虑在拓扑过程中用 set 直接维护。但显然这样时间复杂度爆炸,考虑哪些数是没用的。由于 \(a\operatorname{bitand}b\le\min(a,b)\),所以 \(u\)set\(\le ans_u\) 的数直接扔掉。考虑大于 \(ans_u\) 的数,考虑它们于 \(ans_u\) 不同的最高位,显然 \(ans_u\) 这一位为 \(0\) 而这个数这一位为 \(1\)。而如果还有另一个数这一位也为 \(1\),那么 \(ans_u\) 就不是最大的按位与值了。所以大于 \(ans_u\) 的数最多有 \(O(\log V)\) 个。暴力合并即可。时间复杂度 \(O(m\log^2V)\)

Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=5e5+5;
int n,m,a[maxn],d[maxn],ans[maxn];
vector<int> e[maxn];
queue<int> q;
struct opt{il bool operator()(const int &x,const int &y)const{return a[x]<a[y];}
};
set<int,opt> st[maxn];
int main(){freopen("stone.in","r",stdin);freopen("stone.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];st[i].insert(i);}for(int i=1,u,v;i<=m;i++){cin>>u>>v;d[u]++,e[v].pb(u);}for(int i=1;i<=n;i++){ans[i]=-1;if(d[i]==0){q.push(i);}}while(q.size()){int u=q.front();q.pop();
//		cout<<u<<' '<<ans[u]<<'\n';for(int v:e[u]){if(--d[v]==0){q.push(v);}ans[v]=max(ans[v],ans[u]);for(int x:st[u]){for(int y:st[v]){if(x==y){continue;}ans[v]=max(ans[v],a[x]&a[y]);}}for(int x:st[u]){if(a[x]>=ans[v]){st[v].insert(x);}}if(a[*st[v].rbegin()]<=ans[v]){st[v].clear();continue;}for(auto it=st[v].begin();it!=st[v].end();it++){if(a[*it]>ans[v]){st[v].erase(st[v].begin(),it);break;}}}}for(int i=1;i<=n;i++){cout<<ans[i]<<' ';}return 0;
}
}
signed main(){return asbt::main();}

D. 彩色括号 (witch)

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

相关文章:

  • 羊驼二次免疫的六大风险:纳米抗体制备不可忽视的 “隐形陷阱”
  • 完整教程:C++项目:仿muduo库高并发服务器-------connection模块
  • 深入解析:线性代数 SVD | 令人困扰的精度 1
  • 营销数字化专家要求
  • 小程序反编译包的架构文件
  • 10.22 CSP-S模拟37/2025多校冲刺CSP模拟赛7 改题记录
  • [题解]P11126 [ROIR 2024] 三等分的数组 (Day 2)
  • Acrobat Pro DC 2025下载及破解安装教程,附永久免费免激活中文版Acrobat Pro DC安装包(稳定版)
  • VSLAM 十四讲--阅读中知识点记录
  • 数据库学习篇(持续更新中)
  • Fortinet产品安全漏洞分析:FGFM协议未经认证连接重置漏洞
  • 李超线段树
  • fiddler修改请求(修改搜索框的内容)
  • 20251022
  • 10月22号
  • 将“百度”的URL改为“163网易云”(修改URL地址)
  • Yolo11分割模型
  • 星旗笔试
  • 智联笔记项目——251022登录注册、后端管理及内容类型处理优化
  • 2025.10.22博客
  • 这是一个测试文档
  • JavaScript formatter插件的使用
  • 完整教程:基于WebAssembly的STEP文件3D在线查看器实现详解
  • 20232407 2025-2026-1 《网络与系统攻防技术》 实验二实验报告
  • 10.21 CSP-S模拟36 改题记录
  • 20232406 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • 程序员必备!5款小白也能秒上手的AI编程工具
  • 笔记本 copilot按键 PowerToys映射
  • 实用指南:86-python电网可视化项目-6
  • 详细介绍:3.5mm耳机插座技术全解析:从镀层工艺到阻抗稳定性测试