当前位置: 首页 > article >正文

L2-3 花非花,雾非雾

题目描述 :

CC 在梦中遇到了一个美丽序列,但是醒来已经记不清具体数值了。但幸运的是他还记得些某两个数的异或值,和某些具体值。需要你来帮助他完成序列回忆。  

即现在有一个长度为 n 的数列 a1​ , a2​ , a3​ ··· an​,但是不知道具体数值,现在有 q 条信息,每条信息只会是以下 2 种之一。  
   1 : U x y w  表示 ax​ ^ ay​ = w。  
   2 : S x y      表示 ax​ = y。  

输入格式

第一行包含 2 个整数 n、q。  (1≤n≤4×104,1≤q≤4×105)
第二到 q+1 行每行给出一条信息。  (1≤x,y≤n,1≤ai​≤109)

输出格式 :

对于每条信息,若与前面能得出的信息发生矛盾则忽略本条信息。最后只需输出数列 a,如果不能确定唯一的数列则输出sad

输入输出样例:

输入样例1

5 6
U 1 3 6
U 3 5 2
U 1 5 5
S 2 4
S 1 5
U 1 4 7

输出样例1

5 4 3 2 1

输入样例2

5 4
U 1 3 6
U 3 5 2
U 1 2 5
U 1 4 1

输出样例2

sad

样例解释

对于样例一,最开始每个数都不知道  
第一条信息 a1​ ^ a3​ = 6  
第二条信息 a3​ ^ a5​ = 2  
第三条信息 a1​ ^ a5​ = 5  (与前面能得出的信息矛盾,忽略该信息)  
第四条信息 a2​ = 4  
第五条信息 a1​ = 5  
第五条信息 a1​ ^ a4​  = 7  
最终可以得出 a 数列为 5 4 3 2 1  

对于样例二,可证明不能确定唯一的数列。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
#define int long long
typedef pair<int,int> pii;

const int N=400010;

int n,q;
int cnt[N],p[N],ans[N];
vector<pii>g[N];
int st[N];

int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}

void dfs(int x,int fa)
{
    st[x]=1;
    for(auto [a,b]:g[x])
    {
        if(a==fa)continue;
        ans[a]=ans[x]^b;
        dfs(a,x);
    }
}
void solve()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        ans[i]=-1;
        p[i]=i;
    }
    while(q--)
    {
        char op;
        cin>>op;
        if(op=='U')
        {
            int a,b,c;
            cin>>a>>b>>c;
            int aa=find(a),bb=find(b);
            if(aa!=bb&&cnt[aa]+cnt[bb]<=1)
            {
                p[aa]=bb;
                cnt[bb]+=cnt[aa];
                g[a].push_back({b,c});
                g[b].push_back({a,c});
            }
        }else{
            int a,b;
            cin>>a>>b;
            int aa=find(a);
            if(cnt[aa]==0)
            {
                cnt[aa]++;
                ans[a]=b;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(ans[i]!=-1&&st[i]==0)
        {
            dfs(i,-1);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(ans[i]==-1)
        {
            cout<<"sad"<<endl;
            return;
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }
}
signed main()
{ 
    int good_luck_to_you;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    good_luck_to_you=1;
  // cin>>good_luck_to_you;
    while(good_luck_to_you--)
    {
       solve();
    }
}

思路:比赛的时候想着应该是dfs一类的,但是不能排除冲突条件,所以不知道怎么写。

正确思路是并查集+dfs,因为如果a^b=c,那么a和b一定是有关系,我们就可以想到他们是一个连通块,而且只要这个连通块里面有一个确定的值,其他的数就都可以确定,所以不管冲不冲突,对于a^b=c我们只需要判断a和b是否再同一个连通块中并且确定值必须<=1,对于a=b,我们就判断a所在的连通块是否已经有了一个确定的值,如果没有,我们就把下标为a的值赋成b并且a所在的连通块就已经有了值 。

我们用dfs来填充最后的值,加入st数组判断这个下标的数是否已经被填过,最后判断一下数组中是否有-1,如果有,则按照题目输出即可。

 


http://www.kler.cn/a/589377.html

相关文章:

  • maven使用install将jar包编译到本地仓库管理
  • 【系统架构设计师】操作系统 - 文件管理 ② ( 位示图 | 空闲区域 管理 | 位号 | 字号 )
  • 牛客周赛 Round 85
  • ElementUI 表格中插入图片缩略图,鼠标悬停显示大图
  • 电脑型号与尺寸
  • Leetcode Hot 100 200.岛屿数量
  • 【Agent】OpenManus-Flow-BaseFlow详细分析
  • element-ui progress 组件源码分享
  • 蓝牙技术联盟中国实体成立!华为、小米发声支持本土化战略
  • 实战ansible-playbook
  • 《C#上位机开发从门外到门内》3-3:基于USB的设备管理系统
  • MCP 开放协议
  • Visual Studio里的“公共语言运行时支持”各选项的作用是什么,分别适用于哪些场景?
  • 基于CPLD+MCU的3U机箱数字量输入采集板DI,主要针对标准DC110V开关量信号进行采集处理
  • LINUX驱动学习之IIC驱动-----以AP3216C为例
  • ZED X系列双目3D相机的耐用性与创新设计解析
  • 基于python+django+vue.js开发的停车管理系统运行-期末作业
  • 基于Python的tkinter开发的一个工具,解析图片文件名并将数据自动化导出为Excel文件
  • Spring 原生启动过程
  • Jenkins 快讯