Practice.
A. Colored Balls: Revisited
题意
给定 \(n\) 个染有颜色的球，定义操作为选定两个不同颜色的球并将两个球拿走。
在满足总和为奇数的情况下，输出只剩下一种颜色的球后，球的颜色编号。
思路
显然，我们将数量小的和数量次小的球拿走，最后肯定会剩下数量最多的那个颜色。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define all(x) x.begin(),x.end()
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
vector<pii> cnt(n);
for(int i=0;i<n;i++) {
cin >> cnt[i].fs;
cnt[i].sc = i + 1;
}
sort(all(cnt));
cout << cnt[n - 1].sc << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}很蠢
B. Best Permutation
题意
对于一个排列 \(p\)，定义它的值的计算方式如下：
令 \(x = 0\)；
枚举 \(p_i\)，如果 \(x < p_i\)，那么 \(x = x + p_1\)，否则 \(x = 0\)。
最后，\(x\) 即为 \(p\) 的值
现在，给定排列的长度，构造一个值最大的排列并输出。
思路
显然，我们不难发现，最后的 \(x\) 一定为 \(n + n - 1\)，我们找不出其他排列满足这个条件。
那么，我们来考虑如何构造：
我们将 \(n - 1, n\) 放在序列的最后，那么如果剩余的数的个数为偶数，我们直接按顺序放入 \(i, i - 1\) 即可，这样即可每隔两个数清空 \(x\)。
如果个数为奇数，那么我们不妨塞上 \(1, 2, 3\)，然后继续放即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define all(x) x.begin(),x.end()
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
if(n == 4) cout << "2 1 3 4\n";
else{
if(n % 2 == 1) cout << "1 2 3 ";
for(int i=n-2;i>=(n % 2 == 1 ? 4 : 1);i--) cout << i << ' ';
cout << n - 1 << ' ' << n << '\n';
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}主打一个差点看错题
C. Digital Logarithm
题意
定义 \(f(x)\) 等于 十进制下 \(x\) 所有位数之和。
给定两个序列 \(a, b\)，定义一次操作为选定任意 \(a_i\) 并将其赋值为 \(f(a_i)\)，或选定任意 \(b_i\) 并将其赋值为 \(f(b_i)\)。
输出最小的操作数，使两个序列升序排序后相等。
思路
我们可以用优先队列实现。
我们先将所有 \(a_i, b_i\) 分别放入两个优先队列中，然后枚举 \(a, b\) 中的头元素。
如果头元素相等，那么把这对数取出，否则，我们对较大的头元素执行一次操作，然后继续遍历，最后一定可以得到答案。
不难证明这样操作得到的答案就是最小的。
时间复杂度：小于\(O(3n \log (3n))\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
priority_queue<int> a, b;
for(int i=0;i<n;i++) {
int cur;
cin >> cur;
a.emplace(cur);
}
for(int i=0;i<n;i++) {
int cur;
cin >> cur;
b.emplace(cur);
}
int ans = 0;
while(!a.empty()){
if(a.top() == b.top()){
a.pop();
b.pop();
continue;
}
ans ++;
if(a.top() > b.top()){
a.emplace(to_string(a.top()).size());
a.pop();
}else{
b.emplace(to_string(b.top()).size());
b.pop();
}
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}我写的更模拟（
D. Letter Picking
题意
给定一个字符串，以及两个玩家 \(Alice, Bob\)。
\(Alice\) 先手。每次操作中，玩家可以选择字符串的第一个或最后一个字符，将其取出并拼接到自己的字符串的前面。
两个人足够聪明，输出最后字典序最小的玩家。
思路
我们不妨换个角度考虑这题：
如果我们从最后的状态向前推，那么就等价于我们将拿出的字符拼接到两个选手的字符串后面。
这就好办了，只要前面没有出现平局，那么后面无论怎么操作都无法改变胜负。
因而，我们考虑从小区间递推到大区间的思路，也就是区间 \(dp\)。
我们定义 \(dp[i][j]\) 为 \([i, j]\) 区间内的胜负情况，\(-1\) 为 \(Alice\) 赢，\(0\) 为平局，\(1\) 为 \(Bob\) 赢，那么 \(dp[0][n]\) 就是答案。
那么，我们只需分讨递推即可。
对于 \(A\) 的不同选择，我们分别取最小值。
对于 \(B\) 的不同选择，我们分别取最大值。
然后，如果前一个状态是平局，我们就判断当前的胜负，否则我们就从上一个状态递推得到答案。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
int calc(char a, char b){
return a == b ? 0 : (a > b ? 1 : -1);
}
void solve(){
string s;
cin >> s;
int n = s.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for(int len=2;len<=n;len+=2){
for(int l=0;l+len<=n;l++){
int r = l + len;
dp[l][r] = 1;
//Alice choose the left
int now = -1;
if(dp[l + 1][r - 1] != 0) now = max(now, dp[l + 1][r - 1]);
else now = max(now, calc(s[l], s[r - 1]));
if(dp[l + 2][r] != 0) now = max(now, dp[l + 2][r]);
else now = max(now, calc(s[l], s[l + 1]));
dp[l][r] = min(dp[l][r], now);
//Alice choose the right
now = -1;
if(dp[l + 1][r - 1] != 0) now = max(now, dp[l + 1][r - 1]);
else now = max(now, calc(s[r - 1], s[l]));
if(dp[l][r - 2] != 0) now = max(now, dp[l][r - 2]);
else now = max(now, calc(s[r - 1], s[r - 2]));
dp[l][r] = min(dp[l][r], now);
}
}
cout << (dp[0][n] == 0 ? "Draw\n" : (dp[0][n] == 1 ? "Bob\n" : "Alice\n"));
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}还真没想到倒着搞，该加训了（