这是C,B,G题的个人想法
C
要让数组总和最大，核心原则是：能替换成的数越大，总和就越大。结合题目操作规则，最终最优解是： 首尾元素无法被修改，保留原值；中间所有元素都替换成整个数组的全局最大值（这是能填充的最大数值），此时总和最大。
1. 分析操作规则的本质约束
题目允许任意次操作：选区间 (l, r)，将区间内元素替换为 max(a[l], a[r])。 约束 1：首尾元素永远无法被修改（因为操作只能改 “区间内” 的元素，首尾只能当区间端点，无法被其他区间包含）； 约束 2：要让总和最大，中间元素应尽可能替换成 “能达到的最大值”—— 而整个数组的全局最大值是所有元素中最大的，且一定能通过操作覆盖所有中间元素（比如以最大值所在位置为端点，分两次操作覆盖所有中间位置）。
2. 确定计算逻辑
基于约束，总和的计算公式为： 最终总和 = 第一个元素值 + 最后一个元素值 + 全局最大值 × (数组长度 - 2) 数组长度 - 2：中间可替换的元素数量（总长度减去首尾 2 个不可修改的元素）； 全局最大值 × 中间元素数量：中间所有元素都替换成全局最大值的总和； 加上首尾元素：这两个元素无法修改，只能保留原值。
代码展示：
using namespace std;
int main() {
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
long long a1, a2, x;
long long global_max = 0;
cin>>a1;
global_max = a1;
for(int i=1;i<=n-2;i++){
cin>>x;
if(x > global_max) {
global_max = x;
}
}
if(n>=2){
cin>>a2;
if(a2 > global_max) {
global_max = a2;
}
}
if(n<=2){
long long m;
if(n==1){
m=a1;
}
else{
m=a1+a2;
}
cout<<m<<endl;
continue;
}
cout<<a1 + a2 + global_max*(n-2)<<endl;
}
return 0;
}
B
核心思路：
先通过降序排列找到最大得分（等于a中大于b最小值的数字个数），再通过将a分为 “大于b_min” 和 “小于b_min” 两段，得出方案数是两段阶乘的乘积
（1）最大得分的推导：为什么是 “a 中大于 b 最小值的数字个数”？
- 你的核心观察非常关键，我们用通俗的语言拆解这个结论：
- 前提：题目规则是 “小苯和小红各出一张牌，小苯牌大则得分 + 1，然后两张牌都删除；重复此过程直到牌用完”。
- 最优策略（降序排 a）：把a降序排列后，小苯每次都用当前最大的牌去匹配小红的牌 —— 而小红的牌里最小的那个b_min是最容易被赢的。
- 关键结论：
- 所有a中大于b_min的数，无论匹配小红的哪张牌，最终一定会 “赢一次”（因为哪怕先匹配小红的大牌，输了之后这张a的数会去匹配更小的b，最终总能赢b_min）；
- 所有a中小于b_min的数，永远赢不了任何一张b的牌（因为b_min是小红最小的牌）。
- 因此，最大得分 = a中大于b_min的数字个数（记为x），剩余y = n - x个数永远赢不了。
（2）方案数的推导：为什么是x! * y!？
- 你的 “两段划分” 逻辑是这个结论的核心，我们用乘法原理和场景验证拆解：
- 必要条件：要拿到最大得分x，必须保证 “所有大于b_min的a的数，都能在b_min被匹配前用完 / 匹配到”—— 而实现这个目标的唯一要求是：把所有大于b_min的数放在a的前x个位置，小于的放在后y个位置。
- 如果不这么做（比如把一个小于b_min的数放在前x位），这个数会先匹配小红的牌，赢不了，且会 “占用一次匹配机会”，导致后面一个大于b_min的数无法匹配到b_min，得分减少。
- 乘法原理应用：
- 前x个位置（大于b_min的数）：内部可以任意排列，有x!种方式；
- 后y个位置（小于b_min的数）：内部可以任意排列，有y!种方式；
- 总方案数 = 前一段排列数 × 后一段排列数 = x! * y!（全程取模998244353）。
代码展示：
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int MAXN = 2e5 + 10;
ll fact[MAXN];
void preprocess() {
fact[0] = 1;
for (int i = 1; i < MAXN; i++) {
fact[i] = fact[i-1] * i % MOD;
}
}
int main() {
preprocess();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n), b(n);
int min_b = INT_MAX;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) {
cin >> b[i];
min_b = min(min_b, b[i]);
}
int x = 0;
for (int num : a) {
if (num > min_b) x++;
}
int y = n - x;
ll ans = fact[x] * fact[y] % MOD;
cout << ans << endl;
}
return 0;
}
G
核心思路：
放弃暴力遍历区间内所有数，转而精准枚举「折叠数可能最大」的关键候选数，通过计算这些候选数的折叠数来找到最大值。
1.核心观察：
折叠数的大小由反转后的数字高位决定，而末尾全是 9 的数（如 9、19、99、129、999 等）反转后高位是 9，折叠数大概率最大，因此这类数是最优解的核心候选。
2.枚举策略：
围绕 “末尾全 9 的数” 分层构造候选集，而非遍历全部数： 优先找 R 附近个位为 9 的数（比如 R=123 则找 119）； 再找与 R 位数匹配的全 9 数（比如 R=1234 则找 999）； 最后遍历所有位数的 “末尾全 9 数”（9、99、999…），覆盖所有可能； 兜底检查区间端点 L/R，避免极端情况漏检。
代码展示：
using namespace std;
long long reverse_num(long long a) {
long long res = 0;
while (a > 0) {
int dig = a % 10;
res = res * 10 + dig;
a /= 10;
}
return res;
}
int main() {
int t;
cin >> t;
while (t--) {
long long l, r;
cin >> l >> r;
long long max_fold = 0;
long long start = max(l, r - 1000);
for (long long x = start; x <= r; x++) {
max_fold = max(max_fold, reverse_num(x));
}
long long tenk = 1;
while (tenk <= r * 10) {
long long candidate = (r / tenk) * tenk + (tenk - 1);
if (candidate > r) {
if (r / tenk == 0) break;
candidate = (r / tenk - 1) * tenk + (tenk - 1);
}
if (candidate >= l && candidate <= r) {
max_fold = max(max_fold, reverse_num(candidate));
}
tenk *= 10;
}
cout << max_fold << endl;
}
return 0;
}
京公网安备 11010502036488号