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

2025多校冲刺CSP模拟赛7

news 2025/10/22 14:35:16

2025多校冲刺CSP模拟赛7

不是你怎么还有加赛？ys

A. gcd&xor (gcdxor)

转化为外层枚举 \(\gcd\)，内层枚举 \(i,j\)，打表即可。可以发现规律，是调和级数做法，时间复杂度大约 \(O(1.5 \times 10^8)\)。

Code：

#include<bits/stdc++.h>
#define int long longusing namespace std;const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar()                                                              \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt)     \? EOF                                                                 \: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{int x=0,c=getchar(),f=0;for(;c>'9'||c<'0';f=c=='-',c=getchar());for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return f?-x:x;
}
inline void write(int x)
{if(x<0) x=-x,putchar('-');if(x>9)  write(x/10);putchar(x%10+'0');
}// #ifndef ONLINE_JUDGE
// #define ONLINE_JUDGE
// #endif// int logn[1<<20];
// vector<pair<int,int> > v[20][1<<16];signed main()
{// #ifndef ONLINE_JUDGEfreopen("gcdxor.in","r",stdin);freopen("gcdxor.out","w",stdout);int n;int ans=0;cin>>n;for(int i=1;i<=n;i++)for(int j=i;j<=n-i;j+=i)ans+=(j^(j+i))==i;cout<<ans;// for(int i=2;i<(1<<20);i++) logn[i]=logn[i>>1]+1;// for(int k=1;;k<<=1)// {// 	int L=1<<logn[k],R=min(n,(1ll<<(logn[k]+1))-1);// 	if(L>n) break;// 	cerr<<L<<" "<<R<<"\n";// 	for(int i=L;i<=R;i++)// 	for(int j=i+1;j<=R;j++)// 	{// 		if(__gcd(i,j)==(i^j))// 		{// 			v[logn[k]][i^j].push_back(make_pair(i,j));// 			// cout<<i<<" "<<j<<" "<<(i^j)<<"\n";// 			ans++;// 		}// 	}// 	// cerr<<"\n------------------\n\n";// }// for(int i=1;i<=n;i++)// {// 	bool f=0;// 	for(int k=1;k<=logn[n];k++)// 	{// 		if(v[k][i].empty()) continue;// 		f=1;// 		cout<<"\nxor="<<i<<"\nk="<<k<<"\n";// 		for(auto nw:v[k][i]) cout<<nw.first<<","<<nw.second<<"\n";// 	}// 	if(f) cout<<"\n-----------------------------------------\n";// }// cout<<ans;// #endif//mt19937_64 myrand(time(0));return 0;
}

B. 异或树 (xortree)

暴力写假两次，std 写假一次。

发现规律。加一次点后，只有加操作之前的那些叶子节点的子树 xor 值会更改。非叶子节点的子树 xor 值均固定。

又发现值域很小。所以直接暴力 dp 更改即可。复杂度小常数 \(O(nV)\)，可以通过。

注意：有人 (HS_fu3) 使用 unordered_map 被卡常了。

Code：

#include<bits/stdc++.h>
#define int long longusing namespace std;const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar()                                                              \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt)     \? EOF                                                                 \: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{int x=0,c=getchar(),f=0;for(;c>'9'||c<'0';f=c=='-',c=getchar());for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return f?-x:x;
}
inline void write(int x)
{if(x<0) x=-x,putchar('-');if(x>9)  write(x/10);putchar(x%10+'0');
}// #ifndef ONLINE_JUDGE
// #define ONLINE_JUDGE
// #endifint k0,q;
struct Node{int op,x;
}a[1<<20];vector<int> E[1<<20];
int val[1<<20];
int cnt[8193];
int sum[1<<22];
int tot=1;void dfs(int p,int x)
{// cerr<<p<<" "<<x<<" "<<E[p].size()<<"\n";// exit(0);if(!E[p].size()){E[p].push_back(++tot);E[p].push_back(++tot);val[tot-1]=val[p];val[tot]=val[p]^x;return;}dfs(E[p][0],x);dfs(E[p][1],x);
}void find(int p)
{sum[p]=val[p];for(int to:E[p]){find(to);sum[p]^=sum[to];}cnt[sum[p]]++;
}signed main()
{//xortree// #ifndef ONLINE_JUDGEfreopen("xortree.in","r",stdin);freopen("baoli.out","w",stdout);k0=read();q=read();val[1]=k0;cnt[k0]=1;for(int i=1;i<=q;i++){int op=read(),x=read();a[i]={op,x};if(op==1){memset(cnt,0,sizeof(cnt));memset(sum,0,sizeof(sum));dfs(1,x);find(1);}else{// dd(1);cout<<cnt[x]<<"\n";}}// #endif//mt19937_64 myrand(time(0));return 0;
}