题目来源:小Hi小Ho的惊天大作战:扫雷·一
解题思路:因为只要确定了第一个是否有地雷就可以推算出后面是否有地雷(要么为0,要么为1,如果不是这两个值就说明这个方案行不通),如果两种可能中有一种成功,只需要计算包含有多少个1和多少个0,如果两种可能都成功了,都为1的才是有雷,都为0的才是没有地雷。
具体算法(java版,可以直接AC)
import java.util.Scanner; public class Main { public static boolean flag1 = true;//当第一个为1(有雷)时,依次推算后的结果
public static boolean flag2 = true;//当第一个为0(没雷)时,依次推算后的结果 public static void solve(int[] maze, int[][] mine, int N) {
mine[0][1] = 1;//第一个有雷
mine[1][1] = 0;//第一个没雷 for (int i = 2; i <= N; i++) {
if (flag1) {
mine[0][i] = maze[i - 1] - mine[0][i - 1] - mine[0][i - 2];
//要么有雷,要么没雷
if (mine[0][i] == 1 || mine[0][i] == 0) {
flag1 = true;
} else {
flag1 = false;//推算失败
break;
}
}
} for (int i = 2; i <= N; i++) {
if (flag2) {
mine[1][i] = maze[i - 1] - mine[1][i - 1] - mine[1][i - 2];
if (mine[1][i] == 1 || mine[1][i] == 0) {
flag2 = true;
} else {
flag2 = false;
break;
}
}
}
if (flag1) {//验证最后一个是否正确
if (maze[N] != mine[0][N - 1] + mine[0][N]) {
flag1 = false;
}
}
if (flag2) {
if (maze[N] != mine[1][N - 1] + mine[1][N]) {
flag2 = false;
}
}
} public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int task = scanner.nextInt();
while (task > 0) {
task--;
int N = scanner.nextInt();
int[] maze = new int[N + 1];
int[][] mine = new int[2][N + 1];
for (int i = 1; i <= N; i++) {
maze[i] = scanner.nextInt();
}
flag1 = flag2 = true;
solve(maze, mine, N);
int hasMine = 0, noMine = 0;//统计有雷和没雷的数量
int[] hasMineAns = new int[N];
int[] noMineAns = new int[N];
if (flag1 && flag2) {//两种可能都成功
for (int i = 1; i <= N; i++) {
if (mine[0][i] == 1 && mine[1][i] == 1) {//同时为1(有雷)
hasMineAns[hasMine++] = i;
} else if (mine[0][i] == 0 && mine[1][i] == 0) {//同时为0(没雷)
noMineAns[noMine++] = i;
}
}
} else if (flag1 && !flag2) {//其中一种可能是成功的,另外一种失败
for(int i=1;i<=N;i++){
if(mine[0][i]==1){
hasMineAns[hasMine++] = i;
}else{
noMineAns[noMine++] = i;
}
}
} else if (!flag1 && flag2) {
for(int i=1;i<=N;i++){
if(mine[1][i]==1){
hasMineAns[hasMine++] = i;
}else{
noMineAns[noMine++] = i;
}
}
}
System.out.print(String.format("%d", hasMine));
for(int i=0;i<hasMine;i++){
System.out.print(String.format(" %d", hasMineAns[i]));
}
System.out.print(String.format("\n%d", noMine));
for(int i=0;i<noMine;i++){
System.out.print(String.format(" %d", noMineAns[i]));
}
System.out.println();
}
scanner.close();
}
}