NOIP模拟赛

2025年8月25日 ooliver OI

DAY1

A. 剪切字符串

可以想到一个简单的贪心，就是在最坏情况下，我两个字串长度都取 $1$ ，此时 $LCP$ 最大为 $3$ ，即每个 $LCP$ 最大为 $1$ 。所以我们贪心地认为 $i = 1$ ，此时可以对字符串 $c$ 中的每一个字母个数进行前缀和，然后枚举 $j$ ，判断 $c$ 的字串中能否找到一个字母异于 $a_{i}$ 和 $b_{j}$ 。代码如下：

#include
using namespace std;
const int N=1e5+5;
int T,n;
string a,b,c;
int sum[N][30];
int main(){
	freopen("lcp.in","r",stdin);
	freopen("lcp.out","w",stdout);
	cin>>T;
	while(T--){
		memset(sum,0,sizeof sum);
		int ans=3;
		cin>>n>>a>>b>>c;
		a=" "+a,b=" "+b,c=" "+c;
		for(int i=1;i

`#include
using namespace std;
const int N=1e5+5;
int T,n;
string a,b,c;
int sum[N][30];
int main(){
	freopen("lcp.in","r",stdin);
	freopen("lcp.out","w",stdout);
	cin>>T;
	while(T--){
		memset(sum,0,sizeof sum);
		int ans=3;
		cin>>n>>a>>b>>c;
		a=" "+a,b=" "+b,c=" "+c;
		for(int i=1;i
			for(int j=0;j30;j++) sum[i][j]+=sum[i-1][j];
			sum[i][c[i]-'a']++;
		}
		for(int i=2;i
			if(a[1]==b[i]){
				int cnt=sum[n][a[1]-'a']-sum[i][a[1]-'a'];
				if(cntmin(ans,1);
				else ans=min(ans,3);
			}
			else{
				int cnt=(sum[n][a[1]-'a']-sum[i][a[1]-'a'])+(sum[n][b[i]-'a']-sum[i][b[i]-'a']);
				if(cntmin(ans,0);
				else ans=min(ans,1);
			}
		}
		cout
	}
	return 0;
}`

DAY2

A. gcd&xor

一看到是数学题，直接枚举了一下 $100$ 以内的符合题意的数对，发现数对的一个充分不必要条件，即 $| a - b | = [PARSE ERROR: Undefined("Command(\"gcd\")")] (a, b)$ 。发现可以枚举 $[PARSE ERROR: Undefined("Command(\"gcd\")")]$ ，对于每一个 $i = [PARSE ERROR: Undefined("Command(\"gcd\")")]$ ，循环判断每一个 $j \oplus (j + i)$ 是否与 $i$ 相等，需要 $O (\sum_{i = 1}^{n} \frac{n}{i})$ 的复杂度。注意到： $\sum_{i = 1}^{n} \frac{n}{i} = n \sum_{i = 1}^{n} \frac{1}{i}$ 其中调和级数 $\sum_{i = 1}^{n} \frac{1}{i}$ 满足： $$ \sum^{n}_{i=1} \frac{1}{i} = \ln(n+1)+γ

#include
using namespace std;
int n,ans;
int main(){
	freopen("gcdxor.in","r",stdin);
	freopen("gcdxor.out","w",stdout);
	cin>>n;
	for(int i=1;i>1;i++) for(int j=i;j+i

`#include
using namespace std;
int n,ans;
int main(){
	freopen("gcdxor.in","r",stdin);
	freopen("gcdxor.out","w",stdout);
	cin>>n;
	for(int i=1;i>1;i++) for(int j=i;j+iif((j^(j+i))==i) ans++;
	cout
	return 0;
}`

B. 异或树

先讨论操作一：对于每个点权为 $w$ 的叶子节点，会新增两个点权分别为 $w$ 和 $w \oplus x$ 的子节点，对于子树异或和的贡献为两个值为 $w \oplus x$ 的子树，而对于叶子节点的贡献是新增一个点权为 $w \oplus x$ 的点。所以很容易想到去枚举每一次操作后的叶子节点。但是操作次数 $q \leq 8000$ ，又发现 $k_{0}, x \in [0, 2^{13})$ ，想到可以用两个桶数组分别存储答案和每个值对应叶子节点数量，并再用一个桶数组表示每个值新增叶子节点的数量，最后转移到总叶子节点桶数组即可，可以避免在同层加叶子节点时重复计算。代码：

#include
using namespace std;
#define int long long
int read(){
    int k=0,f=1;
    char c=getchar();
    while(c'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c

`#include
using namespace std;
#define int long long
int read(){
    int k=0,f=1;
    char c=getchar();
    while(c'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c'9')k=k*10+c-'0',c=getchar();
    return k*f;
}
const int N=8200,mod=998244353;
int k,q;
int t[N],tag[N],ntag[N];
signed main(){
	freopen("xortree.in","r",stdin);
	freopen("xortree.out","w",stdout);
	k=read(),q=read();
	t[k]=tag[k]=1;
	while(q--){
		int op,x;
		op=read(),x=read();
		if(op==1){
			for(int i=0;iif(tag[i]){
				(ntag[(i^x)]+=tag[i])%=mod;
				(t[(i^x)]+=2*tag[i])%=mod;
			}
			for(int i=0;itag[i]+=ntag[i])%=mod,ntag[i]=0;
		}
		else if(op==2) printf("%lld\n",t[x]%mod);
	}
	return 0;
}`

DAY3

只写了第一题，结果还挂了50分，现在玄关了……