2018年刑侦科推理试题

不难发现一题有四个选项，一共有十题
所以可能的答案一共有$4^{10}$即$2^{20}$约$1e6$
另外一个可能的答案判断需要$10$次
所以复杂度约为$n^k * k$
将$n = 4, k = 10$带入上式约为$1e7$所以暴力有解

另外，当做只有两个选项的题的时候可以用二进制枚举，四个选项其实也可以运用此法
例如：规定0->A 1->B 2->C 3->D
当前枚举的st为 10086
转化为二进制 -> 0000 0010 0111 0110 0110
按照两位划分开来-> 00 00 00 10 01 11 01 10 01 10
即表示当前的选项为 A A A C B D B C B C
然后进入check()

另外这题其实可以dfs暴力剪枝速度更快但是写起来也不容易

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

bool check(LL st){
    int option[10];
    for (int i = 0; i < 10; i ++ )
        option[i] = (((st >> ((i << 1) + 1)) & 1) << 1) + ((st >> (i << 1)) & 1);

    if (option[2] == 0 && !(option[2] != option[5] && option[5] == option[1] && option[1] == option[3]))
        return false;
    else if (option[2] == 1 && !(option[5] != option[2] && option[2] == option[1] && option[1] == option[3])) 
        return false;
    else if (option[2] == 2 && !(option[1] != option[2] && option[2] == option[3] && option[3] == option[5]))
        return false;
    else if (option[2] == 3 && !(option[2] != option[3] && option[2] == option[5] && option[5] == option[1]))
        return false;

    if (option[3] == 0 && !(option[0] == option[4]))
        return false;
    else if (option[3] == 1 && !(option[1] == option[6]))
        return false;
    else if (option[3] == 2 && !(option[0] == option[8]))
        return false;
    else if (option[3] == 3 && !(option[5] == option[9]))
        return false;

    if (option[4] == 0 && !(option[4] == option[7]))
        return false;
    else if (option[4] == 1 && !(option[4] == option[3]))
        return false;
    else if (option[4] == 2 && !(option[4] == option[8]))
        return false;
    else if (option[4] == 3 && !(option[4] == option[6]))
        return false;

    if (option[5] == 0 && !(option[1] == option[7] && option[1] == option[3]))
        return false;
    else if (option[5] == 1 && !(option[0] == option[5] && option[0] == option[7]))
        return false;
    else if (option[5] == 2 && !(option[2] == option[9] && option[2] == option[7]))
        return false;
    else if (option[5] == 3 && !(option[4] == option[7] && option[7] == option[8]))
        return false;

    int cnt[4];
    memset(cnt, 0, sizeof cnt);
    for (int i = 0; i < 10; i ++ )
        cnt[option[i]] ++;

    if (option[6] == 0 && !(cnt[2] < cnt[0] && cnt[2] < cnt[1] && cnt[2] < cnt[3]))
        return false;
    else if (option[6] == 1 && !(cnt[1] < cnt[0] && cnt[1] < cnt[2] && cnt[1] < cnt[3]))
        return false;
    else if (option[6] == 2 && !(cnt[0] < cnt[1] && cnt[0] < cnt[2] && cnt[0] < cnt[3]))
        return false;
    else if (option[6] == 3 && !(cnt[3] < cnt[0] && cnt[3] < cnt[1] && cnt[3] < cnt[2]))
        return false;

    if (option[7] == 0 && !(option[6] + 1 != option[0] && option[6] - 1 != option[0]))
        return false;
    else if (option[7] == 1 && !(option[4] + 1 != option[0] && option[4] - 1 != option[0]))
        return false;
    else if (option[7] == 2 && !(option[1] + 1 != option[0] && option[1] - 1 != option[0]))
        return false;
    else if (option[7] == 3 && !(option[9] + 1 != option[0] && option[9] - 1 != option[0]))
        return false;

    int res = 0;
    res += option[0] == option[5];
    if (option[8] == 0)
        res += option[5] == option[4];
    else if (option[8] == 1)
        res += option[9] == option[4];
    else if (option[8] == 2)
        res += option[1] == option[4];
    else
        res += option[8] == option[4];
    if (res % 2 == 0)
        return false;

    int maxv = *max_element(cnt, cnt + 4);
    int minv = *min_element(cnt, cnt + 4);
    int v = maxv - minv;

    if (option[9] == 0 && v == 3)
        return true;
    else if (option[9] == 1 && v == 2)
        return true;
    else if (option[9] == 2 && v == 4)
        return true;
    else if (option[9] == 3 && v == 1)
        return true;
    return false;
}

int main()
{
    LL st;
    for (st = 0; st <= 1 << 20 ; st ++)
        if (check(st))
            break;
    int option[10];
    for (int i = 0; i < 10; i ++ )
        option[i] = (((st >> ((i << 1) + 1)) & 1) << 1) + ((st >> (i << 1)) & 1);
    for (auto x: option)
        cout << (char)(x + 'A') << ' ';
    puts("");
    return 0;
}