每日一题-20250809

发表于 阅读次数： 本文字数： 604 阅读时长 ≈ 2 分钟

Leetcode

231. 2 的幂

  • 位运算

太简单（

判一下二进制位上是否至多存在一个 1 即可。注意数据里面有负数（

1
2
3
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n.bit_count() <= 1

Codeforces

easy

CF2057C/Rating 1500

  • 位运算
  • 贪心
  • 构造

考虑二进制下的某一位，这一位能对答案产生贡献当且仅当 a,b,ca, b, c 三个数在这一位上不都相同。

因此我们可以构造：

a=(0111…1)2b=(1000…0)2\begin{aligned} a &= (0111\dots 1)_2 \\ b &= (1000\dots 0)_2 \end{aligned}

为了让 aa 和 bb 都在 [L,R][L, R] 区间范围内，在前面拼一个前缀即可，cc 随意挑一个就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def getBit(x: int, i: int):
    return x & (1 << i)

def solve():
    l, r = map(int, input().split())
    pre = 0
    for i in range(30, -1, -1):
        if getBit(l, i) != getBit(r, i):
            x, y = (1 << i) - 1, 0
            x += pre
            y += pre + (1 << i)
            z = l if x != l and y != l else r
            print(x, y, z)
            return
        pre += (1 << i) if getBit(l, i) else 0
    return

t = int(input())
for _ in range(t):
    solve()

hard

CF1101G/Rating 2300

  • 位运算
  • 线性基

首先考虑无解：由于是任取若干子段，如果整个序列异或和为 00 ，则当所有子段都被取出时就寄了，无解。

既然是区间异或和，考虑前缀异或和 pi=⨁j=1iajp_i = \bigoplus_{j = 1}^i a_j，则一段区间 [l,r][l, r] 的异或和为 pr⊕pl−1p_r \oplus p_{l - 1}。

要求任意子段的异或和都非 00，可以考虑把 p1,p2,…,pnp_1, p_2, \dots, p_n 都插入线性基，如果 pip_i 能插入，说明在这里到目前没有任何一个子段能表示出 pip_i，否则，说明前面的某几个子段相互异或可以表示出 pip_i，必须要在这里分段。

答案即为线性基的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
#define endl '\n'
#define ioclear std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);

using i64 = long long;

struct Basis
{
    using i64 = long long;
    using T = i64;
    static const int n = 60;
 
    T p[n + 10] {};
    T siz = 0;
 
    void add(T x)
    {
        for(int i = n; i >= 0; i--)
            if(x >> i & 1)
            {
                if(p[i] == 0)
                {
                    p[i] = x;
                    siz++;
                    break;
                }
                x ^= p[i];
            }
        return;
    }

    T size()
    {
        return siz;
    }
 
    bool query(T x)
    {
        for(int i = n; i >= 0; i--)
            if((x >> i & 1) && p[i] != 0)
                x ^= p[i];
        return x == 0;
    }
    
    T mx()
    {
        T ans = 0;
        for(int i = n; i >= 0; i--)
            ans = std::max(ans, (ans ^ p[i]));
        return ans;
    }
};

void solve()
{
    int n;
    std::cin >> n;
    int pre = 0;
    Basis basis;
    for(int i = 1; i <= n; i++)
    {
        int x;
        std::cin >> x;
        pre ^= x;
        basis.add(pre);
    }
    if(pre == 0)
        std::cout << "-1\n";
    else
        std::cout << basis.size() << endl;

}

int main()
{
    #ifdef ONLINE_JUDGE
    ioclear;
    #endif

    int t = 1;
    // std::cin >> t;
    while(t--)
        solve();
}