2
8
2015
0

Bzoj 题一览 II [2015.2.8]

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.
Category: 题目 | Tags: 二分 树状数组 bzoj 动态规划 图论 并查集 搜索 | Read Count: 314

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com