首页 > 其他分享 >多重映射

多重映射

时间:2024-03-09 17:01:58浏览次数:24  
标签:多重 转换 映射 字符 int cin 转化 mp

题目:AtCoder Beginner Contest 342_C
链接:https://atcoder.jp/contests/abc342
题意:
给出一串字符串S,字符串仅由小写字母组成,有m次操作,第mi次操作的意思为将字符串S中所有出现的字符C转化为字符D,m次操作完成后输出最终字符串。
思路:
本题是一道非常标准的字符多重映射问题,仅需要用一个数组ans将每一个字符映射后所对应的字符存下来即可。但由于是多重映射,因此我们需要考虑先后顺序与字符覆盖的问题。
如:
样例1:a->b 与 样例2:a->b
b->c b->c
a->d
对于样例一应将a,b,c均输出为c,而对于样例二a转化为的d,b转化为了c。
对于已经转化了的字符a,若转化后的字符又继续转化,因将字符a一起转化。由于本题的数据比较小,仅有26,因此可以在每次转化时遍历数组ans,将每一个符合条件的字符转换。
代码:

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int add(int x, int y){return x ? add((x & y) << 1, x ^ y): y;}

#define ONLINE_JUDGE

int n,m;
string s;
char a[30];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    ios;
    cin>>n;
    cin>>s;
    cin>>m;
    char x,y;
    for(char i='a';i<='z';i++)
    {
        a[i-'a'+1]=i;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        for(int j=1;j<=26;j++)
        {
            if(a[j]==x)
            {
                a[j]=y;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        cout<<a[s[i]-'a'+1];
    }
    cout<<"\n";
    return 0;
}

题目:牛客小白月赛88_E
链接:https://ac.nowcoder.com/acm/contest/75771/E
题意:
给出一个序列,函数M(x)=y表示将序列中的所有x转换为y,m次操作,操作可以反复叠加,输出m次操作后的序列。
思路:
显然该题的思路与做法与上面一题类似,用一张map去记录转化的值,但本题的数据大小为1e6,显然按照上一题的做法直接遍历肯定会TLE,需要换一种方法。
可以发现多重映射后可能存在多个原序列的值对应一个转换后的值,但一个原序列的值不可能对应多个转换后的值,每一次转换都会将前一次转换的值给覆盖了。而我们不关心中间的转换值是多少,仅需要输出最终的转换结果就好,因此可以将上一题的存储方式反一下,用最终的转化结果返回去找对应的原数组。若原序列中的a转换为b后又将b转换为了c,就可以将c所对应的值中加上a,把b所对应的值中的a删除
如:
a->b
c->b
b->d
对于这个样例我们首先将a与c放入b所对应的数组下标中,对于b->d将b所对应的值全部放入c中,然后将b的值清除即可。最终输出答案时仅需要在转换完成的数组中查找原序列值在哪里即可。
代码:

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int add(int x, int y){return x ? add((x & y) << 1, x ^ y): y;}

#define ONLINE_JUDGE

const int N=1e6+10;
int t,n,m;
int a[N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    ios;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        map<int,int> ans;
        map<int,basic_string<int>> mp;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            ans[a[i]]=a[i];
            if(!mp.count(a[i]))
            {
                mp[a[i]]={a[i]};
            }
        }
        while(m--)
        {
            int x,y;
            cin>>y>>x;
            if(x==y)
            {
                continue;
            }
            mp[x];mp[y];
            if(mp[x].size()<mp[y].size())
            {
                mp[x].swap(mp[y]);
            }
            mp[x]+=mp[y];
            mp.erase(y);
        }
        for(auto [res,v] : mp)
        {
            for(auto i : v)
            {
                ans[i]=res;
            }
        }
        for(int i=1;i<=n;i++)
        {
            cout<<ans[a[i]]<<" ";
        }
        cout<<"\n";
    }

    return 0;
}

标签:多重,转换,映射,字符,int,cin,转化,mp
From: https://www.cnblogs.com/Aliciaandsakura/p/18062968

相关文章

  • 映射本地图片
    importorg.springframework.context.annotation.Configuration;importorg.springframework.web.servlet.config.annotation.ResourceHandlerRegistry;importorg.springframework.web.servlet.config.annotation.WebMvcConfigurer;/***映射本地图片类,找到url对应的文件,配置Spr......
  • Mybatis20_MyBatis映射文件深入(动态SQL)6
    一、动态sql语句1、动态sql语句概述Mybatis的映射文件中,前面我们的SQL都是比较简单的,有些时候业务逻辑复杂时,我们的SQL是动态变化的,此时在前面的学习中我们的SQL就不能满足要求了。2、环境搭建UserMapper.javapackagecom.itheima.mapper;importcom.......
  • 本地快速搭建airflow docker镜像,映射本地路径
    airflow官方文档拉取镜像dockerpullapache/airflow:2.8.2拉取配置文件curl-LfO'https://airflow.apache.org/docs/apache-airflow/2.8.2/docker-compose.yaml'修改刚刚拉取的yaml文件关闭示例dagAIRFLOW__CORE__LOAD_EXAMPLES:'false'映射本地路径volumes:......
  • docker-部署mysql8,并映射数据目录和日志目录
    下载镜像dockerpullmysql:8.0.21在主机上准备目录mkdir-p/mysql8/data/mysql8/log  /mysql8/cnf编写配置文件[root@localhostcnf]#catmy.cnf[mysqld]datadir=/mysql/datalog-error=/mysql/log/mysql-log.logpid-file=/mysql/mysqld/mysqld.pids......
  • 在Windows操作系统上进行端口映射通常需要使用网络地址转换(NAT)规则或端口转发来实现。
    端口映射通常与目的网络地址转换(DNAT)概念相关联。在网络中,DNAT是一种技术,用于将传入的数据包的目的IP地址和/或端口号修改为内部网络中另一台计算机的IP地址和端口号。这样可以实现将外部流量导向内部特定计算机或服务的功能。因此,端口映射通常涉及DNAT技术,用于在网络中重......
  • RISC-V SV39地址映射方式
    SV39地址映射PTESV39是RV64支持的虚拟地址转换方式,其虚拟地址是39bit,可以映射的物理地址是56bit,页表entry格式如下,512GB地址空间被划分为512个1GB的吉页,每个吉页被进一步划分为512个2MB的兆页,每个兆页被进一步划分为512个4KB的基页:  satpSV39页表的基地址由satp(Supervisor......
  • 对象不能从 DBNull 转换为其他类型,数据库空数据映射实体类的时候如何处理数据
    场景是这样的数据库有几个字段是可以为空的、即插入的时候可以不插这些数据,当一条有‘缺口’的数据回到后端映射实体类的时候,会导致对象不能从DBNull转换为其他类型的错误此时可以编写一个通用的方法来处理这种转换publicstaticTConvertDBNull<T>(objectvalue,Tdefaul......
  • .NET Core AutoMapping 对象映射器转换
    先在NuGet程序包里下载这个文件然后新建一个类继承:ProfileusingAutoMapper;usingRBAC_Domain;usingRBAC_Domain.DTO;namespaceRBAC_Service.MyProFiles{///<summary>///转换对象映射器类///</summary>publicclassMappingProfile:Profile......
  • FRP(Fast Reverse Proxy)网络映射工具部署
    FastReverseProxy(FRP)是一款由fatedier开发的高性能的反向代理工具,用于穿透防火墙、NAT等网络障碍,将内网服务映射到公网上github地址https://github.com/fatedier/frp 下载https://github.com/fatedier/frp/releases根据操作系统找到对应版本,客户端服务端共用一个包。 ......
  • Taurus.MVC WebMVC 入门开发教程6:路由配置与路由映射
    前言:在本篇Taurus.MVCWebMVC入门开发教程的第六篇文章中,我们将讨论如何配置路由并映射到控制器和操作方法。路由是决定应用程序如何响应客户端请求的重要组成部分,因此在Web开发中非常重要。我们将继续使用Taurus.Mvc命名空间,并探讨如何在应用程序中配置路由。步骤1:了......