题解：P14305 【MX-J27-T2】转换

· · 题解

前言

由于我上次打你谷的这种赛制的比赛还是在上次，所以我在所有代码前都加上了这么一句：

freopen("xxx.in","r",stdin);
freopen("xxx.out","w",stdout);

不出意外地宝玲了。

思路

我的可能比较奇特。

我首先找出来所有的参与运算的串，并给他们赋予编号，然后放进堆里，按所有参与的运算符的优先级排序（左面的符号）。并用 f_i 表示字符串 i 的右边是否为 ,，具体如下：

cin>>(s+1);
int n=strlen(s+1);
string str="";int cnt=0;
for(int i=1;i<=n;i++)
{
    if(s[i]=='+'||s[i]=='*'||s[i]==',')
    {
        a[++cnt]=str;
        str="";
        q.push({s[i],cnt});
        if(s[i]==',') f[cnt]=1;
        continue;
    }
    str+=s[i];
}
a[++cnt]=str;

而堆中的排序方式我这样定义：

bool operator <(pair<char,int> a,pair<char,int> b)
{
    if(a.first=='*')
    {
        if(b.first=='*') return a.second<b.second;
        return 1;   
    }
    else if(b.first=='*') return 0;
    else if(a.first=='+')
    {
        if(b.first=='+') return a.second<b.second;
        return 1;
    }
    else if(b.first=='+') return 0;
    return a.second<b.second;
}

好上面的基础设施完成了，那我们每从堆中弹出来一个运算时，怎么将其更改呢？因为我们考虑到所有连续一段的同种运算符运算后，那些字符串成为了一个整体，而他们的类型一单更改，就要全部更改，而如果暴力实现的话肯定不行，我们自然而然的想到了并查集。

这样我们只用把运算符两边的字符串的 fa_i 更改即可，具体如下：

for(int i=1;i<=cnt;i++) fa[i]=i;
while(!q.empty())
{
    int t=q.top().second;
    q.pop();
    int x=find(t),y=find(t+1);
    if(f[t]) {fa[x]=y;continue;}
    if(a[x]=="bool"||a[x]=="char") a[x]="int";
    if(a[y]=="bool"||a[y]=="char") a[y]="int";
    if(a[x]==a[y]){fa[x]=y;continue;}
    if(a[x]=="double") fa[y]=x;         
    else if(a[y]=="double") fa[x]=y;
    else if(a[x]=="float") fa[y]=x;
    else if(a[y]=="float") fa[x]=y;
    else if(a[x]=="longlong") fa[y]=x;
    else if(a[y]=="longlong") fa[x]=y;
    else fa[x]=y;   
}

到这里就讲完了，完整代码如下：

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int c,T,fa[N];
bool f[N];
string a[N];
char s[N<<4];
int find(int x) 
{
    while (x != fa[x]) 
    {
        fa[x] = fa[fa[x]];  
        x = fa[x];
    }
    return x;
}
bool operator <(pair<char,int> a,pair<char,int> b)
{
    if(a.first=='*')
    {
        if(b.first=='*') return a.second<b.second;
        return 1;   
    }
    else if(b.first=='*') return 0;
    else if(a.first=='+')
    {
        if(b.first=='+') return a.second<b.second;
        return 1;
    }
    else if(b.first=='+') return 0;
    return a.second<b.second;
}
priority_queue<pair<char,int>,vector<pair<char,int> >,greater<pair<char,int> > > q;
signed main()
{
    freopen("conversion.in","r",stdin);
    freopen("conversion.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>c>>T;
    while(T--)
    {
        while(!q.empty()) q.pop();
        memset(f,0,sizeof(f));
        cin>>(s+1);
        int n=strlen(s+1);
        string str="";int cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='+'||s[i]=='*'||s[i]==',')
            {
                a[++cnt]=str;
                str="";
                q.push({s[i],cnt});
                if(s[i]==',') f[cnt]=1;
                continue;
            }
            str+=s[i];
        }
        a[++cnt]=str;
        for(int i=1;i<=cnt;i++) fa[i]=i;
        while(!q.empty())
        {
            int t=q.top().second;
            q.pop();
            int x=find(t),y=find(t+1);
            if(f[t]) {fa[x]=y;continue;}
            if(a[x]=="bool"||a[x]=="char") a[x]="int";
            if(a[y]=="bool"||a[y]=="char") a[y]="int";
            if(a[x]==a[y]){fa[x]=y;continue;}
            if(a[x]=="double") fa[y]=x;         
            else if(a[y]=="double") fa[x]=y;
            else if(a[x]=="float") fa[y]=x;
            else if(a[y]=="float") fa[x]=y;
            else if(a[x]=="longlong") fa[y]=x;
            else if(a[y]=="longlong") fa[x]=y;
            else fa[x]=y;
        }
        cout<<a[find(1)]<<'\n';
    }
    return 0;
}