QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#573850 | #5414. Stop, Yesterday Please No More | PonyHex | WA | 0ms | 3684kb | C++20 | 3.4kb | 2024-09-18 20:07:24 | 2024-09-18 20:07:25 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int N = 2005;
int n, m, k;
string s;
int xl, xr, yl, yr;
vector<pair<int, int> > nums;
int mp[N][N];
void solve() {
cin >> n >> m >> k;
for (int i = 0; i <= 2 * n; i++) {
for (int j = 0; j <= 2 * m; j++) {
mp[i][j] = 0;
}
}
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);
}
xl = 1 - disux; yl = 1 - disly;
xr = n - disdx; yr = m - disry;
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--; miy--;
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; i++) {
for (int j = 1; j <= 2 * m; 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;
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);
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;
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: 0
Wrong Answer
time: 0ms
memory: 3684kb
input:
3 4 5 3 ULDDRR 4 5 0 UUUUUUU 4 5 10 UUUUUUU
output:
2 0 0
result:
wrong answer 2nd numbers differ - expected: '20', found: '0'