百度松果泡泡 (数组模拟 TLE)

Jay_fearless 2024-07-14 原文

题目描述

小码哥一开始吹出的泡泡被母体记为1，2，。。。，n，而泡泡的碰撞融合实际是数字的拼接(有序)。
母体会通过模拟得知两个泡泡环碰撞的情况(用x->y表示)
例如，有一个为1-2的泡泡环与3-4-5的泡泡环碰撞，碰撞的点为1->4(后一个数字接在前一个数字下面)，则会形成1-4-5-3-2的泡泡环
一开始所有泡泡环都只有一个数字，母体演算出了泡泡之后的碰撞点，现在请你输出泡泡碰撞完后的所有泡泡的情况。

输入格式

第一行两个正整数n,m，表示一开始泡泡的数量和泡泡碰撞的次数
接下来m行，每行两个数字x,y，表示泡泡碰撞的两个点

输出格式

输出所有泡泡的情况，一行表示一个泡泡的情况
要求按照字典序最小的方式按顺序输出

输入样例

输出样例

1 2 4 6 8 5 
3 
7 9

解释
$1≤m<n≤10^6$ , $1 < x, y < n$ 保证x，y属于不同的泡泡环

分析

本题目的一个基本操作a->b，即以b为首元素的序列插入到a所在泡泡的a的位置的后面。
每一个泡泡的融合都需要找到a和b在各自泡泡中的位置。

C++ 代码

#pragma GCC optimize(2)
#include<bits/stdc++.h> 
using namespace std;
const int N = 1e6+10;
int n,m,a,b,idx=1;
bool st[N];
vector<int> v[N];
unordered_map<int,int> mp;
int main( )
{
    scanf("%d%d",&n,&m);
    //刚开始每个泡泡都是独立的
    for(int i=1;i<=n;i++)
    {
        mp[i]=i;
        v[mp[i]].push_back(i);
    }
    
    for(int i=0;i<m;i++)
    {
            cin>>a>>b;
            //找到a在自己泡泡中的位置
            int t1=mp[a],insertp;
            for(insertp=0;insertp<v[t1].size();insertp++)
            {
                if(v[t1][insertp]==a) break;
            }
            
            //找到b在自己泡泡中的位置
            int t2=mp[b],j,l=10000001;
            for(j=0;j<v[t2].size();j++)
            {
                if(v[t2][j]==b)
                {
                    l=j;
                    break;
                }
            }
            
            //以b为首元素将其后的元素插入到a泡泡中
            for(j=l;j<v[t2].size();j++)
            {
                insertp=min(insertp+1,(int)v[t1].size());
                v[t1].insert(v[t1].begin()+insertp,v[t2][j]);
                mp[v[t2][j]]=mp[v[t1][0]];
            }
            
            //将b所在泡泡中剩下的元素插入到a泡泡中
            for(j=0;j<l;j++)
            {
                insertp=min(insertp+1,(int)v[t1].size());
                v[t1].insert(v[t1].begin()+insertp,v[t2][j]);
                mp[v[t2][j]]=mp[v[t1][0]];
            }
    }
    
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            //找到泡泡中最小的一个元素
            int t=mp[i],j;
            for(j=0;j<v[t].size();j++)
            {
                if(v[t][j]==i)
                {
                    break;
                }
            }
            
            //以该元素为首输出泡泡即可保证字典序最小
            for(int k=j;k<v[t].size();k++)
            {
                st[v[t][k]]=1;
                cout<<v[t][k]<<" ";
            }
            for(int k=0;k<j;k++)
            {
                st[v[t][k]]=1;
                cout<<v[t][k]<<" ";                
            }
            puts("");
            
            
        }
    }

    
    return 0;
}

松果 TLE span class style c++算法图论

有关百度松果泡泡 (数组模拟 TLE)的更多相关文章

ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2
我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代
ruby - 多次弹出/移动 ruby 数组 - 2
我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。关于ruby-多次弹出/移动ruby数组，我们在StackOverflow上找到一
ruby - 将数组的内容转换为 int - 2
我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]
ruby - 通过 erb 模板输出 ruby 数组 - 2
我正在使用puppet为ruby程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这
ruby - 如何模拟 Net::HTTP::Post？ - 2
是的，我知道最好使用webmock，但我想知道如何在RSpec中模拟此方法:defmethod_to_testurl=URI.parseurireq=Net::HTTP::Post.newurl.pathres=Net::HTTP.start(url.host,url.port)do|http|http.requestreq,foo:1endresend这是RSpec:let(:uri){'http://example.com'}specify'HTTPcall'dohttp=mock:httpNet::HTTP.stub!(:start).and_yieldhttphttp.shou
ruby - 检查数组是否在增加 - 2
这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife
ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2
我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat
ruby - 在 Ruby 中用键盘诅咒数组浏览 - 2
我正在尝试在Ruby中制作一个cli应用程序，它接受一个给定的数组，然后将其显示为一个列表，我可以使用箭头键浏览它。我觉得我已经在Ruby中看到一个库已经这样做了，但我记不起它的名字了。我正在尝试对soundcloud2000中的代码进行逆向工程做类似的事情，但他的代码与SoundcloudAPI的使用紧密耦合。我知道cursesgem，我正在考虑更抽象的东西。广告有没有人见过可以做到这一点的库或一些概念证明的Ruby代码可以做到这一点？最佳答案我不知道这是否是您正在寻找的，但也许您可以使用我的想法。由于我没有关于您要完成的工作
ruby - 如何在 Grape 中定义哈希数组？ - 2
我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>
ruby - 使用多个数组创建计数 - 2
我正在尝试按0-9和a-z的顺序创建数字和字母列表。我有一组值value_array=['0','1','2','3','4','5','6','7','8','9','a','b'，'光盘'，'e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','','u','v','w','x','y','z']和一个组合列表的数组，按顺序，这些数字可以产生x个字符，比方说三个list_array=[]和一个当前字母和数字组合的数组(在将它插入列表数组之前我会把它变成一个字符串，]current_combo['0','0','0']

百度松果 泡泡 (数组模拟 TLE)