集训队 队列p9247 2018

## 上午二维数组/函数 - [B2101 计算矩阵边缘元素之和](https://www.luogu.com.cn/problem/B2101) 点击查看代码 ``` #include using namespace std; const int N=110; int n,m,a[N][N]; i ......

先考虑暴力 **dp**。设 $f_{u,x}$ 表示在子树 $u$ 中选出的节点集合的 $w$ 最小值为 $x$ 的情况下，最大的节点集合的大小。有两种转移（选不选 $u$）： $f_{u,x}\gets \sum\limits_{v\in \text{substree}_u} f_{v,\ge ......

# 题目 农夫约翰有一块很大的田，他正在考虑种甜玉米。经过对他农田的调查，FJ发现它形成了一个（N-1）×（N-1）的 正方形。西南角为坐标（0,0），东北角是（N-1，N-1）。在某些整数坐标的位置中有双头喷头，每一个都能够同 时喷洒水和肥料。一个在（i，j）处的双头喷头会将水洒在农田中所有在其东 ......

参考博客： https://blog.csdn.net/weixin_59074080/article/details/130673121 https://blog.csdn.net/m0_46979453/article/details/127229005 https://zhuanlan.zhi ......

## 上午/一维数组排序 - 排序：sort，冒泡，选择，插入，计数 复杂度：$O(nlogn),O(n^2),O(n^2),O(n^2),O(n)$ 点击查看代码 ``` #include #include using namespace std; const int N=1e5+10; int ......

说句题外话，这个博客不更是因为我转cnblogs了。 2023正睿金华暑假集训 7月15日，我跟随大队来到了金华 第一次参加暑假出省线下集训，之前在高中部集训过， 但都是校内的集训，没怎么出去过。唯一一次好像还是去六中集训，但最多也就是几个学校之间的小打小闹。 7月份是在C班集训，课没怎么听，主要是 ......

#【单调队列】 单调队列的“扫描线”理解 **“如果一个选手比你小还比你强，你就可以退役了。”——单调队列的原理** - 比你强，而且比你影响时间更长。 - 某种意义上，数学思维是生活中的思考的延伸。 [算法学习笔记(66): 单调队列](https://zhuanlan.zhihu.com/p/3 ......

双向队列容器（Deque）是C++ STL中的一种数据结构，是一种双端队列，允许在容器的两端进行快速插入和删除操作，可以看作是一种动态数组的扩展，支持随机访问，同时提供了高效的在队列头尾插入和删除元素的操作。 Deque 双向队列容器与Vector非常相似，它不但可以在数组尾部插入和删除元素，还可以 ......

## 单调数列：滑动窗口最大值(力扣239.) - 给定滑动窗口的范围，求每个滑动窗口范围内的最大值 - 使用单调队列实现 - 对于最大值数字前面的数字不存入数列，对于最大值数字后面的数字存入数列中 - 单调队列中数字的大小呈递减顺序 - pop(value)：如果窗口移除的元素等于单调队列的队口元 ......

## 上午测试讲题 - [U259234 累加累乘/accmul](https://www.luogu.com.cn/problem/U259234) 分析：直接开两个变量记录答案即可，使用for循环n次，对于s1也可以使用等差数列求和公式。 点击查看代码 ```cpp #include using ......

# Redis专题-队列 首先，想一想 Redis 适合做消息队列吗？ ## 1、消息队列的消息存取需求是什么？redis中的解决方案是什么？ 无非就是下面这几点： 0、数据可以顺序读取 1、支持阻塞等待拉取消息 2、支持发布/订阅模式 3、重新消费 4、消息不丢失 5、消息可堆积 那我们来看看re ......

链表队列是一种基于链表实现的队列，相比于顺序队列而言，链表队列不需要预先申请固定大小的内存空间，可以根据需要动态申请和释放内存。在链表队列中，每个节点包含一个数据元素和一个指向下一个节点的指针，头节点表示队头，尾节点表示队尾，入队操作在队尾插入元素，出队操作在队头删除元素，队列的长度由节点数量决定。... ......

# T2 考场一直卡在二进制思路里面，最后打了一个 $O(n\max\{a_i\})$ 的方法，居然忘了继续向后跑 $\log$ 位，挂掉 $20pts$（像这种情况全挂也是有可能的）。 我认为其实有的时候**不要随便简化问题**，或者说想多了也要及时回来（虽然这可能很不容易）。自己认为的简化不一定 ......

[link](https://www.luogu.com.cn/problem/P4809) 大概是 oi 生涯目前最无聊的时候写的最~~啰嗦~~详细的题解。 #### 题目描述 给定一个 $n\times m$ 的点阵和两类边，第 $i$ 行 $j$ 列的城市我们叫祂城市 $(i,j)$。 横边： ......

####快速幂 ```c++ #include using namespace std; unsigned long long a,b,k,ans=1; int main(){ cin>>a>>b>>k; if(b==0){ ans=1%k; cout>=1; }cout using namespa ......

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 ) 示例 1： 输入： ["CQueue","appendTail","dele ......

# 1.整除，最大公因数和最小公倍数 ## 1.1 整除 若整数 $b$ 除以非零整数 $a$ ，商为整数，且余数为零，$b$ 为被除数，$a$ 为除数，即$a|b$，读作“ $a $整除 $b $ ”或“ $b $能被 $a $ 整除”。 其中，整除具有如下三条性质： - 整除的传递性，证明如下： ......

好的，这是一个晴朗的夜晚。 - 苯荏水平不高甚至菜亖，博客仅仅写给自己避免自己忘记学了什么，也仅据我理解写出，不严谨，非常不严谨。 单调队列。 在原序列基础上，维护一个单调的序列。 单调队列中的元素在原序列中的相对位置不变，且在单调队列中的元素是单调的。 基本模板题：https://www.luog ......

官方文档不推荐使用列表 因为列表删除第一个元素会把剩余元素向左移一位 速度很慢 官方推荐的是 collections下的deque 记录一下 防止忘记 from collections import deque d = deque(‘内容’，maxlength) 内容可以是推导式 也可以直接写内容 ......

如何在C语言中实现队列和堆栈的动态扩容 队列和堆栈是在C语言中常用的数据结构，它们可以帮助我们高效地处理数据。然而，在实际编程中，我们经常会遇到数据量超过容量限制的情况。这时，我们需要实现队列和堆栈的动态扩容，以满足实际需求。 6如何在C语言中实现队列和堆栈的动态扩容 动态扩容是指在数据结构的容量不 ......

数组、链表、栈和队列是四种基础数据结构，他们是高级、复杂的数据结构和算法的基础。本篇先来讲述**数组，链表，及算法的优化策略**。 ### 数组 #### 定义 **数组：数组是一种线性表数据结构，它用一组连续的内存空间存储一组具有相同类型的数据。** 定义中有三个关键词： - **线性表** - ......

继[数据结构与算法 组数、链表、栈和队列（一）](https://niuery.com/post/41)讲解完数组，链表及算法的优化策略之后，接下来继续讲解**两种特殊的线性表结构，栈和队列**。 ## 栈 对“栈”有一个很形象的比喻，栈就像一摞叠在一起的盘子，放盘子时，只能放在上面，不能将盘子插入 ......

记 $f_n$ 为 $k=0$ 的答案。则有答案为 $\binom n k ^2 2^k k! f_{n-k}$。接下来的问题变为怎样对每个 $n,k$ 求出 $f_{n-k}$。 **组合意义** 以下记 $\overline{A}$ 为 $A$ 的情侣。 欲求 $f_n$，不妨设第一排坐的两个人 ......

[机器翻译](https://www.luogu.com.cn/problem/P1540) ``` #include #include #include #include #include #include #include #include #define DEBUG using namespa ......

## C语言实现 ``` #include #define MAX_SIZE 10 typedef struct { int queue[MAX_SIZE]; int front; int rear; } CircularQueue; void initializeQueue(CircularQue ......

题目简述： 某天刮了一阵大风，把牛棚的门吹飞了，总共有s个牛棚，幸运的是并不是每个牛棚都有牛。现在你可以购买m块木板，商店里有各种型号的木板，木板长度为多少就需要多少金钱。木板用来给牛棚装上门。要求把所有有牛的牛棚都装上门，并且花的金钱最少。 给了一正整数C，接下来C行每行一个正整数，表示该牛棚有牛 ......

# T2 考场先是想到（根本没想）了一个 $O(n^5)$ 的思路，然后猜了一个比较好打的结论开打。结果小样例和答案差一点，大样例就差的多了。确认不是精度问题后就明显是猜的结论有问题了。这下是彻底没办法了，只有打了那个 $O(n^5)$ 的暴力。 出分我一看——怎么挂了 $20pts$？而且按照暴力 ......

# T1 考场打的是一个伪正解（没正确性的那种），评测的时候发现有 subtask 人都给我吓傻了，还好还有 $50pts$。就是不知道为什么 zxc 和我思路一样但是有 $85$ pts。 这个正解确实有点难想，而且证明正确性也比较困难。 关于题解的正确性： - 若 $a$ 的逆元不是本身。那么如 ......

P1631 序列合并 这个没做出来属实有些惭愧。看了题解觉得很妙。如果直接想的话可能反而很麻烦 题目是给两个n个数的不下降序列，问这两个序列任意各取出一个后相加的最小的n个数是什么。 直接贴题解吧题解 P1631 【序列合并】 一共会产生n*n个数， a[1]+b[1]<=a[1]+b[2].... ......

要点：键和值都要序列化或反序列化两次，也就是已经是string后，还要再序列化一次或反序列化一次 namespace RedisDemo { class Program { static void Main(string[] args) { var scannedData = Newtonsoft. ......