牛客2025秋季算法编程训练联赛4-基础组

牛客2025秋季算法编程训练联赛4-基础组_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

C 子段乘积

比赛时思路（没写出来OvO）：

本题一开始想到了一个方法，简单来说就是先乘上一个数然后除掉结尾的数每次运算进行取模，但是发现0这个数处理比较复杂，于是就一直纠结在处理0的问题上。怎样选择k个数，其中不包含0呢？

我想到了状态记录，将0位开始的k个数所对应的状态记录为1，其余为0，那就将以这个数据结尾的k个数相乘再取最大值就可以了。但是我忽视了时间复杂度，状态记录需要两层循环，时间复杂度是$O(nk)$超时了。

我又想到了个方法，就是用last记录上一次0出现的下标，如果当前非0数离上一个0距离>k,那就将以这个数据结尾的k个数相乘再取最大值，但是我想了好久都没有实现。

AC思路：

思路1：尺取法，l代表左端点，r代表右端点。l先不动，r往前扫描，如果成功扫到，有k个非0元素的子段就累成起来，最后把最左端的元素除了，左端点往前移动，l++，再继续扫描。再未达到k个非零元素的子段前，如果遇到0，当前的区间就废了 ,左端点直接到0的下一个位置。继续扫描。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const ll N  = 200005;
ll a[N];
ll Max = 0;//记录最终结果 
ll sum = 1;
ll Qpow(ll x,ll k)//快速幂求逆元 
{
    ll ans = 1;
    while(k)
    {
        if(k%2!=0) ans = ans*x%mod;
        k=k>>1;
        x=x*x%mod;
    }
    return ans;
}
int main()
{
    ll n,k;
    cin>>n>>k; 
    for(int i=1;i<=n;i++)
    {
       cin>>a[i];    
    }
    ll l = 1; //尺取法 
    ll r = 1;
    while(r<=n)
    {
        if(a[r]) //不是0就累乘直到达到k段子段 
        {
            sum=(sum*a[r])%mod;//sum是每一次扫描成功的值 
            if((r-l+1)%k==0) //达到k子段 
            {
                if(sum>Max) Max = sum;//题上要求取最大的 
                sum = sum*Qpow(a[l],mod-2)%mod;//逆元 ，原本是sum=sum/a[l] 。
                //一次扫描成功后，就吧最左端的元素除掉，再继续扫描。当然不能直接除 ，
                //这里需要用到逆元知识，不懂的可以去了解下 ，反正我那个式子就=（a[l]*a[l+1]*..*a[r]）/a[l] 
                //我是这样理解的，因为才学，可能有错误的地方，请指出 
                l++;
            }

        }
        else  //再未达到k个非零元素的子段前，如果遇到0，当前的区间就废了  
        {
             l = r + 1;// 左端点直接到0的下一个位置 
             sum = 1;//sum归1 
        }
        r++;
    }
    cout<<Max<<endl;
    return 0;
}

由于需要取模，所以要直到两个取模运算法则：

• (a * b) % mod = ((a % mod) * (b % mod)) % mod
• (a / b) % mod 需要用到费马小定理，具体可见算法文章

思路2 ：前缀零+前缀乘。（借鉴舍友的写法，我觉得思路挺好的，就学习下来了）思路请看注释。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL mod = 998244353;
const LL N = 2e5 +10;

int n, k, a[N];

LL pre_z[N], pre_mul[N] = {1}, maxx = 0;
//pre_z前缀零 pre_mul前缀乘 maxx字段乘积的最大值

LL quick_pow(LL x, LL p, LL mod)//快速幂求逆元
{
	LL ans = 1;
	
	x %= mod;
	
	while (p)
	{
		if (p & 1)
			ans = (ans * x) % mod;
		x = (x * x) % mod;
		p >>= 1;
	}
	
	return ans;
}

LL solve(LL a, LL b, LL mod)//费马小定理求(a  / b) % mod
{
	return (a % mod * quick_pow(b, mod - 2, mod)) % mod;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	
	for (int i = 1; i <= n; i++)
	{
		//初始化前缀零数组，pre_z[i]表示前i个数中有多少个0
		pre_z[i] = (pre_z[i - 1] + (a[i] == 0)) % mod;
		//初始化前缀乘数组，pre_z[i]表示前i个数乘积是多少(0视为1处理)
		pre_mul[i] = (pre_mul[i - 1] * (a[i] == 0 ? 1 : a[i])) % mod;
	}
	
	//滑动区间
	for (int i = k; i <= n; i++)
		if (pre_z[i] == pre_z[i - k])//找长度为k且没有0的区间
			maxx = max(maxx, solve(pre_mul[i], pre_mul[i - k], mod)); //求区间乘积
	
	cout << maxx << endl;
	
	/*滑动区间思考过程
	2 0 3 4  1   0 k = 3
	0 1 1 1  1   2
	2 2 6 24 24  24
	*/
	
	return 0;
}

D 子段异或

想了一会没啥思路就跳走做别的题目了^^(主要是看AC的人比较少)

前置知识：(下面的[xx,yy]代表从xx到yy的异或和)

[l,r]=a[l]⊕a[l+1]⊕…⊕a[r−1]⊕a[r]
[1,l−1]=a[1]⊕a[2]⊕…⊕a[l−2]⊕a[l−1]
[1,r]=a[1]⊕a[2]⊕…⊕a[r−1]⊕a[r]

所以有：[1,l−1]⊕[1,r]=[l,r]

所以预处理出所有的前缀异或和即可，由于需要[l,r]=0，故[1,l−1]=[1,r]

因此，只需要将所有前缀异或和相同的区间中选择两个区间的情况数相加即可。

由于选择两个区间正常需要计算组合数，这里给出一层循环就可以解决的方法：

这里可以用到map来计数，mp[k]表示前缀异或和为k的数量.

用sum记录从a[1]到当前位的前缀异或和，让答案加上之前前缀异或和为sum的序列的数量mp[sum] (加当前的配对数，"隐式"计算组合数)，最后让mp[sum]++.

初始化：如果没有 a[0] = 1，那么第一次遇到 Si=0 时，之前没有 0 的记录，就会漏算。

那为什么只有0需要初始化呢？因为只有sum=0的时候是从第一个元素开始的子段，而其他数值第一次出现时，无法形成异或为 0 的子段（因为需要两个相同的前缀异或），所以不需要预先初始化。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL N = 2e5 + 10;

LL n, sum, ans;
LL a[N];

map<LL, LL >mp;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	
	mp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		sum = sum ^ a[i];// 这里不是直接加组合数，而是加当前匹配数
		ans += mp[sum];
		mp[sum]++;
	}
	
	cout << ans << endl;
	
	return 0;
}