题目链接：Codeforces Round 967 (Div. 2) - Codeforces
总结：B题没测试就交wa一发，C题一直没想到怎么回溯，哎。
A. Make All Equal
tag：签到
Solution：找到相同元素的最大值，将其它所有元素删去。
void solve(){
cin >> n;
vector<int> a(n);
map<int, int> mp;
int ans = 0;
for (int i = 0; i < n; i ++){
cin >> a[i];
mp[a[i]] ++;
ans = max(ans, mp[a[i]]);
}
cout << n - ans << endl;
}
B. Generate Permutation
tag：构造
Solution：对于一个数\(i\)，我们发现如果\(i - 1\)在它左边，则第二台打字机执行一次回车；如果在它右边，则第一台打字机执行一次回车。那么我们构造一个\(a_4a_2a_1a_3a_5\)。同时发现\(n\)是偶数，一定不行。
Competing：一下就猜中了，写完代码后没测试，wa一发。
void solve(){
cin >> n;
if (n % 2 == 0){
cout << "-1\n";
}
else{
vector<int> a(n);
int t = n - 1;
for (int i = 1; t; i ++){
a[i] = t;
t -= 2;
}
t = n;
for (int i = n; t >= 1; i --){
a[i] = t;
t -= 2;
}
for (int i = 1; i <= n; i ++){
cout << a[i] << " \n"[i == n];
}
}
}
C. Guess The Tree
tag：交互 + dfs
Description：给定一个\(n\)个节点的数，每次询问输出? a b，会返回一个节点\(x\)，使|d(x - a) - d(x - b)|最小。\(d(x, y)\)表示\(x\)到\(y\)的距离。如果有多个这样的节点，会返回使d(x, a)最小的节点。用最多\(15n\)次查询，得出树的结构。
Solution：分析每次询问得到的结果发现每次都会给出\(a, b\)路径上的中点\(mid\)，那么我们继续询问\(a, mid\)与\(mid, b\)，直到\(mid == a || mid == b\)。
- 需要记录每个节点的父节点，避免重复询问。
- 对于一棵树，我们可以假设任意一个节点为根
Competing：想到应该用\(mid\)继续往下问，但是没想到使用\(dfs\)，导致不知道如何回溯。
int query(int a, int b){
cout << "? " << a << " " << b << endl;
int x;
cin >> x;
return x;
}
void dfs(int a, int b){ // a是父节点
if (fa[a] && fa[b])
return;
int t = query(a, b);
if (a == t || t == b){
fa[b] = a;
ans.push_back({a, b});
return;
}
else{
dfs(a, t);
dfs(t, b);
}
}
void solve(){
cin >> n;
ans.clear();
for (int i = 0; i <= n; i ++){
fa[i] = 0;
}
fa[1] = 1;
while (ans.size() < n - 1){
for (int i = 2; i <= n; i ++){
if (fa[i] == 0){
dfs(1, i);
}
}
}
cout << "! ";
for (int i = 0; i < ans.size(); i ++){
cout << ans[i].fi << " " << ans[i].se << " ";
}
cout << endl;
}
D. Longest Max Min Subsequence
tag：思维 + 贪心 + 单调队列优化
Description：给定一个整数序列\(a\)，\(s\)是\(a\)的所有非空子序列的集合，要找到一个最长的\(s\)，如果有多个序列，则找出奇数位乘\(-1\)，之后字典序最小的序列。
n <= 3e5
Solution：我们首先可以确定哪些值是必须要选的。我们要保证能选出最长的序列，就需要记录每个值最后出现的位置，在最后出现的位置最小的元素之前我们可以任意选择，而不能先选在该元素之后的其他元素。
- 一个可选的区间内，对于奇数位我们选择值最大的元素，对于偶数位我们选择值最小的元素。如果我们每次暴力寻找，时间复杂度为\(O(n ^2)\)，考虑使用单调队列优化。
void solve(){
cin >> n;
vector<int> a(n + 1);
unordered_map<int, int> mp;
set<int> st;
for (int i = 1; i <= n; i ++){
cin >> a[i];
mp[a[i]] = i;
}
for (auto [x, y] : mp){ // 记录每个元素最后出现的位置
st.insert(y);
}
int sz = mp.size();
cout << sz << endl;
int s = 1;
int c = 0;
priority_queue<pii, vector<pii>, greater<pii>> smi; // 值从小到大，序号从小到大
priority_queue<pii, vector<pii>, greater<pii>> sma; // 值从大到下，序号从小到大
int tt = 0;
while (c < sz){
int et = *(st.begin()); // 当前最前面最后出现的元素的位置
int res, idx;
for (int i = s; i <= et; i ++){
if (mp[a[i]] != 0){ // 等于0说明选过了
smi.push({a[i], i});
sma.push({-a[i], i});
}
}
if ((c + 1) & 1){ // 选最大值
auto [x, y] = sma.top();
res = x, idx = y;
}
else{ // 选最小值
auto [x, y] = smi.top();
res = x, idx = y;
}
cout << a[idx] << " ";
st.erase(mp[a[idx]]); // 删除选择点的下标
mp[a[idx]] = 0;
s = et + 1;
c ++;
while (sma.size()){ // 删除选择过的元素或者下标小于当前值的元素
auto [x, y] = sma.top();
if (res > 0)
res = -res;
if (!mp[-x] || y <= idx)
sma.pop();
else
break;
}
while (smi.size()){
auto [x, y] = smi.top();
if (res < 0)
res = -res;
if (!mp[x] || y <= idx)
smi.pop();
else
break;
}
}
cout << endl;
}