xc01

分类

题解(32)

/ 注册

全部文章（共32篇）

题解40 小咪买东西

前言：这是一道01分数规划题，要用二分+验证解决。记枚举元素为x，sum(value)/sum(cost)>=x即满足要求,sum(value)-x*sum(cost)>=0;则sum(value-x *cost)>=0 sum()=>最大的前k项加起来 AC代码&思...

C++ 二分查找

2025-08-17

0 8

题解39 [HDU6231] K-th Number

前言：第M大元素，依然可以用二分+验证解决。现在问题是如何验证。记二分枚举元素位x，则应找到>=x的元素大于k的区间个数。因为这种区间的第k大的数在数组b中一定排在x的前面或一块（相等）。如果区间个数>=m，说明枚举的x<=第m大元素，反之，x>第m大元素。注意：二分查找要...

C++ 二分查找数学

2025-08-17

0 7

题解38 [NOIP2012 提高组] 借教室

前言：具有二分性质，在处理到某个人时，教室数量突然就<0，然后就不能再处理请求了。将处理的订单数作为二分枚举对象依旧是一道二分+验证的题,并且同前缀和与差分结合起来（注意：涉及到对区间大量的+-操作，一定不能直接操作，而是要维护一个差分数组，不然时间直接爆表）思路&AC代码： #...

C++ 二分查找前缀和

2025-08-17

0 8

题解37 [CQOI2010] 扑克牌

思路：一道最值问题，故尝试把组成牌的套数当作二分对象，假设需要组成牌的套数过多就一定组不成（有明显的区分点）。故使用二分枚举+验证，现在重点在于如何验证？这要用到抽屉原理的知识。每套牌不能有重复的，则最多一张joker，如果need>套数，则一定有重复的。且给出的joker数量要足够 AC代码...

C++ 二分查找

2025-08-17

0 6

题解36 [USACO 2010 Feb S]Chocolate Eating（二分+验证）

题目：贝西从公牛那里收到了 N （1 <= N <= 50,000）巧克力，但不想吃得太快，所以她想计划下一个 D （1 <= D <= 50,000）天的巧克力吃时间表，以便在这些日子里最大限度地提高她的最低幸福水平。 Bessie 的幸福感是一个整数，从 0 开始，...

C++ 分治

2025-08-15

0 9

题解35 烘干（poj3104）二分查找＋验证

题目：有 n 件刚洗完的衣服，其中第 i 件衣服上含有 ai 单位水分。自然晾干的情况下，每件衣服每分钟可以减少 1 单位水分。有一个可以使用的烘***，同一时间仅能容纳最多一件衣服。在使用烘***的情况下，每件衣服每分钟可以减少 k 单位水分。烘***每次使用的工作时间必须是整数分钟，不足...

C++ C 二分查找

2025-08-15

0 10

题解34 【模板】整数域二分

前言：又是一道模板题，我感觉关于边界的问题不好考虑，确定好自己唯一的一种写法就好。我的写法是按照正常思路考虑，然后求<=的最后一个元素时将mid=l+(r-l+1)/2，即(l+r+1)/2，写成r-l可以将让两个int范围边缘的正数相加不超限。后附有二分代码与使用STL函数的代码 AC代码（...

C++ C 二分查找

2025-08-13

0 10

题解33（快速幂与快速乘）

模板题，记住算了...想的有点晕前言：首先要知道(a * b)%p==(a%p)*(b%p)%p; 因为这一题普通乘法用ull会超范围，只能用int128，但是int128要手写输入输出，所以还是用快速幂，快（慢）速乘算了思路：如3^^5==3^^(0101)==3^^(2^^2+2^^0);然...

C++ C 数学

2025-08-13

0 14

题解31-32（二叉树已知某两遍历求另外一遍历）

前言：这两道题需要二叉树的知识（不会的可以去B站搜搜），需要画图，但博客里好像没有在线画图的功能，所以我只能写写大致的思路了题解31：https://ac.nowcoder.com/acm/problem/16692 PS：二叉树遍历知二求一，但已知先后序遍历不行，需要额外的特殊条件来将左右子...

C++ C 二叉树递归

2025-08-13

0 12

题解30 FBI树

前言：左右移操作一定要检查左右移的位数不是负数，两个等价的表达式，在边界数据输入后，结果天差地别如：1<<n 和2<<(n-1),输入正数时两者等价，输入0时2<<-1未定义操作，会出现奇奇怪怪的值，使得输入函数的参数出错，最终无限递归，内存超限，所以当时我都想...

C++ C 递归二叉树

2025-08-13

0 13