该题 CF 数据不够强
查看原帖
该题 CF 数据不够强
908514
DHT666楼主2024/12/18 17:08

该题(简单版) 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;
}

主要的思路就是在选 aia_i 的时候选在 bb 数组中右下 ai+1a_{i+1} 个数最少的那个 bi,jb_{i,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

题解区的两篇带代码的都是对的。

证明我的这种思路是错的,在写困难版的时候就别这么做了。

2024/12/18 17:08
加载中...