Codeforces Round #746 (Div. 2) D - Hemose in ICPC ?(交互 二分 欧拉序)

简介: Codeforces Round #746 (Div. 2) D - Hemose in ICPC ?(交互 二分 欧拉序)

linkkk

题意:

给出一个树,每条边都有权值。定义两个点之间的距离为两点路径上的边的权值的g c d。

每次可以询问一个点集,答案返回该点集中任意两个点之间距离的最大值。

求两点使得距离是最大的。

思路:

第一个性质就是由于距离是边的权值取g c d,所以单条边的距离是最大的,也就是说最后的答案的点是相邻的。


首先我们可以询问所有的点,得到一个最大值a n s,接下来只需要查找a n s是由哪两个点连接形成的就好了。

还能够询问11次,而n = 1000,看能否用二分来解。

将树上问题转化为序列问题可以借助欧拉序,欧拉序有很多种,可以根据实际情况写。对于本题最好是将每条边和两个端点都枚举出来。

可以这样:

void dfs(int u,int fa){
  for(int tt:g[u]){
    if(tt==fa) continue;
    seq[++top]=tt;//欧拉序有很多种
    dfs(tt,u);
    seq[++top]=u;
  }
}

得到的序列是[ 1 , 2 , 3 , 2 , 4 , 2 , 1 , 5 , 6 , 5 , 1 ]

这样每条边的端点都是序列里相邻的两个点了。

对答案进行二分,假设最大值的边是由下标为l , r的两个端点构成。

那么只需要查询下标为[ 1 , m i d ]的点集中的最大值,如果说该最大值等于a n s的话,说明边在左边区间;反之,说明边在右边区间。继续二分就可以了。


由于得到的序列中每个点出现的次数不是唯一的,所以在查询的时候要进行去重。

还有一个小tips,交互题如果不使用f f l u s h ( s t d o u t ) ; 的话,可以输出的时候用c o u t < < … … < < e n d l cout<<……<

参考视频

巨巨的E都更完了,我的D才刚补完

参考博客

代码:

// Problem: D. Hemose in ICPC ?
// Contest: Codeforces - Codeforces Round #746 (Div. 2)
// URL: https://codeforces.com/contest/1592/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD;
#define I_int ll
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
#define read read()
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define dep(i, a, b) for(int i=(a);i>=(b);--i)
ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
const int maxn=1e6+7,maxm=1e6+7,mod=1e9+7;
int n,seq[maxn],top,ans;
vector<int>g[maxn];
vector<int>q;
void dfs(int u,int fa){
  for(int tt:g[u]){
    if(tt==fa) continue;
    seq[++top]=tt;//欧拉序有很多种
    dfs(tt,u);
    seq[++top]=u;
  }
}
int query(){
  sort(q.begin(),q.end());
  q.erase(unique(q.begin(),q.end()),q.end());
  cout<<"? "<<(int)q.size()<<" ";
  for(int i=0;i<q.size();i++){
    cout<<q[i]<<" ";
  }
  cout<<endl;
  q.clear();
  int ans;cin>>ans;
  return ans;
}
int main(){
  cin>>n;
  for(int i=1;i<n;i++){
    int u,v;cin>>u>>v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  seq[++top]=1;
  dfs(1,0);
  for(int i=1;i<=n;i++) q.push_back(i);
  ans=query();
  int l=1,r=top,res;
  while(l<r-1){
    int mid=(l+r)/2;
    for(int i=1;i<=mid;i++) q.push_back(seq[i]);
    int now=query();
    if(now==ans) r=mid;
    else l=mid;
  }
  cout<<"! "<<seq[l]<<" "<<seq[r]<<endl;
//  printf("! %d %d\n",seq[l],seq[r]);
  return 0;
}



目录
相关文章
|
6月前
【每日一题Day312】LC2240买钢笔和铅笔的方案数 | 完全背包 数学
【每日一题Day312】LC2240买钢笔和铅笔的方案数 | 完全背包 数学
59 0
|
算法
代码随想录 Day26 贪心 01 全集 LeetCode455 分发饼干 LeetCodeT346摆动序列 LeetCdoe T53 最大子数组和
代码随想录 Day26 贪心 01 全集 LeetCode455 分发饼干 LeetCodeT346摆动序列 LeetCdoe T53 最大子数组和
43 0
|
1月前
|
算法
Leecode第十六题(最接近的三数之和)
这篇文章介绍了LeetCode第16题“最接近的三数之和”的题目要求、解题思路和代码实现,该算法题目要求从给定的整数数组中找出三个数,使它们的和最接近给定的目标值。
46 0
|
5月前
|
6月前
|
机器学习/深度学习 算法 vr&ar
☆打卡算法☆LeetCode 204. 计数质数 算法解析
☆打卡算法☆LeetCode 204. 计数质数 算法解析
|
人工智能
P1208 [USACO1.3]混合牛奶 Mixing Milk(贪心思想加一点特别的循环)
P1208 [USACO1.3]混合牛奶 Mixing Milk(贪心思想加一点特别的循环)
69 0
|
机器学习/深度学习
Codeforces1499——C. Minimum Grid Path(思维+分奇偶+贪心)
Codeforces1499——C. Minimum Grid Path(思维+分奇偶+贪心)
93 0
☆打卡算法☆LeetCode 69、Sqrt(x) 算法解析
“给定一个非负整数,计算并返回x的算术平方根。”
☆打卡算法☆LeetCode 72、编辑距离 算法解析
“给定两个单词,计算出单词1转换为单词2所最少操作数。”