QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#251892#5414. Stop, Yesterday Please No MoreTimMCBenWA 6ms3836kbC++204.1kb2023-11-15 12:07:382023-11-15 12:07:38

Judging History

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

  • [2023-11-15 12:07:38]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3836kb
  • [2023-11-15 12:07:38]
  • 提交

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';
            else if(it=='D') it='U';
        }
        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')
            {
                //上边界往下move距离
                pre++;
            }else
            {
                //下边界往上move距离
                pre--;
            }
            u=max(u,pre);
            d=max(d,-pre);
        }
        int U = 1 + u ;
        int D = n - d ;

        pre=0;
        int l=0,r=0;
        for(auto it:b)
        {
            if(it=='R')
            {
                //左边界往右move距离
                pre++;
            }else
            {
                //右边界往左move距离
                pre--;
            }
            l=max(l,pre);
            r=max(r,-pre);
        }
        int L = 1 + l;
        int R = m - r;

        if(L>R||U>D)
        {
            if(k==0)
            {
                cout<<n*m<<endl;
            }else
            {
                cout<<0<<endl;
            }
            continue;
        }

        int len = u + d + 1;
        int wid = l + r + 1;

        vector<vector<int>>v(len+1,vector<int>(wid+1));

        int x = len - d, y = wid - r;
        
        v[x][y]=1;
        /* cout<< x<<" "<< y<<endl; */
        for(auto it:s)
        {
            if(it=='U') x++;
            else if(it=='D') x--;
            else if(it=='L') y++;
            else if(it=='R') y--;
            v[x][y] = 1;
        }
/*         for(int i=1;i<=len;i++)
        {
            for(int j=1;j<=wid;j++)
            {
                cout<<v[i][j]<<" ";
            }
            cout<<endl;
        } */

        vector<vector<int>>pr=v;
        for(int i=1;i<=len;i++)
        {
            for(int j=1;j<=wid;j++)
            {
                pr[i][j]=pr[i][j]+pr[i-1][j]+pr[i][j-1]-pr[i-1][j-1];
            }
        }

/*         for(int i=1;i<=len;i++)
        {
            for(int j=1;j<=wid;j++)
            {
                cout<<pr[i][j];
            }
            cout<<endl;
        }  */       
        int ans = (R - L +1)*(D - U +1);
        /* cout<<ans<<endl; */
        int res = 0;
        //枚举原矩形的右下角的位置
        for(int i=1;i<=n + d;i++)
        {
            for(int j=1;j<=m + r;j++)
            {
                int x_d = min(D , i);
                int x_u = max(U , i - len +1);

                int x_r = min(R , j);
                int x_l = max(L , j - wid +1);

/*                 if(i-d==4&&j-r==2)
                {
                    cout<<"gg"<<endl;
                    cout<<x_u<<" "<<x_d<<endl;
                    cout<<x_l<<" "<<x_r<<endl;
                } */


                if(x_u > x_d) continue;
                if(x_l > x_r) continue;

                int x = len - (i-x_d);
                int y = wid - (j-x_r);

                int w = len - (i-x_u);
                int z = wid - (j-x_l); 

                if(i-d>=1&&i-d<=n&&j-r>=1&&j-r<=m)
                {
                    if(ans-(pr[x][y]-pr[x][z-1]-pr[w-1][y]+pr[w-1][z-1])==k)
                    {
                        res++;
                     }
                   /* cout<< x<<" "<<y<<" "<<w<<" "<<z<<endl;
                   cout<<pr[x][y]-pr[x][z-1]-pr[w-1][y]+pr[w-1][z-1]<<endl; */
                }             
                  
            }

        }
        cout<<res<<endl;
    }
}
/*
3
4 5 3
ULDDRR
4 5 0
UUUUUUU
4 5 10
UUUUUU
*/

详细

Test #1:

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

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
Wrong Answer
time: 6ms
memory: 3836kb

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:

228
11
1
99
5
15
16
240
6
0
0
1
11
18
13
0
0
16
108
4
1
1
3
4
0
1
3
4
0
7
10
9
4
5
320
8
5
3
0
0
3
0
11
0
0
6
0
22
36
51
12
5
6
1
2
48
28
8
63
11
49
13
4
2
108
7
9
44
0
1
8
0
4
30
12
99
105
5
1
17
0
66
8
11
28
52
15
56
11
5
56
90
14
0
121
3
48
1
16
10
0
30
1
3
3
7
16
45
9
32
0
19
0
4
0
3
0
20
12
48
...

result:

wrong answer 3rd numbers differ - expected: '20', found: '1'