列表

详情

NC25727. Matrix

描述

    Matrices are square tables, containing integers in rows and columns. Do you know how to multiply matrices? The product of matrices A and B of size is a matrix C = AB, such that
    
    Here the brackets contain numbers of row and column, where the corresponding element of matrix is located.
    One day, God Chai has been addicted to studying till midnight, after which he feels extremely hungry. Thus he turns to Coach Fang for some chocolates. But Coach Fang is a pretty cunning person, so that God Chai must figure out his question before getting chocolates.
    The question is that, give 8 types of matrices, an incomplete matrix sequence A and a target matrix m. Initially, the matrix sequence A consists of n elements ranging from 0 to 8, in which 0 means void. For every 0 in A, God Chai need replace it with number 14. There is no need to replace all 0 with the same number. But eventually, the product of n matrices in A should equal to the target matrix m.
8 types of matrices are as following:
    1: 2:3: 4:
    5:  6: 7:8:
    Now please judge if it is possible to solve the question.



输入描述

    The first line contains an integer number T, the number of test cases.
    For each test case :
    The first line contains an integer n(), the number of matrix sequence A.
    The second line contains n integers (), the serial number of matrices in A.
    The third line contains an integer m(), the serial number of target matrix.

输出描述

For each test case print“YES”(without quotes) if it is possible, and“NO”(without quotes) otherwise.

示例1

输入: 

2
4
0 2 7 3
5
4
2 3 7 0
5

输出: 

YES
NO

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 179ms, 内存消耗: 868K, 提交时间: 2019-06-29 13:19:09 

#include <iostream>
using namespace std;
const int maxn = 100005;
int tab[9][9] = {
    {0,0,0,0,0,0,0,0,0}
    ,{0,1,2,3,4,5,6,7,8}
    ,{0,2,5,4,6,7,8,1,3}
    ,{0,3,8,5,2,6,1,4,7}
    ,{0,4,3,7,5,8,2,6,1}
    ,{0,5,7,6,8,1,3,2,4}
    ,{0,6,4,1,7,3,5,8,2}
    ,{0,7,1,8,3,2,4,5,6}
    ,{0,8,6,2,1,4,7,3,5}
};
int rev[] = {0,1,7,6,8,5,3,2,4};
int a[maxn];
int calc(int l, int r){
    int ret = 1;
    for(int i = l; i <= r; i++){
        ret = tab[ret][a[i]];
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n;
        int cnt = 0, pos = -1;
        for(int i = 0; i < n; i++){
            cin >> a[i];
            if(a[i] == 0){
                cnt++;
                pos = i;
            }
        }
        cin >> m;
        bool ok = false;
        if(cnt == 0)
            ok = (calc(0, n-1) == m);
        else if(cnt == 1)
            ok = (tab[tab[rev[calc(0, pos - 1)]][m]][rev[calc(pos + 1, n - 1)]] <= 4);
        else
            ok = true;
        cout << (ok ? "YES\n" : "NO\n");
    }
}

上一题

© 2024 nowcoder.com