并查集之——单链表式并查集

普通并查集（树状）: p[i]表示节点i的父节点，i所在树的根节点是代表元素。单链表式并查集（单链表状）时间复杂度 O(m元素值域+n)O(m_{元素值域}+n)O(m元素值域​+n)元素值域​+n) ，空间复杂度不同问题不一样。p [ i ] p[i]p[i] 表示 i ii 在单链表形式并查集中
算法 2023年03月02日 870次浏览

括号序列的性质总结

括号序列的性质：(1) 左、右括号的数量相等(2) 任意前缀的左括号数量必须大于等于右括号数量
刷题 2023年02月28日 835次浏览

单源最短路和最长路总结

单源最短路和最长路一共分为(1) 加法最短路(2) 加法最长路(3) 乘法最短路(4) 乘法最长路套用最短路和最长路就能求啊，所以SPFA当然可以求，SPFA的正确性是基于它的松弛操作，所以自然是可以求乘积最小值和乘积最大值的。考虑Dij为什么不一定行，因为Dij的最短路算法是贪心的，它贪心的选最小
算法 2023年02月27日 698次浏览

牛客小白月赛67——F题《翼伯父作威》

题目链接博弈论——威佐夫博弈必败态的所有下一状态都是必胜态；必胜态的下一状态之一必有必败态。#include <bits/stdc++.h>using namespace std;#define fs first#define sc secondtypedef pair<int,
刷题 2023年02月25日 652次浏览

Codeforces Round #851 (Div. 2)——E题

题面见：《E. Sum Over Zero》dp + 树状数组/线段树 优化由于每次查询的是从1开始前缀的max，不涉及其他区间，因此可以用树状数组来维护区间最值。#include <bits/stdc++.h>using namespace std;typedef long long
刷题 2023年02月24日 771次浏览

关于逆序对

逆序对一般可以用归并排序来做一般的求逆序对如下：给定一个长度为 n的整数数列，请你计算数列中的逆序对的数量。逆序对的定义如下：对于数列的第 iii 个和第 jjj 个元素，如果满足 i<ji<ji<j 且 a[i]>a[j]a[i]>a[j]a[i]>a[j]，则
算法 2023年02月07日 804次浏览

牛客寒假集训营第六场补题

随着第六场的结束，这场短暂的旅行也走到了终点。革命尚未成功~1、B题《阿宁的倍数》题目描述阿宁有一个长度为 nnn 的数组 aaa，下标从 111 开始，有 qqq 次操作。修改操作：数组末尾增加一个数 xxx，数组长度加 111。询问操作：有多少个 i(i>x)i(i>x)i(i>
刷题 2023年02月06日 842次浏览

牛客寒假集训营第五场补题

1、C题《小沙の不懂》题目描述小沙作为著名的数学差生，今天又学不会数学了，所以想请你帮帮他。小沙有两个数字 aaa , bbb ，同时他还有个下标从 000 开始数字为 000 到 999 的长度为 101010 的排列 ppp ，在将这两个数字给你之前，他会对这两个数的每一位数进行一次 ai
刷题 2023年02月02日 667次浏览

牛客寒假集训营第四场补题

1、B题《清楚姐姐学构造》题目描述清楚姐姐最近在学习构造类问题，她现在遇到这样一个题目：给定一个长度为 NNN 的数组 ccc 和一个质数 mmm ，请你构造另外两个数组 a,ba,ba,b 满足：{ai≡aN−1−i(modm)bi≡−bN−1−i(modm)ci≡ai+bi(modm)\left
刷题 2023年01月31日 787次浏览

牛客寒假集训营第三场补题

纯纯的数学场~1、B题《勉强拼凑的记忆》题目描述小红希望用恰好 nnn 块矩形积木来搭建正方形，其中小红可以自由选择每块积木的大小，但必须是 1∗k1∗k1∗k 的长和宽。其中 1≤k≤⌈n2⌉1\leq k \leq \lceil \frac{n}{2} \rceil1≤k≤⌈2n​⌉ 。小红想知
刷题 2023年01月24日 827次浏览