Codeforces Round 882 (Div. 2)

A.The Man who became a God

题目大意

给定一个数组 \({x_1,x_2,⋯,x_n}\) 和一个整数 \(k\)，记 \(f(l,r)=∑_{i=0}^{i≤r−l}∣x_l+i−x_l+i+1∣\)，求将数组划分为 \(k\) 个部分的划分方案，使得对每个部分的 \(f(l,r)\) 之和最小.

思路

求出相邻两个元素的差值，去掉前 \(m\) 个大的差值以后的差值和为答案。

memset(b, 0, sizeof(b));
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
	cin >> a[i];
for (int i = 1; i < n; i++)
	b[i] = abs(a[i] - a[i + 1]);
sort(b + 1, b + n + 1);
int ans = 0;
for (int i = 1; i <= n - k + 1; i++)
	ans += b[i];
cout << ans << endl;

B Hamon Odyssey

题目大意

长长长......link

思路

首先我们已知

\[\min(a,b)≥a \&b\\ \]

所以每两个数一直两两相与一定会形成一个不下降序列，易得 \(a_1 \& a_2\&...\&a_n\) 为最题意中的小值

因为这个值是最小值，所以当这个数 \(>0\) 时，使用其他分组的答案和一定比这个答案大，所以只能分一组，也就是一整组为一组

当最小值为 \(0\) 时，我们考虑从 \(a_1\) 一直遍历到 \(a_n\) ，一定会有一种情况使得 \(a_1 \& a_2...\&a_i\) 的值为 \(0\) ，因为保底到 \(a_n\)

当出现为 \(0\) 的情况时，就切一刀，分一组，因为要尽量分多组，且 \(0\) 已经是最小的了。

#include <bits/stdc++.h>
using namespace std;
int t, n;
int a[200004];
int ans, minn, an = -1;
int main()
{
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n >> a[1];
        int minn = a[1];
        for (int i = 2; i <= n; i++)
            cin >> a[i], minn = minn & a[i];
        if (minn > 0)
        {
            puts("1");
            continue;
        }
        int an = -1, ans = 0;
        for (int i = 1; i <= n; i++)
        {
            if (an == -1)
                an = a[i];
            an &= a[i];
            if (an == 0)
            {
                an = -1;
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

C.Vampiric Powers, anyone?

题目大意

link

思路

我们发现对于 \(l,r\) 我们先取 \(r\) 再取 \(l\) 进行操作，然后我们就发现， \(r+1 \to n\) 的位置都无效了,因为 \(A \oplus B\oplus B=A\) ,\(r+1\) 到 \(n\) 异或了两次，自然无效

所以我们可以把问题转化为

给定一个序列 \(a\) ,求 \(a\) 中的区间最大异或和

很容易想到 \(dp\)，我们令 \(dp_{i,j}\) 为以 \(i\) 为结尾的区间知否有可能异或和为 \(j\)

边界条件：\(dp_{0,0}=1,dp_{i,a_i}=1\)

状态转移方程

\[dp_{i,j \oplus a_i}|=dp_{i-1,j} \]

很容易想到，将那个区间再添加一个 \(a_i\) 的值就行了

我们枚举所有可能的 \(j\) (也就是所有状态) 即可

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
bool dp[N][1 << 8 | 1];
int a[N];

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        dp[0][0] = 1;
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < (1 << 8); j++)
                dp[i][j] = 0;
            for (int j = 0; j < (1 << 8); j++)
            {
                dp[i][j ^ a[i]] |= dp[i - 1][j];
                if (dp[i][j])
                    ans = max(ans, j);
            }
            dp[i][a[i]] = 1;
            ans = max(ans, a[i]);
        }
        cout << ans << endl;
    }
    return 0;
}