UVa10718 Bit Mask

題目連結

  • 題意:求一個數字 M[L,U] 之間,使得 N or M 最大,如果有多個 M 滿足,輸出最小的。
  • 題解:把每個 bit 拆開來判斷,一開始設 M=0,設 NiN 個第 i 位 bit,有兩種情況可以讓 M+=2i,第一種是 Ni=0M+2i<=U 的話,第二種是 Ni=1 且 如果 M 不加 2i 就會 <L
    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
    #pragma GCC optimize("O2")
    #include <bits/stdc++.h>
    using namespace std;
    using LL = long long;
    using ULL = unsigned long long;
    using PII = pair<int, int>;
    using PLL = pair<LL, LL>;
    using VI = vector<int>;
    using VVI = vector<vector<int>>;
    const int INF = 1e9;
    const int MXN = 0;
    const int MXV = 0;
    const double EPS = 1e-9;
    const int MOD = 1e9 + 7;
    #define MP make_pair
    #define PB push_back
    #define F first
    #define S second
    #define FOR(i, L, R) for (int i = L; i < (int)R; ++i)
    #define FORD(i, L, R) for (int i = L; i > (int)R; --i)
    #define IOS \
    cin.tie(nullptr); \
    cout.tie(nullptr); \
    ios_base::sync_with_stdio(false);

    int main()
    {
    IOS;
    unsigned int N, L, U;
    while (cin >> N >> L >> U)
    {
    unsigned int ans = 0;
    FORD(i, 31, 0 - 1)
    {
    if (((N & (1U << i)) && ((ans | (1U << i)) <= L)) ||
    (!(N & (1U << i)) && ((ans | (1U << i)) <= U)))
    {
    ans |= (1 << i);
    }
    }
    cout << ans << '\n';
    }
    }

如果你覺得這篇文章很棒,請你不吝點讚 (゚∀゚)

Recommended Posts