马蹄集 oj赛(双周赛第二十九次)

目录

供水管线

附庸的附庸

逆序

队列安排

管理通讯簿

调整队伍

泡泡

一元多项式的加法

约瑟夫环

暧昧团

快排变形

采蜜


供水管线


难度:钻石● 时间限制:1秒巴: 占用内存:128 M
在几个城市之间原本要规划修建许多条下水管道,管理人员发现这些管道会形成一条回路,而下水道只要将城市联通即可,所以回路会加大施工的成本。所以希望你来帮忙找出多余的管道来进行优化。当然管道和管道之间是有区别的,比如用s来表示i到j的管道管理费用,8越小则表示该管道管理费用越低。能否去除一些管线,使得总管理成本最低。求出最低的管理成本(不存在自身与自身成为回路的管道)。

def main():
    #code here
    n,k = map(int,input().split())
    # 这里我采用的是字典和元组存储顶点和边长,格式为为{(1,2):5,(1,2):3.....}
    # 另外也可以使用类进行实现,但是我感觉会有些麻烦。不过思想都是统一的,喜欢使用那个就使用那个
    dic = {}
    # 记录输入的数据
    for i in range(k):
        i,j,c = map(int,input().split())
        if (i,j) in dic:
            if dic[(i,j)] > c:
                 dic[(i,j)] = c
        else:
            dic[(i,j)] = c
    # 排序,按照边的长度从小到大排序
    new_dic = dict(sorted(dic.items(),key=lambda x:x[1]))
    reslut = 0
    #为每个顶点配置一个不同的标记,
    assists = [i for i in range(n)]
    for key,item in new_dic.items():
        #找到当前边的两个顶点在 assists 数组中的位置下标
        initial = key[0] -1
        end = key[1]-1
        num = 0  # 记录选择边的数量
        # 如果顶点位置存在且顶点的标记不同,说明不在一个集合中,不会产生回路
        if assists[initial] != assists[end]:
            # 记录该边,作为最小生成树的组成部分,其实就是记录顶点和边,具体情况根据实际情况可以自己调整
            # 在本题中题目只需要记录最低管理费用,所以只需要记录每次添加进的数据
            reslut+=item
            #将新加入生成树的顶点标记全部改为一样的  关键内容
            elem = assists[end]
            num+=1
            for j in range(n):
                if assists[j] == elem:
                    assists[j]= assists[initial]
                
            #如果选择的边的数量和顶点数相差1,证明最小生成树已经形成,退出循环
            if num == n-1:
                break


    print(reslut)



if __name__ == '__main__':
    main();

附庸的附庸


了难度:黄金时间限制:1秒巴 占用内存:128 M
蒙德城的旧贵族们存在着附庸的关系。欧洲有一位伟人说过,我的附庸的附庸不是我的附庸。尽管如此他们还是存在着隐性的自上而下的关系,属于同一个利益集团。所以,在蒙德城,附庸的附庸也是附庸。也就是说,如果两个附庸都能追溯到同一个贵族,他们也存在附庸关系(仅仅是蒙德人这样认为)蒙德城人口众多,现在小码哥把各人的关系都梳理了出来交给了你,并想让你告诉他,某两个人存不存在附庸关系(按照蒙德人的观念)。
格式
输入格式:第一行一个整数 n,表示几个关系;
接下来 n 行,每行两个数 a,b,表示b是 a 的附庸;下一行一个整数 q,表示询问次数;
接下来 q 行,每行两个数 a,b,询问 a和b是否存在附庸关系
输出格式:q 行,每行一个数。
1表示存在附庸关系,0表示不存在。

n = int(input())
fa = [i for i in range(2 * 10 ** 4 + 7)]
def find(x):
    if x == fa[x]:
        return x
    fa[x] = find(fa[x])
    return fa[x]
for _ in range(n):
    a, b = map(int, input().split())
    fa[find(b)] = find(a)
q = int(input())
for _ in range(q):
    a, b = map(int, input().split())
    if find(a) == find(b):
        print(1)
    else:
        print(0)

逆序


少 难度:钻石时间限制:1秒巴 占用内存:128 M
给一个长度为n的排列p,找一个元素,使得从排列中取出这个元素以后排列的records最多。record 是一个元素 ai满足:对于每个正整数 1≤j<i,ai>aj。一个
格式
输入格式:第一行为 n;
第二行为排列 p。
输出格式:一个整数即答案。
样例 1
输入:5
复制
5 123 4
输出:5
复制

//
// Created by felix on 2024/6/27.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 +7;
int n;
int c[N],chg [N];

int lowbit(int x){ return x &-x; }
void add(int x) {
    for (;x < N;x += lowbit(x))
        c[x]++;
}
        int sum(int x) {
    int ret =0;
    for (;x>0;x-=lowbit(x))
        ret += c[x];
    return ret;
}
        int main(){
            cin >>n;
            int x=0,maxx =0;
            for (int i = 1;i<=n;i++){
                cin >>x;
                maxx = max(maxx,x);
                int cnt = sum(x);
                if (cnt ==i-1)
                    chg [maxx]--;
                else if(cnt==i-2)
                chg [maxx]++;
                add (x);
            }
    int ans = 1;
    for (int i = 1;i <= n;i++)
        if (chg[i] > chg[ans])
            ans = i;
    cout <<ans <<endl;
    return 0;
}

队列安排


巴 占用内存:128 M了 难度:黄金时间限制:1秒
-个学校里老师要将班上N个同学排成一列,同学被编号为1~N,他采取如下的方法:1.先将1号同学安排进队列,这时队列中只有他一个人;2.2-N号同学依次入列,编号为i的同学入列方式为:老师指定编号为i的同学站在编号为1~(-1)中某位同学(即之前已经入列的同学)的左边或右边;3.从队列中去掉M(M<N)个同学,其他同学位置顺序不变
在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号。
格式
输入格式:第1行为一个正整数 N ,表示了有 N 个同学;第 2-N 行,第i行包含两个整数k,p,其中k为小于i的正整数,p为0或者1。若p为0,则表示将i号同学插入到 k号同学的左边,p为1则表示插入到右边;第 N +1 行为一个正整数 M ,表示去掉的同学数目;接下来 M 行,每行一个正整数…,表示将:号同学从队列中移去,如果”号同学已经不在队列中则忽略这一条指令。

n = int(input())
head = 1
pre = [0] * 100005
nxt = [0] * 100005
exist = [0] * 100005

for i in range(2, n + 1):
    k, p = map(int, input().split())

    if not p:
        if k == head:
            head = i
        pre[i] = pre[k]
        nxt[i] = k
        nxt[pre[k]] = i
        pre[k] = i

    if p:
        pre[i] = k
        nxt[i] = nxt[k]
        pre[nxt[k]] = i
        nxt[k] = i

m = int(input())

for i in range(1, m + 1):
    x = int(input())
    if x == head:
        head = nxt[x]
    if exist[x]:
        continue

    nxt[pre[x]] = nxt[x]
    pre[nxt[x]] = pre[x]
    exist[x] = 1

i = head
while i:
    print(i, end=" ")
    i = nxt[i]

管理通讯簿


四 占用内存:128 M难度:白银时间限制:1秒
已知一个通讯记录是由学号(6位整数,并且学号不重复)、姓名(长度小于18,只包含大写字母和小写字母)、性别(F或M)、出生日期(长度小于18)、邮编(6位整数)、通讯地址(长度小于38,只包含大写字母或小写字母)、QQ号(9位整数)、电话(11位整数)等数据项组成,利用单链表编写管理通讯(多个通讯记录)的程序,要求实现添加、删除、查找、逆序打印通讯记录功能。输入必须合理
格式
输入格式:第一行输入学生数量,正整数(大于2,小于10);后续行依次输入每个学生学号、姓名、性别、生日、邮编、通讯地址、QQ号、电话,空格分隔。每个学生一行。输入数据必须合理,不考虑不合理的输入或是溢出等特殊情况。然后输入正整数N,根据N的值执行添加、删除、查找、逆序打印。
如上文所述,首先输入学生信息来建立通讯录。然后输入正整数N:如果N为1,执行添加操作,后续行输入一个学生学号、姓名、性别、生日、邮编、通讯地址、QQ号、电话,空格分隔。然后输出第一行Therecords is:后续行逆序打印通讯录。
如果N为2,执行删除操作,第二行输入整型学号,删除对应节点(若找不到要删除的节点,则不进行删除操作),然后输出第一行Therecordsis:,后续行逆序打印通讯录。

//
// Created by felix on 2024/6/27.
//
#include <bits/stdc++.h>
using namespace std;

struct NODE {
    int studentNum, postCode, qq, nex;
    char name[10], sex[10], birthDay[10], address[30], tel[11];
} node[10];

int head, pos;

void insert() {
    NODE tmp;
    cin >> tmp.studentNum >> tmp.name >> tmp.sex >> tmp.birthDay >>
        tmp.postCode >> tmp.address >> tmp.qq >> tmp.tel;
    node[++pos] = tmp;
    node[pos].nex = node[head].nex;
    node[head].nex = pos;
}

void del() {
    int num;
    cin >> num;
    int curr = head;
    while (node[curr].nex) {
        if (node[node[curr].nex].studentNum == num) {
            node[curr].nex = node[node[curr].nex].nex;
            return;
        } else {
            curr = node[curr].nex;
        }
    }
}

void find() {
    int num;
    cin >> num;
    int curr = node[head].nex;
    while (curr) {
        if (node[curr].studentNum == num) {
            cout << node[curr].studentNum << " " << node[curr].name << " "
            << node[curr].sex << " " << node[curr].birthDay << " "
            << node[curr].postCode << " " << node[curr].address << " "
            << node[curr].qq << " " << node[curr].tel << endl;
            return;
        } else {
            curr = node[curr].nex;
        }
    }
    cout << "not found";
}

void print() {
    cout << "The records is:"<< endl;
    int curr = node[head].nex;

    while (curr) {
        cout << node[curr].studentNum << " " << node[curr].name << " "
        << node[curr].sex << " " << node[curr].birthDay << " "
             << node[curr].postCode << " " << node[curr].address << " "
        << node[curr].qq << " " << node[curr].tel << endl;
        curr = node[curr].nex;
    }
}

int main() {
    int n;
    cin >> n;
    head = 0;
    pos = 0;
    node[head].nex = 0;

    for (int i = 1; i <= n; i++) {
        insert();
    }

    cin >> n;
    if (n == 1) {
        insert();
        print();
    } else if (n == 2) {
        del();
        print();
    } else if (n == 3) {
        find();
    } else if (n == 4) {
        print();
    }

    return 0;
}

调整队伍


多难度:黄金巴 占用内存:128 M时间限制:1秒
小码哥迎来了他大学的第一次军训,军训的第一个项目就是列队,每个同学在队伍中都有属于自己的编号。但在练习过程中,教官怎么看这支队伍怎么不顺眼,于是决定调整一下队伍的顺序。
为了顺便考验同学们的反应力,教官与学生们约定了一个口令,每当他说xy0,x号同学就要移动到y号同学的前面,每当他说xy1,*号同学就要移动到y号同学的后面,但学生们不想一次次慢慢移动这么麻烦,想要知道队伍最后是怎么排的然后直接排好。为了解决同学们的烦恼,小码哥立刻动手原地
写了一个程序算出了最终排序。
现在告诉你队伍从前到后的初始排序编号以及教官的口令,要你得出队伍从前往后的最终排序。已知有n个学生,编号不重复且1<编号<n。
格式
输入格式:第一行两个正整数 n,m,表示学生的数量和教官口令的数量;第二行 n 个正整数,表示学生们的初始排序;接下来 m 行,每行 3 个整数,表示教官的口令。

//
// Created by felix on 2024/6/27.
//
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 7;

struct node {
    int l, r;
} stu[N];

int n, m, head, tail, curr;

int main() {
    ios::sync_with_stdio(false); // Speed up input/output
    cin.tie(0);

    cin >> n >> m;
    head = 0;
    tail = 0;
    curr = 0;
    
    // Initialize the list with the initial order
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        stu[num].l = curr;
        if (i == 0) {
            head = num; // first element becomes the head
        } else {
            stu[curr].r = num;
        }
        curr = num;
    }
    tail = curr;
    stu[tail].r = 0; // last element points to 0

    // Process the commands
    while (m--) {
        int x, y, op;
        cin >> x >> y >> op;
        
        // Remove x from its current position
        int t1 = stu[x].l, t2 = stu[x].r;
        if (t1) stu[t1].r = t2;
        if (t2) stu[t2].l = t1;
        if (x == head) head = t2;
        if (x == tail) tail = t1;

        if (op == 0) { // move x to the front of y
            t1 = stu[y].l;
            stu[x].l = t1;
            stu[x].r = y;
            if (t1) stu[t1].r = x;
            stu[y].l = x;
            if (y == head) head = x;
        } else { // move x to the back of y
            t2 = stu[y].r;
            stu[x].r = t2;
            stu[x].l = y;
            if (t2) stu[t2].l = x;
            stu[y].r = x;
            if (y == tail) tail = x;
        }
    }

    // Print the result
    curr = head;
    while (curr) {
        cout << curr << " ";
        curr = stu[curr].r;
    }
    cout << endl;

    return 0;
}

泡泡


乡难度:黄金时间限制:1秒巴 占用内存:128 M
小码哥小时候喜欢吹泡泡,有一次他吹出了几个一样小的泡泡,过了一段时间后,这些泡泡相互碰到一起,形成了各种大小的泡泡…,但小码哥不知道的是,他生活的地方是母体构筑的虚拟世界,里面的泡泡实际是一串串被拼成环状的数字。
小码哥一开始吹出的泡泡被母体记为1,2,...,n,而泡泡的碰撞融合实际是数字的拼接(有序)。母体会通过模拟得知两个泡泡环碰撞的情况(用->y表示)。例如,有一个为1-2的泡泡环与3-4-5的泡泡环碰撞,碰撞的点为1->4(后一个数字接在前一个数字下面),则会形成1-4-5-3-2的泡泡环。
一开始所有泡泡环都只有一个数字,母体演算出了泡泡之后的碰撞点,现在请你输出泡泡碰撞完后的所有泡泡的情况。
格式
输入格式:第一行两个正整数 n,m,表示一开始泡泡的数量和泡泡碰撞的次数;接下来 m 行,每行两个数字 ,y,表示泡泡碰撞的两个点。

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int maxn = 1000005;

int n, m;
struct B {
    int before, next;
} b[maxn];
bool book[maxn];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        b[i].before = b[i].next = i;

    while(m--) {
        int x, y;
        cin >> x >> y;
        b[b[y].before].next = b[x].next;
        b[b[x].next].before = b[y].before;
        b[x].next = y;
        b[y].before = x;
    }

    for(int i = 1; i <= n; i++) {
        if(!book[i]) {
            int t = i;
            do {
                printf("%d ", t);
                book[t] = true;
                t = b[t].next;
            } while(t != i);
            printf("\n");
        }
    }
    return 0;
}

一元多项式的加法


乡难度:钻石时间限制:1秒四占用内存:128 M
小码哥给出两个一元多项式工和,请你将这两个一元多项式相加,得到新的一元多项式 工c。
如样例:
LA=1-10x6 + 2x8 + 7x14LB=-x4+10x6-3x10 + 8x14 + 4x18LC=LA+LB=1-x4+2x8-3x10 + 15x14 +4x18
格式
输入格式:第一行两个整数n和m,分别表示 LA和 L 的项数;接下来 n 行,每行输入 L的每一项的信息,两个整数分别表示该项的系数 coef和次数expn,输入保证次数递增:接下来 m 行,每行输入 Lp 的每一项的信息,两个整数分别表示该项的系数 coe,f和次数 expn ,输入保证次数递增。
输出格式:输出k行,k为工c的项数,每行输出工。的每一项的信息,两个整数分别表示该项的系数 coef和次数 expn ,输出按次数递增。

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 2e6 + 7;

struct NODE {
    ll nex, coef, expn;
} node[N];

int n, m, head, tail, pos;
ll coefA[N], expnA[N], coefB[N], expnB[N];

void insert(int curr, ll val1, ll val2) {
    node[++pos].coef = val1;
    node[pos].expn = val2;
    node[pos].nex = node[curr].nex;
    node[curr].nex = pos;
    if (!node[pos].nex)
        tail = pos;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &coefA[i], &expnA[i]);
    for (int i = 1; i <= m; i++)
        scanf("%lld%lld", &coefB[i], &expnB[i]);

    int l = 1, r = 1;
    while (l <= n && r <= m) {
        if (expnA[l] == expnB[r]) {
            insert(tail, coefA[l] + coefB[r], expnA[l]);
            l++, r++;
        } else {
            if (expnA[l] < expnB[r]) {
                insert(tail, coefA[l], expnA[l]);
                l++;
            } else {
                insert(tail, coefB[r], expnB[r]);
                r++;
            }
        }
    }
    while (l <= n) {
        insert(tail, coefA[l], expnA[l]);
        l++;
    }
    while (r <= m) {
        insert(tail, coefB[r], expnB[r]);
        r++;
    }

    // output result
    for (int i = node[head].nex; i != 0; i = node[i].nex)
        if (node[i].coef != 0)
            printf("%lld %lld\n", node[i].coef,node[i].expn);
    return 0;
}

约瑟夫环


难度:黄金 时间限制:1秒巴: 占用内存:128 M
讲一个比较有意思的故事:约瑟夫是犹太军队的一个将军,在反抗罗马的起义中,他所率领的军队被击溃,只剩下残余的部队48余人,他们都是宁死不屈的人,所以不愿投降做叛徒。一群人表决说要死,所以用一种策略来先后杀死所有人。
于是约瑟夫建议:每次由其他两人一起杀死一个人,而被杀的人的先后顺序是由抽签决定的,约瑟夫有预谋地抽到了最后一签,在杀了除了他和剩余那个人之外的最后一人,他劝服了另外一个没死的人投降了罗马
我们这个规则是这么定的:
在一间房间总共有几个人(编号1~n),最后只能有一个人活下来。
按照如下规则去杀人:
所有人围成一圈;从1号开始顺时针(1->n)报数,每次报到q的人将被杀掉,被杀掉的人将从房间内被移走。然后从被杀掉的下一个人重新报数,继续报到g,再清除,直到剩余一人。你要做的是:当你在这一群人之间时,你必须选择一个位置以使得你变成那剩余的最后一人,也就是活下来。
实现约瑟夫环首先需要判断选择的那个人是否是最后一个幸存的人,不是的话再进行约瑟夫环行动。

//
// Created by felix on 2024/6/27.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 +10;
struct NODE{
int val,nex;
}node[N];
int pos,n,q,curr;

void insert(int curr,int num) {
    node[++pos].val = num;
    node[pos].nex = node[curr].nex;
    node[curr].nex = pos;
}
    //删除操作,被删节点的前驱节点是pre
    void del(int pre){node[pre].nex = node[node[pre].nex].nex;}
        int main(){
            cin >>n >>q;
            if(q==1){
                cout << n;
                return 0;
            }
            node[0]={0,1};//定义一个头节点
            node[1]={1,1};
            pos=1;
                for (int i=2;i <= n;i++)
                    insert(pos,i);
     while (true){
        for (int k = 1;k < q;k++)
            curr = node[curr].nex;
        if (node[curr].nex == curr){
            cout << node[curr].val;
            return 0;
        }
        del(curr);
    }
    return 0;
}

暧昧团


难度:黄金®时间限制:1秒四占用内存:128 M
小码哥正在整理NPU的学生信息。现在到了关键的一步:存储cp信息。
因为众所周知情网很乱,所以可能一个人和多个人暖昧,并且不分性别,而且有可能自己和自己暖昧。
同时一对暖昧关系可能会由于大意等原因多次记录。
现在我们知道几个人,并且有m个暖昧关系。现在我们对暖昧团进行定义:一个人所有和他有直接暖昧关系以及间接暖昧关系的集合。比如1与2暖昧,2与3暖昧,3与4暖昧,5与3暖昧,6与2暖昧,那么{1,2,3,4,5,6},{2,3},{1,4,5,6}{空集合}就均属于暖昧团,其中,{1,2,3,4,5,6}就是极大暖昧团。现在小码哥告诉你一个人名的编号,让你回答与所处极大暖昧团的大小。如果一个人和谁都不暖昧,那么答案就是1
格式
输入格式:第一行一个整数 n,m(1≤n,m<1e5 ),表示人数,和暖昧关系的数量;接下来 m 行,每行两个整数 a,b(1 ≤ a,b≤n),表示 a,b之间存在暖昧关系,

/**
	输入格式:第一行一个整数n,m ( 1 ≤n,m ≤le5),表示人数,和暧昧关系的数量;
            接下来m行,每行两个整数a,b ( 1≤a, b≤n ),表示a,b之间存在暧昧关系;
            最后一行一个整数x,表示询问x所处极大暖昧团的大小。
	输出格式:一行一个整数表示答案。
	样例1   输入:6 8
                1 2
                5 2
                3 6
                4 5
                1 4
                2 2
                3 6
                3 6
                3
			输出:2
*/         
#include<bits/stdc++.h> 

using namespace std;
const int N = 1e5 + 5;
int f[N], s[N], n, m;

//并查集的模板
int find(int x){//查找根节点
    //将键与值对比,相同返回键;不同返回值,拿值做键在做比较
    return x == f[x] ? x : (f[x] = find(f[x]));//路径压缩
}
void merge(int i, int j){//合并暧昧值
    int x = find(i);//查找根节点的暧昧值
    int y = find(j);
    if(x != y){
        f[x] = y;//将节点赋值为根节点的值
        s[y] += s[x];//根节点的值为暧昧值的总和
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        s[i] = 1;//暧昧值每个人都为1
        f[i] = i;//并查集初始化
    }
    while(m--){
        int a, b;
        cin >> a >> b;
        merge(a, b);
    }
    int x;
    cin >> x;
    cout << s[find(x)];//返回根节点的索引对应的最大暧昧值
    return 0;
}

快排变形


难度:黄金
 时间限制:1秒巴 占用内存:128 M
有几个数,问如果通过每次交换邻项的两个数来使数组中的元素变为升序排列。
eg:98765,
变为升序:
5 67 89。
需要10次邻项交换。
格式
输入格式:第一行输入一个整数n,表示序列长度:第二行输入 n 个数。
输出格式:输出一个整数,表示最少的交换次数。

#include<bits/stdc++.h> 

using namespace std;
#define int long long

int n, ans = 0;
int a[200010], temp[200010];

void merge_pai(int l, int r, int mid) {
    int i = l, p = l, j = mid;
    while (i < mid && j <= r) {
        if (a[i] <= a[j]) 
            temp[p++] = a[i++];
        else {
            temp[p++] = a[j++];
            ans += mid - i;
        }
    }
    while (i < mid) 
        temp[p++] = a[i++];
    while (j <= r) 
        temp[p++] = a[j++];
    p = i = l;
    while (p <= r) 
        a[i++] = temp[p++];
}

void merge_sort(int l, int r) {
    if (l < r) {
        int mid = (l + r) / 2;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
        merge_pai(l, r, mid + 1);
    }
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> a[i];
    merge_sort(1, n);
    cout << ans << endl;
}

采蜜


难度:黄金● 时间限制:1秒巴 占用内存:128 M
现在有 n个蜂巢,每一个蜂窝都对应了一个蜂蜜值Si。
小码哥发现:有一些蜂窝相互联结,使得他们可以共享蜂蜜值,即该蜂巢的蜂蜜值变为:它和它连接(直接连接或间接连接)的蜂巢的蜂蜜值的和。
现在小码哥想要查询一下一些蜂巢的蜂蜜值。
格式
输入格式:第一行有两个数n(蜂巢的数量)、m(操作的数量)第二行有 n 个数字(s1,·…·,8n):分别表示了每一个蜂巢的蜂蜜值。随后有 m 行:第一个数字如果是1,则后面还有两个数字 a,b,表示此次发现蜂巢 a 和 b 是相连的。第一个数字如果是 2,则后面只有一个数字 c,表示查询所有与蜂巢 c 相连的蜂巢(包括自己)的总蜂蜜值。
输出格式:对每一次的查询操作输出查询的蜂巢的蜂蜜值。

#include <cstdio>
#define maxn 100005
using namespace std;

int n, m, a[maxn], fa[maxn];

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

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        fa[i] = i;
    }
    while (m--) {
        int f = 0;
        scanf("%d", &f);
        if (f == 1) {
            int x, y;
            scanf("%d%d", &x, &y);
            int fx = get(x), fy = get(y);
            if (fx != fy) {
                fa[fy] = fx;
                a[fx] += a[fy];
            }
        } else {
            int x;
            scanf("%d", &x);
            printf("%d\n", a[get(x)]);
        }
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/749579.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Mind+在线图形编程软件(Sractch类软件)

Scratch作为图形编程软件&#xff0c;可以为小朋友学习编程提供很好的入门&#xff0c;是初次接触编程的小朋友的首选开发软件。这里介绍的Mind软件与Sractch用法几乎完全一致&#xff0c;并且可以提供在线免安装版本使用&#xff0c;浏览器直接打开网址&#xff1a; ide.mindp…

从零开始做一辆简易麦克纳姆轮小车

一、前期准备 麦克纳姆轮小车&#xff08;Mecanum wheel robot&#xff09;是一种能够实现全向移动的机器人&#xff0c;其核心在于使用了特殊设计的麦克纳姆轮。要从头开始制作一辆麦克纳姆轮小车&#xff0c;你可能需要准备以下组件和工具&#xff1a; 1. 材料和部件 麦克纳…

uniApp获取实时定位

通过你获取的key放到项目manifest.json里面&#xff0c;对应填写你所需要的key值&#xff0c;还有高德用户名 用户名&#xff1a; key值的位置&#xff1a; 代码&#xff1a; html: <view class"intList pdNone"><view class"label">详细地…

fpga bitstream userid

fpga version register # xdc 文件 set_property BITSTREAM.CONFIG.USERID "0xDEADC0DE" [current_design] set_property BITSTREAM.CONFIG.USR_ACCESS 0x66669999 [current_design]ug908 在bit下载之后的property可以看到 &#xff0c;GUI里面Tools → Edit Devic…

链动2+1奖金制度|2+1玩法走人留人机制|电商分销模式

用这个链动21模式&#xff0c;半年清空42万瓶白酒库存&#xff0c;还帮你迅速搭建个人团队。 这是一次彻底的玩法拆解&#xff0c;一步步教你如何用这个模式实现销量和收益双提高&#xff01; 链动21模式是当前裂变会员发展速度最快的一种方式&#xff0c;它具备合理合规的身份…

[创业之路-131] :制造业企业的必备管理神器-ERP-ERP常见单据

目录 一、采购管理的ERP常见单据 1.1 请购单&#xff1a; 主要内容 作用 操作流程 1.2 采购订单&#xff08;Purchase Order, PO&#xff09;&#xff1a; 1.3 采购合同&#xff08;Purchase Contract&#xff09;&#xff1a; 1.4 采购发票&#xff08;Purchase Invoi…

通过验证邮箱进行注册信息确认

应用在进行注册时&#xff0c;避免恶意攻击和垃圾注册&#xff0c;可以通过验证注册者身份后才能够提交。一般可以使用验证手机短信或者验证邮箱&#xff0c;验证短信会有专门的第三方服务&#xff0c;可以进行付费购买。验证邮箱的正确与否&#xff0c;可以通过以下2种方式进行…

一张顶20张H100,速度10倍于B200:史上最快AI芯片,华人制造

在谈到 AI、大模型、算力等关键词时&#xff0c;如果要提及硬件产品&#xff0c;很多人应该会不假思索的说出英伟达。的确&#xff0c;在全球都缺算力的环境下&#xff0c;英伟达的地位是独特又难以撼动的。然而就在近日&#xff0c;有一家公司带着自己的 AI 芯片来叫板了。昨天…

海南聚广众达电子商务咨询有限公司抖音开店靠谱吗?

在当今数字化时代&#xff0c;电商行业迅猛发展&#xff0c;抖音作为短视频平台的佼佼者&#xff0c;其电商功能也日益凸显出其巨大的商业价值。海南聚广众达电子商务咨询有限公司&#xff0c;凭借其专业的电商服务能力和对抖音平台的深入理解&#xff0c;成为众多品牌进军抖音…

C++实现一个简单的Qt信号槽机制

昨天写这个文章《深入探讨C的高级反射机制&#xff08;2&#xff09;&#xff1a;写个能用的反射库》的时候就在想&#xff0c;是不是也能在这套反射逻辑的基础上&#xff0c;实现一个类似Qt的信号槽机制&#xff1f; Qt信号槽机制简介 所谓的Qt的信号槽&#xff08;Signals …

多维度mysql性能优化手段实践

数据库优化维度有四个:硬件升级、系统配置、表结构设计、SQL语句及索引。 优化选择: 优化成本:硬件升级>系统配置>表结构设计>SQL语句及索引。 优化效果:硬件升级<系统配置<表结构设计<SQL语句及索引。 系统配置优化 保证从内存中读取数据 MySQL会在内…

Open3d 点云投影到 xoy yoz 平面最简单的方式(附python 代码)

最简单的方式&#xff0c;就是直接把原有的点云的数据的 z or x 赋值为0, 然后生成一个新的点云。 filename_model1 r"1.pcd"down 10point_cloud o3d.io.read_point_cloud(filename_model1) point_cloud point_cloud.uniform_down_sample(int(down)) print(降采样…

Java对象集合按照指定元素顺序排序

需求背景 最近在对一个集合列表的数据进行排序&#xff0c;需求是要集合数据按照一个排序状态值进行排序&#xff0c;而这个状态值&#xff0c;不是按照从小到大这样的顺序排序的&#xff0c;而是要按照特定的顺序&#xff0c;比如按照1, 0, 2的顺序排的&#xff0c;所以需要自…

Attention步骤

一个典型的Attention思想包括三部分&#xff1a;Qquery、Kkey、Vvalue。 Q是query&#xff0c;是输入的信息&#xff1b;key和value成组出现&#xff0c;通常是原始文本等已有的信息&#xff1b;通过计算Q与K之间的相关性a&#xff0c;得出不同的K对输出的重要程度&#xff1b;…

智慧公厕系统在办公楼卫生管理中的作用,高效、便捷、智能

在现代化的办公楼中&#xff0c;卫生管理是营造舒适、高效工作环境的重要环节。而智慧公厕系统的引入&#xff0c;正以其高效、便捷、智能的特点&#xff0c;为办公楼的卫生管理带来了革命性的变革。 一、智慧公厕系统首先展现出了令人瞩目的高效性。 传统的公厕管理往往依赖人…

【zabbix】zabbix四大监控方式

zabbix四大监控方式 zabbix四大监控方式1、 Agent2、 SNMP3、IPMI4、JMX 设置 zabbix-snmp 监控 zabbix监控tomcat的jvm内存1.介绍Zabbix Java Gateway 主要功能使用场景 2.Zabbix Java Gateway 配置步骤**3.在被控端的tomcat上开启jvm监控**4.在zabbix-server上添加监控4.1.添…

Codeforces Round 954 (Div. 3) (A~F)(不会数学)

A - X Axis 暴力枚举一下所有可能 void solve() {int a , b , c;cin >> a >> b >> c;int ans 100;for(int i 0 ; i < 10 ; i ){ans min(ans , abs(i - a) abs(i - b) abs(i - c));} cout << ans << endl; } B - Matrix Stabiliz…

Python魔法参数:深入解析*args和**kwargs的强大用途

目录 引言 基础概念解析 *args:处理位置参数 **kwargs:处理关键字参数 *args和**kwargs的实际应用场景 1. 函数装饰器中使用*args和**kwargs 2. 类构造函数中使用*args和**kwargs 3. API调用中使用**kwargs 与其他参数类型的结合使用 结合默认参数 位置参数与关键…

第5讲:建立自己的C函数库,js调用自己写的C/C++函数,并包含依赖C/C++第三方静态库。

在javascript中&#xff0c;Array有很多内置的功能&#xff0c;比如Array.map&#xff0c;Array.filter&#xff0c;Array.find等等&#xff0c;能用内置的功能就用内置的功能&#xff0c;最好不要自己实现一套&#xff0c;因为底层调用的可能压根就不是js语言本身&#xff0c;…

从零开始了解GPT-4o模型:它是如何工作的?

人工智能&#xff08;AI&#xff09;技术正以惊人的速度发展&#xff0c;其中最引人注目的是OpenAI发布的GPT-4o模型。作为GPT系列的新成员&#xff0c;GPT-4o在多模态输入处理和响应速度上取得了重大进展。本文将深入探讨GPT-4o的工作原理&#xff0c;帮助您全面了解这一尖端A…