活泼泼

分类

zngg数据结构专题班(6) 题解(21)

/ 注册

全部文章（共27篇）

题解 | #借教室#

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

2021-04-11

1 688

题解 | #[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 519

牛牛的汉诺塔

第一次写发现超时了，于是选择了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

校门外的树（离散化处理）

如果这题道路长1e9，数组开不下，就可以进行离散化处理：记录每次输入的左右端点，将这些点编号，并按照所在位置大小排序。最后遍历完这些点，统计出没砍掉的区间里有多少树。左端点的position记为1，右端点记为-1.一段区间没砍掉，当且仅当它左边的左端点个数等于右端点个数因此可以用一个变量sum来记录...

2021-03-27

3 847