Codeforces Round 967 (Div. 2) 8.20

本文主要是介绍Codeforces Round 967 (Div. 2) 8.20，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

8.20 Div 2
- A. Make All Equal
- - 思路
  - 代码
- B. Generate Permutation
- - 思路
  - 代码
- C. Guess The Tree
- - 思路
  - 代码
- 总结

8.20 Div 2

Dashboard - Codeforces Round 967 (Div. 2) - Codeforces

A. Make All Equal

思路

题目中说相邻元素比大小，再删除，最后只剩相同元素。求最少运算次数。

找几个数字模拟一下就发现，凡是不同的总有办法删去，所以答案就是 $n - (最多相同元素个数)$

代码

int a[N];
void solve()
{int n,h=1,ans=1;cin>>n;fir(i,1,n)cin>>a[i];sort(a,a+n+1);fir(i,2,n){if(a[i]==a[i-1])h++;else{ans=max(ans,h);h=1;}}ans=max(ans,h);cout<<n-ans<<'\n';
}
signed main()
{IOSint t;cin>>t;while(t--)solve();return 0;
}

B. Generate Permutation

首尾两台打字机，分别可以进行

回车

写入

移动指针

求用两台打字机回车次数相同的数字序列

思路

发现，偶数永远不行。

奇数

正序输出 $[1, n /2]$ ,倒序输出 $[n, n /2 + 1]$

这样回车次数全为 $n /2 + 1$ .

代码

void solve()
{int n;cin>>n;if(n%2==0)cout<<"-1"<<'\n';else{fir(i,1,n/2)cout<<i<<" ";for(int i=n;i>n/2;i--)cout<<i<<" ";cout<<'\n';}
}

C. Guess The Tree

这是一道交互题

“? a b” - Misuki 会告诉你哪个节点 x 最小化了 |d(a,x)−d(b,x)| ，其中 d(x,y) 节点 x 和 y 之间的距离。如果存在不止一个这样的节点，那么 Misuki 会告诉您哪个节点能使 d(a,x) 最小化。
输出一行格式为"！ a1 b1 a2 b2 … an−1 bn−1 " (不带引号)，这意味着每个 1≤i≤n−1 节点的 ai和 bi之间都有一条边。您可以按任意顺序打印这些边。

思路

不断判断两个点x,b，如果输入a的是两点之一，说明二者之间有边，存起来，否则再询问a,b.类似于二分查找得出与b相连的边。

关键是x,b如何选取

我最初是相邻的两个进行判断，但出现了问题，有些边无法发现，后来改一下，样例1过了，边没漏，为什么也不太清楚，又出现问题超出测试 2 的空闲限制。

如果全以1为x,作为基准。看从1到各个点的最小化节点，是谁，再不断二分查找。

这样看起来就比较严谨。是因为这样：

不用担心想我之前一样会重复选择同一边，导致漏选

从1到x判断，最终找到ax所连边。

我们是从前往后找与某节点相连的边。如果（a>x)，不需要担心一会遍历到a会选择（xa）。因为都是从1开始判断，刚才结果是a,说明a比x距离1更近，就肯定不会考虑x。

代码

#define PII pair<int,int> 
#define fi first
#define se second
map<PII,int> mp; 
void solve()
{mp.clear();int n;cin>>n;fir(i,2,n){int x=1,b=i;while(x!=b){cout<<"? "<<x<<" "<<b<<'\n';int a;cin>>a;if(a==x||a==b) break;x=a;}mp[{x,b}]=1;}cout<<"! ";for(auto it:mp){cout<<it.fi.fi<<" "<<it.fi.se<<" ";}cout.flush();
}
signed main()
{ int t;cin>>t;while(t--) {     solve();}return 0;
}