2024-07-12 23:15 已编辑重庆科技大学 C++ 发布于广东

关注

牛客小白月赛98出题人题解

更新：

F 题假了，出题人在此向本场比赛的收到影响的选手道歉！！已经把F题题解删除，如果有大佬想到了正解，欢迎讨论。

hack例子：

5 5
1 0 0 0 -7

答案应该是 $7$ 。

A. 骰子魔术

Tag：签到

若存在一个 $a_i=x$ 则输出 YES，否则输出 NO。

Code

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, x;
    std::cin >> n >> x;
    
    for (int i = 1; i <= n; i++) {
        int a;
        std::cin >> a;
        if (a == x) {
            std::cout << "YES\n";
            return 0;
        }
    }
    
    std::cout << "NO\n";
    
    return 0;
}

B. 最少剩几个

Tag：简单贪心

观察两种操作：

$a_i+a_j$ 是奇数 $\iff$ $a_i$ 与 $a_j$ 其中一个是奇数，另一个是偶数。
$a_i\times a_j$ 是奇数 $\iff$ $a_i$ 与 $a_j$ 都必须是奇数。

由此我们发现，想要消除偶数，必须配一个奇数；要消除奇数，配奇数或者偶数都可以。

所以我们简单贪心即可：优先奇偶配对，然后剩下的奇奇配对即可。

Code

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    int odd = 0, even = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        std::cin >> x;
        if (x % 2) odd++;
        else even++;
    }
    
    int same = std::min(odd, even);
    
    std::cout << even - same + (odd - same) % 2 << '\n';
    
    return 0;
}

C. 两个函数

Tag：数学，推公式

观察函数的形式，发现是递推，容易得到：

$g(x)=\begin{cases}a&x=1\\a^2(1+2+3+...+x-1)&x>1\end{cases}$

当 $x>1$ 发现就是一个等差数列求和，可以 $O(1)$ 计算。

注意，当 $x=1$ ， $g(1)=a\mod 998244353$ ，要注意取模，这是一个易WA点，有些人会忘了取模这时候。

Code

#include <bits/stdc++.h>

using LL = long long;
const int mod = 998244353;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int Q;
    std::cin >> Q;
    
    while (Q--) {
        int a, x;
        std::cin >> a >> x;
        if (x == 1) {
            std::cout << a % mod << '\n';
        } else {
            std::cout << 1LL * x * (x - 1) / 2 % mod * a % mod * a % mod << '\n';
        }
    }
    
    return 0;
}

D. 切割 01 串 2.0

Tag：区间DP

考虑区间DP，令 $dp_{l,r}$ 表示考虑 $[l,r]$ 的 $01$ 串最多能切割几次，转移的时候枚举切割点 $k$ 即可，同时判断一下切割是否合法，判断切割是否合法的时候可以用前缀和，这样总的时间复杂度就为 $O(n^3)$ 。

状态转移方程：

dp_{l,r}=\begin{cases}0&l=r\\\max_{l\leq k<r}\{dp_{l,k}+dp_{k+1,r}+1\}&l\not=r,且满足切割条件\end{cases}

Code

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, L, R;
    std::cin >> n >> L >> R;
    
    std::string s;
    std::cin >> s;
    s = '?' + s;
    
    std::vector<int> sum0(n + 1, 0), sum1(n + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        sum0[i] = sum0[i - 1] + (s[i] == '0');
        sum1[i] = sum1[i - 1] + (s[i] == '1');
    }
    
    std::vector dp(n + 1, std::vector<int>(n + 1, 0));
    
    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            if (len == 1) continue;
            int r = l + len - 1;
            for (int k = l; k < r; k++) {
                int dif = std::abs(sum0[k] - sum0[l - 1] - sum1[r] + sum1[k]);
                if (dif >= L && dif <= R) {
                    dp[l][r] = std::max(dp[l][r], dp[l][k] + dp[k + 1][r] + 1);
                }
            }
        }
    }
    
    std::cout << dp[1][n] << '\n';
    
    return 0;
}

E. and xor and

Tag：观察性质，拆位，双指针，二分，ST表

本题方法很多，这里随便展开几种讲一下。

首先注意到当 $k_1,k_2$ 很大的时候是没用的，因为 $a_i\leq 10^{18}$ ，所以我们只要考虑 $60$ 位，这里可以提前判掉一些情况。

观察到单调性，不难发现 $(a_l\&a_{l+1}\&...\&a_r)\oplus(a_l|a_{l+1}|...|a_r)$ ，当 $l$ 固定， $r$ 增大的时候， $(a_l\&a_{l+1}\&...\&a_r)$ 是变小的， $(a_l|a_{l+1}|...|a_r)$ 是变大的，有两个角度可以得出其单调不降的结论，根据 $a\oplus b=a|b-a\&b$ 可知；或者你按位来看， $\&$ 可能会让某一位置为 $0$ ， $|$ 可能会让某一位变成 $1$ ，这样 $1\oplus0=1$ ，即可能让某一位变成 $1$ ，不难发现其值一定是单调不降的。

所以我们基于这个单调性，可以得到很多做法（且这种做法不要求上下界是 $2$ 的次幂）：
- 双指针 + 按位维护区间 and 和区间 or，复杂度瓶颈 $O(60n)$ 。
- ST 表预处理区间 and 和区间 or，然后在双指针（或者二分），复杂度瓶颈 $O(n\log n)$ 。
没观察到单调性，但由于给出的上下界都是 $2$ 的次幂，容易往拆位想，观察 $\ge 2^{k_1}$ ，其相当于要求我们 $(\&...\&)\oplus(|...|)$ 的值在 $[k_1,60]$ 位中存在至少一个 $1$ ，而 $<2^{k_2}$ ，其相当于要求 $(\&...\&)\oplus(|...|)$ 的值在 $[k_2,60]$ 位中不能存在一个 $1$ 。基于这两个发现，我们容易得到双指针的做法，我们枚举位 $k$ ，在 $\ge 2^{k1}$ 的角度上看，其实就要求在区间 $[l,r]$ 中所有的 $a_i$ 在第 $k$ 位中至少存在一个 $1$ 和 $0$ ；在 $<2^{k_2}$ 的角度上看，其实就要求在区间 $[l,r]$ 中所有的 $a_i$ 在第 $k$ 位全是 $0$ 或者全是 $1$ 。据此我们根据这两个角度，可以用双指针得到对于每一个左端点 $l$ ，所对应合法的右端点 $r$ 是一个区间 $[r_a,r_b]$ 。

........（当然还有其他角度，方法比较多，复杂度也有所不同，但终究切入点还是从二进制考虑）

Code

法1：双指针+按位维护区间 and 和区间 or

#include <bits/stdc++.h>
using LL = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k1, k2;
    std::cin >> n >> k1 >> k2;
    k2 = std::min(k2, 60);
    if (k1 >= k2) {
        std::cout << 0 << '\n';
        return 0;
    }
    
    std::vector<LL> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    
    auto solve = [&](LL x) {
        LL res = 0;
        std::vector<int> cnt(61, 0);
        LL OR = 0, AND = 0;
        auto update = [&](LL x, int len, int v) {
            OR = AND = 0;
            for (int i = 0; i <= 60; i++) {
                if (x >> i & 1) {
                    cnt[i] += v;
                }
                if (cnt[i] > 0) {
                    OR |= 1LL << i;
                }
                if (len && cnt[i] == len) {
                    AND |= 1LL << i;
                }
            }
        };
        for (int i = 1, j = 1; i <= n; i++) {
            update(a[i], i - j + 1, 1);
            while (j <= n && (OR ^ AND) > x) {
                update(a[j], i - j, -1);
                j++;
            }
            res += i - j + 1;
        }
        return res;
    };
    
    
    std::cout << solve((1LL << k2) - 1) - solve((1LL << k1) - 1) << '\n';
    
    return 0;
}

法2：ST 表预处理区间 and 和区间 or，然后在双指针

#include <bits/stdc++.h>
using LL = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k1, k2;
    std::cin >> n >> k1 >> k2;
    k2 = std::min(k2, 60);
    if (k1 >= k2) {
        std::cout << 0 << '\n';
        return 0;
    }
    
    std::vector<LL> a(n + 1);
    
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    
    int LOG = std::__lg(n);
    
    std::vector AND(n + 1, std::vector<LL>(LOG + 1));
    std::vector OR(n + 1, std::vector<LL>(LOG + 1));
    
    for (int j = 0; j <= LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            if (!j) {
                AND[i][j] = a[i];
                OR[i][j] = a[i];
            } else {
                AND[i][j] = AND[i][j - 1] & AND[i + (1 << (j - 1))][j - 1];
                OR[i][j] = OR[i][j - 1] | OR[i + (1 << (j - 1))][j - 1];
            }
        }
    }
    
    auto ask_AND = [&](int l, int r) {
        int k = std::__lg(r - l + 1);
        return AND[l][k] & AND[r - (1 << k) + 1][k];  
    };
    auto ask_OR = [&](int l, int r) {
        int k = std::__lg(r - l + 1);
        return OR[l][k] | OR[r - (1 << k) + 1][k];  
    };
    
    LL ans = 0;
    
    LL down = 1LL << k1, up = 1LL << k2;
    
    for (int i = 1, j1 = 1, j2 = 1; i <= n; i++) {
        while (j1 <= n && (ask_AND(i, j1) ^ (ask_OR(i, j1))) < down) j1++;
        while (j2 <= n && ((ask_AND(i, j2)) ^ (ask_OR(i, j2))) < up) j2++;
        ans += j2 - j1;
    }
    std::cout << ans << '\n';
    
    return 0;
}

法3：ST 表预处理区间 and 和区间 or，然后二分

#include <bits/stdc++.h>
using LL = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k1, k2;
    std::cin >> n >> k1 >> k2;
    k2 = std::min(k2, 60);
    if (k1 >= k2) {
        std::cout << 0 << '\n';
        return 0;
    }
    
    std::vector<LL> a(n + 1);
    
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    
    int LOG = std::__lg(n);
    
    std::vector AND(n + 1, std::vector<LL>(LOG + 1));
    std::vector OR(n + 1, std::vector<LL>(LOG + 1));
    
    for (int j = 0; j <= LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            if (!j) {
                AND[i][j] = a[i];
                OR[i][j] = a[i];
            } else {
                AND[i][j] = AND[i][j - 1] & AND[i + (1 << (j - 1))][j - 1];
                OR[i][j] = OR[i][j - 1] | OR[i + (1 << (j - 1))][j - 1];
            }
        }
    }
    
    auto ask_AND = [&](int l, int r) {
        int k = std::__lg(r - l + 1);
        return AND[l][k] & AND[r - (1 << k) + 1][k];  
    };
    auto ask_OR = [&](int l, int r) {
        int k = std::__lg(r - l + 1);
        return OR[l][k] | OR[r - (1 << k) + 1][k];  
    };
    
    LL ans = 0;
    
    LL down = 1LL << k1, up = 1LL << k2;
    
    for (int i = 1; i <= n; i++) {
        int lo = i, hi = n + 1;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if ((ask_AND(i, mid) ^ ask_OR(i, mid)) >= down) hi = mid;
            else lo = mid + 1;
        }
        int j1 = lo;
        lo = i - 1, hi = n;
        while (lo < hi) {
            int mid = (lo + hi + 1) >> 1;
            if ((ask_AND(i, mid) ^ ask_OR(i, mid)) < up) lo = mid;
            else hi = mid - 1;
        }
        int j2 = lo;
        ans += std::max(0, j2 - j1 + 1);
    }
    std::cout << ans << '\n';
    
    return 0;
}

法4：根据拆位分 $\ge 2^{k1}$ 和 $<2^{k_2}$ 两个角度去双指针

#include <bits/stdc++.h>
typedef long long LL;


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int n, k1, k2;
	std::cin >> n >> k1 >> k2;
	
	std::vector<LL> a(n);
	
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
	}
	
	constexpr int m = 60;
	
	k2 = std::min(m, k2);
	
	if (k1 >= k2) {
		std::cout << 0 << '\n';
		return 0;
	}
	
	std::vector<int> l(n, n), r(n, n);
	for (int s = k1; s <= m; s++) {
		for (int i = 0, j1 = 0, j2 = 0, c0 = 0, c1 = 0; i < n; i++) {
			while (j1 < n && !c0) {
				c0 += !(a[j1++] >> s & 1);
			}
			while (j2 < n && !c1) {
				c1 += a[j2++] >> s & 1;
			}
			if (c0 && c1) {
				l[i] = std::min(l[i], std::max(j1, j2) - 1);
			}
			c0 -= !(a[i] >> s & 1);
			c1 -= a[i] >> s & 1;
		}
	}
	
	for (int s = k2; s <= m; s++) {
		for (int i = 0; i < n; i++) {
			int j = i;
			while (j < n && (a[j] >> s & 1) == (a[i] >> s & 1)) j++;
			for (int k = i; k < j; k++) {
				r[k] = std::min(r[k], j - 1);
			}
			i = j - 1;
		}
	}
	
	LL ans = 0;
	
	for (int i = 0; i < n; i++) {
		ans += std::max(0, r[i] - l[i] + 1);
	}
	
	std::cout << ans << '\n';
	
	
	return 0;
}