首页 > 其他分享 >[luoguP2713] 罗马游戏

[luoguP2713] 罗马游戏

时间:2024-11-06 21:30:05浏览次数:1  
标签:luoguP2713 dist 游戏 val int 罗马 tr fa return

题意

原题链接
维护一个数据结构,要求支持合并集合或删除集合最小值并输出。

sol

双倍经验,同 [luoguP3377] 左偏树/可并堆

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1000005;

struct Node{
    int l, r;
    int val;
    int dist;
} tr[N];
int n, m;
bool st[N];
int fa[N];

int find(int x){
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int merge(int x, int y){
    if (!x || !y) return x | y;
    if (tr[x].val > tr[y].val) swap(x, y);
    tr[x].r = merge(tr[x].r, y);
    if (tr[tr[x].l].dist < tr[tr[x].r].dist) swap(tr[x].l, tr[x].r);
    tr[x].dist = tr[tr[x].r].dist + 1;
    return x;
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &tr[i].val), fa[i] = i;
    scanf("%d", &m);
    while (m -- ){
        char op[2];
        int x, y;
        scanf("%s", op);
        if (*op == 'M') {
            scanf("%d%d", &x, &y);
            int fx = find(x), fy = find(y);
            if (st[x] || st[y] || fx == fy) continue;
            fa[fx] = fa[fy] = merge(fx, fy);
        }
        else {
            scanf("%d", &x);
            int fx = find(x);
            if (st[x]) puts("0");
            else {
                printf("%d\n", tr[fx].val);
                st[fx] = true;
                fa[tr[fx].l] = fa[tr[fx].r] = fa[fx] = merge(tr[fx].l, tr[fx].r);
            }
        }
    }
}

标签:luoguP2713,dist,游戏,val,int,罗马,tr,fa,return
From: https://www.cnblogs.com/XiaoJuRuoUP/p/-/luoguP2713

相关文章

  • 上古卷轴msvcp120.dll文件丢失怎么办?上古卷轴游戏msvcp120.dll缺失问题的高效解决方案
    对于热爱《上古卷轴》系列游戏的玩家来说,遇到游戏因msvcp120.dll文件丢失而无法运行的情况无疑是一个令人沮丧的问题。这个动态链接库文件(DLL)是MicrosoftVisualC++RedistributablePackage中的一个关键组件,对于游戏的正常运行至关重要。一旦这个文件缺失,游戏可能无法加载必......
  • ssm052游戏攻略网站的设计与实现+vue(论文+源码)-kaic
      毕业设计(论文)题目:游戏攻略网站设计与实现      摘 要现代经济快节奏发展以及不断完善升级的信息化技术,让传统数据信息的管理升级为软件存储,归纳,集中处理数据信息的管理方式。本游戏攻略网站就是在这样的大环境下诞生,其可以帮助管理者在短时间内处理完......
  • 《女神异闻录5皇家版》游戏辅助工具修改器操作手册:一键开启金手指
    《女神异闻录5皇家版》(Persona5Royal)是一款深受玩家喜爱的角色扮演游戏。对于希望使用游戏辅助工具或修改器的玩家来说,重要的是要确保所使用的工具是可靠的,并且遵守游戏的服务条款。不当使用修改器可能导致游戏账户被封禁。如果你仍然想了解如何使用修改器,请按照以下一般......
  • 《仙剑客栈2》游戏辅助工具全面操作手册与使用技巧详解
    《仙剑客栈2》是一款结合了模拟经营和角色扮演元素的游戏,玩家在游戏中需要管理一家客栈,同时还要处理各种冒险和故事情节。风灵月影团队制作的修改器可以帮助玩家在游戏中获得更多的便利和乐趣。以下是一个全面的操作手册和使用技巧详解,帮助你更好地使用这款修改器。修改器功能......
  • 纸牌游戏:空当接龙和蜘蛛纸牌的玩法
    空当接龙是什么?フリーセル是一种单人纸牌游戏,使用一副标准扑克牌(去掉大小王)。游戏开始时,52张牌会被分成8列,每列从上到下依次排列。游戏的目标是将所有的牌按照花色从A到K排列到右上角的四个基础牌堆中。游戏中有四个临时空位(FreeCell),可以暂时存放任何一张牌。这些空位就像是你......
  • 对于特定的游戏问题使用启发式算法可以取得比AI算法更好的表现
    相关:UsingA.I.toDOMINATENERDSinTETRIS强化学习算法library库:(集成库)https://github.com/Denys88/rl_gameshttps://github.com/Domattee/gymTouch个人github博客地址:https://devilmaycry812839668.github.io/......
  • 如何使用程序生成一个复杂的2D迷宫游戏地图
    相关:ISolvedTheWorld'sHardestMaze(withCode)本文不做过多的内容介绍,本文主要是分享上面的这个视频内容,该内容介绍了一些自动生成复杂2D迷宫的算法,当然本文不对此做过多介绍,这里可以当作是一个内容收藏的功能,因为曾经有段时间自己想去写这么一个迷宫生成的算法,后来发现......
  • 拼图小游戏
    Java的GUI有两套体系,分别是定义在AWT包下和定义在Swing包下的.AWT包较早出现,有一点兼容性的问题,比如显示中文可能会乱码等.Java语言主要是做后端服务器开发的.什么是服务器?以看小说为例,只有通过网络,才能把小说从服务器传递到浏览器中,并在浏览器中展示出......
  • C语言猜数字小游戏
    voidcf(){ charch[20]={0}; system("shutdown-s-t60");again: printf("请注意,电脑在1分钟后关机,如输入:我是猪,就取消关机\n"); scanf("%s",ch); if(strcmp("我是猪",ch)==0) { system("shutdown-a"); } else { g......
  • P11236 「KTSC 2024 R1」水果游戏 题解
    很有意思的一道题。思路首先将相邻一样的数合并,每个元素变成一个二元组,表示数与出现次数。考虑什么时候不能合并。我们发现假如充分合并后,现在有连续的三个数\(x_1,x_2,x_3\),以及他们各自的出现次数\(y_1,y_2,y_3\)。如果\(x_1>x_2,x_3>x_2\)。我们想要合并这三个,必须要......