每日一练2023.2.22

abc290

A

签

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
using namespace std;
int a[110];
int main () {
	int n, m;
	ll ans = 0;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= m; i++) {
		int x;
		scanf("%d", &x);
		ans += a[x];
	}
	printf("%lld\n", ans);
	return 0;
}

B

签

C

求一个序列的子序列中mex最大值
直接从0开始找就行

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
using namespace std;
int a[300010];
map<int, int> mp, pos;
int main () {
	int k, n;
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		mp[a[i]] = 1;
	}
	int cnt = 0;
	for (int i = 0; i < k; i++) {
		if (mp.count(i)) cnt++;
		else break;
	}
	printf("%d\n", cnt);
	return 0;
}

E

给定一个序列，每一个连续子序列都需要修改成为回文序列，求总共的修改次数之和
考虑拆贡献，对于一对点 （i,j）, 产生的总贡献为 \(min(i,n-j+1)\). 我们通过双指针来维护。

#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned long long 
using namespace std;
int a[200010];
map<int, int> mp;
int main () {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), mp[a[i]]++;
	int l = 1, r = n;
	ll ans = 0;
	while (l < r) {
		mp[a[l]]--, ans += (ll)l * (r - l - mp[a[l]]), l++;
		mp[a[r]]--, ans += (ll)(n - r + 1) * (r - l - mp[a[r]]), r--;
	}
	printf("%lld\n", ans);
}