正文

家谱（gen）——洛谷p2814

baka  baka  2022-08-27  678

关键词：

 1 #include <iostream>  
 2 #include <string> 
 3 #include <map>
 4 using namespace std;  
 5 map < string, string > mp;  
 6 int main()  
 7 {   
 8     string s1 = "", s2 = "";  
 9     while(cin >> s1)  
10     {  
11         mp.clear();  
12         while(s1 != "$")  
13         {  
14             if(s1[0] == ‘#‘)  
15             {  
16                 s2 = s1.substr(1,s1.size()-1);  
17                 if(mp[s2] == "") mp[s2] = s2;  
18             }  
19             if(s1[0] == ‘+‘)  
20             {  
21                 s1 = s1.substr(1,s1.size()-1);  
22                 while(mp[s2] != s2) s2 = mp[s2];  
23                 mp[s1] = s2;  
24             }  
25             if(s1[0] == ‘?‘)  
26             {  
27                 s1 = s1.substr(1,s1.size()-1);  
28                 string s3 = s1;  
29                 while(s3 != mp[s3]) s3 = mp[s3];  
30                 cout << s1 << ‘ ‘ << s3 << endl;  
31             }  
32             cin >> s1;  
33         }  
34     }  
35     return 0;  
36 }

充斥着STL的代码，感觉自己STL依赖症到了一个新的境界。。。

是个并查集（然而并没有看出来），用map控制映射。→_→

洛谷p2814家谱

P2814家谱题目背景现代的人对于本家族血统越来越感兴趣。题目描述给出充足的父子关系，请你编写程序找到某个人的最早的祖先。输入输出格式输入格式：输入由多行组成，首先是一系列有关父子关系的描述，其中每一组... 查看详情

洛谷p2814家谱

题目背景现代的人对于本家族血统越来越感兴趣。题目描述给出充足的父子关系，请你编写程序找到某个人的最早的祖先。输入输出格式输入格式：输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系... 查看详情

洛谷p2814家谱

题解p2814家谱(代码片段)

map版本映射并查集注意其初始化其祖先字符串是其本身#include<bits/stdc++.h>usingnamespacestd;map<string,string>p;charflag;strings,tmp;stringfind(stringx)if(p[x]==x)returnx;returnp[x]=find(p[x]);intmain()cin>& 查看详情

p2814家谱(代码片段)

【题目描述】　　　　输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子... 查看详情

洛谷p2814题解

标准并查集题目，开map做数组。每次遇到’&‘，’#‘，’+‘，’?\'就做不同的处理。为了好做，就用了函数(为了递归)，#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;#definectxcout<<"xxxxx"<<endl#defineinf0x3f3f3f3fconstintIN 查看详情

家谱(gen)

家谱(gen)时间限制 2S【问题描述】现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。【输入格式】gen.in　　输入文件由多行组成，首先是一系列有关父... 查看详情

家谱（gen）

题目描述输入文件名　　GEN.IN 输出文件名 GEN.OUT时间限制 2S 现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。输... 查看详情

[洛谷2814]家谱

思路：字符串哈希，然后用普通的并查集维护即可。1#include<cstdio>2#include<cctype>3#include<cstring>4constintmod=19260817;5charname[mod][7];6inlineinthash(char*s){7intn=strlen(s),ret=0;8for(inti=0;i<n;i++ 查看详情

洛谷p1472奶牛家谱cowpedigrees

P1472奶牛家谱CowPedigrees102通过193提交题目提供者该用户不存在标签USACO难度普及+/提高提交讨论题解最新讨论暂时没有讨论题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个... 查看详情

家谱要测试数据的在评论里发联系方式

洛谷p1827美国血统americanheritagelabel：字符串water

...。然而他不是一个真正优秀的记帐员。他把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是用图形的方法。你的任务是在被给予奶牛家谱的“... 查看详情

洛谷p1827美国血统americanheritage

动规(23)-并查集基础题——家谱(代码片段)

【问题描述】现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。【输入格式】gen.in　　输入文件由多行组成，首先是一系列有关父子关系的描述，其中... 查看详情

动规(23)-并查集基础题——家谱(代码片段)

洛谷p1827美国血统americanheritage

...。然而他不是一个真正优秀的记帐员。他把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历&rdq 查看详情

动规(23)-并查集基础题——家谱(代码片段)

...有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。【输出格式】gen.out　　按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+... 查看详情