活泼泼

题解

zngg数据结构专题班(6)

/ 注册

全部文章 / 题解（共21篇）

题解 | #滑动窗口#

用数组du作为单调队列，把对应a中的下标记录下来。l和r分别是数组du的左右界。以求区间最大为例，如果后来的元素更大，则前面比它小的元素就没机会成为最大了，直接去掉。若后来的元素更小，由于位序偏后，可能会成为某个区间的最大。当区间里的数多于k个，就把最前面的元素去掉。最终du对应a中的元素单调下降，...

2021-04-16

0 425

题解 | #Sliding Window#

用数组du作为单调队列，把对应a中的下标记录下来。l和r分别是数组du的左右界。以求区间最大为例，如果后来的元素更大，则前面比它小的元素就没机会成为最大了，直接去掉。若后来的元素更小，由于位序偏后，可能会成为某个区间的最大。当区间里的数多于k个，就把最前面的元素去掉。最终du对应a中的元素单调下降，...

2021-04-16

0 546

题解 | #蚯蚓#

如果x1>x2，那么floor(px1)>floor(px2)，且x1-floor(px1)>x2-floor(px2)因此，可以把原来的蚯蚓、切开后长的蚯蚓、切开后短的蚯蚓分别放入三个队列，每次只需取三个队列中front的最大数，就是当前蚯蚓的最大长度另外为了统一，规定放进队列时...

2021-04-16

3 504

题解 | #好串#

可以把a看成左括号，b看成右括号，这样判断是否为好串就能转化成括号匹配问题方法一：开栈。碰到左括号就入栈，右括号就出栈，使左右括号对应匹配，若有一次栈空（即左括号不够）但还有右括号，则右括号多了，不是好串。最终只要栈空，就是好串，否则不是好串方法二：计数。本题中只有一种括号，因此无需开栈，只需要记录...

2021-04-15

5 1271

题解 | #借教室#

二分k+差分检查我们可以把每天能借的教室数量用数组存下来。当第i天到第j天需要借出k间教室时，a[i]到a[j]的数都减k。这样就能用差分数组来完成。若前k份订单可以，则前面k-1份都可以；若第k份不行，则后面都不行，因此想到二分每次都对前k份订单用差分数组维护，看看是否会减成负数这里用的差分数...

2021-04-11

1 686

题解 | #[CQOI2010]扑克牌#

依然是典型的二分。如果可以凑成k张牌，则比k小的也能凑，这时候下界l变成mid+1；如果k张牌凑不成，则比k大的也不能凑，这时候上界变成mid-1.本题几个需要注意的代码细节：1.r的初值。极限状态下Ci最大5e8，同时J牌也是5e8，每组要么一张J牌要么一张Ci，能抽出1e9对牌。2.int的范围...

2021-04-11

1 643

题解 | #Drying#

这题几个小坑，调了很久才出来：1.注意k是吹风机和自然烘干的共同结果！减去1后才是吹风机的单独作用！2.需要对边界k==1特判思路不会太难：本题相当于求晾干最长时间的最小值，可以考虑二分解决。若用时间x能晾干，则>x也能晾干，接下来只需考虑<x的部分。若用时x晾不干，则>x也不能...

2021-04-11

1 518

牛牛的汉诺塔

第一次写发现超时了，于是选择了30和50来打表 #include <bits stdc++.h> using namespace std; unsigned long long a[9]; unsigned long long sum; void Hanoi(int n,char pre...

2021-04-05

0 533

Flip game

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std; char oriLights1[4];//最初灯的状...

2021-03-28

1 564

Subsequence （尺取法）

尺取法（双指针）例题。暴力算法就是两重for循环枚举i和j的位置。这里我们可以进行优化：①当i到j的和≥s时，j就不需要往后移动了；②当i变成i+1时，由于i到j-1的和小于s，i到j的和≥s，因此i+1到j-1的和一定小于s。也就是说，当i加1时，j只需后移一位即可开始新一轮的判断。这里从i到j的...

2021-03-28

1 548