[COCI2018-2019#1]Zamjena 题解

qianxinyu · 2023-08-28 12:59:51 · 题解

Zamjena

题目大意

你有两个数组，数组中有很多数或变量，变量可以赋任意值。你需要判断是否存在一种方法让两个数组中的数两两对应相等。

思路

显然有三种对应关系：

当一个常量和一个常量对应时：如果两数相等，它们俩就人畜无害，如果两数不等，那么这两个数组就不可能两两对应相等。
当一个变量和一个常量对应时：这个变量没得选，只能跟随常量赋值，但如果这个变量已经和另一个常量对应了，那么就与条件一相似，无解。
当一个变量和一个变量对应时：相当于这两个变量同命了，和成一个变量，一个对应了常量，另一个要对应这个常量。

常量的判断简单。那么任何处理对应呢？

可以想到用并查集将变量合并到常量或另一个变量上。

处理

注：不了解处理中相关算法的可以翻到最底下。

1.输入

考虑到字符串输入，所以使用 scanf("%s",a); 进行输入。

2.判重

需要判断变量名相同。

很多人会想到用 map 进行处理。

但是，字符串的题就应该用字符串的方法：字典树。字典树数应该更适合做有关前缀的题，但是，这题也可以用上它。它会比 map 更优，因为 map 的单次查询需要 O(\log{n}) 的复杂度，而字典树可以实现 O(|s|) 的复杂度。

所以目前我是最优解。

然后可以先特判出数字，对字符串进行标号，让每一个变量都有自己专属的编号。

代码

int trie[500010][30],cnt=1;//注意开10倍数组
int map[500010],cnt2=1010;//我不用万能头，所以可以用这个变量名
int query(char c[])
{
    int now=1,l=strlen(c);
    if(c[0]<='9'&&c[0]>='0')
    {
        now=0;
        for(int i=0;i<l;i++)
        {
            now*=10;
            now+=c[i]-'0';
        }
        return now;//数字
    }
    for(int i=0;i<l;i++)
    {
        if(!trie[now][c[i]-'a'+1])trie[now][c[i]-'a'+1]=++cnt;
        now=trie[now][c[i]-'a'+1];
    }
    if(!map[now])map[now]=++cnt2;
    return map[now];//变量
}

并查集

并查集板子很好写。

不过我不喜欢预处理，所以加了一个特判，在不需要处理 0 时可以写成这样： if(f[x]==0)return f[x]=x;

代码

int find(int x)
{
    if(f[x]==0)return f[x]=x;
    if(x!=f[x])return f[x]=find(f[x]);
    return f[x];
}
void hb(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)f[fy]=fx;
}

判断

分步处理。注意：优先把变量并进常量，在两个变量之间匹配过常量的最好不被并入其它变量中。

代码

for(int i=1;i<=n;i++)
{
    int x=query(a[i]),y=query(b[i]);
    if(x==y)continue;//人畜无害
    int fx=find(x);
    if(x<=1000&&y<=1000)//常量不相等
    {
        printf("NE");
        return 0;
    }
    else if(x<=1000)hb(x,y);//y对应的变量等于x
    else if(fx<=1000)hb(x,y);//y对应的变量等于x对应的变量匹配的常量
    else hb(y,x);//其它情况
}
for(int i=1;i<=1000;i++)
{
    if(find(i)!=i)//常量被要求等于另一个常量
    {
        printf("NE");
        return 0;
    }
}
printf("DA");//全部匹配

完整代码

#include<cstdio>
#include<cstring>
int trie[500010][30],cnt=1;
int map[500010],cnt2=1010;
int query(char c[])
{
    int now=1,l=strlen(c);
    if(c[0]<='9'&&c[0]>='0')
    {
        now=0;
        for(int i=0;i<l;i++)
        {
            now*=10;
            now+=c[i]-'0';
        }
        return now;
    }
    for(int i=0;i<l;i++)
    {
        if(!trie[now][c[i]-'a'+1])trie[now][c[i]-'a'+1]=++cnt;
        now=trie[now][c[i]-'a'+1];
    }
    if(!map[now])map[now]=++cnt2;
    return map[now];
}
int f[50010];
int find(int x)
{
    if(f[x]==0)return f[x]=x;
    if(x!=f[x])return f[x]=find(f[x]);
    return f[x];
}
void hb(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)f[fy]=fx;
}
char a[50010][15],b[50010][15];;
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%s",a[i]);
    for(int i=1;i<=n;i++)scanf("%s",b[i]);
    for(int i=1;i<=n;i++)
    {
        int x=query(a[i]),y=query(b[i]);
        if(x==y)continue;
        int fx=find(x);
        if(x<=1000&&y<=1000)
        {
            printf("NE");
            return 0;
        }
        else if(x<=1000)hb(x,y);
        else if(fx<=1000)hb(x,y);
        else hb(y,x);
    }
    for(int i=1;i<=1000;i++)
    {
        if(find(i)!=i)
        {
            printf("NE");
            return 0;
        }
    }
    printf("DA");
    return 0;
}