PAT A1032 Sharing

这篇具有很好参考价值的文章主要介绍了PAT A1032 Sharing。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1032 Sharing

分数 25

作者 CHEN, Yue

单位 浙江大学

To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, loading and being are stored as showed in Figure 1.

PAT A1032 Sharing

Figure 1

You are supposed to find the starting position of the common suffix (e.g. the position of i in Figure 1).

Input Specification:

Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (≤105), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Data Next

whereAddress is the position of the node, Data is the letter contained by this node which is an English letter chosen from { a-z, A-Z }, and Next is the position of the next node.

Output Specification:

For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output -1 instead.

Sample Input 1:

11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010

Sample Output 1:

67890

Sample Input 2:

 

00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1

Sample Output 2:

-1

 

 * 寻找有相同后缀的第一个字符位置,如果没有相同后缀,则输出-1;
 *
 * 使用静态数组代替链表。
 *
 * 先各自遍历两个链表,将其所有出现元素的下标记录在hs数组中,每出现一次,对应的元素加一,
 * 最后遍历其中一个链表的元素,查看hs数组中的值,如果对应的值等于2,则为答案。
文章来源地址https://www.toymoban.com/news/detail-437547.html

/**
 * 寻找有相同后缀的第一个字符位置,如果没有相同后缀,则输出-1;
 * 
 * 使用静态数组代替链表。
 * 
 * 先各自遍历两个链表,将其所有出现元素的下标记录在hs数组中,每出现一次,对应的元素加一,
 * 最后遍历其中一个链表的元素,查看hs数组中的值,如果对应的值等于2,则为答案。
*/

#include <iostream>

using namespace std;

struct Node
{
    int add, nex;
    char ch;
};

const int N = 1e5+10;
struct Node a[N];
int hs[N];
int h1, h2, n;

void Read()
{
    cin >> h1 >> h2 >> n;
    for(int i=0; i<n; ++i)
    {
        char ch;
        int add, nex;
        
        cin >> add >> ch >> nex;
        a[add] = {add, nex, ch};
    }
}

int main()
{
    Read();
    
    int temp = h1;
    while(temp != -1)
    {
        hs[temp]++;
        temp = a[temp].nex;
    }
    
    temp = h2;
    while(temp != -1)
    {
        hs[temp]++;
        temp = a[temp].nex;
    }
    
    int res = -1;
    while(h1 != -1)
    {
        if(hs[h1] == 2)
        {
            res = h1;
            break;
        }
        
        h1 = a[h1].nex;
    }
    
    if(res != -1)
        printf("%05d\n", res);
    else printf("%d\n", -1);
    
    return 0;
}

到了这里,关于PAT A1032 Sharing的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 记录安装cnpm报错:internal/modules/cjs/loader.js:1032 throw err;

    安装cnpm时一直安装无报错但是查看版本时提示错误: 无法安装可以这样解决: 查看版本报错安装不成功解决:是npm和cnpm版本不匹配导致的 一:查看当前npm版本 二:安装对应版本 三:查看cnpm版本,出现以下提示即安装成功  

    2024年02月06日
    浏览(40)
  • 【密码学】【多方安全计算】Secret Sharing秘密共享浅析

    秘密共享(Secret Sharing)是实现多方安全计算的一种常用方式,MPC当然也可以用混淆电路(Garbled Circuit)实现,本文旨在浅析秘密共享的基本原理,有对混淆电路感兴趣的同学可阅读下一篇博客。 Secret Sharing被称为秘密共享或私密共享,有一个秘密数值D,数值D被分解为n个片

    2024年02月15日
    浏览(40)
  • MySql主从复制1032错误(Slave_IO_Running: Yes Slave_SQL_Running: No)

    报错: Last_SQL_Error: Could not execute Delete_rows event on table hr.test; Can’t find record in ‘test’, Error_code: 1032; handler error HA_ERR_END_OF_FILE; the event’s master log mysqlbin.000017, end_log_pos 3392 原因: 个人搭建mysql主从复制后,进行相关表的主从同步练习进行多次操作发现表数据的增加、删除、更

    2024年02月13日
    浏览(44)
  • 什么是多线程环境下的伪共享(false sharing)?

    在Java中,伪共享(false sharing)是指多线程环境下,由于缓存一致性协议的影响,不同线程访问同一缓存行中的不同数据造成的性能下降现象。当多个线程同时访问不同变量,但这些变量存储在同一缓存行中时,每个线程只修改自己的变量,但由于缓存一致性协议的要求,需要将

    2024年02月10日
    浏览(39)
  • Swap 2 Secrets via Homomorphic Properties of Shamir Secret Sharing

    I have 2 secrets denoted as s 1 , s 2 s_1, s_2 s 1 ​ , s 2 ​ and they are in different vector with same dimensions. Now all the vector are encrypted by the Shamir Secret Sharing. What is I really want is to swap the s 1 , s 2 s_1, s_2 s 1 ​ , s 2 ​ in their shares format via the homomorphic properties of Secret Sharing. I need you give me a python im

    2024年02月06日
    浏览(26)
  • EtherCAT超高速实时运动控制卡XPCIE1032H上位机C#开发(三):EtherCAT总线CSP,CSV,CST模式切换

    XPCIE1032H是一款基于PCI Express的EtherCAT总线运动控制卡,可选6-64轴运动控制,支持多路高速数字输入输出,可轻松实现多轴同步控制和高速数据传输。 XPCIE1032H运动控制卡集成了强大的运动控制功能,结合MotionRT7运动控制实时软核,解决了高速高精应用中,PC Windows开发的非实时

    2024年02月05日
    浏览(47)
  • EtherCAT驱动器回零与控制器回零:EtherCAT超高速实时运动控制卡XPCIE1032H上位机C#开发(九)

    XPCIE1032H是一款基于PCI Express的EtherCAT总线运动控制卡,可选6-64轴运动控制,支持多路高速数字输入输出,可轻松实现多轴同步控制和高速数据传输。 XPCIE1032H集成了强大的运动控制功能,结合MotionRT7运动控制实时软核,解决了高速高精应用中,PC Windows开发的非实时痛点,指令

    2024年02月02日
    浏览(50)
  • 【论文阅读】Multi-ConDoS: Multimodal Contrastive Domain Sharing Generative Adversarial Networks for Self-S

    paper:Multi-ConDoS: Multimodal Contrastive Domain Sharing Generative Adversarial Networks for Self-Supervised Medical Image Segmentation         现有的自监督医学图像分割通常会遇到域偏移问题(也就是说,预训练的输入分布不同于微调的输入分布)和/或多模态问题(也就是说,它仅基于单模态数据,无法利

    2024年02月03日
    浏览(50)
  • 取消Async Stack Traces无法解决Sharing is only supported for boot loader classes时的解决方法

    报错问题: 搜到的解决方法(不能用版): , 目前网上大多数解决方法都是说取消idea中此处的勾选,但是我在这里取消勾选后,警告仍然存在。于是接下来通过不断的查资料对这个警告也有了一定的认识,看到这里,没耐心的小伙伴可以先行退出,因为这个警告完全可以不

    2024年02月04日
    浏览(56)
  • ES:先按相关性分数进行排序,分数相同时再按其他字段排序

    最近,在公司学习ES的使用,导师给了个题目,如何对一个文档先计算分数,用分数进行排序,在分数相同的情况下再按照别的字段(如时间)进行排序,为此,从来没接触过ES的我开启了艰难的学习之路 本文参考自 ES权威指南(中文版) 以下是目录: 相关性算分描述了一个

    2024年02月05日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包