2026牛客寒假算法基础集训营1

B

https://ac.nowcoder.com/acm/contest/120561/B

假设小红手上所有牌中最小的为x，将小笨手上比x大和比x小的牌分为两部分，那么小笨手上所有比x大的牌都会被移除，移除的数量就是最高得分，因此答案就是两部分的全排列结果相乘。

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

const int mod = 998244353;
const int N = 2e5 + 10;
typedef long long LL;
int t, n;
int a[N], b[N];

LL fact[N];

void f(){
	fact[0] = 1;
	for (int i = 1; i < N; i++)
		fact[i] = (fact[i - 1] * i) % mod;
}

void sol(){
	cin >> n;
	int minb = 1e6 +10;
    for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++){
		cin >> b[i];
		if (b[i] < minb) minb = b[i]; 
	}	
	int t = 0, k;
	for (int i = 1; i <= n; i++)
		if (a[i] > minb)
			t++;
	k = n - t;
	cout << (fact[t] * fact[k]) % mod << endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	f();
	cin >> t;
	while (t--) sol();
}

C

https://ac.nowcoder.com/acm/contest/120561/C

找到最大数的位置，尽可能大的覆盖区间。注意运算时候要用long long类型，比赛时没注意wa了好几次。

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

const int N = 5e7+10;
int t, n;
int a[N];

void sol(){
	cin >> n;
	
	for (int i = 1; i <= n; i++) cin >> a[i];
	if (n == 1){
		cout << a[1] << endl;
		return;
	}
	else if (n == 2){
		cout << a[1] + a[2] << endl;
		return;
	}
	int maxn = 1;
	for (int i = 2; i <= n; i++)
		if (a[i] > a[maxn])
			maxn = i;
 	if (maxn == 1)
		cout << (long long)a[maxn] * (n-1)+a[n] << endl;
	else if (maxn == n)
		cout << (long long)a[maxn] * (n-1) + a[1] << endl;
	else
		cout << (long long)a[maxn]*(n-2)+a[1]+a[n] << endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while (t--) sol();
}

E

https://ac.nowcoder.com/acm/contest/120561/E

简单想一下就是用下标模拟循环移位找最大值，注意类型long long

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

typedef long long LL;
LL t, n, k;

void sol(){
	cin >> n >> k;
	n++;
	vector<LL> vec(n);
	vec[n-1] = k;
	for (int i = 0; i < n-1; i++)	cin >> vec[i];
	LL maxn = -1e15;
	for (int i = 0; i < n; i++){
		maxn = max(maxn, (LL)(vec[i] + vec[(i + 1) % n]));
	}
	cout << maxn << endl;
}

int main(){
	cin >> t;
	while (t--) sol();
}

G

https://ac.nowcoder.com/acm/contest/120561/G

这道题是我觉得在我们能力范围内比较需要耐心的一道模拟题。

看位数是否相同，如果相同看看可操作的位数是否可以构造成末尾尽可能多的9，如果不相同，可以选择去掉一位全部构造成9，也可以将结尾构造尽可能多的9。最后相同位数直接输出构造出来的就行，不相同位数就比较两个构造的谁更大

里面细节很多，不是特别好些，在比赛时候写出来还是很哇塞的

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

int t;

bool cmp(string a, string b){
	if (a.size() != b.size())
		return a.size() > b.size();
	return a > b;
}

void sol(){
	string x, y;
	cin >> x >> y;
	int k, len1 = x.size(), len2 = y.size();
	k = len2;
	string s;
	bool f;
	//长度相同看有几位可以操作
	if (len1 == len2){
		f  = true;
		int i = 0;
		while (i < len1 && x[i] == y[i]) i++;
		k = len1 - 1 - i;
	}else{//长度不同构造len-1位全9的最大数
		f = false;
		for (int i = 1; i <= len2 - 1; i++)
			s.push_back('9');
	}
	//构造末尾全为9的最大数
	for (int i = len2 - 1; i >= 1 && k > 0; i--, k--){
		if (y[i] != '9' && ((i == 1 && y[0] > '1') || (i != 1 && y[i - 1] > '0'))){
			y[i - 1]--;
			for (int j = i; j < len2; j++)
				y[j] = '9';
		}
	}
	//删除前导0
	while (y.back() == '0')
		y.pop_back();
	reverse(y.begin(), y.end());
	if (f){
		cout << y << endl;
	}else{
//		cout << "*" << s << ' ' << y << endl;
//		cout << max(s, y, cmp) << endl;
		if (cmp(s, y))
			cout << s << endl;
		else
			cout << y << endl;
	}
}

int main(){
	cin >> t;
	while (t--){
		sol();
	}
}

K

https://ac.nowcoder.com/acm/contest/120561/K

诈骗题，3以内有解，从4开始手动模拟一下就知道不可能

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

typedef long long LL;
int t, n;

void sol(){
	cin >> n;
	if (n == 1){
		cout << "YES" << endl;
		cout << 1 << endl;
	}
	else if (n == 3){
		cout << "YES" << endl;
		cout << 1 << ' ' << 2 << ' ' << 3 << endl;
	}
	else{
		cout << "NO" << endl;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while (t--) sol();
}

L

https://ac.nowcoder.com/acm/contest/120561/L

打表，2的倍数打5,5的倍数打2，其余打10

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

typedef long long LL;
int k[10] = {1,10,5,10,5,2,5,10,5,10};

void sol(){
	LL n;
	cin >> n;
	cout << k[n % 10] << endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	sol();
}