【cf】Codeforces Round 882（Div.2）题解 A - C

A. The Man who became a God

题意

把一个长度为 n 的数组分成 k 段，要求每一段中相邻元素差值之和相加起来最小

思路

把相邻元素的差值全部算出来排序，因为可以分成 k 段，中间有（k - 1）个间隔，所以删去最大的（k - 1）个，输出其余元素的和

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

const int N = 110;

int t, n, k;
int a[N];
vector<int> b;

void solve()
{
	cin >> n >> k;
	b.clear();
	
	for (int i = 0; i < n; i ++ ) cin >> a[i];
	for (int i = 1; i < n; i ++ ) b.push_back(abs(a[i] - a[i - 1]));
	sort(b.begin(), b.end());
	
	int ans = 0;
	for (int i = 0; i < n - k; i ++ ) ans += b[i];
	cout << ans << endl;
}

int main()
{
	cin >> t;
	while (t -- )
	{
		solve();
	}
	return 0;
}

B. Hamon Odyssey

题意

把一个长度为 n 的数组分成任意段，要求每一段取 & 的值相加最小，输出可以分成的最大段数

思路

看整个数组能分成多少个取 & 为 0 的段，每出现一段为 0 的就将 ans + 1，如果整段取 & 都不为 0 就输出 1

代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 200010;

int t, n;
int a[N];

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    int ans = 0, temp = 0;
    for (int i = 0; i < n; i ++ )
    {
        if (temp == 0) temp = a[i];
        else temp = a[i] & temp;

        if (temp == 0) ans ++ ;
    }
    if (ans == 0) ans = 1;
    cout << ans << endl;
}

int main()
{
    cin >> t;
    while (t -- )
    {
        solve();
    }
    return 0;
}

C. Vampiric Powers, anyone?

题意

在数组中每次取最后任意长度的子序列，求异或和，将这个值加到数列末尾，求任意次操作后能加到末尾的最大值是多少

思路

（思路参考了榜单第一的代码
任意长度子序列都可以通过给定操作消去
比如说结尾两个数是 1, 2，只要在后面添上 1, 2 的异或和，就可以消去结尾的 1, 2 对新添加的数产生的影响
根据这个性质，题目就转换成，数列中任意元素异或和的最大值

代码

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int t, n;

void solve()
{
	cin >> n;
	set<int> X;
    X.insert(0);
    int curr_xor = 0;
	int ans = 0;
	for (int i = 1; i <= n; i ++ ) 
	{
		int a;
		scanf("%d", &a);
		curr_xor ^= a;
		for (int x : X) ans = max(ans, curr_xor ^ x);
		X.insert(curr_xor);
     }
	 cout << ans << endl;
}
 
int main() 
{
	cin >> t;
	while (t -- )
	{
		solve();
	}
	return 0;
}