QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#250571 | #5414. Stop, Yesterday Please No More | cscnk52 | TL | 3ms | 18184kb | C++14 | 2.3kb | 2023-11-13 13:19:56 | 2023-11-13 13:19:57 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e3 + 7;
int sum[N<<1][N<<1];
const int M=1e3+5;
signed main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
string s;
cin >> s;
int slen = s.length();
int max_L=0 , max_R=0 , max_U=0 , max_D=0 , x=0 , y=0;
for(int i=0;i<slen;i++)
{
if(s[i]=='L') y--;
if(s[i]=='R') y++;
if(s[i]=='U') x--;
if(s[i]=='D') x++;
max_L=max(min(max_L , y) , -m);
max_R=min(max(max_R , y) , m);
max_U=max(min(max_U , x) , -n);
max_D=min(max(max_D , x) , n);
}
// cout<<max_L<<" "<<max_R<<" "<<max_U<<" "<<max_D<<endl;
int now_Ux=abs(max_U);
int now_Dx=n-1-max_D;
int now_Ly=abs(max_L);
int now_Ry=m-1-max_R;
// cout<<"now_Ux="<<now_Ux<<" now_Dx="<<now_Dx<<" now_Lx="<<now_Ly<<" now_Rx="<<now_Ry<<endl;
int now_num=(now_Ry-now_Ly+1)*(now_Dx-now_Ux+1);
int holl_x=M , holl_y=M;
now_Ly+=M;
now_Ry+=M;
now_Dx+=M;
now_Ux+=M;
sum[holl_x][holl_y]=1;
for(int i=0;i<(int)s.size();i++)
{
if(s[i]=='L') holl_y++;
if(s[i]=='R') holl_y--;
if(s[i]=='U') holl_x++;
if(s[i]=='D') holl_x--;
sum[holl_x][holl_y]=1;
}
// for(int i=M-10;i<(M+n);i++)
// {
// for(int j=M-10;j<(M+m);j++)
// cout<<sum[i][j]<<" ";
// cout<<endl;
// }
// cout<<endl;
for(int i=1;i<=(M+n);i++)
for(int j=1;j<=(M+m);j++)
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
int ans=0;
// for(int i=M;i<(M+n);i++)
// {
// for(int j=M;j<(M+m);j++)
// cout<<sum[i][j]<<" ";
// cout<<endl;
// }
// cout<<endl;
//
// for(int i=M-10;i<(M+n);i++)
// {
// for(int j=M-10;j<(M+m);j++)
// cout<<sum[i][j]<<" ";
// cout<<endl;
// }
//
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int real_dx=now_Dx-i;
int real_ux=now_Ux-i;
int real_ly=now_Ly-j;
int real_ry=now_Ry-j;
int cnt_x=sum[real_dx][real_ry]-sum[real_ux-1][real_ry]-sum[real_dx][real_ly-1]+sum[real_ux-1][real_ly-1];
if(now_num-cnt_x==k) ans++;
}
}
cout<<ans<<endl;
for(int i=1;i<=M+n;i++)
{
for(int j=1;j<=M+m;j++)
{
sum[i][j]=0;
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 18184kb
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
Time Limit Exceeded
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:
21 11 20 99 18 15 34 0 15 0 0 13 14 18 14 16 1 19 108 8 2 2 3 7 0 30 16 21 0 8 10 9 15 5 13 11 7 3 0 0 12 0 11 0 0 14 0 22 36 51 23 7 6 4 2 0 28 8 63 22 49 13 10 4 108 10 18 44 0 14 9 0 4 0 14 99 105 10 14 17 0 0 10 11 28 52 34 56 33 14 56 0 14 0 121 3 48 30 25 13 0 30 6 8 3 11 16 45 20 34 0 38 0 21...