UVA 1493 DRAW A MASS

8780 단어
첫 번째는 세그먼트 트리 버전을 직접 덮어쓰면 됩니다.
#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int n,m;
const int N = 211;
const int M = 51111;
int color[N][M<<2];
void build(int l,int r,int rt,int i){
  color[i][rt] = 0;
  if(l==r) return ;
  int m = (l+r)>>1;
  build(lson,i);
  build(rson,i);
}
void push_down(int rt,int i){
  if(color[i][rt]){
    color[i][rt<<1]=color[i][rt<<1|1]=color[i][rt];
    color[i][rt] = 0;
  }
}
void update(int l,int r,int rt,int L,int R,int val,int i){
  if(L<=l&&r<=R){
     color[i][rt] = val;
     return ;
  }
  push_down(rt,i);
  int m = (l+r)>>1;
  if(L<=m) update(lson,L,R,val,i);
  if(R >m) update(rson,L,R,val,i);
}
int query(int l,int r,int rt,int posi,int i){
  if(color[i][rt]||l==r){
     return color[i][rt];
  }
  int m = (l+r)>>1;
  if(posi<=m) return query(lson,posi,i);
  return query(rson,posi,i);
}
int xc, yc, r, c, l , w;
//xc, yc, r, c;
void circle(int i,int& L,int& R){
  int te = r*r - (i-xc)*(i-xc);
  if(te<0||i<xc-r||i>xc+r){
    L = 1; R = 0; return ;
  }
  te = floor(sqrt(te*1.0));
  L = max(yc-te,1);
  R = min(yc+te,m);
 // printf("%d --> %d %d
",i,L,R);
}
//xc, yc, r, c£»
void diamond(int i,int& L,int& R){
  int te = r - abs(i-xc);
  if(te<0){
    L = 1; R = 0; return ;
  }
  L = max(yc-te,1);
  R = min(yc+te,m);
}
//xc, yc, l, w, c,
void rectangle(int i,int& L,int& R){
  if(i<xc||i>xc+l-1) {
     L = 1; R = 0;
     return ;
  }
  L = ceil(max(yc*1.0,1.0));
  R = floor(min(yc+w-1.0,m*1.0));
}
//xc, yc, w, c
void triangle(int i,int& L,int& R){
  if(i<xc || i >= xc +(w+1)/2){
     L= 1; R= 0; return ;
  }
  int dis=(w-1)/2-(i-xc);
  L = max(yc-dis,1);
  R = min(yc+dis,m);
}
int main()
{
    int Q;
    char cmd[100];
    while(scanf("%d %d %d",&n,&m,&Q)==3){
        for(int i=1;i<=n;i++) build(1,m,1,i);
        while(Q--){
        scanf("%s",cmd);
        if(cmd[0]=='C'){
            scanf("%d %d %d %d",&xc, &yc, &r, &c);
            xc++; yc++;
            for(int i=1;i<=n;i++){
                int L,R;
                circle(i,L,R);
                if(L <= R){
                    update(1,m,1,L,R,c,i);
                }
            }
        }
        else if(cmd[0]=='D'){
            scanf("%d %d %d %d",&xc, &yc, &r, &c);
            xc++; yc++;
            for(int i=1;i<=n;i++){
                int L,R;
                diamond(i,L,R);
                if(L <= R){
                    update(1,m,1,L,R,c,i);
                }
            }
        }
        else if(cmd[0]=='T'){
            scanf("%d %d %d %d",&xc, &yc, &w, &c);
            xc++; yc++;
            for(int i=1;i<=n;i++){
                int L,R;
                triangle(i,L,R);
                if(L <= R){
                    update(1,m,1,L,R,c,i);
                }
            }
        }
        else {
           scanf("%d %d %d %d %d",&xc, &yc,&l, &w, &c);
            xc++; yc++;
            for(int i=1;i<=n;i++){
                int L,R;
                rectangle(i,L,R);
                if(L <= R){
                    update(1,m,1,L,R,c,i);
                }
            }
        }
        }
      //void show(); show();
      int cnt[10]={0};
      for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
          cnt[query(1,m,1,j,i)]++;
      for(int i=1;i<=9;i++) {
          if(i>1) printf(" ");
          printf("%d",cnt[i]);
      }
      printf("
");
    }
    return 0;
}
void show(){
  printf("*****************
");
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        printf("%d",query(1,m,1,j,i));
    }
    printf("
");
  }
}

두 번째는 캐시를 먼저 한 다음 거꾸로 덮어쓰는 것입니다. 착색되지 않은 점만 있으면 착색을 해야 합니다. 그리고 유사한 상태 압축 함수를 사용하여 변경된 점의 다음 덮어쓰지 않은 점을 구합니다.
아래의 프로그램은 입력에 끊기를 넣었지만 아직 끊지 않고 빨리 달리는 것이 없어서 어이가 없다.
#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int n,m;
const int N = 211;
const int M = 51111;
int color[N][M],jump[N][M],cnt[10];
int xc, yc, r, c, l , w;
int find(int st,int i){
  if(!color[i][jump[i][st]]) return jump[i][st];
  return jump[i][st] = find(jump[i][st],i);
}
void update(int st,int ed,int i){
  for(int j=st;j<=ed;){
     if(!color[i][j]) {
        color[i][j] = 1;
        cnt[c]++;
     }
     j=find(j,i);
  }
}
template <class T>
inline bool scan_d(T &ret) {
    char c; int sgn;
    if(c=getchar(),c==EOF) return 0; //EOF
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
struct node{
  char cmd;
  int data[10];
}cun[M];
void read_input(int i){
  char str[100];
  scanf("%s",str);
  cun[i].cmd=str[0];
  scan_d(cun[i].data[0]);
  scan_d(cun[i].data[1]);
  scan_d(cun[i].data[2]);
  scan_d(cun[i].data[3]);
  if(str[0]=='R')
    scan_d(cun[i].data[4]);
}
//xc, yc, r, c;
void circle(int i,int& L,int& R){
  int te = r*r - (i-xc)*(i-xc);
  if(te<0||i<xc-r||i>xc+r){
    L = 1; R = 0; return ;
  }
  te = floor(sqrt(te*1.0));
  L = max(yc-te,1);
  R = min(yc+te,m);
 // printf("%d --> %d %d
",i,L,R);
}
//xc, yc, r, c£»
void diamond(int i,int& L,int& R){
  int te = r - abs(i-xc);
  if(te<0){
    L = 1; R = 0; return ;
  }
  L = max(yc-te,1);
  R = min(yc+te,m);
}
//xc, yc, l, w, c,
void rectangle(int i,int& L,int& R){
  if(i<xc||i>xc+l-1) {
     L = 1; R = 0;
     return ;
  }
  L = ceil(max(yc*1.0,1.0));
  R = floor(min(yc+w-1.0,m*1.0));
}
//xc, yc, w, c
void triangle(int i,int& L,int& R){
  if(i<xc || i >= xc +(w+1)/2){
     L= 1; R= 0; return ;
  }
  int dis=(w-1)/2-(i-xc);
  L = max(yc-dis,1);
  R = min(yc+dis,m);
}
int main()
{
    int Q;
    char cmd[100];
    while(scanf("%d %d %d",&n,&m,&Q)==3){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
              color[i][j] = 0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m+1;j++)
                jump[i][j]=j+1;
        }
        for(int i=1;i<=9;i++) cnt[i] = 0;
        for(int i=1;i<=Q;i++) read_input(i);
       for(int g=Q;g>=1;g--){
        if(cun[g].cmd=='C'){
            xc = cun[g].data[0];
            yc = cun[g].data[1];
            r  = cun[g].data[2];
            c  = cun[g].data[3];
            xc++; yc++;
            for(int i=1;i<=n;i++){
                int L,R;
                circle(i,L,R);
                if(L <= R){
                    update(L,R,i);
                }
            }
        }
        else if(cun[g].cmd=='D'){
            xc = cun[g].data[0];
            yc = cun[g].data[1];
            r  = cun[g].data[2];
            c  = cun[g].data[3];
            xc++; yc++;
            for(int i=1;i<=n;i++){
                int L,R;
                diamond(i,L,R);
                if(L <= R){
                   // printf("%d %d
",L,R);
                    update(L,R,i);
                }
            }
        }
        else if(cun[g].cmd=='T'){
            xc = cun[g].data[0];
            yc = cun[g].data[1];
            w  = cun[g].data[2];
            c  = cun[g].data[3];
            xc++; yc++;
            for(int i=1;i<=n;i++){
                int L,R;
                triangle(i,L,R);
                if(L <= R){
                    update(L,R,i);
                }
            }
        }
        else {
            xc = cun[g].data[0];
            yc = cun[g].data[1];
            l  = cun[g].data[2];
            w  = cun[g].data[3];
            c  = cun[g].data[4];
            xc++; yc++;
            for(int i=1;i<=n;i++){
                int L,R;
                rectangle(i,L,R);
                if(L <= R){
                    update(L,R,i);
                }
            }
        }
        }
      for(int i=1;i<=9;i++) {
          if(i>1) printf(" ");
          printf("%d",cnt[i]);
      }
      printf("
");
    }
    return 0;
}
vue 프로젝트 npm run build 후 index를 엽니다.html 공백, 일부 그림 글꼴 파일 불러올 수 없음 해결 방법
증분 추출 hiv 과정 에서 의 모니터링

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage