Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

终于AC了,在TLE12次后。。位运算+暴力匹配。。注意一下这个TLE的点。。

Posted by ckcz123 at 2012-11-16 14:38:00 on Problem 3690
直接上我的AC代码。注意一下在judge里面的那个注释。。

[code=C/C++]
// Oh,my god!! &%$%@#$$%#%&@#%&&......
// TLE,TLE,TLE... TLE*12,WA*3......

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int m,n,p,q;
char map[1010][1010],star[55][55];
long long int mapnum[1010][1010],starnum[55];

bool judge()
{
    bool e;
    /*** If you swap the "for" of i and j here,then you will TLE.......... ***/
    for (int i=0;i<=m-p;i++)
    {
        for (int j=0;j<=n-q;j++)
        {
            e=true;
            for (int w=0;w<=p-1;w++)
            {
                if (mapnum[i+w][j]!=starnum[w])
                {
                    e=false;break;
                }
            }
            if (e) return true;
        }
    }
    return false;
}

int main()
{
    int t=0,k,num=0;
    long long int flag;
    while (cin >> m >> n >> k >> p >> q)
    {
        if (m+n+k+p+q==0) break;
        t++;num=0;
        flag=~(1LL<<(q-1));
        if (p>m || q>n)
        {
            printf("Case %d: 0\n",t);continue;
        }
        for (int i=0;i<=m-1;i++)
        {
            mapnum[i][0]=0;
            scanf("%s",map[i]);
            for (int j=0;j<=q-1;j++)
            {
                mapnum[i][0]<<=1;
                mapnum[i][0]|=(map[i][j]=='*');
            }
            for (int j=1;j<=n-q;j++)
                mapnum[i][j]=((mapnum[i][j-1]&flag)<<1)|(map[i][j+q-1]=='*');
        }
        while (k--)
        {
            for (int i=0;i<=p-1;i++)
            {
                scanf("%s",star[i]);
                starnum[i]=0;
                for (int j=0;j<=q-1;j++)
                {
                    starnum[i]<<=1;
                    starnum[i]|=(star[i][j]=='*');
                }
            }
            if (judge())
                num++;
        }
        printf("Case %d: %d\n",t,num);
    }
    return 0;
}
[/code]

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator