源代码:ACM/OpenjudgeNow/Codeforces at master · abmcar/ACM (github.com)

A. Min Or Sum

题目大意:

思路:

a+b >= a|b,我们可以把a,b换成0,a|b,这种形式,最终,我们可以把数组替换为若干个0和一个数组|和

最终的和为数组 | 和

代码:

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

题目大意:

思路:

思考一下,如果我们发现了一个局部最大值,那么我们应该怎么操作?

如果改变较大的那个数,会发现可能导致新的局部最大值产生,因此,需要改变较小的值

选择后一个较小值(因为前面的已经操作过了),使得nums[i+1] = max(nums[i], nums[i + 2])即可

代码:

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

题目大意:

思路:

由于不最小化操作数,可以发现如果数组最后两个不递减,可以使得其他数都为最后两数之差(为负)

如果为负数,那么只有当前面的数也全为负数时才可能不递减,如果存在正数,则无法把num[x] 替换为小于 num[y]的(只有-正数才会更小),此时判断是否已经排序即可

代码:

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

题目大意:

思路:

很容易可以想到按位数dp

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

难点在于已有数的去重添加

如果我们去生成的话,数量会很大,难以承受(因为也是类fib上升)

正难则反,由于生成存在一定规律,我们可以做一个set存原始节点,判断后续每个数是否可以从该节点产生

如果末尾为1,则为从x*2+1生成

如果末尾为00,则为x*4生成

如果末尾为10,则不可生成

之后按照fib来dp即可

代码:

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;
}

Q.E.D.