2
10
2015
0

Bzoj 题一览 III [2015.2.9 - 2015.2.10]

2015.2.9

Bzoj 3208 花神的秒题计划Ⅰ
C 直接修改 O(1)
S,B 直接记录 O(n^2)
Q 记忆化搜索 O(n^2)
Total:O(100*n^2+m)<=1E8
 
#include <cstdio>
#include <set>
#include <cstring>
#include <iostream>
 
using namespace std;
 
#define Rep(i,x,y) for (i=x;i<=y;++i)
 
const int Inf = 201529,N=701 + 1 ;
         int Dx[4]={0,0,-1,1},Dy[4]={1,-1,0,0};
 
int F[N][N],A[N][N],x,y,z,Ans,Max,n,i,j,m,p,x1,x2,y1,y2;
bool Lazy,C[N][N];
char c[N];
 
int Dfs(int x,int y) {
    int i,X,Y;
    int Mt=0;
    if (F[x][y]) return F[x][y];
    Rep(i,0,3) {
        X=x+Dx[i],Y=y+Dy[i];
        if (X>0&&X<=n&&Y>0&&Y<=n&&A[x][y]>A[X][Y]&&C[X][Y]) {
            int T=Dfs(X,Y);
            if (T>Mt) Mt=T;
            }
        }
    return F[x][y]=Mt+1;
}
 
int main() {
    scanf("%d\n",&n);
    Rep(i,1,n) Rep(j,1,n) scanf("%d",&A[i][j]);
    Rep(i,1,n) Rep(j,1,n) C[i][j]=1;
    cin>>m;
    Lazy=1;
    while (m--) {
        scanf("%s",c);
        switch (c[0]) {
          case 'C':  
              scanf("%d%d%d",&x,&y,&z); 
              A[x][y]=z; 
              Lazy=1; 
              break;
          case 'Q': 
              if (!Lazy) printf("%d\n",Ans);
              else { 
                  Lazy=0;
                  Max=-1;
                  memset(F,0,sizeof(F));
                  Rep(i,1,n) Rep(j,1,n) {
                     if (C[i][j]) p=Dfs(i,j);
                     if (p>Max) Max=p;
                     }
                  printf("%d\n",Max);
                  Ans=Max;
              }
              break;
          case 'S':  
              scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 
              Rep(i,x1,x2) Rep(j,y1,y2) C[i][j]=0; 
              Lazy=1;
              break;
          case 'B':  
              scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 
              Rep(i,x1,x2) Rep(j,y1,y2) C[i][j]=1; 
              Lazy=1;
              break;
        }
    }
    return 0;
}
Category: 题目 | Tags: 记忆化搜索 bzoj 数据范围认识 | Read Count: 272

登录 *


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