Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3699 miniSQL---模拟

Posted on 2010-04-03 20:35 Uriel 阅读(447) 评论(0)  编辑 收藏 引用 所属分类: POJ模拟
        这题快一年前就看了,觉得太麻烦就一直没做,昨天心情不爽于是又拿来做找刺激。。结果完全杯具。。今天晚上才过掉。。
        昨天写的方法是:先把要输出的那个表格存进一个char型数组,觉得这样输出的时候不那么纠结。。但是这题没说STR型的数据最多多长,于是不停的提交来试。。结果就是MLE, RE, WA, OLE, TLE...加起来快60次。。以为是哪里没考虑到,于是-0这样的恶心数据也考虑了,负数也考虑了,空数据也考虑了。。还是一次次的杯具。。
        最后实在受不了了,于是改方法,不存结果,最后一行一行输出。。竟然一下就过了。。。但是G++还是TLE,不知原因啊。。也许memset太多了。。
        都不知道这题到底什么trick了。。能考虑的都考虑了。。(知道的只有-0的情况不要考虑),代码夹杂了一堆调试的语句和第一种方法的部分。。也懒得改了。。贴个代码。。哪位一样被这题虐的ACMer可以对拍下数据什么的。。具体代码就不要看了。。丑陋至极。。10527B。。

/*
  Problem: 3699  User: Uriel 
  Memory: 21832K  Time: 157MS 
  Language: C++  Result: Accepted 
*/

#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<algorithm>
using namespace std; 

#define MAXN 10001

char P[MAXN][11][201];
int n;//col总数
int m;//记录总数 
int qry;//每个询问有多少个属性
int k;//共有几个询问 
int q;//0->'='; 1->'<'; 2->'>'
int si;//0->限制条件为int,1->限制条件为string
int nres;//满足条件的结果数 
int cons;//限制条件是第几个col
char xd[11][201];//存需要输出的属性的名字 
int id[11];//存要输出的属性的代号 
int kind[11];//每个col的数据类型,0为string,1为int
char col[11][201];//每个col的名字
int res[MAXN];//存满足限制条件的结果的序号(输入序号,非ID)
int width,height;//最后结果的宽和高
//char ans[MAXN+5][3200];//存最后要输出的结果 
int val;
int maxl;  
char str[301];
char sample[301];
char type[11];//暂存每个col数值类型 
char tmps[10];//去掉select,where 
int maxdis[11];//输出每一格的最大宽度 

int main()
{
    
int i,j,h; 
    
char c;
    memset(P,
0x00,sizeof(P));
//    freopen("out.txt","w",stdout);
    scanf("%d %d %d",&n,&m,&k);
    
for(i=0;i<n;i++)
    
{
        scanf(
"%s %s",col[i],type);
//        printf("*%s %s*\n",col[i],type);
        if(strcmp(type,"STR")==0)
        
{
            kind[i]
=1;
        }

        
else
        
{
            kind[i]
=0;
        }

    }

    
for(i=0;i<m;i++)
    
{
        
for(j=0;j<n;j++)
        
{
            scanf(
"%s",P[i][j]);
//            printf("* %d *\n",kind[j]);
//            if(kind[j]==0 && P[i][j][0]=='-' && P[i][j][1]=='0')
//            {
//                printf("*");
//                P[i][j][0]='0';
//                P[i][j][1]='\0';
//            }
//            printf("*%s*\n",P[i][j]);
        }

    }

    
while(k--)
    
{
        scanf(
"%s",tmps);
//        printf("*%s*\n",tmps);
        getchar();
        qry
=0;
        memset(xd,
0x00,sizeof(xd));
        
while(1)
        

            
int tmp=0;
            
while(1)
            
{
                c
=getchar();
                
if(c==' ')
                
{
                    qry
++;
                    
goto flag;
                }

                
else if(c==',')break;
                
else
                    xd[qry][tmp
++]=c;
            }

//            printf("* %s *\n",xd[qry]);
            qry++;
        }

//      for(i=0;i<qry;i++)
//        {
//          printf("* %s *\n",xd[i]);
//      }
flag:    for(i=0;i<qry;i++)
        
{
            
for(j=0;j<n;j++)
            
{
                
if(strcmp(xd[i],col[j])==0)
                
{
                    id[i]
=j;
//                    printf("id[%d]=%d\n",i,j);
                    break;
                }

            }

        }

        j
=0;
//        getchar();
        scanf("%s",tmps);
//        printf("* %s *\n",tmps);
        getchar();
        memset(str,
0x00,sizeof(str));
        
while(1)
        
{
            c
=getchar();
            
if(c=='=')
            
{
//                printf("* %s *\n",str);
                q=0;
                
for(i=0;i<n;i++)
                
{
                    
if(strcmp(col[i],str)==0)
                    
{
                        cons
=i;
                        
break;
                    }

                }

//                cons=i;
                if(kind[i]==1)
                
{
                    si
=1;
                    
while(c=getchar()==' ')getchar();
//                    getchar();//去掉第一个"
                    scanf("%s",sample);
//                    printf("%s\n",sample);
                    sample[strlen(sample)-1]='\0';//去掉第二个"
//                    printf("sample=%s\n",sample);
                }

                
else
                
{
                    si
=0;
                    scanf(
"%s",sample);
//                    printf("sample=%s\n",sample);
                    val=atoi(sample);
/*                    if(sample[0]=='-')
                    {          
                        val=(-1)*(sample[1]-'0');          
                        for(i=2;i<strlen(sample);i++)
                        {
                            val=val*10+sample[i]-'0';
                        }
                    }
                    else
                    {
                        for(i=0;i<strlen(sample);i++)
                        {
                            val=val*10+sample[i]-'0';
                        }
                    }               
*/
 
                }

                
break;
            }

            
else if(c=='<')
            
{
//                printf("* %s *\n",str);
                q=1;
                si
=0;
                
for(i=0;i<n;i++)
                
{
                    
if(strcmp(col[i],str)==0)
                    
{
                        cons
=i;
                        
break;
                    }

                }

//                cons=i;
                scanf("%s",sample);
//                printf("sample=%s\n",sample);
                val=atoi(sample);
/*                if(sample[0]=='-')
                {          
                    val=(-1)*(sample[1]-'0');          
                    for(i=2;i<strlen(sample);i++)
                    {
                        val=val*10+sample[i]-'0';
                    }
                }
                else
                {
                    for(i=0;i<strlen(sample);i++)
                    {
                        val=val*10+sample[i]-'0';
                    }
                }               
*/

                
break;
            }

            
else if(c=='>')
            
{
//                printf("* %s *\n",str);
                q=2;
                si
=0;
                
for(i=0;i<n;i++)
                
{
                    
if(strcmp(col[i],str)==0)
                    
{
                        cons
=i;
                        
break;
                    }

                }

//                cons=i;
//                printf("cons=%d\n",cons);
                scanf("%s",sample);
//                printf("sample=%s\n",sample);
                val=atoi(sample);
/*                if(sample[0]=='-')
                {          
                    val=(-1)*(sample[1]-'0');          
                    for(i=2;i<strlen(sample);i++)
                    {
                        val=val*10+sample[i]-'0';
                    }
                }
                else
                {
                    for(i=0;i<strlen(sample);i++)
                    {
                        val=val*10+sample[i]-'0';
                    }
                }               
*/

                
break;
            }

            
else if(c==' ')continue;
            
else
                str[j
++]=c;
        }

//        printf("val=%d\n",val);
//        printf("sample=%s\n",sample);
//        memset(res,0,sizeof(res));
//        memset(ans,0x00,sizeof(ans));
        nres=0;
        
if(!si)//限制条件是数字类型
        {
//            printf("*");
            if(q==0)
            
{
                
for(i=0;i<m;i++)
                
{
                    
if(atoi(P[i][cons])==val)
                    
{
                        res[nres
++]=i;
                    }

                }

            }

            
else if(q==1)
            
{
                
for(i=0;i<m;i++)
                
{
                    
if(atoi(P[i][cons])<val)
                    
{
                        res[nres
++]=i;
                    }

                }

            }

            
else if(q==2)
            
{
                
for(i=0;i<m;i++)
                
{
//                    printf("tmp=%d\n",atoi(P[i][cons]));
                    if(atoi(P[i][cons])>val)
                    
{
                        res[nres
++]=i;
//                        printf("*\n");
                    }

                }

            }

        }

        
else 
        
{
//            printf("dd\n");
            for(i=0;i<m;i++)
            
{
                
if(strcmp(P[i][cons],sample)==0)
                
{
                    res[nres
++]=i;
//                    printf("res=%d\n",i);
                }

            }

        }

//        for(i=0;i<nres;i++)
//        {
//            printf("res=%d\n",res[i]);
//        }
//        memset(ans,0x00,sizeof(ans));
/*------------------------------------------------------------------------        
        ans[0][0]='+';
        width=0;
        height=nres+4;
//        printf("high=%d\n",height);
        for(i=1;i<height-1;i++)
        {
            ans[i][0]='|';
        } 
        ans[i][0]='+';
//        for(i=0;i<height;i++)
//          {
//           for(j=0;j<1;j++)
//            {
//                printf("%c",ans[i][j]);
//            }
//            printf("\n");
//        }          
//        break;   
//        printf("nres=%d\n",nres);
        for(j=0;j<qry;j++)
        {
//            printf("width=%d\n",width);
            maxl=strlen(col[id[j]]);//每格的宽度 
//            printf("maxl=%d\n",maxl);
            for(i=0;i<nres;i++)
            {
                if(strlen(P[res[i]][id[j]])>maxl)maxl=strlen(P[res[i]][id[j]]);
            }
            maxl+=2; 
//            printf("maxl=%d\n",maxl);
//            width+=maxl;
            for(i=width+1;i<=width+maxl;i++)
            {
                ans[2][i]='-';
            }
            for(i=1;i<height-1;i++)
            {
                ans[i][width+maxl+1]='|';
            }
            for(i=width+1;i<=width+maxl;i++)
            {
                ans[1][i]=' ';
            }
//            printf("maxl=%d\nwidth=%d\n",maxl,width);
            strcpy(&ans[1][width+(maxl-strlen(col[id[j]]))/2+1],col[id[j]]);
            for(i=0;i<nres;i++)
            {
                for(h=width+1;h<width+maxl+1;h++)
                {
                    ans[i+3][h]=' ';
                }
                strcpy(&ans[i+3][width+(maxl-strlen(P[res[i]][id[j]]))/2+1],P[res[i]][id[j]]);
            }               
            width=width+maxl+1;
        }    
        for(i=0;i<height;i++)
        {
            for(j=0;j<width;j++)
            {
                ans[i][j]=' ';
            }
        }               
//        printf("width=%d\n",width);
//        printf("height=%d\n",height);
        for(i=1;i<width;i++)
        {
            ans[0][i]='-';
            ans[height-1][i]='-';
        }
        ans[0][width]='+';
        ans[height-1][width]='+'; 
//        for(i=0;i<m;i++)
//        {
//            for(j=0;j<n;j++)
//            {
//                printf("%s ",P[i][j]);
//            }
//            printf("\n");
//        }                           
        for(i=0;i<height;i++)
          {
            for(j=0;j<=width;j++)
            {
                printf("%c",ans[i][j]);
            }
            printf("\n");   
        }            
------------------------------------------------------------------------
*/
   
        width
=1;
//        printf("qry=%d\n",qry);
        for(i=0;i<qry;i++)
        
{
            maxdis[i]
=strlen(col[id[i]]);
            
for(j=0;j<nres;j++)    
            
{
                
if(maxdis[i]<strlen(P[res[j]][id[i]]))
                
{
                    maxdis[i]
=strlen(P[res[j]][id[i]]);
                }

            }

            maxdis[i]
+=2;
//            printf("dis=%d\n",maxdis[i]);
            width+=maxdis[i]+1;
        }

        printf(
"+");
        
for(i=1;i<width-1;i++)
        
{
            printf(
"-");
        }

        printf(
"+\n");
        printf(
"|");
        
for(i=0;i<qry;i++)
        
{
            
for(j=0;j<(maxdis[i]-strlen(col[id[i]]))/2;j++)
            
{
                printf(
" ");
            }

            printf(
"%s",col[id[i]]);
            
for(j=0;j<(maxdis[i]-strlen(col[id[i]])+1)/2;j++)
            
{
                printf(
" ");
            }

            printf(
"|");
        }

        printf(
"\n");
        printf(
"|");
        
for(i=0;i<qry;i++)
        
{
            
for(j=0;j<maxdis[i];j++)
            
{
                printf(
"-");
            }

            printf(
"|");
        }

        printf(
"\n");
        
for(i=0;i<nres;i++)
        
{
            printf(
"|");
            
for(j=0;j<qry;j++)
            
{              
                
for(h=0;h<(maxdis[j]-strlen(P[res[i]][id[j]]))/2;h++)
                
{
                    printf(
" ");
                }

                printf(
"%s",P[res[i]][id[j]]);
                
for(h=0;h<(maxdis[j]-strlen(P[res[i]][id[j]]+1))/2;h++)
                
{
                    printf(
" ");
                }

                printf(
"|");
            }

            printf(
"\n");
        }

        printf(
"+");
        
for(i=1;i<width-1;i++)
        
{
            printf(
"-");
        }

        printf(
"+\n");    
        printf(
"\n");
    }

//    system("PAUSE");
    return 0;
}




只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理