首页分享

# 题目

SP31972 ADAPOWER - Ada and Power

# 分析

本题主要考察矩阵乘法。

设 AA 为 m×pm \times p 的矩阵，BB 为 p×np \times n 的矩阵，
那么称 m×nm \times n 的矩阵 CC 为矩阵 AA 与 BB 的乘积，记作 C=ABC = AB，
则乘积矩阵中的第 ii 行第 jj 列元素可以表示为：

(AB)ij=Cij=∑k=1paikbkj(AB)_{ij}=C_{ij}=\sum_{k=1}^pa_{ik}b_{kj}

（摘自百度百科）

本题让求一个方阵的平方，由上面的公式可得：
设 AA 为 n×nn \times n 的方阵，C=A2C=A^2，
则平方后的矩阵中的第 ii 行第 jj 列的元素可以表示为：

(A2)ij=Cij=∑k=1naikakj(A^2)_{ij}=C_{ij}=\sum_{k=1}^na_{ik}a_{kj}

了解了这些，我们就可以轻而易举的写出本题的代码了。具体实现的细节请参考代码中的注释。

# 代码

/* 
 * 
 * 题解
 * SP31972 ADAPOWER - Ada and Power
 * https://www.luogu.com.cn/problem/SP31972
 * 
 */
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
const int N = 150;
int n, q;
int numbers[N + 1][N + 1];                                      // 原方阵
int numbersSquare[N + 1][N + 1];                                // 平方后的方阵
bool changed;                                                   // 记录 numbers 是否与 numbersSquare 匹配，用于优化。匹配为 false，不匹配为 true。不懂的话请往下看
int main ( ) {
    //cin，cout 关闭同步，可以加快输入、输出速度
    std::ios::sync_with_stdio ( false );
    cin.tie ( nullptr );
    cout.tie ( nullptr );
    // 输入
    cin >> n >> q;
    for ( int i = 1; i <= n; ++ i ) {
        for ( int j = 1; j <= n; ++ j ) {
            cin >> numbers[ i ][ j ];
        }
    }
    // 现在 numbersSquare 还未计算，所以 numbers 与 numbersSquare 不匹配
    changed = true;
    for ( int query = 1; query <= q; ++ query ) {
        int op;
        cin >> op;
        if ( op == 1 ) {
            int a, b, x, y, v;
            cin >> a >> b >> x >> y >> v;
            // 题目中的方阵下标从 0 开始，我的代码中的方阵下标从 1 开始，所以需要将数据中的下标 + 1
            // （这个东西卡了我几十分钟）
            ++ a;
            ++ b;
            ++ x;
            ++ y;
            for ( int i = a; i <= x; ++ i ) {
                for ( int j = b; j <= y; ++ j ) {
                    numbers[ i ][ j ] += v;                     // 将对应位置的元素 + v
                }
            }
            changed = true;                                     // 由于 numbers 被修改，所以现在 numbers 与 numbersSquare 不匹配
        }
        else if ( op == 2 ) {
            int newNumber;
            bool isSquare = true;                               // 记录据中的新方阵是否等于 numbersSquare
            if ( changed ) {                                    // 如果 numbers 与 numbersSquare 不匹配
                for ( int i = 1; i <= n; ++ i ) {               // 则开始计算 numbersSquare
                    for ( int j = 1; j <= n; ++ j ) {
                        numbersSquare[ i ][ j ] = 0;            // 一定要初始化为 0
                        for ( int k = 1; k <= n; ++ k ) {       // 计算 numbersSquare [i][ j ]，矩阵乘法
                            numbersSquare[ i ][ j ] += numbers[ i ][ k ] * numbers[ k ][ j ];
                        }
                        // 计算的同时开始判断数据中的新方阵是否等于 numbersSquare
                        // 因为只需要判断输入的新方阵中当前元素是否等于 numbersSquare，所以不需要开新数组存储新方阵
                        cin >> newNumber;                       // 输入数据中的新方阵
                        // 首先判断之前有没有找到新方阵中的一个元素不等于 numbersSquare 中对应位置的元素，即 isSquare == false
                        // 因为如果之前已经发现有不等的话就意味着这次询问需要输出 no，不需要继续判断下去
                        // 如果 isSquare == true，则继续判断
                        if ( isSquare && newNumber != numbersSquare[ i ][ j ] ) {
                            isSquare = false;
                            // 不要直接 break，因为数据中输入的是完整方阵，现在没有输入完这个方阵，直接 break 会造成输入混乱
                        }
                    }
                }
                changed = false;                                //numbersSquare 计算完成，numbers 与 numbersSquare 匹配
            }
            else {                                              // 如果 numbers 与 numbersSquare 匹配，直接开始判断即可，不需要再计算一遍
                for ( int i = 1; i <= n; ++ i ) {
                    for ( int j = 1; j <= n; ++ j ) {
                        // 同上
                        cin >> newNumber;
                        // 同上
                        if ( isSquare && newNumber != numbersSquare[ i ][ j ] ) {
                            isSquare = false;
                            // 同上
                        }
                    }
                }
            }
            if ( isSquare ) {                                   // 输出结果
                cout << "yes\n";
            }
            else {
                cout << "no\n";
            }
        }
    }
    cout << endl;
    return 0;
}
/* 
 * 
 * 其实这道题的数据范围不需要 numbersSquare 和 changed 来优化的，直接每询问一次就计算一次，具体做法请参考其他题解
 * 
 */
AC 记录


此文章已被阅读次数:正在加载...更新于