[COCI2018-2019#1] Zamjena 解题记录

[COCI2018-2019#1] Zamjena 解题记录

题意简述

给定两行长度为 $N$ 的数组 $a$ 和 $b$，其中包含数字和变量，变量名为一个字符串。
问是否可以通过将变量赋值使得 $a$ 和 $b$ 相等（同一个变量名只能使用一个值）。

题目分析

看到大佬的题解都是并查集，可是我不会，所以就暴力做了出来 （这不水题吗为什么要用并查集）。
直接模拟，先用一个 map<string,int> vis 把 $a$ 和 $b$ 中的变量标记为一个特定的数，再用一个 map<int,int> mp 记录每个变量应该变什么，然后遍历一遍查看是否冲突。
怎么记录每个变量应该变成什么呢？我们可以分类讨论。

1. 如果 $a_i$ 是变量，$b_i$ 是数字，那么 mp[a[i]]=b[i]。
2. 如果 $b_i$ 是变量，$a_i$ 是数字，那么 mp[b[i]]=a[i]。
3. 如果 $a_i$ 和 $b_i$ 都是变量，先看它们的其中一个是否可以转换为数字。如果 $a_i$ 能，那么就先把 $a_i$ 转化为 mp[a[i]]，然后 mp[b[i]]=a[i]；如果 $b_i$ 能，那么就先把 $b_i$ 转化为 mp[b[i]，然后 mp[a[i]]=b[i]。
   于是我们可以得到这份代码：

#include<bits/stdc++.h>
#define arrout(a,n) rep(i,1,n)std::cout<<a[i]<<" "
#define arrin(a,n) rep(i,1,n)std::cin>>a[i]
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dep(i,x,n) for(int i=x;i>=n;i--)
#define erg(i,x) for(int i=head[x];i;i=e[i].nex)
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a+1,a+1+n
#define PII std::pair<int,int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
CI N=1e5+5;
std::unordered_map<std::string,int> vis;
std::unordered_map<int,int> mp;
int n,cnt,a[N],b[N];
signed main() {
    std::cin>>n;
    rep(i,1,n) {
        std::string s;
        std::cin>>s;
        if(s[0]>='0'&&s[0]<='9') {
            a[i]=atoi(s.c_str());
        } else {
            a[i]=1000+(!vis[s]?vis[s]=++cnt:vis[s]);
        }
    }
    rep(i,1,n) {
        std::string s;
        std::cin>>s;
        if(s[0]>='0'&&s[0]<='9') {
            b[i]=atoi(s.c_str());
        } else {
            b[i]=1000+(!vis[s]?vis[s]=++cnt:vis[s]);
        }
    }
    int t=100;
    rep(i,1,n) {
        if(a[i]>1000&&b[i]>1000) {
            if(mp[a[i]]) {
                a[i]=mp[a[i]];
                if(!mp[b[i]]) {
                    mp[b[i]]=a[i];
                    b[i]=a[i];
                }
            }
            if(mp[b[i]]) {
                b[i]=mp[b[i]];
                if(!mp[a[i]]) {
                    mp[a[i]]=b[i];
                    a[i]=b[i];
                }
            }
        }
        if(a[i]>1000&&b[i]<=1000) {
            if(!mp[a[i]]) {
                mp[a[i]]=b[i];
                a[i]=b[i];
            } else if(mp[a[i]]!=b[i]) {
                puts("NE");
                exit(0);
            }
        }
        if(b[i]>1000&&a[i]<=1000) {
            if(!mp[b[i]]) {
                mp[b[i]]=a[i];
                b[i]=a[i];
            } else if(mp[b[i]]!=a[i]) {
                puts("NE");
                exit(0);
            }
        }
    }
    rep(i,1,n) {
        if(mp[a[i]]!=0&&a[i]>1000) {
            a[i]=mp[a[i]];
        }
        if(mp[b[i]]!=0&&b[i]>1000) {
            b[i]=mp[b[i]];
        }
        if(b[i]!=a[i]&&a[i]<=1000&&b[i]<=1000) {
            puts("NE");
            exit(0);
        }
    }
    puts("DA");
    // arrout(a,n);
    // puts("");
    // arrout(b,n);
    return 0;
}

结果 59 分，检查发现是有些情况一次更新不完，根据我多年的偏分经验，观察数据范围 $1\le N\le 5\times 10^4$，于是我们可以重复检查 100 遍，确保每个数都被更新到。
可以成功水过此题。