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)
原