该题(简单版) CF 数据不够强,放过了我的错解。
我的代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL N = 310, M = 10;
LL T;
LL l, n, m;
LL a[N];
LL b[N][N];
LL sum[N][N][M];
int main() {
scanf("%lld", &T);
while(T--) {
scanf("%lld%lld%lld", &l, &n, &m);
for(LL i = 1;i <= l;i++) {
scanf("%lld", &a[i]);
}
for(LL i = 1;i <= n;i++) {
for(LL j = 1;j <= m;j++) {
scanf("%lld", &b[i][j]);
for(LL k = 1;k <= 7;k++) {
sum[i][j][k] = sum[i - 1][j][k] + sum[i][j - 1][k] - sum[i - 1][j - 1][k] + (b[i][j] == k);
}
}
}
LL li = 0, lj = 0, f = 0;
for(LL i = 1;i <= l - 1;i++) {
LL ri = 0, rj = 0, p = 1e13;
for(LL j = li + 1;j <= n;j++) {
for(LL k = lj + 1;k <= m;k++) {
if(b[j][k] == a[i]) {
if(sum[n][m][a[i + 1]] - sum[j][m][a[i + 1]] - sum[n][k][a[i + 1]] + sum[j][k][a[i + 1]] < p) { // 改为 <= 就能过 Hack 但不能过 CF
p = sum[n][m][a[i + 1]] - sum[j][m][a[i + 1]] - sum[n][k][a[i + 1]] + sum[j][k][a[i + 1]];
ri = j, rj = k;
}
}
}
}
if(p == 0) {
puts((i & 1) ? "T" : "N");
f = 1;
break;
}
if(p == 1e13) {
puts((i & 1) == 0 ? "T" : "N");
f = 1;
break;
}
li = ri, lj = rj;
}
if(!f) {
bool u = 0;
for(LL i = li + 1;i <= n;i++) {
for(LL j = lj + 1;j <= m;j++) {
if(b[i][j] == a[l]) {
u = 1;
break;
}
}
}
if(u) u = (l & 1);
else u = (l & 1) == 0;
puts(u ? "T" : "N");
}
}
return 0;
}
主要的思路就是在选 ai 的时候选在 b 数组中右下 ai+1 个数最少的那个 bi,j,当有个数相等时就选靠左上的,如果改成相等时选靠右下的就能过 Hack 但 CF 数据过不了。
Hack:
Input:
1
3 4 4
2 1 6
7 2 7 7
2 7 1 7
7 1 7 7
7 7 6 7
Output:
N
Answer:
T
题解区的两篇带代码的都是对的。
证明我的这种思路是错的,在写困难版的时候就别这么做了。