Source code: ACM/OpenjudgeNow/Codeforces at master · abmcar/ACM (github.com)

Better reading experience: Jump coordinate

A. Min Or Sum

Main idea of the title:

Idea:

A + b > = a | B, we can replace a and B with 0,a|b. in this form, finally, we can replace the array with several zeros and an array | and

The final sum is the array | and

code:

void work()
{
    cin >> n;
    int ans = 0;
    for (int i=  1; i <= n; i++)
    {
        int temp;
        cin >> temp;
        ans |= temp;
    }
    cout << ans << Endl;
}

B. Avoid Local Maximums

Main idea of the title:

Idea:

Think about it. If we find a local maximum, what should we do?

If you change the larger number, you will find that it may lead to a new local maximum. Therefore, you need to change the smaller value

Select the latter smaller value (because the previous one has been operated), so that num [i + 1] = max (Num [i], Num [i + 2])

code:

void work()
{
    cin >> n;
    vector<int> nums(n + 3);
    for (int i = 1; i <= n; i++)
        cin >> nums[i];
    nums[0] = nums[n + 1] = 1e9;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1])
        {
            nums[i + 1] = max(nums[i], nums[i + 2]);
            ans++;
        }
    }
    cout << ans << endl;
    for (int i = 1; i <= n; i++)
        cout << nums[i] << " \n"[i == n];
}

C. Differential Sorting

Main idea of the title:

Idea:

Since the operands are not minimized, it can be found that if the last two of the array are not decremented, the other numbers can be the difference between the last two (negative)

If it is negative, it may not decrease only when the previous numbers are all negative. If there are positive numbers, num[x] cannot be replaced with less than num[y] (only - positive numbers will be smaller). At this time, judge whether it has been sorted

code:

void solution()
{
    cin >> n;
    nums.resize(n + 1);
    nums[0] = -1e14;
    for (int i = 1; i <= n; i++)
        cin >> nums[i];
    if (nums[n - 1] > nums[n])
    {
        cout << "-1" << endl;
        return;
    }
    else
    {
        if (nums[n] < 0)
        {
            if (is_sorted(nums.begin(), nums.end()))
                cout << 0 << endl;
            else
                cout << -1 << endl;
            return;
        }
    }
    cout << n - 2 << endl;
    for (int i = 1; i <= n - 2; i++)
        cout << i << " " << n - 1 << " " << n << endl;
}

D. Infinite Set

Main idea of the title:

Idea:

It's easy to think of the number dp

dp[i] = dp[i-1] + dp[i-2]

The difficulty lies in the de duplication and addition of existing numbers

If we generate it, the number will be very large and unbearable (because the class fib also rises)

Because there is a certain law in the generation, we can make a set to store the original node to judge whether each subsequent number can be generated from this node

If the end is 1, it is generated from x*2+1

If the end is 00, it is generated by x*4

If the end is 10, it cannot be generated

Then dp according to fib

code:

signed main()
{
    cin >> n >> p;
    nums.resize(n + 1);
    dp.resize(p + 50);
    for (int i = 1; i <= n; i++)
    {
        cin >> nums[i];
    }
    sort(nums.begin() + 1, nums.end());
    // cout << nums[1] << " " << nums[2] << endl;
    for (int i = 1; i <= n; i++)
    {
        int nowNum = nums[i];
        bool flag = false;
        while (nowNum > 0)
        {
            if (useful.count(nowNum))
            {
                flag = true;
                break;
            }
            if (nowNum & 1)
            {
                nowNum >>= 1;
            }
            else if (nowNum & 3)
            {
                break;
            }
            else
            {
                nowNum >>= 2;
            }
        }
        if (!flag)
            useful.insert(nums[i]);
    }
    vector<int> tmp(p + 50, 0);
    for (int it : useful)
        tmp[log2(it) + 1]++;
    int ans = 0;
    for (int i = 1; i <= p; i++)
    {
        dp[i] = tmp[i];
        if (i >= 2)
        {
            dp[i] += dp[i - 1];
            dp[i] = dp[i] % Mod;
        }
        if (i >= 3)
        {
            dp[i] += dp[i - 2];
            dp[i] = dp[i] % Mod;
        }
        ans += dp[i];
        ans = ans % Mod;
    }
    cout << ans << endl;
    return 0;
}