题目分析（环形测试问题）

题意简述

• $n$ 个人围成一圈，编号 $1$ 到 $n$，每个人要么是诚实者，要么是说谎者。
• 说谎者数量不超过 $t$。
• 每个人 $i$ 测试 $i+1$（$n$ 测试 $1$），结果为 $a_{i,j}$（$0$ 或 $1$）。
• 诚实者的测试结果可信，说谎者的测试结果不可信。
• 要求找出必定是说谎者的人。

输入

• 多组测试用例，每组包含：
  • $n$（人数）和 $t$（最多说谎者数量）。
  • $n$ 个测试结果 $a_{1,2}, a_{2,3}, \dots, a_{n,1}$。

输出

每组测试用例输出两个整数：

1. 必定说谎者的人数；
2. 这些说谎者中的最小编号（如果没有，输出 $0\ 0$）。

解题思路

问题建模

• 将每个人看作图中的节点，测试结果作为边。
• 诚实者的测试结果可信，说谎者的测试结果不可信（可能是 $0$ 或 $1$）。

关键观察

• 如果某个人 $i$ 是诚实者，那么他的测试结果 $a_{i,j}$ 必须准确反映 $j$ 的身份。
• 如果 $i$ 是说谎者，则 $a_{i,j}$ 可能是任意值。

算法选择

1. 枚举法
   • 尝试假设每个人是诚实者，检查是否满足说谎者数量不超过 $t$。
2. 优化
   • 使用逻辑推导排除不可能的情况。
   • 提前终止不可能的搜索路径。

代码实现

#include <iostream>
#include <stdio.h>
using namespace std;

int N, T;
int said[1005];
int mnLiar[2][1005][1005];

int mn(int a, int b){
	return (a>b) ? b : a;
}

void init(){
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < N; j++){
			for(int k = 0; k < N; k++){
				mnLiar[i][j][k] = -1;
			}
		}
	}
}

int get(int tag, int start, int end){
	if(mnLiar[tag][start][end] != -1) return mnLiar[tag][start][end];
	if(start == end){
		if(tag){
			mnLiar[tag][start][end] = 1;
			return 1;
		}
		else {
			mnLiar[tag][start][end] = 0;
			return 0;
		}
	}
	if(tag){
		int res = mn(get(0, (start+1)%N, end), get(1, (start+1)%N, end)) + 1;
		mnLiar[tag][start][end] = res;
		return res;
	}
	else if(said[start]){
		int res = get(1, (start+1)%N, end);
		mnLiar[tag][start][end] = res;
		return res;
	}
	else{
		int res = get(0, (start+1)%N, end);
		mnLiar[tag][start][end] = res;
		return res;
	}
}

int main() {
	int t;
	scanf("%d", &t);
	for(int i = 0; i < t; i++){
		scanf("%d%d", &N, &T);
		for(int j = 0; j < N; j++){
			scanf("%d", &said[j]);
		}
		if(T == 0){
			printf("0 0\n");
			continue;
		}
		init();
		int liarNum = 0;
		int mnLiar = -1;
		int offset, start, end;
		for(int j = 0; j < N; j++){
			int det[1005] = {0};
			bool kysz = 1;
			int jdgs = 0;
			int fwgs = 1;
			det[j] = 1;
			offset = j;
			while(1){
				if(said[offset]){
					offset = (offset+1)%N;
					if(det[offset] == 1){
						kysz = 0;
						goto done;
					}
					else if(det[offset] == 0){
						det[offset] = -1;
						jdgs++;
						fwgs++;
						if(jdgs > T) {
							kysz = 0;
							goto done;
						}
					}
					break;
				}
				else{
					offset = (offset+1)%N;
					if(det[offset] == -1){
						kysz = 0;
						goto done;
					}
					else if(det[offset] == 0){
						det[offset] = 1;
						fwgs++;
					}
				}
			}
			start = (offset+1)%N;
			offset = (j+N-1)%N;
			if(said[offset]){
				if(det[offset] == 1){
					kysz = 0;
					goto done;
				}
				else if(det[offset] == 0){
					det[offset] = -1;
					jdgs++;
					fwgs++;
					if(jdgs > T){
						kysz = 0;
						goto done;
					}
				}
				offset = (offset+N-1)%N;
				while(!said[offset]){
					if(det[offset] == 1){
						kysz = 0;
						goto done;
					}
					else if(det[offset] == 0){
						det[offset] = -1;
						jdgs++;
						fwgs++;
						if(jdgs > T){
							kysz = 0;
							goto done;
						}
					}
					offset = (offset+N-1)%N;
				}
				end = offset;
			}
			else{
				end = offset;
			}
			if(fwgs >= N) goto done;
			if(jdgs + mn(get(0, start, end), get(1, start, end)) > T) kysz = 0;
			done:
			if(!kysz){
				liarNum++;
				if(mnLiar == -1) mnLiar = j;
			}
			if(liarNum == T) break;
		}
		printf("%d %d\n", liarNum, mnLiar+1);
	}
	return 0;
}

代码说明

1. 输入处理
   • 读取测试用例数量 $T$，每组测试用例的 $n$, $t$ 和测试结果数组 $a$。
2. 逻辑判断
   • 对每个人 $k$，假设他是说谎者，推断其他人的身份。
   • 如果推断结果导致说谎者数量超过 $t$，则 $k$ 必定是说谎者。
3. 输出结果
   • 统计必定说谎者的人数和最小编号。
   • 如果没有必定说谎者，输出 $0$ $0$。

复杂度分析

• 时间复杂度：$O(T \times n^2)$，其中 $T$ 是测试用例数量，$n$ 是人数。
• 空间复杂度：$O(n)$，用于存储测试结果和状态。