题目背景
一天，GD和MW正在玩一款名叫大海战的游戏。
题目描述
游戏在一个1*n的棋盘上进行。一开始GD拥有c种战舰，每种战舰的宽度为1，长度为ci，共有ti个。GD要将所有这些战舰放置在棋盘上，并且任意两艘战舰间不能重叠（但可以相邻）。接下来，MW进行q次“攻击”，每次攻击一个1*1的格子，而MW将告知他这次攻击是否“打中”了一艘战舰（或者它的某个部分）。令人疑惑的是，每次MW都告诉GD说他没有打中任何一艘战舰，而这显然是不现实的。现在MW把整个游戏的过程告诉了你，他想知道，最早在他的第几次询问之后，可以断定GD一定（至少有一次）说了谎。
输入输出格式
输入格式： 第一行一个整数t，表示测试数据的组数。对于每组数据，第一行三个整数n，c，q，代表棋盘的长度、战舰的种数和攻击的次数。接下来c行，每行两个整数ci、ti，表示第i种战舰的长度和数量。（不同的战舰，长度可能相同。）接下来一行q个整数，表示MW的攻击序列。
输出格式： 对于每组数据，输出一个整数ans，表示最早在第ans次操作后可以断定GD说了谎。特别地，如果一开始就不可能按要求摆上所有的战舰，输出0；如果q次询问后都不能判断GD是否说了谎，则输出－1。
输入输出样例
输入样例#1： 3 12 2 2 1 1 2 5 6 8 5 1 2 3 1 1 5 11 3 0 2 2 3 1 5 1 输出样例#1： 2 -1 0 说明
样例解释
对于第一个样例，存在布阵｛1，22，22，0，22，22，22｝（0表示没有放置），使得第一次不会受到攻击；不存在一个布阵使得两次都没有受到攻击。
对于第二个样例，存在布阵｛0，333，0｝，使得两次均不会受到攻击。
对于第三个样例，一开始就不可能把所有战舰合法地布置在棋盘上。
数据范围
对于100%的数据，1<=t<=5,n>=1,c>=1,q>=0,1<=qi<=n,0<=ci<=100000，0<=ti<=100000。
对于测试点1，n<=1000000000，c<=100000，q=0；
对于测试点2、3，所有的ti均为1；
对于测试点2-8，n<=400000，c<=100，q=1；
对于测试点9，n<=100，c=1，q<=100；
对于测试点10-14，n<=200000，c=1，q<=200000；
对于测试点15、16，n<=200，c=2，q<=200；
对于测试点17-20，n<=4000，c=2，q<=4000。
提示 你可能不需要一个读入优化，但可能需要一些常数优化。
友情提示，此题代码在自己机子上评A了，在洛谷上交只有85（QAQ，T了三个点）
大体思路：
第一个点没有询问，只需要判断初始棋盘能否放下就行了。——直接把所有ci*ti加起来，判是否小于等于n即可。（但是大家似乎忘记了ci和ti的范围——乘起来会爆int，造成许多P党直接RE……）
第2到第8个点，只有一次询问。这个询问把棋盘分成了两段，我们考虑其中较短的那部分，就变成了一个背包问题——要在这部分中放置尽量多的物品，空间浪费得越少越好。（至于剩下的那部分，直接用物品总体积减去前面能够放入的物品体积，与剩余的空间进行比较即可。）每个战舰的价值即为它的长度，直接多重背包即可。第2、3个点直接是01背包，而后面的点由于c*n较大，朴素的背包会T，需要用单调队列优化得到O(cn)的算法，可以参见http://www.cppblog.com/MatoNo1/archive/2011/07/05/150231.aspx。（我尝试卡过二进制拆分的多重背包，但写得优美的话也可以过）。
第9到14个点，只有一种物品。我们二分答案，那么询问序列把棋盘分成了多个部分。假设某一段的长度为L，那么就可以放下L/size个物品。于是我们扫一遍就可以统计最多放置的物品数量，然后再根据要求二分下去即可。
第15到20个点，有两种物品。在二分的基础上（设分为了mid段），我们用f[i][j]表示考虑到前i段，恰好放置j种1号物品的前提下，可以放置的最多2号物品的数量。设第i段的长度为Li，转移方程为f[i][j]=max(f[i-1][j-k]+(Li-k*size1)/size2)，其中0<=k<=j且k*size1<=Li。那么f[mid][num1]就是当前状态可以放置的最多2号物品的数量，与要求进行比较，再二分即可。看上去这个方程是O(n^3)的，但实际上我们有k<=Li，因此对于确定的j，考虑所有的i，总共的决策数量不会超过sigma(Li)，即不会超过O(n)个。所以DP的复杂度为O(n^2)，整个算法的时间复杂度为O(n^2logq)，但远远达不到这个界，稍微优化一下就可以过了。
program df; var i,j,n,m,x,y,z,k,t,tt,kk:longint; ans:int64; a,b,c,d,f:array[0..400000] of longint; g:array[0..2,0..4000] of longint;
function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end;
procedure sq(l,r:longint); var i,j,mm,dd:longint; begin i:=l; j:=r; mm:=a[(l+r) div 2]; repeat while mm>a[i] do inc(i); while a[j]>mm do dec(j); if i<=j then begin dd:=a[i]; a[i]:=a[j]; a[j]:=dd; dd:=b[i]; b[i]:=b[j]; b[j]:=dd; inc(i); dec(j); end; until i>j; if j>l then sq(l,j); if r>i then sq(i,r); end;
procedure deal1(n,m:longint); //将长度都加起来与n比较即可 var s:int64; x,y,i:longint; begin s:=0; for i:=1 to m do begin readln(x,y); s:=s+int64(x)*int64(y); end; if s>n then writeln(0) else writeln(-1); end;
function min(x,y:longint):longint; begin if x>y then exit(y) else exit(x); end;
//——————————————————————————华丽的分割线
procedure check1(x,y:longint); //完全背包 var i,j:longint; begin for i:=x to y do if f[i-x]+x>f[i] then f[i]:=f[i-x]+x; end;
procedure check2(x,y:longint); //01背包 var i,j:longint; begin for i:=y downto x do if f[i-x]+x>f[i] then f[i]:=f[i-x]+x; end;
procedure deal2(n,m:longint); //只有一处攻击，分成两个区域，将较小区域的用背包做出，另一个区域用背包总面积减去即可（背包因数据范围太大，用二进制优化即可，但最好用单调队列） var s:int64; x,y,i,j,k:longint; begin s:=0; for i:=1 to m do begin readln(b[i],a[i]); s:=s+int64(a[i])*int64(b[i]); end; readln(x); if s>n then begin writeln(0); exit; end; if s=n then begin writeln(1); exit; end; y:=min(x-1,n-x); x:=n-y-1; fillchar(f,sizeof(f),0); for i:=1 to m do //背包的二进制优化，不懂自己查 begin if a[i]*b[i]>y then check1(b[i],y) else begin kk:=1; tt:=a[i]; while tt>kk*2 do begin check2(kk*b[i],y); tt:=tt-kk; kk:=kk*2; end; check2(tt*b[i],y); end; end; if s-f[y]>x then writeln(1) else writeln(-1); end; //——————————————————————————华丽的分割线 function search(mid,x,y:longint):boolean; //对小于等于mid的攻击处理，将每个区域贪心即可（因为只有一种战舰忙） var i,j,l:longint; ans:int64; begin ans:=0; l:=0; for i:=1 to k do //将各个区域能放置的战舰数量加起来即可 if b[i]<=mid then begin ans:=ans+((a[i]-l-1) div x); l:=a[i]; end; ans:=ans+((n-l) div x); if ans>=y then exit(false) else exit(true); end;
procedure deal3(n,k:longint); //只有一种战舰，对于询问按区域排序，二分（具体见代码） var s:int64; x,y,i,j,l,r,mid:longint; begin readln(x,y); if int64(x)*int64(y)>n then begin writeln(0); exit; end; for i:=1 to k do begin read(a[i]); b[i]:=i; end; sq(1,k); a[k+1]:=0; b[k+1]:=0; l:=1; r:=k; while r-1>l do begin mid:=(l+r) div 2; if search(mid,x,y) then r:=mid else l:=mid; end; if search(l,x,y) then writeln(l) else if search(r,x,y) then writeln(r) else writeln(-1); end;
//———————————————————————————————–华丽的分割线
function check(x,n,k:longint):boolean; //将所有分割的区域统计一下（操作和上次差不多），然后对于两种战舰的选择dp处理（具体代码里解释） var i,j,ans,l,t,xx,yy:longint; begin l:=0; t:=0; fillchar(g,sizeof(g),$9f); for i:=1 to k do //将满足条件的各个区域的长度求解出来 if b[i]<=x then begin inc(t); f[t]:=a[i]-l-1; l:=a[i]; end; inc(t); f[t]:=n-l; g[0,0]:=0; for i:=1 to t do //各个区域列举 for j:=0 to d[1] do //第一类战舰的数量从0列举 begin xx:=0; yy:=0; //xx代表第i个区域放入第一类战舰的数量，yy代表表示xx个第一类战舰所占的面积 while (xx<=j) and (yy<=f[i]) do begin g[i and 1,j]:=max(g[i and 1,j],g[(i and 1) xor 1,j-xx]+(f[i]-yy) div c[2]); //数值较大，所以用了滚动数组，再次稍作解释（i and 1就是判断0和1而已，xor是取反，一个滚动数组从另一个滚动数组的状态转移而来，不懂得自己查） inc(xx); yy:=yy+c[1]; end; end; if d[2]>g[t and 1,d[1]] then exit(true) else exit(false); end;
procedure deal4(n,m,k:longint); //有两种战舰，还是二分处理询问，但二分中不再是贪心，而是dp（见代码） var i,j,x,y,z,l,r,mid:longint; ans:int64; begin ans:=0; for i:=1 to m do begin readln(c[i],d[i]); ans:=ans+int64(c[i])*int64(d[i]); end; for i:=1 to k do begin read(a[i]); b[i]:=i; end; if ans>n then begin writeln(0); exit; end; sq(1,k); l:=1; r:=k; while r-1>l do begin mid:=(l+r) div 2; if check(mid,n,k) then r:=mid else l:=mid; end; if check(l,n,k) then writeln(l) else if check(r,n,k) then writeln(r) else writeln(-1); end;
begin assign(input,’1.in’); reset(input); assign(output,’seabattle.out’); rewrite(output); readln(t); for z:=1 to t do begin readln(n,m,k); if k=0 then deal1(n,m) //没有攻击 else if k=1 then deal2(n,m) //只有一次攻击 else if m=1 then deal3(n,k) //只有一种战舰 else deal4(n,m,k); //两种战舰 end; close(input); close(output); end.
