代码部落 20250629 CSP-S复赛 模拟赛

网址：代码部落

一    小小旅行者：

        思路：因为n最大为1e5,所以不能用最短路来做，根据题目可以直接想到：只需求出a与b异或后的值在二进制下1的个数即可：

        那么这时可能有人想到，在前往b的路上，小S会不会先到了一个不存在的点，然后在到达0-n以内的点？   实际上是不会的，只要从低位开始更改（举个栗子：）

输入  53 43 52

10（43）=2（101011）
10（52）=2（110100）
预计答案为 5
演示: 43-->42(101010)-->40(101000)-->44(101100)-->36(100100)-->52
其中并未越界 且答案确实为5

        代码：

#include<bits/stdc++.h>
using namespace std;
int n,a,b;
void ct(int m){
	int cnt=0;
	while(m){
		if(m%2==1) cnt++;
		m/=2;
	}
	cout<<cnt<<endl;
}//也可以用 ： __builtin_popcount(a ^ b);
int main(){
	cin>>n>>a>>b;
	int m=a^b;
	ct(m);
	return 0;
}

 二  随机表达式：

        思路：对于某个⽣成的公式，只要出现了⾄少⼀个 + 或者 - ，那就⼀定可以通过把 + 变成 - ，把 - 变成 + 来获得另⼀ 个公式。并且将这两个公式的结果相加后，第⼀个 + / - 后⾯的所有内容将会被正负抵消，对答案没有贡献。

        因此，真正对答案有贡献的部分应当是第⼀个 + / - 号之前的连续⼀段的异或和（即第⼀段的连续异或和）。 直接 for 循环枚举第⼀段连续异或的运算最⼤到哪个位置，记录S=A1^A2^…^Ai

        假设 A1~Ai是第⼀段连续异或运算的范围，注意分为两种情况：

        1. i<n 此时 Ai与Ai+1 之间需要放⼀个除异或以外的运算符，有2 种情况；及Ai+1之后还有N-i 个数 字，也就是还有 N-i-1个空位可以任意放运算符,有 pow(3,N-i-1) 种情况，因此对答案的贡献即Si*2*pow(3,N-i-1)

        2.i==n    贡献为Sn

        代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
int n;
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    vector<ll> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    vector<ll> ve(n + 1);
    ve[0]=1;
    for(int i=1;i<=n;i++)ve[i] = ve[i - 1] * 3 % mod;
    ll ans=0,xw=0;
    for(int i=0;i<n;i++){
    	xw^=a[i];
    	if(i<n-1){
    		int id=n-i-2;
    		ll ctas=xw%mod;
    		ctas=ctas*2%mod;
    		ctas=ctas*ve[id]%mod;
    		ans=(ans+ctas)%mod;
		}
		else ans=(ans+xw)%mod;
	}
    ans%=mod;
    if(ans<0)ans+=mod;
    cout<<ans<<endl;
}