QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#251742#5414. Stop, Yesterday Please No MoreTimMCBenRE 0ms3620kbC++204.3kb2023-11-15 02:22:472023-11-15 02:22:47

Judging History

你现在查看的是最新测评结果

  • [2023-11-15 02:22:47]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3620kb
  • [2023-11-15 02:22:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
int main()
{
    IOS;
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,k;
        cin>>n>>m>>k;
        string s;
        cin>>s;
        vector<int>a,b;
        for(auto it:s)
        {
            if(it=='U'||it=='D')
            {
                a.push_back(it);
            }else
            {
                b.push_back(it);
            }
        }
        int pre=0;
        int u=0,d=0;
        for(auto it:a)
        {
            if(it=='D')
            {
                pre++;
            }else
            {
                pre--;
            }
            u=max(u,pre);
            d=min(d,pre);
        }

        pre=0;
        int l=0,r=0;
        for(auto it:b)
        {
            if(it=='L')
            {
                //方向相反
                pre++;
            }else
            {
                pre--;
            }
            l=min(l,pre);
            r=max(r,pre);
        }

        int len=u-d+1;
        int wid=r-l+1;
/*         cout<<len<<" "<<wid<<endl;
        cout<<len-u<<" "<<wid-r<<endl;
        cout<<l<<" "<<r<<" "<<u<<" "<<d<<endl; */
        if(l<-m||r>m||u>n||d<-n)
        {
            if(k==0)
            {
                cout<<n*m<<endl;
            }else
            {
                cout<<0<<endl;
            }
            continue;
        }
        int L=1+r;
        int R=m+l;

        int U=1+u;
        int D=n+d;

        if(L>R||U>D)
        {
            if(k==0)
            {
                cout<<n*m<<endl;
            }else
            {
                cout<<0<<endl;
            }
            continue;            
        }
        //D、U是上下
        //L、R是左右
        assert(len>0);
        assert(wid>0);
        vector<vector<int>>v(len+1,vector<int>(wid+1));
        v[len-u][wid-r]=-1;
        assert(len-u>0);
        assert(wid-r>0);
        int x=len-u,y=wid-r;
        
        for(auto it:s)
        {
            if(it=='U')
            {
                x++;
            }else if(it=='D')
            {
                x--;
            }else if(it=='L')
            {
                y++;
            }else
            {
                y--;
            }
            v[x][y]=-1;
        }
        
        vector<vector<int>>pr(len+1,vector<int>(wid+1));
        //二维前缀和
        for(int i=1;i<=len;i++)
        {
            for(int j=1;j<=wid;j++)
            {
                pr[i][j]=pr[i-1][j]+pr[i][j-1]+v[i][j]-pr[i-1][j-1];
            }
        }

        function<int(int,int)>judge=[&](int x,int y)
        {   

            int res=0;
            //上下边界
            int x_d=x,x_u=x-len+1;
            int y_r=y,y_l=y-wid+1;
            int ans=(R-L+1)*(D-U+1);
            /* cout<<ans<<endl; */
            int l=max(y_l,L);
            int r=min(y_r,R);

            int d=min(x_d,D);
            int u=max(x_u,U);

            if(l<=r&&u<=d)
            {
                //
                int w=wid-(y-r);
                int h=len-(x-d);

                y=w-(r-l);
                x=h-(d-u);
                assert(w>=1);
                assert(h>=1);
                assert(y>=1);
                assert(x>=1);
                assert(w<=wid);
                assert(h<=len);
                assert(y<=wid);
                assert(x<=len);
                /* cout<<"read:";      
                cout<<x<<" "<<y<<" "<<h<<" "<<w<<endl;
                cout<<pr[h][w]-pr[h][y-1]-pr[x-1][w]+pr[x-1][y-1]<<endl; */
                return (int)(ans+pr[h][w]-pr[h][y-1]-pr[x-1][w]+pr[x-1][y-1]==k);
            }
            /* cout<<l<<" "<<r<<" "<<u<<" "<<d<<endl; */
            return 0;
        };
        int ans=0;
        for(int i=1;i<=n+u;i++)
        {
            for(int j=1;j<=m+r;j++)
            {
                if(i-u>=1&&i-u<=n&&j-r>=1&&j-r<=m)
                {
                    /* cout<<i<<" "<<j<<endl; */
                    ans+=judge(i,j);
                }
            }
        }

        cout<<ans<<endl;
  /*       pre=0;
        for(auto it:r)
        {
            
        } */
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

input:

3
4 5 3
ULDDRR
4 5 0
UUUUUUU
4 5 10
UUUUUUU

output:

2
20
0

result:

ok 3 number(s): "2 20 0"

Test #2:

score: -100
Runtime Error

input:

1060
19 12 0
UDLDDUUUUDDDLLRDUDUURULUUUDRDUDRDRLRLRLULULLLDLDDRLUUUURUUUDDRLLRUUUDULURUULLRDRLRDDURDUUURRRLURLRUULRRUDURDLUUURDLURDDLUUURDDRLLURRDLRUDLRDRLLRRDRDDLDRURRRLUDULLLRUUDLRRURRDLLRRRDLLRDDDLRLRURURDDDL
11 1 0
UR
3 18 33
UDRLR
17 11 132
RLDRDLDRUU
6 10 13
UULUDDLRDLUUDLDD
1 15 0
D
6 20 50
D...

output:


result: