UVA 1493 DRAW A MASS

现在的位置: 首页 > 综合 > 正文

UVA 1493 DRAW A MASS

2018年03月17日 ⁄ 综合 ⁄ 共 5016字 ⁄ 字号小中大 ⁄ 评论关闭

第一个为线段树版本直接覆盖即可

#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\n",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("\n");
    }
    return 0;
}
void show(){
  printf("*****************\n");
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        printf("%d",query(1,m,1,j,i));
    }
    printf("\n");
  }
}

第二个为先缓存，然后倒顺序覆盖，只要没着色的点便需要着色，然后使用类似并查集的状态压缩函数求改点的下一个未被覆盖点。

下面的程序输入加了挂，可还没有不加挂跑的快，无语了。

#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\n",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\n",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("\n");
    }
    return 0;
}

【上篇】Project Euler problem 68
【下篇】UVA – 311 Pockets(贪心策略)

作者: Feercotmom

该日志由 Feercotmom 于6年前发表在综合分类下，最后更新于 2018年03月17日.
转载请注明: UVA 1493 DRAW A MASS | 学步园 +复制链接

抱歉!评论已关闭.

学步园

UVA 1493 DRAW A MASS

作者: Feercotmom

书签

最新文章New

本站推荐

返回首页