Contents

Hint
对于第一组数据，1 到 3 跳过了路径上的点 2，所以不合法。

对于第二组数据，1 到 3 时点 2 已经被经过了，所以合法。

对于第三组数据,8→1→6→7 路径均没有中间点，所以合法。

• 直接模拟

#include <cstdio>
#include <cstring>
bool mp[10][10] = {false}, mk[10];
int a[9];
int main(int argc, char* argv[]){

    int t, k;//下面这个预处理代表这几个键之间有键值，例如mp[1][3],要想13合法，就必须键值访问过mk[(a[i - 1] + a[i]) >> 1] == 1
    mp[1][3] = mp[3][1] = mp[1][7] = mp[7][1] = mp[1][9] = mp[9][1] = mp[2][8] = mp[8][2] =
    mp[3][7] = mp[7][3] = mp[3][9] = mp[9][3] = mp[4][6] = mp[6][4] = mp[7][9] = mp[9][7] = true;
    scanf("%d", &t);
    while (t--)
    {
        memset(mk, false, sizeof(mk));
        scanf("%d%d", &k, a);       //吃回车，用到了a数组的第一个元素
        if (k < 4 || a[0] < 1 || a[0] > 9)
            mk[0] = true;
        else
            mk[a[0]] = true;
        for (int i = 1; i < k; ++i)
        {
            scanf("%d", a + i);//第一个数是合法的且在[1,9]中且没访问过,且(a[i-1]和a[i]之间没有键值或有键值且访问过)
            if (!mk[0] && a[i] > 0 && a[i] <= 9 && !mk[a[i]] && (!mp[a[i - 1]][a[i]] || mk[(a[i - 1] + a[i]) >> 1]))
                mk[a[i]] = true;
            else
                mk[0] = true;
        }
        puts(mk[0] ? "invalid" : "valid");
    }
    return 0;
}