专栏文章

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

llzt415
P14305题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mini7fur
此快照首次捕获于
2025/12/02 02:49
3 个月前
此快照最后确认于
2025/12/02 02:49
3 个月前
查看原文

前言

由于我上次打你谷的这种赛制的比赛还是在上次，所以我在所有代码前都加上了这么一句：
CPP
freopen("xxx.in","r",stdin);
freopen("xxx.out","w",stdout);
不出意外地宝玲了。

思路

我的可能比较奇特。
我首先找出来所有的参与运算的串，并给他们赋予编号，然后放进堆里，按所有参与的运算符的优先级排序（左面的符号）。并用 fif_i 表示字符串 ii 的右边是否为 ,，具体如下：
CPP
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;
而堆中的排序方式我这样定义：
CPP
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;
}
好上面的基础设施完成了，那我们每从堆中弹出来一个运算时，怎么将其更改呢？因为我们考虑到所有连续一段的同种运算符运算后，那些字符串成为了一个整体，而他们的类型一单更改，就要全部更改，而如果暴力实现的话肯定不行，我们自然而然的想到了并查集。
这样我们只用把运算符两边的字符串的 faifa_i 更改即可，具体如下：
CPP
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

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...