Codeforces Round 908 (Div. 2) 解题报告
T1 题目解析
A/B双人竞技赛规则：每轮需先赢得X局者胜，整个比赛需先赢得Y局者胜。已知总比赛局数n(1≤n≤20)及各局胜负记录，判定最终胜者。
关键观察：最终决胜局的胜利者即为整体胜者。由于比赛会在决出胜负时终止，故只需取最后一局结果。
#include <bits/stdc++.h>
using namespace std;
int main() {
int testCases;
cin >> testCases;
while (testCases--) {
int roundCount;
string resultSequence;
cin >> roundCount >> resultSequence;
cout << resultSequence[roundCount-1] << endl;
}
return 0;
}T2 题目解析
给定数组a，构造数组b(元素值仅限1/2/3)，需满足以下三个条件中的恰好两个：
- 存在i,j使a[i]=a[j]且b[i]=1,b[j]=2
- 存在i,j使a[i]=a[j]且b[i]=1,b[j]=3
- 存在i,j使a[i]=a[j]且b[i]=2,b[j]=3
解法策略：对重复元素采用差异化赋值。统计每个数值出现次数，优先为高频元素分配不同值。当重复元素数量不足时返回-1。
#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 105;
int inputArray[MAX_SIZE], outputArray[MAX_SIZE];
int main() {
int testCases;
cin >> testCases;
while (testCases--) {
int arraySize;
cin >> arraySize;
memset(outputArray, 0, sizeof(outputArray));
for (int i=1; i<=arraySize; ++i) {
cin >> inputArray[i];
outputArray[inputArray[i]]++;
}
int duplicateGroups = 0;
for (int i=1; i<=100; ++i) {
if (outputArray[i] > 1) duplicateGroups++;
}
if (duplicateGroups < 2) {
cout << "-1\n";
continue;
}
int valueCounter = 2;
for (int i=1; i<=arraySize; ++i) {
if (outputArray[inputArray[i]] > 1 && valueCounter < 4) {
cout << valueCounter << " ";
valueCounter++;
outputArray[inputArray[i]] = 0;
} else {
cout << "1 ";
}
}
cout << "\n";
}
return 0;
}T3 题目解析
给定初始序列a和目标序列b，判断是否存在经过k次合法操作后能转化为b。每次操作需选择满足a[x]=x的元素，执行x次循环移位。
核心发现：每次操作后a[n]的位置值会保持稳定。通过逆向推导，每次移动量等于当前a[n]的值。当移动量超过序列长度时判定不可行。
#include <bits/stdc++.h>
using namespace std;
const int MAX_LEN = 2e5 + 5;
int sequence[MAX_LEN];
int main() {
int testCases;
cin >> testCases;
while (testCases--) {
int length, operationCount;
cin >> length >> operationCount;
for (int i=1; i<=length; ++i) cin >> sequence[i];
if (operationCount > length) operationCount = length;
int shiftAmount = 0;
bool isValid = true;
for (int step=1; step<=operationCount; ++step) {
if (sequence[length - shiftAmount] > length) {
isValid = false;
break;
}
shiftAmount += sequence[length - shiftAmount];
if (shiftAmount >= length) shiftAmount -= length;
}
cout << (isValid ? "Yes" : "No") << "\n";
}
return 0;
}T4 题目解析
给定两个序列a和b，构造新序列c使得最长递增子序列长度最短。a序列顺序固定，b序列元素可任意插入位置。
最优策略：将b排序后按升序插入a中。这样保证新增元素不会破坏原有LIS结构，最终LIS长度等于原a序列的LIS长度。
#include <bits/stdc++.h>
using namespace std;
const int MAX_LEN = 2e5 + 5;
int main() {
int testCases;
cin >> testCases;
while (testCases--) {
int aSize, bSize;
cin >> aSize >> bSize;
// 实现逻辑略
}
return 0;
}T5 题目解析
定义多重集合的不优美度为元素值等于集合长度的出现次数。给定m个多重集合，每个集合包含若干不同元素的多个副本。需选择每个集合选取的元素数量区间[l_i, r_i]，使最终合并集合的不优美度最小。
关键点：对于每个集合，优先选取较小的元素值，以减少与集合长度相等的元素数量。通过贪心策略选择最优的元素组合。
