有点爆。感觉自己速度又慢效果又不好。
A
简单题。
最多就尽量让 \(1,0\) 搭配起；最少就是尽量搭配\(0,0\) 和 \(1,1\)。
B
也是简单题，想一下就可以了。
首先，想要保证给定的是中位数，最简单的就是比它小的分一组，比它大的分一组，自己分一组。但是因为组长度必须是奇数，所以只有在偶数位置上才行。那奇数可以考虑分5段。很明显，当在第一个和最后一个位置时，分不出五段，但是我们发现只有一个数时，在开头和结尾才合法，特判即可。
C
比较直接，但是我犯了一个错，硬控自己。
首先读完题，就可以发现，我们要做的是让最小值加次小值大于最大值。所以钦定最大值为 \(a_i\) ,就可以计算出是第一个严格大于 \(a_i/2\) 的位置，就可以计算答案。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int t,n,m,a[N];
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
int ans=n;
for(int i=1;i<=n;i++)
{
int res=(n-i),k=(a[i]/2)+1;
int j=lower_bound(a+1,a+n+1,k)-a;
// cout<<"** "<<j<<'\n';
res+=j-1;
if(j!=1)
{
if(a[j-1]+a[j]>a[i])res--;//有一个比它小的数可以不改
}
ans=min(ans,res);
}
cout<<ans<<'\n';
}
return 0;
}
错误原因：
1.最开始只增大最小值，不缩小最大值
2.应该是严格大于，不能等于
D
交互题，不要再用 \(cin,cout\) 了。改了半天发现交互错了。
首先想要直接顺着做，没做出来（只是因为我菜）。然后倒着做发现树一定上面几层和一条很长的链，所以从结尾开始找，一直找到一个链的最上端，用双指针扫一遍即可（一个扫当前节点，一个扫父亲）。
这是赛时做法有点累赘，直接双指针即可 \(O(n)\) 完成。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int t,n,fa[N],cnt;
int check(int x,int y)
{
cout<<"? "<<x<<" "<<y<<endl;
int jg; cin>>jg;
return jg;
}
int main()
{
//cin.tie(0)->sync_with_stdio(0);
cin>>t;
while(t--)
{
cin>>n;
int i,flag=1;
n-=1;
for(i=n-1;i>=1;i--)
{
if(check(i,n))
{
flag=i+1;
break;
}
else fa[i+1]=i;
}
int j=flag-2;
for(i=flag;i>=2;i--)
{
while(check(i,j))j--;
fa[i]=j--;
if(j<=0)break;
}
cout<<"! ";
for(int z=1;z<=n;z++)
cout<<fa[z]<<" ";
fa[z]=0;
}
cout<<endl;
// if(cnt>2*(n+1)-6)cout<<"No";
}
return 0;
}
E
赛时做到了方程那一步，不过没见识过稀疏矩阵高消，所以以为高消做不了，给自己卡死了。
明天看有没有时间来改。
F
博弈论+dp看出来了，一开始正着想发现不好做，实际上应该倒着来，这样才能确定当前的状态。
明天再说