B. Switches and Lamps
有一个n*m的棋盘，些格子上可能放有棋子。问能否找出至多（n-1）行，使得每列上都至少有一个棋子。
每行棋子的状态用bitset存储，枚举丢失的那行，若其他行或起来是满的，则yes。
C. Liebig's Barrels
总共有n*k条木板，k块木板能组成一个木桶，要组成n个木桶。根据短板效应，木桶能装水的容量由最短的板的长度决定。现在，你需要造出n个木桶，使得木桶的总容量尽可能大，但造出的木桶两两之间的容量差要<=l。
首先，我们能够知道，长度最小的木板一定是其中一个木桶的容量，也是木桶的最小容量。所以，我们能确定木桶的容量在a~a+l之间。然后，按照贪心的方法，从大的往小配，配的过程中，一定要用到至少一块这个区间的木板。
D. Sand Fortress
比赛的时候，最基本的不等式算错了。
堆沙子。给定n和h。你需要在x轴的正方向上堆出总容量为n的沙子，你需要用到最少的点。有如下几点要求：1、你在1这个点上最多放h的沙子。2、相邻两点的沙子数量最多差1.
沙子的形状只有这样两类，直接分类讨论即可。
E. Pencils and Boxes
有一堆铅笔，你要把铅笔装在盒子里。你可以使用任意个盒子，但每个盒子里至少要装k只笔。并且每只笔都有个长度，你需要保证，每个铅笔盒里的笔的长度差的最大值要<=d。问，能否成功。
刚开始思考的时候，发现十分棘手。后来发现，是一个数据结构题。
我们将所有的铅笔按照长度排序，可以发现，如果可以装盒子，那么肯定是从最小长度的铅笔开始，一段一段分配的。（不是这样装的话， 不是自己找不自在吗）这样之后，我们可以给排序完后的数组的每个位置分配一个状态，tree[i]。如果tree[i]大于0，代表从1开始到i这个位置，能够被刚好分配掉。（因为这个题求得是能不能，不是最少），(最少的话可以考虑在线段树上操作)。也就是说，我们按从小到大的顺序，查找每个位置，如果tree[i-1]>0，那么我们可以尝试分配拥有i的那段，将第i只铅笔设为一端，那么要保证至少有k只，所以右端的最下为i+k-1。要保证差<=d,所以二分一下，搜到那个位置。把那段区间覆盖即可。代表从1~i-1能够被分配的状态能转移到1~（i+k-1，maxr）能被分配。用树状数组即可。
- #include"stdio.h"
- #include"string.h"
- #include"algorithm"
- using namespace std;
- int vis[505000];
- int a[505000];
- int tree[505000];
- int n;
- int lowbit(int k){
- return k&(-k);
- }
- int query(int k){
- int x=k;
- int ans=0;
- while(x>0){
- ans+=tree[x];
- x=x-lowbit(x);
- }
- return ans;
- }
- void add(int l,int r){
- int x=l;
- while(x<=n) {
- tree[x]++;
- x=x+lowbit(x);
- }
- x=r+1;
- while(x<=n){
- tree[x]--;
- x=x+lowbit(x);
- }
- }
- int main(){
- int m,d;
- int i;
- int p,ps;
- scanf("%d %d %d",&n,&m,&d);
- for (i=1;i<=n;i++) scanf("%d",&a[i]);
- sort(a+1,a+1+n);
- memset(tree,0,sizeof(tree));
- for (i=1;i<=n;i++) if (i==1||query(i-1)>0){
- p=upper_bound(a+1,a+1+n,a[i]+d)-a;
- p--;
- ps=i+m-1;
- if (p>=ps) add(ps,min(p,n));
- }
- if (query(n)>0) printf("YES\n");else printf("NO\n");
- }
