E
题意：给定一个数 \(x\) ，找出严格小于 \(x\) 的一个数 \(y\) 使得 \(gcd(x,y)=x\oplus y\) 。
赛时小 \(wa\) 一次，答案就是 \(x-lowbit(x)\) （不为 \(0\) 的前提下）。
C
题意：
H
B （补题）
题意：给定图， \(q\) 次询问，每次给出一个点集，求解该点集的最小生成树。（保证询问的点数之和不超过 \(1e5\) ）。
赛时各种乱七八糟的思路……对于点很少的询问，完全可以每次都暴力跑 \(kruskal\) ；对于点很多的询问，肯定不会超过很多次，所以也可也直接跑 \(kruskal\) ……所以关键来到了怎么找出点集里所有涉及到的点。对于点数很少的询问，直接两重 \(for\) 循环判断边是否存在；对于点数很多的询问，肯定不会很多次，所以直接遍历所有边即可。（正解是这样的，我写了还是 \(tle\) ，下面是几个优化）
-
\(map<pii,int>\) 改为 \(unordered\_map<int,int>\) ，将点对哈希成数存储。
-
提前对所有边按照权值排序，对于点数很多的询问遍历完以后就不需要再次排序
-
对于点数很少的询问，在寻找所有的边时，比较邻接表查边的另一端是否在点集中与直接 \(for\) 循环判断与点集中剩余点是否构成合法边哪一个更优
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define il inline
#define endl '\n'
const int N=1e5+5;
const int mod=998244353;
int fa[N],n,m;
struct edge
{
int a,b,w;
bool operator<(const edge &W)const { return w<W.w; }
}e[N],edge[N];
il int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
il int kruskal(int num)
{
int res=0,cnt=0;
for(int i=1;i<=m;i++)
{
int a=edge[i].a,b=edge[i].b,w=edge[i].w;
a=find(a),b=find(b);
if(a!=b)
{
fa[a]=b;
res+=w;
cnt++;
}
}
if(cnt<num-1) return -1;
return res;
}
const int h=3e9+9;
int gethash(int x,int y) { return x*h+y; }
unordered_map<int,int>mp,mpp;
vector<int>g[N];
void solve()
{
int mm,qx;cin>>n>>mm>>qx;
for(int i=1;i<=mm;i++)
{
int u,v,w;cin>>u>>v>>w;
e[i]={u,v,w};
g[u].push_back(v),g[v].push_back(u);
mp[gethash(u,v)]=mp[gethash(v,u)]=w;
}
vector<int>z(100005);
sort(e+1,e+mm+1);
for(int i=1;i<=qx;i++)
{
mpp.clear();
int num; cin>>num;
m=0;
for(int j=1;j<=num;j++)
{
cin>>z[j];
fa[z[j]]=z[j];
mpp[z[j]]++;
}
if(num>300)
{
for(int i=1;i<=mm;i++)
{
auto [u,v,w]=e[i];
if(mpp[u]&&mpp[v]) edge[++m]={u,v,w};
}
}
else
{
for(int j=1;j<=num;j++)
{
int u=z[j];
if(g[u].size()<(num-j))
{
for(auto v:g[u])
if(mpp[v]) edge[++m]={u,v,mp[gethash(u,v)]};
}
else
{
for(int k=j+1;k<=num;k++)
{
int v=z[k],f=mp[gethash(u,v)];
if(f) edge[++m]={u,v,f};
}
}
}
sort(edge+1,edge+m+1);
}
cout<<kruskal(num)<<endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;
while(T--) solve();
return 0;
}