QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#577139 | #5414. Stop, Yesterday Please No More | PonyHex | AC ✓ | 42ms | 53348kb | C++20 | 4.3kb | 2024-09-20 08:25:27 | 2024-09-20 08:25:28 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int N = 2020;
int n, m, k;
string s;
int xl, xr, yl, yr;
vector<pair<int, int> > nums;
int mp[N][N] = { 0 };
void solve() {
cin >> n >> m >> k;
cin >> s;
int px = 0, py = 0;
int disux = 0, disdx = 0, disly = 0, disry = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == 'U') {
px--;
}
else if (s[i] == 'D') {
px++;
}
else if (s[i] == 'L') {
py--;
}
else if (s[i] == 'R') {
py++;
}
//判定位置,然后更新dis,然后判定k=n*m,k=0的情况
disux = min(disux, px); disdx = max(disdx, px);
disly = min(disly, py); disry = max(disry, py);
/*
if (disux <= -n || disdx >= n || disly <= -m || disry >= m) {
if (k == 0) {
cout << n * m << endl; return;
}
else if (k == n * m) {
cout << 0 << endl; return;
}
}*/
if (disdx - disux >= n || disry - disly>=m) {
if (k == 0) {
cout << n * m << endl; return;
}
else if (k == n * m) {
cout << 0 << endl; return;
}
}
}
xl = 1 - disux; yl = 1 - disly;
xr = n - disdx; yr = m - disry;//进行的最大位移
//cout << xl << " " << yl << " " << xr << " " << yr << endl;
int sum = (yr - yl + 1) * (xr - xl + 1);
int x = 0, y = 0;
nums.push_back({ x,y });
for (int i = 0; i < s.length(); i++) {
if (s[i] == 'U') {
x++;
nums.push_back({ x,y });
}
else if (s[i] == 'D') {
x--;
nums.push_back({ x,y });
}
else if (s[i] == 'L') {
y++;
nums.push_back({ x,y });
}
else if (s[i] == 'R') {
y--;
nums.push_back({ x,y });
}
}
int mix = 1e18, miy = 1e18;
for (auto p = nums.begin(); p != nums.end(); p++) {
mix = min(mix, p->first);
miy = min(miy, p->second);
}
mix -= 5; miy -= 5;//使起点移动到5,5的位置
mix = -mix, miy = -miy;
for (auto p = nums.begin(); p != nums.end(); p++) {
mp[p->first + mix][p->second + miy] = 1;
}
for (int i = 1; i <= 2 * n + 10; i++) {
for (int j = 1; j <= 2 * m + 10; j++) {
mp[i][j] = mp[i][j] + mp[i - 1][j] + mp[i][j - 1] - mp[i - 1][j - 1];
//cout<<mp[i][j]<<' ';
}//cout<<endl;
}
//cout<<sum<<endl;
int ans = 0;
//枚举起点,1,1一直到n,m;
//cout << xl << " " << yl << " " << xr << " " << yr << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
//枚举在原矩阵中起点的位置,获取位置关系
///右下,约束为最大n+mix,m+miy
//左上,如果越界,约束为1,1
int dx = (xl - i), dy = (yl - j);
int x = mix + dx, y = miy + dy;
int xx = mix + dx + (xr - xl), yy = miy + dy + (yr - yl);
//cout << x << " " << y << " " << xx << " " << yy << endl;
if (xx <= 0 || yy <= 0) {
if (0 == sum - k)ans++;
continue;
}
x = max(1ll, x), y = max(1ll, y);
if ((mp[xx][yy] + mp[x - 1][y - 1] - mp[x - 1][yy] - mp[xx][y - 1]) == sum - k)ans++;
// int xx = i, yy = j;
// int x = i - (xr - xl), y = j - (yr - yl);
// x = max(1ll, x); y = max(1ll, y);
//if ((mp[xx][yy] + mp[x - 1][y - 1] - mp[x - 1][yy] - mp[xx][y - 1]) == sum - k)ans++;
//放左上角
}
}
cout << ans << endl;
for (int i = 0; i <= 2 * n + 10; i++) {
for (int j = 0; j <= 2 * m + 10; j++) {
mp[i][j] = 0;
}
}
nums.clear();
return;
}
signed main() {
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T_case = 1;
cin >> T_case;
while (T_case--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3628kb
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: 0
Accepted
time: 8ms
memory: 4884kb
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 20 99 18 15 34 240 15 0 0 13 14 18 26 16 1 19 108 8 2 2 3 7 0 30 16 21 0 8 10 9 15 5 320 11 7 3 0 0 12 0 11 0 0 14 0 22 36 51 23 7 6 4 2 48 28 8 63 22 49 13 10 4 108 10 18 44 0 15 9 0 4 30 14 99 105 10 14 17 0 66 10 11 28 52 34 56 33 14 56 90 14 0 121 3 48 30 36 13 0 30 7 8 3 11 16 45 20 34 0...
result:
ok 1060 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 35296kb
input:
1 1000 1000 979065 DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU
output:
958416
result:
ok 1 number(s): "958416"
Test #4:
score: 0
Accepted
time: 4ms
memory: 35404kb
input:
1 1000 1000 943471 LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...
output:
889224
result:
ok 1 number(s): "889224"
Test #5:
score: 0
Accepted
time: 36ms
memory: 53348kb
input:
1 1000 1000 315808 LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...
output:
426
result:
ok 1 number(s): "426"
Test #6:
score: 0
Accepted
time: 12ms
memory: 35280kb
input:
1 1000 1000 986018 LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD
output:
972180
result:
ok 1 number(s): "972180"
Test #7:
score: 0
Accepted
time: 8ms
memory: 35396kb
input:
1 1000 1000 945431 DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...
output:
893000
result:
ok 1 number(s): "893000"
Test #8:
score: 0
Accepted
time: 42ms
memory: 53032kb
input:
1 1000 1000 460035 RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...
output:
417
result:
ok 1 number(s): "417"
Test #9:
score: 0
Accepted
time: 16ms
memory: 35432kb
input:
1 1000 1000 992010 LLLLLDLDRRLUDRR
output:
1999
result:
ok 1 number(s): "1999"
Test #10:
score: 0
Accepted
time: 12ms
memory: 35300kb
input:
1 1000 1000 919600 LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...
output:
944
result:
ok 1 number(s): "944"
Test #11:
score: 0
Accepted
time: 36ms
memory: 53216kb
input:
1 1000 1000 804351 DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...
output:
640000
result:
ok 1 number(s): "640000"