首页 > 代码库 > 【NOIP模拟】matrix(简化矩阵)

【NOIP模拟】matrix(简化矩阵)

题目背景

SOURCE:NOIP2016-RZZ-1

题目描述

给出两个 N×N 的矩阵 A、B,矩阵每行每列标号 0~N-1 。
定义这两个矩阵的乘积 AB 为

    技术分享

现在要在这两个矩阵上依次进行 Q 次修改操作,两种操作描述如下:

    • A i j K ,将 Ai,j 的值修改为 K 。
    • B i j K ,将 Bi,j 的值修改为 K 。

在每一次修改操作进行后,输出矩阵 AB(这两个矩阵的乘积矩阵)中每个位置元素的权值之和。

输入格式

第一行,一个正整数 N ,表示矩阵的大小。
接下来 N 行,每行 N 个整数,描述矩阵 A 。
接下来 N 行,每行 N 个整数,描述矩阵 B 。
接下来一行,一个正整数 Q ,表示操作次数。
接下来 Q 行,每行描述一个操作,格式如题面所示。

输出格式

输出 Q 行,每行一个整数,表示这次操作完成后的答案。

样例数据 1

输入


1 2 
3 4 
4 3 
2 1 

A 1 1 2 
B 0 1 3 
A 0 0 10

输出

40 
40 
103

备注

【数据规模与约定】

对于 10% 的数据,N = 1。对于 30% 的数据,N,Q≤10。对于 80% 的数据,1≤N≤100,|Ai,j|,|Bi,j|≤10。
对于 100% 的数据,1≤N≤1000,1≤Q≤105,|Aij|,|Bi,j|≤1000。

【题目分析】

 矩阵乘法的答案矩阵中的$(i, j)$为:矩阵$1$的第$i$行中的每个数$(i, k)$,乘上矩阵$2$中第j列的每一个数$(k, j)$

 所以要求每次操作的答案,只需要记录一个$sum1[i]$表示矩阵$1$中第$i$列的和,和$sum2[i]$表示矩阵$2$中第$i$行的和,和$sum$表示答案矩阵的和。

修改矩阵$1$中的$(i, j)$时,$sum$只需加上$delta × sum2[i]$

修改矩阵$2$中的$(i, j)$时, $sum$只需加上$delta × sum1[j]$即可。

【CODE】

技术分享
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<algorithm>#include<vector>using namespace std;typedef long long ll;const int N = 1005;ll all, sum1[N], sum2[N];int a[N][N], b[N][N];int n, Q;inline int Re(){    int i = 0, f = 1; char ch = getchar();    for(; (ch < 0 || ch > 9) && ch != -; ch = getchar());    if(ch == -) f = -1, ch = getchar();    for(; ch >= 0 && ch <= 9; ch = getchar())        i = (i << 3) + (i << 1) + (ch - 0);    return i * f;}inline void Wr(ll x){    if(x < 0) putchar(-), x = -x;    if(x > 9) Wr(x / 10);    putchar(x % 10 + 0);}int main(){//    freopen("matrix.in", "r", stdin);//    freopen("matrix.out", "w", stdout);    n = Re();        for(int i = 1; i <= n; i++)        for(int j = 1; j <= n; j++)            a[i][j] = Re(),            sum1[j] += (ll)a[i][j];    for(int i = 1; i <= n; i++)        for(int j = 1; j <= n; j++)            b[i][j] = Re(),            sum2[i] += (ll)b[i][j],            all += 1LL * sum1[i] * b[i][j];//    for(int i = 1; i <= n; i++) cout<<sum1[i]<<" "<<sum2[i]<<endl;return 0;    Q = Re();    while(Q--){        char opt;        scanf("%c", &opt);        if(opt == A){            int i = Re() + 1, j = Re() + 1, tmp = Re();            sum1[j] += (tmp - (a[i][j]));            all += 1LL * (tmp - (a[i][j])) * sum2[j];            a[i][j] = tmp;        }        else if(opt == B){            int i = Re() + 1, j = Re() + 1, tmp = Re();            sum2[i] += (tmp - (b[i][j]));            all += 1LL * (tmp - (b[i][j])) * sum1[i];            b[i][j] = tmp;        }        Wr(all), putchar(\n);    }    return 0;}
View Code

 

【NOIP模拟】matrix(简化矩阵)