Codeforces 1038部分题解

$A$A：统计前 $k$k个字符最少的字符个数，乘上 $k$k即可

代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
char s[N];
int cnt[26];
int n, k;
void solve() {
	scanf("%d%d%s", &n, &k, s + 1);
	for(int i = 1; s[i]; i++)
		cnt[s[i] - 'A']++;
	
	int Ma = N;
	for(int i = 0; i < k; i++)
		Ma = min(Ma, cnt[i]);
		
	printf("%d\n", Ma * k);
}

int main()
{
	int T = 1;
	//scanf("%d", &T);
	while(T--) {
		solve();
	}
} 

$B$B：
题意： 求使得前 $n$n个正整数分为两个集合后，两个集合之和的 $gcd>1$gcd>1的构造方案。
题解： 当 $n==1\mid \mid n==2$n==1∣∣n==2那么直接判 $No$No
当 $n\ge 3$n≥3：:一个构造的想法：奇数放一块，偶数放一块。
证明：
设 $x$x为偶数的个数，则 $x=\lfloor \frac{n}{2}\rfloor$x=⌊2n​⌋。
设 $y$y为奇数的个数，则 y=x+(n&1)
由等差数列公式，前 $k$k个正偶数和为 $k\times (k+1)$k×(k+1)，前 $k$k个正奇数和为 $k^2$k2
当 $x=y$x=y，即 $n$n为偶数，则 $gcd(x\times (x+1),x^2)=x\ge 2$gcd(x×(x+1),x2)=x≥2，
当 $y=x+1$y=x+1，即 $n$n为奇数，则 $gcd(x\times (x+1),(x+1{)}^2)=(x+1)\ge 2$gcd(x×(x+1),(x+1)2)=(x+1)≥2

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;

void solve() {
	scanf("%d", &n);	
	
	if(n == 1 || n == 2) puts("No");
	else {
		puts("Yes");
		printf("%d", (n + 1) / 2);
		for(int i = 1; i <= n; i += 2) printf(" %d", i);
		puts("");
		printf("%d", n / 2);
		for(int i = 2; i <= n; i += 2) printf(" %d", i);
		puts("");
	} 
}

int main()
{
	int T = 1;
	//scanf("%d", &T);
	while(T--) {
		solve();
	}
} 

$C$C：
题意： $A,B$A,B两个人分别有两个序列，初始两人分数均为 $0$0，每回合每人可以选自己序列中的数 $x$x，然后自己得分加 $x$x，或者可以删除对方序列中的一个数 $x$x，使其无法再选到这个数，一个序列中可能有多个值相同的数。 $A$A先手，两人都采用最优策略，则 $max\left(sum\right(A-B\left)\right)$max(sum(A−B))等于多少。
题解： 两个列表均从大到小排个序，每次选择时，若自己可以加的最大分大于对方当前的最大分，则加，否则删掉对方的最大分。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
int a[N], b[N];
int n;

void solve() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);	
	for(int i = 0; i < n; i++) scanf("%d", &b[i]);
	sort(a, a + n); reverse(a, a + n);
	sort(b, b + n); reverse(b, b + n);
	a[n] = b[n] = -1;
	
	int a1 = 0, b1 = 0;
	ll sum1 = 0, sum2 = 0;
	while(n--) {
		if(a[a1] >= b[b1]) {
			sum1 += a[a1];
			a1++;
		}
		
		else b1++;
		
		if(b[b1] >= a[a1]) {
			sum2 += b[b1];
			b1++;
		}
		else a1++;
	}
	
	printf("%lld\n", sum1 - sum2);
}

int main()
{
	int T = 1;
	//scanf("%d", &T);
	while(T--) {
		solve();
	}
} 

题意： 给定 $n$n个史莱姆的价值，每个史莱姆（价值为 $x$x）可以吞噬其左边或右边相邻的史莱姆（价值为 $y$y），吞噬后该史莱姆的价值为 $x-y$x−y，问只剩一个史莱姆时，该史莱姆可以达到的最大价值。
题解： 当 $n=1$n=1，直接输出其价值。
当 $n\ge 2$n≥2：
若全正或全负，则找到价值绝对值最小的史莱姆，从这个开始吞噬其他史莱姆，则可以得到最大可能值为 $\sum \left(abs\right(v[1,n]\left)\right)-2\times min\left(abs\right(v\left[i\right]\left)\right)$∑(abs(v[1,n]))−2×min(abs(v[i]))
若有正有负，则对于任意一个史莱姆，都要找到与其价值正负相反的史莱姆进行吞噬或被吞噬。
那么对于史莱姆的吞噬先后顺序就有要求了，若 $a$a吞噬 $b$b后，全正或者全负，则调换成 $b$b吞噬 $a$a，否则任意。最后得到答案即 $\sum \left(abs\right(v[1,n]\left)\right)$∑(abs(v[1,n]))。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 5e5 + 10;

void solve() {
	int n; scanf("%d", &n);
	
	ll sum = 0, Mi = 1e9 + 7, m1 = 0, m2 = 0;
	for(int i = 1; i <= n; i++) {
		ll x; scanf("%lld", &x); 
		if(n == 1) {
			printf("%lld\n", x);
			return ;
		}
		if(x < 0) m1 = 1;
		if(x > 0) m2 = 1;
		ll t = abs(x);
		Mi = min(Mi, t);
		sum += t;
	}
	
	printf("%lld\n", sum - 2ll * (m1 && m2 ? 0 : Mi));
}

int main()
{
	int T = 1;
	//scanf("%d", &T);
	while(T--) {
		solve();
	}
} 

$E$E：待补