2021 ICPC 沈阳站

B. Bitwise Exclusive-OR Sequence

分析：

• 图由链和环构成

  • 考虑环： 从一个点开始到这个点结束的亦或和为0（因为每个点权都用了两次），就是说：若出现环，且环的亦或和不为0，就输出 “-1”

  • 考虑链：从链的一端出发 设 $(a_1,a_2,...,a_n)$ 为链上的点权

    $a_1\wedge a_2=w_1$

    $a_2\wedge a_3=w_2$

    $...$

    $a_{n-1}\wedge a_n=w_{n-1}$

    转换一下：

    $a_1\wedge a_2=w_1$

    $a_1\wedge a_3=w_1\wedge w_2$

    $...$

    $a_1\wedge a_n=w_1\wedge w_2\wedge ...\wedge w_{n-1}$

  • 转换到上述形式，可以发现只需确定任意一点权便可求出所有的点权

    令上述亦或和分别为：$s_1,s_2,...,s_{n-1}$ ；再移一下项

    $a_2=s_1\wedge a_1$

    $a_3=s_2\wedge a_1$

    $...$

    $a_n=s_{n-1}\wedge a_1$

• 题目要求的是 ${\sum }_{i=1}^n{a}_i$ 的最小值，s 已知，确定 $a_1$ 即可

  • 考虑枚举 $a_1$ ，$1e9$ 直接炸
  • 思路转换：逐位确定 $a_1$ 的每一位

• 将某一连通分量的所有点直接与 $a_1$ 相连，就变成了一个菊花图

反思：

• 赛时就卡在思路转换这一步卡了一个多小时，没有在草稿纸上进行演算，就口胡加想想，甚至都要放弃了，最后发现过了两百多了，无奈继续硬着头皮去看 T_T

  还是题写太少了

DFS

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
vector <pair<int,int> > g[N];
int flag=1,vis[N];
int f[N];
vector <int> res[N];
void dfs(int st,int u)
{
vis[u]=1;
for(auto t : g[u])
{
int v=t.first, w=t.second;
if(vis[v]) //成环了
{
if(f[v]!=(f[u]^w)) flag=0;
}
else
{
f[v]=f[u]^w;
res[st].push_back(v);
dfs(st,v);
}
}
}
int cnt[55];
int add(int st)
{
memset(cnt,0,sizeof(cnt));
int len=res[st].size();
int x=0;
for(int j=0;j<30;j++)
{
for(int v : res[st])
{
if((f[v]>>j)&1) cnt[j]++;
}
if(cnt[j]>len/2) x+=(1<<j); // 当前位的1的个数超过len/2，那么a1的当前位取1更优
}
int ans=x;
for(int v : res[st]) ans+=f[v]^x;
return ans;
}
signed main()
{
ios_base::sync_with_stdio(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(!vis[i] && flag)
{
dfs(i,i);
ans+=add(i);
}
}
if(flag) cout<<ans<<"n";
else cout<<"-1n";
}

BFS

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
vector <pair<int,int> > g[N];
vector <int> ans[N];
int vis[N],f[N];
int flag=1;
void bfs(int st)
{
queue <int> q;
q.push(st);
vis[st]=1;
while(!q.empty())
{
int u=q.front(); q.pop();
for(auto t : g[u])
{
int w=t.second,v=t.first;
if(vis[v])
{
if(f[v]!=(f[u]^w)) flag=0;
}
else
{
vis[v]=1;
f[v]=f[u]^w;
ans[st].push_back(v);
q.push(v);
}
}
}
}
int cnt[55];
int add(int st)
{
memset(cnt,0,sizeof(cnt));
int len=ans[st].size();
int x=0;
for(int j=0;j<30;j++)
{
for(int v : ans[st])
{
int t=f[v];
if((t>>j)&1) cnt[j]++;
}
if(cnt[j]>len/2) x+=(1<<j);
}
int ans1=x;
for(int v : ans[st]) ans1+=f[v]^x;
return ans1;
}
signed main()
{
ios_base::sync_with_stdio(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
int ans1=0;
for(int i=1;i<=n;i++)
{
if(flag && !vis[i])
{
bfs(i);
int t=add(i);
ans1+=t;
}
}
if(flag) cout<<ans1<<endl;
else cout<<-1<<endl;
}

最后

以上就是朴素向日葵为你收集整理的2021 ICPC 沈阳站 B. Bitwise Exclusive-OR Sequence（亦或，位运算，菊花图）2021 ICPC 沈阳站的全部内容，希望文章能够帮你解决2021 ICPC 沈阳站 B. Bitwise Exclusive-OR Sequence（亦或，位运算，菊花图）2021 ICPC 沈阳站所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。