2015.2.8
Bzoj 3441 乌鸦喝水
模拟喝水 O(nm)
可以整体累加的直接加轮
不则将当前轮分为一段一段累加 各次二分到当前最后一个 可以证明答案是可以喝水次数的其中一个 O(mlog2(n)^2)
//Bzoj 3441 乌鸦喝水
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define Rep(i,x,y) for (i=x;i<=y;++i)
#define Maxn 100010
#define Lowbit(x) x&(-x)
int A[Maxn],B[Maxn],C[Maxn],T[Maxn],M,X,i,Id[Maxn],N,m,St,_Add,Ans,Pos,L,R,Mid;
inline bool Cmp(int x,int y){
return (T[x]==T[y])?x<y:T[x]<T[y];
}
void Add(int x,int y) {
while (x<=N) {
C[x]+=y;
x+=Lowbit(x);
}
}
int Query(int x) {
int y=0;
while (x>0) {
y+=C[x];
x-=Lowbit(x);
}
return y;
}
int main() {
scanf("%d%d%d",&N,&M,&X);
Rep(i,1,N) scanf("%d",&A[i]);
Rep(i,1,N) scanf("%d",&B[i]);
Rep(i,1,N) {
T[i]=(X-A[i])/B[i]+1;
Id[i]=i; //第i名是原数组第Id[i]个
if (T[i]>0) Add(i,1);
}
//可以证明Ans是T[i]当中其中一个
sort(Id+1,Id+N+1,Cmp); //按从小到大排序可以保证没有后效性
St=N+1;
Rep(i,1,N) if (T[Id[i]]>0) { St=i; break; }
Pos=0,m=1,Ans=0;//Pos 之前最后一个
Rep(i,St,N) {
while (m<=M) {
_Add=Query(N)-Query(Pos);
if (_Add+Ans</*=*/T[Id[i]]) { ++m; Ans+=_Add; Pos=0; }
else break;
} //走一趟
if (m>M) break;
L=Pos,R=N; _Add=Query(Pos); //二分的是当前这次的最后一个 如果带上等号那么后面就不可行
while (L+1<R) {
Mid=(L+R)>>1;
if (Query(Mid)-_Add+Ans<T[Id[i]]) L=Mid; else R=Mid; //注意Query单调递增
} //走半趟 按照原先Id[i]顺序
Ans=T[Id[i]],Pos=R;
Add(Id[i],-1);
while (T[Id[i]]==T[Id[i+1]]) { Add(Id[i+1],-1); ++i; }
}
cout<<Ans<<endl;
return 0;
}
Bzoj 1854 [Scoi2010] 游戏
Right={1,2,3,..n} Left{1,2,3,..m} 对于 (i)(x,y) i->x i->y
对于Right{1,2,3,..n}作二分图匹配 到为止即可
一种并查集 来自 http://www.cnblogs.com/BLADEVIL/p/3474189.html
设联通块大小为N
对于大小为N的环 可以满足其中N个
对于大小为N的树 可以满足其中的N-1个 保证根节点是所在联通块中最大的
将一个装备(x,y)拆分成一条边x<->y
记 p=Fx q=Fy
·p=q 则若原先是环依然可行
原先是树 则根多了选择 即根也可行
·p≠q (不妨p<q) 若均为环依然可行
二树 则可以多选择其中一棵树的根节点
如果选择小的根节点则可以使其继续向上连通 保证是当前最优的
（因为如果之后又有选择 则可以选择大的）
一树一环
如果环已经可行那么树则可行 不然p可行即小的可行理由同上
//http://www.cnblogs.com/BLADEVIL/p/3474189.html
Const
n = 10000;
Var
m,i,p,q,x,y:longint;
F:array[0..2 * n] of longint;
C:array[0..2 * n] of Boolean;
Function Find(x:longint):longint;
begin
if F[x]=x then Exit(x) Else begin F[x]:=Find(F[x]); Find:=F[x]; End;
End;
Procedure Swap(var x,y:longint);
var t:longint;
begin
t:=x;
x:=y;
y:=t;
End;
Begin
Readln(m);
For i:=1 to n do F[i]:=i;
For i:=1 to n do C[i]:=False;
For i:=1 to m do begin
readln(x,y);
p:=Find(x);
q:=Find(y);
if p=q then C[p]:=True
Else begin
if p>q then Swap(p,q);
F[p]:=q;
if C[p] then C[q]:=True Else C[p]:=True; //小的已经可以全部选择 则选择大的根 不然选择小的根 让大的尾False
End;
End;
For i:=1 to n do if C[i]=False then begin Writeln(i-1); Halt; End;
Writeln(n);
End.
Bzoj 1055 [HAOI2008] 玩具取名
字符串操作题 题意为由一个字母表示一串字符
考虑动态规划 F[l][r][p] 表示 l-r 能否合成 p 字符
转移 F[l][r][p]=F[l][j][A[p][i][1]] And F[j+1][r][A[p][i][2]]
这里 A[p][i] 表示第i个双字符可以合成字符p
//http://hzwer.com/5333.html
Const
n = 4;
var
A:array[0..2*n] of longint;
F,S:array[0..n*50,0..n*50,0..2*n] of longint;
B:String;
i,m,j:longint;
C1,C2:Char;
Ok:Boolean;
Function Get(x:Char):longint;
begin
if x='W' then Exit(1);
if x='I' then Exit(2);
if x='N' then Exit(3);
if x='G' then Exit(4);
End;
Function Get2(x:longint):Char;
begin
if x=1 then Exit('W');
if x=2 then Exit('I');
if x=3 then Exit('N');
if x=4 then Exit('G');
End;
Function Dp(l,r,x:longint):Boolean;
var i,j:longint;
Begin
if F[l][r][x]>=0 then begin
if F[l][r][x]=1 then Exit(True) Else Exit(False);
End;
if l=r then begin
if B[l]=Get2(x) then Exit(True) Else Exit(False);
End;
For i:=1 to A[x] do
For j:=l to r-1 do
if Dp(l,j,S[x][i][1]) And Dp(j+1,r,S[x][i][2]) then begin
F[l][r][x]:=1;
Exit(True);
End;
F[l][r][x]:=0;
Exit(False);
End;
Begin
Fillchar(F,Sizeof(F),255);
For i:=1 to n do read(A[i]);
Readln;
For i:=1 to n do begin
For j:=1 to A[i] do begin
readln(C1,C2);
S[i][j][1]:=Get(C1);
S[i][j][2]:=Get(C2);
end;
End;
Readln(B);
m:=Length(B);
Ok:=False;
For i:=1 to n do if Dp(1,m,i) then begin Ok:=True; write(Get2(i)); End;
if Ok=False then writeln('The name is wrong!');
End.
评论 (0)
