第5章数组和稀疏矩阵
5．1实战题解析
【实战5．1】POJ2189——最多围栏个数
时间限制： 1000ms； 内存限制： 65536KB。


视频讲解


问题描述： 一个条形牧场用p(1≤p≤1000)根柱子(编号分别为1~p)分隔成等间距的围栏，每头牛只能在围栏中放牧，现有n(1≤n≤1000)头牛在放牧。请求出数量不超过c(0≤c≤1000)头牛的最大连续区域的围栏个数。
输入格式： 第1行是3个整数n、p和c。第2行到第n+1行，每行包含一个整数x，取值范围为1~p-1，指定一头牛在柱子x和柱子x+1的围栏中放牧。注意一个围栏中允许放牧多头牛。
输出格式： 在第1行中输出一个整数，表示最多有c头牛的最大连续区域的围栏个数。
输入样例： 

2 6 1

2

3

输出样例： 

3

解： 假设柱子x和柱子x+1的围栏的编号为x，设置一维数组num［1．．p-1］，num［i］记录围栏i中放牧的牛数量，题目样例的场景如图5．1所示，围栏的编号为1~5，两头牛分别在围栏2和围栏3中放牧，求出一头牛的最大连续区域的围栏个数为3。
本题就是枚举所有的连续区域，即num［i．．j］(i≤j)，其中包含的围栏个数为j-i+1，求出放牧的牛数量(num［i］+…+num［j］)，在所有小于或等于c的牛数量中求最大的围栏个数，对应的时间复杂度为O(p3)。该方法会出现超时，改进方法是采用前缀和。


图5．1样例的场景


设置一维数组sum，sum［i］表示num中的前i项元素和(称为前缀和)，即

sum［i］=num［1］+num［2］+…+num［i］


第5章数组和稀疏矩阵
数据结构在线编程实训（C++语言）（全程视频讲解版）
可以在O(p)的时间内求出sum数组，其过程是先置sum的所有元素为0，再通过迭代方式求出sum的每个元素： 

for(int i=1;i<=p;i++)

sum［i］=sum［i-1］+num［i］;

假设i≤j，有： 

sum［i-1］=num［1］+num［2］+…+num［i-1］

sum［j］=num［1］+num［2］+…+num［i-1］+num［i］+…+num［j］

用后式减前式： 

sum［j］-num［i-1］=num［i］+…+num［j］

其中，sum［j］-num［i-1］表示围栏i到围栏j的连续区域中放牧的牛数量，其中的围栏个数为j-i+1，这样枚举所有的连续区域，即num［i．．j］(i≤j)，在所有小于或等于c的牛数量中求最大的围栏个数。对应的时间复杂度为O(p2)。
对应的程序如下： 

#include <iostream>

#include <cstring>

const int MAXN=1010;

using namespace std;

int num［MAXN］;					　　//num［x］表示围栏x中放牧的牛的数量

int sum［MAXN］;					　　//存放前缀和

int main()

{int n,p,c,x;

while(~scanf("%d%d%d", &n,&p,&c))

{memset(num,0,sizeof num);

for(int i=0;i<n;i++)

{scanf("%d", &x);

num［x］++;

}

sum［0］=0;

for(int i=1;i<=p;i++)			　　//求前缀和

sum［i］=sum［i-1］+num［i］;

int ans=0;

for(int i=1;i<=p-1;i++)		　　//求题目要求的结果ans

for(int j=i;j<=p-1;j++)

{if(sum［j］-sum［i-1］<=c)

ans=max(ans,j-i+1);

}

printf("%d＼n", ans);

}

return 0;

}

上述程序是AC代码，运行时间为32ms，占用的空间为96KB，编译语言为C++。
【实战5．2】POJ3070——矩阵快速幂求Fibonacci数列
时间限制： 1000ms； 内存限制： 65536KB。


视频讲解


问题描述： Fibonacci数列是F0=0，F1=1，Fn=Fn-1+Fn-2(n≥2)。例如，前10项Fibonacci数列是0，1，1，2，3，5，8，13，21，34。
Fibonacci数列的另外一种公式是： 

Fn+1Fn

FnFn-1=11

10n=11
1011
10…11
10n次


给定一个整数n，请求出Fn的最后4位数字。
输入格式： 输入包含多个测试用例，每个测试用例由单个包含整数n(0≤n≤1000000000)的行构成，以n=-1表示结束。
输出格式： 对于每个测试用例，输出一行包含Fn的最后4位数字，如果均为0则输出'0'，否则忽略前导0(也就是输出Fn mod 10000)。
输入样例： 

0

9

999999999

1000000000

-1

输出样例： 

0

34

626

6875

参考博客： https://blog．csdn．net/u012350533/article/details/12460959博客。
解： 先介绍快速幂算法。如果计算xn，可以将n拆成二进制数，该二进制数的第i位的权为2i-1。例如当n=11时，其二进制数是［1011］2，即11=23×1+22×0+21×1+20×1，因此可以将x11转化为计算x23×x21×x20，也就是x11=x8×x2×x1，如图5．2所示。


图5．2快速幂计算x11

用ans存放计算结果，先置ans=1，base=x(权)，当n>0时循环，取n的末尾二进制位d，若d=0，则跳过； 若d=1，则执行ans*=base，再执行base*=base(向高位移一位的权)，并且将n右移一位。最后返回ans。简单地说，base为x的权，按x、x2、x4、……递增，当对应二进制位为1时ans乘上相应的base。该算法称为快速幂算法，求xn的快速幂算法如下： 

double pow(double x,int n)

{double ans=1.0,base=x;

while (n!=0)

{if ((n&1)==1)				　　//遇到二进制位1

ans*=base;				　　//求ans

base*=base;					　　//权递增

n >>= 1;						　　//n右移一位

}

return ans;

}

将上述xn中的x改为m×m矩阵A，对应快速幂就是矩阵快速幂算法。对于本题有m=2，两个2×2的矩阵A和B相乘的公式如下： 

a0,0a0,1
a1,0a1,1b0,0b0,1
b1,0b1,1=a0,0b0,0+a0,1b1,0a0,0b0,1+a0,1b1,1
a1,0b0,0+a1,1b1,0a1,0b0,1+a1,1b1,1


注意： 任何一个矩阵的0次幂为对应的单位矩阵，即

**
**0=10
01


首先置ans为单位矩阵10
01，A=11
10，采用矩阵快速幂算法求出ans=An，再取ans左上角元素(即Fn)模10000得到最终结果。对应的程序如下： 

#include <iostream>

#include <cstring>

using namespace std;

struct Matrix							　　//表示2×2矩阵类型

{

int data［2］［2］;

};

int n;

Matrix multiply(Matrix A,Matrix B)	　　//返回矩阵A和B相乘的结果

{Matrix C;

memset(C.data,0,sizeof(C.data));

for(int i=0;i<2;i++)

for(int j=0;j<2;j++)

for(int k=0;k<2;k++)

{C.data［i］［j］+=A.data［i］［k］*B.data［k］［j］;

C.data［i］［j］%=10000;

}

return C;

}

Matrix quick_pow(Matrix A,int n)		　　//求矩阵A的n次幂的快速幂算法

{Matrix ans;

memset(ans.data,0,sizeof(ans.data));

for(int i=0;i<2;i++)					　　//置ans为单位矩阵

ans.data［i］［i］=1;

while(n!=0)

{if (n & 1)

ans=multiply(ans,A);

A=multiply(A,A);

n>>=1;							　　//n右移一位

}

return ans;

}

int main()

{while(cin >> n && n!=-1)

{if(n==0)

{cout << 0 << endl;

continue;

}

Matrix ans;

ans.data［0］［0］=0;					　　//先置ans为初始矩阵

ans.data［0］［1］=1;

ans.data［1］［0］=1;

ans.data［1］［1］=1;

ans=quick_pow(ans,n);			　　//取ans左上角元素

cout << ans.data［0］［1］%10000 << endl;

}

return 0;

}

上述程序是AC代码，运行时间为0ms，占用的空间为172KB，编译语言为C++。求ans=xn的快速幂算法和求ans=An的矩阵快速幂算法的对应关系，如表5．1所示。


表5．1快速幂和矩阵快速幂算法的对应关系


比较项
快速幂算法
矩阵快速幂算法
说明
初始化
base=x

ans=1
A为m阶矩阵

ans置为m阶单位矩阵

n的二进制位d=0
跳过
跳过

n的二进制位d=1
ans*=base

base*=base
ans=ans×A

A=A×A
由double数乘法改为矩阵乘法



视频讲解


【实战5．3】HDU4920——稀疏矩阵乘法
时间限制： 2000ms； 内存限制： 131072KB。
问题描述： 给定两个n×n的矩阵a和b，求它们的积，结果矩阵中每个元素值模3。
输入格式： 输入包含多个测试用例，每个测试用例的第一行为n(1≤n≤800)； 接下来n行，每行n个整数，表示矩阵a，第i行的第j个整数为aij； 类似地，再接下来的n行为矩阵b(0≤aij，bij≤109)。
输出格式： 对于每个测试用例，输出n行，每行n个整数表示a×b的结果。
输入样例： 

1

0



图5．3求c=a×b的过程的转换

1

2

0 1

2 3

4 5

6 7

输出样例： 

0

0 1

2 1

解： 本题看起来十分平常，直接按矩阵乘法设计算法即可，但会出现超时。
因为题目要求结果矩阵中的每个元素值模3，按求模性质，可以先对a、b的元素值模3，这样a、b中较多的元素为0，可以看成非严格意义上的稀疏矩阵。矩阵a和b的乘法运算的转换过程如图5．3所示。
例如n=2时，计算c=a×b的公式如下： 

c=a0,0a0,1

a1,0a1,1b0,0b0,1

b1,0b1,1=a0,0b0,0+a0,1b1,0a0,0b0,1+a0,1b1,1
a1,0b0,0+a1,1b1,0a1,0b0,1+a1,1b1,1


常规计算顺序如下： 

c［0］［0］+=a［0］［0］*b［0］［0］

c［0］［0］+=a［0］［1］*b［1］［0］

c［0］［1］+=a［0］［0］*b［0］［1］

c［0］［1］+=a［0］［1］*b［1］［1］

c［1］［0］+=a［1］［0］*b［0］［0］

c［1］［0］+=a［1］［1］*b［1］［0］

c［1］［1］+=a［1］［0］*b［0］［1］

c［1］［1］+=a［1］［1］*b［1］［1］

转换后的计算顺序如下： 

c［0］［0］+=a［0］［0］*b［0］［0］

c［0］［1］+=a［0］［0］*b［0］［1］

c［0］［0］+=a［0］［1］*b［1］［0］

c［0］［1］+=a［0］［1］*b［1］［1］

c［1］［0］+=a［1］［0］*b［0］［0］

c［1］［1］+=a［1］［0］*b［0］［1］

c［1］［0］+=a［1］［1］*b［1］［0］

c［1］［1］+=a［1］［1］*b［1］［1］

之所以做这样的转换是为了提高性能，一方面利用了程序局部性原理，a中元素是按行优先存储的，而按i、j循环处理a［i］［j］也是按行优先访问a中的元素； 另外一方面，当a［i］［j］=0时无论b［j］［k］是多少都不必做乘法运算了，可以优化这种情况的计算。对应的程序如下： 

#include <stdio.h>

using namespace std;

const int MAXN=805;

int a［MAXN］［MAXN］,b［MAXN］［MAXN］,c［MAXN］［MAXN］;

int main()

{int n,i,j,k;

while (~scanf("%d",&n))

{for(i=0;i<n;i++)

for(j=0;j<n;j++)

{scanf("%d",&a［i］［j］);

a［i］［j］%=3;

c［i］［j］=0;

}

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{scanf("%d",&b［i］［j］);

b［i］［j］%=3;

}

for(i=0;i<n;i++)					　　//计算矩阵c

for(j=0;j<n;j++)

{if(!a［i］［j］)

continue;

for(k=0;k<n;k++)

c［i］［k］=c［i］［k］+a［i］［j］*b［j］［k］;

}

for(i=0;i<n;i++)					　　//输出结果

{for(j=0;j<n;j++)

if(j==n-1)

printf("%d＼n",c［i］［j］%3);

else

printf("%d ",c［i］［j］%3);

}

}

return 0;

}

上述程序是AC代码，运行时间为1154ms，占用的空间为9320KB，编译语言为C++。
可以进一步优化计算矩阵c的过程，也就是说根据a［i］［j］取值0、1、2做相应计算，当a［i］［j］=0时跳过; 当a［i］［j］=1时,c［i］［k］+=b［j］［k］(0≤k<n); 当a［i］［j］=2时,c［i］［k］+=2*b［j］［k］(0≤k<n)。对应的程序如下： 

#include <stdio.h>

using namespace std;

const int MAXN=805;

int a［MAXN］［MAXN］,b［MAXN］［MAXN］,c［MAXN］［MAXN］;

int main()

{int n,i,j,k;

while(~scanf("%d",&n))

{for(i=0;i<n;i++)

for(j=0;j<n;j++)

{scanf("%d",&a［i］［j］);

a［i］［j］%=3;

c［i］［j］=0;

}

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{scanf("%d",&b［i］［j］);

b［i］［j］%=3;

}

for(int i=0;i<n;i++)				　　//计算矩阵c

for(int j=0;j<n;j++)

{if(a［i］［j］==1)

for (int k=0;k<n;k++)

c［i］［k］+=b［j］［k］;

else if(a［i］［j］==2)

for(int j=0;j<n; j++ )

c［i］［k］+=(b［j］［k］<<1);

}

for(i=0;i<n;i++)					　　//输出结果

{for(j=0;j<n;j++)

if(j==n-1)

printf("%d＼n",c［i］［j］%3);

else

printf("%d ",c［i］［j］%3);

}

}

return 0;

}

上述程序是AC代码，运行时间为967ms，占用的空间为9316KB，编译语言为C++。
5．2在线编程题解析
5．2．1LeetCode48——旋转图像



视频讲解


问题描述： 给定一个n×n的二维矩阵表示一个图像。将图像顺时针旋转90°。注意必须在原地旋转图像，这意味着需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。例如，给定matrix={{1，2，3}，{4，5，6}，{7，8，9}}，原地旋转输入矩阵，使其变为{{7，4，1}，{8，5，2}，{9，6，3}}。要求设计如下函数： 

class Solution {

public:

void rotate(vector<vector<int>>& matrix)

{…}

};

解： 这里要求只能在原数组中做旋转操作，从中找到图像旋转的规律。实现该操作的步骤如下： 
①  按左下—右上对角线交换所有对角元素。
②  将第i行(0≤i<n/2)的所有元素与倒数第i行交换。
例如，两个示例的旋转过程如图5．4所示。对应的算法如下： 

class Solution 

{

public:

void rotate(vector<vector<int> >& matrix)

{int n=matrix.size();					　　//行、列数为n

for (int i=0;i<n;i++)					 　　//步骤①

for (int j=0;j<n-i;j++)

swap(matrix［i］［j］,matrix［n-j-1］［n-i-1］);

for (int i=0;i<n/2;i++)				　　//步骤②

for (int j=0;j<n;j++)

swap(matrix［i］［j］,matrix［n-i-1］［j］);

}

};

上述程序是AC代码，运行时间为0ms，占用的空间为6．5MB，编译语言为C++。


图5．4两个示例的旋转过程


5．2．2HDU1575——方阵A的迹


视频讲解


时间限制： 1000ms； 内存限制： 32768KB。
问题描述： A为一个方阵，则Tr A表示A的迹(就是主对角线上各项的和)，现要求Tr(A^k)%9973。
输入格式： 数据的第一行是一个t，表示有t组数据。每组数据的第一行是n(2≤n≤10)和k(2≤k<109)两个整数。接下来有n行，每行有n个整数，每个整数的范围是［0，9］，表示方阵A的内容。
输出格式： 对应每组数据，输出Tr(A^k)%9973。
输入样例： 

2

2 2

1 0

0 1

3 99999999

1 2 3

4 5 6

7 8 9

输出样例： 

2

2686

解： 直接采用本书第5章中实战5．2的矩阵快速幂方法求res=A^k，再用ans累加res主对角线上的元素和(模9973)，最后输出ans。对应的程序如下： 

#include <iostream> 

#include <cstring>

using namespace std;

const int MOD=9973;

int n,k;

struct Matrix							　　//矩阵类型

{

int data［10］［10］;

} res,A;

void init()								　　//初始化res和A矩阵

{for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

{res.data［i］［j］=0;

scanf("%d",&A.data［i］［j］);	　　//A为输入的矩阵

if(i==j)

res.data［i］［j］=1;			　　//将res置为n阶单位矩阵

}

}

Matrix multiply(Matrix A,Matrix B)	　　//返回矩阵A和B相乘的结果

{Matrix C;

memset(C.data,0,sizeof(C.data));

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

for(int k=0;k<n;k++)

C.data［i］［j］=(C.data［i］［j］+A.data［i］［k］*B.data［k］［j］) % MOD;

return C;

}

void quick_pow()						　　//求矩阵A的k次幂res(矩阵快速幂)

{while(k!=0)

{if (k & 1)

res=multiply(res,A);

A=multiply(A,A);

k>>=1;							　　//k右移一位

}

}

int main()

{int t;

cin >> t;

while(t--)

{scanf("%d%d",&n,&k);

init();							　　//初始化res和A

quick_pow();					　　//用快速幂方法求A矩阵的k次幂

int ans=0;

for(int i=0;i<n;i++)

ans=(ans+res.data［i］［i］) % MOD;

printf("%d＼n",ans);

}

return 0;

}

上述程序是AC代码，运行时间为15ms，占用的空间为1804KB，编译语言为C++。
5．2．3HDU1559——最大子矩阵


视频讲解


时间限制： 10000ms； 内存限制： 32768KB。
问题描述： 给出一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。
输入格式： 输入数据的第一行为一个正整数t，表示有t组测试数据。每一组测试数据的第一行为4个正整数m、n、x、y(0<m，n<1000，0<x≤m，0<y≤n)，表示给定的矩形有m行n列。接下来是这个矩阵，有m行，每行有n个不大于1000的正整数。
输出格式： 对于每组数据，输出一个整数，表示子矩阵的最大和。
输入样例： 

1

4 5 2 2

3
361
649
676
588

992
762
156
993
169

662
3 4
638
8 9
543

525
165
254
809
280

输出样例： 

2474

解： 用a数组存放m×n的整数矩阵，为了简单，a［1．．m］［1．．n］存放有效数据，其他元素为0。设计一个二维数组sum，sum［i］［j］存放(1,1)~(i,j)矩阵的所有元素和(该矩阵的左上角为(1,1)、右下角为(i,j))，其中行、列下标为0的元素值均为0，类似于前缀和。可以通过如下循环求出sum数组： 

for(int i=1;i<=n;i++)				　　//求(1,1)~(i,j)矩阵的元素和

for(int j=1;j<=m;j++)

sum［i］［j］=sum［i-1］［j］+sum［i］［j-1］+a［i］［j］-sum［i-1］［j-1］;

如图5．5所示，任意一个右下角为(i,j)的x×y的子矩阵(宽度为x、高度为y)的所有元素和表示为sum［i］［j］-sum［i-x］［j］-sum［i］［j-y］+sum［i-x］［j-y］。通过遍历求所有这样子矩阵的元素和，比较求出最大元素和ans，最后输出ans。对应的程序如下： 

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAXN=1007;

int t,m,n,x,y;

int a［MAXN］［MAXN］;

int sum［MAXN］［MAXN］;

int main()

{scanf("%d",&t);

while(t--)

{memset(sum,0,sizeof(sum));

scanf("%d%d%d%d",&n,&m,&x,&y);

int ans=0;						　　//存放x×y子矩阵的最大元素和

for(int i=1;i<=n;i++)				　　//输入a［i］［j］

for(int j=1;j<=m;j++)

scanf("%d",&a［i］［j］);

for(int i=1;i<=n;i++)				　　//求(1,1)~(i,j)矩阵的元素和

for(int j=1;j<=m;j++)

sum［i］［j］=sum［i-1］［j］+sum［i］［j-1］+a［i］［j］-sum［i-1］［j-1］;

for(int i=x;i<=n;i++)				　　//求ans

for (int j=y;j<=m;j++)

ans=max(ans,sum［i］［j］-sum［i-x］［j］-sum［i］［j-y］+sum［i-x］［j-y］);

printf("%d＼n",ans);				　　//输出ans

}

return 0;

}



图5．5求(i-x,j-y)~(i,j)矩阵和


上述程序是AC代码，运行时间为249ms，占用的空间为9656KB，编译语言为C++。当然也可以将3个for循环语言合并起来： 

int ans=0;

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++)

{scanf("%d",&a［i］［j］);

sum［i］［j］=sum［i-1］［j］+sum［i］［j-1］+a［i］［j］-sum［i-1］［j-1］;

if (i>=x && j>=y)

ans=max(ans,sum［i］［j］-sum［i-x］［j］-sum［i］［j-y］+sum［i-x］［j-y］);

}

上述采用类似前缀和的方法，对于每个测试用例，求解的时间复杂度为O(mn)，如果采用直接枚举所有子矩阵的方法，求解的时间复杂度为O(m2n2)。
5．2．4POJ3213——矩阵乘法问题


视频讲解


时间限制： 5000ms； 内存限制： 131072KB。
问题描述： USTC最近开发了并行矩阵乘法机器PM3，用于非常大的矩阵乘法运算。给定两个矩阵A和B，其中A是n×p矩阵，B是p×m矩阵，PM3可以在O(p(n+p+m))时间内计算矩阵C=A×B。然而，PM3的开发人员很快发现了一个小问题： PM3可能出错，而且每当出现错误时，结果矩阵C只包含一个不正确的元素。
开发人员在PM3给出矩阵C之后检查并纠正它。他们认为这是一项简单的任务，因为最多会有一个不正确的元素。请编写一个程序来检查和纠正PM3计算的结果。
输入格式： 输入的第一行是3个整数n、p和m(0<n，p，m≤1000)，它们表示A和B的维数。然后跟随n行，每行有p个整数，以行序优先给出A的元素。之后是B和C的元素以相同的方式给出。
A和B的元素以1000的绝对值为界，C的界限是2000000000。
输出格式： 如果C不包含不正确的元素，请打印“Yes”，否则打印“No”后跟另外两行，第一行上有两个整数r和c，第二行上有另一个整数v，表示C中行r列c的元素应该校正为v。
输入样例： 

2 3 2

1 2-1

3-1 0

-1 0

0 2

1 3

-2 -1

-3 -2

输出样例： 

No

1 2

1

解： 采用二维数组a、b、c分别存放A、B、C矩阵，C为给出的A×B结果，可能会有错，最多只有一个元素出错。
如果按照矩阵乘法求出c=A×B，再将C与c的元素一一比较找到出错的元素，花费的时间较多(时间复杂度为O(n3))。通过一个示例看改进方法(时间复杂度为O(n2))，例如： 

a=123
456
789,b=102030
405060
708090


求c=a×b的公式如下： 

c［i］［j］=∑2l=0a［i］［l］×b［l］［j］


求c的各个行的元素和如下： 
c［0］［0］=1×10+2×40+3×70
c［0］［1］=1×20+2×50+3×80
c［0］［2］=1×30+2×60+3×90
c的第0行所有元素之和=c［0］［0］+c［0］［1］+c［0］［2］=1×(10+20+30)+2×(40+50+60)+3×(70+80+90)
c［1］［0］=4×10+5×40+6×70
c［1］［1］=4×20+5×50+6×80
c［1］［2］=4×30+5×60+6×90
c的第1行所有元素之和=c［1］［0］+c［1］［1］+c［1］［2］=4×(10+20+30)+5×(40+50+60)+6×(70+80+90)
c［2］［0］=7×10+8×40+9×70
c［2］［1］=7×20+8×50+9×80
c［2］［2］=7×30+8×60+9×90
c的第2行所有元素之和=c［2］［0］+c［2］［1］+c［2］［2］=7×(10+20+30)+8×(40+50+60)+9×(70+80+90)
从中看出，c的第i行元素和tmp=∑m-1j=0a［i］［j］×(b数组的第j行元素和)
所以设置两个一维数组b_row和c_row，分别累计b、c数组的每一行元素和。不必计算出c数组，由tmp+=a［i］［j］*b_row［j］(0≤j≤m-1)求出结果矩阵的第i行元素和，当出现tmp≠c_row［i］时，说明出错元素在C的第i行，再采用常规方法在C的第i行中查找出错元素的位置。
对应的程序如下： 

#include <iostream>

using namespace std;

const int N=1001;

int a［N］［N］;

int b［N］［N］;

int c［N］［N］;

int c_row［N］;

int b_row［N］;

int main()

{int n,m,p;

while(~scanf("%d%d%d", &n,&m,&p))

{for (int i=0;i<n;i++)					　　//输入a

for(int j=0;j<m;j++)

scanf("%d",&a［i］［j］);

for (int i=0;i<m;i++)					　　//输入b

for(int j=0;j<p;j++)

scanf("%d",&b［i］［j］);

for (int i=0;i<n;i++)					　　//输入c

for(int j=0;j<p;j++)

scanf("%d",&c［i］［j］);

for(int i=0;i<m;i++)					　　//求出b的每行元素和

{b_row［i］=0;

for (int j=0;j<p;j++)

b_row［i］+=b［i］［j］;

}

for (int i=0;i<n;i++)					　　//求出c的每行元素和

{c_row［i］=0;

for(int j=0;j<p;j++)

c_row［i］+=c［i］［j］;

}

int i;

for (i=0;i<n;i++)						　　//找出错行i

{int tmp=0;

for (int j=0;j<m;j++)

tmp+=a［i］［j］*b_row［j］;

if (tmp!=c_row［i］)

break;

}

if (i==n)								　　//没有错误

printf("Yes＼n");

else

{printf("No＼n");					　　//第i行错误

for(int j=0;j<p;j++)

{int res=0;

for(int k=0;k<m;k++)

res+=a［i］［k］*b［k］［j］;

if(res!=c［i］［j］)

{printf("%d %d＼n",i+1,j+1);

printf("%d＼n",res);

break;

}

}

}

}

}

上述程序是AC代码，运行时间为1188ms，占用的空间为8736KB，编译语言为C++。

5．2．5POJ3292——求H半素数的个数


视频讲解


时间限制： 1000ms； 内存限制： 65536KB。
问题描述： H数是一个正数，为4的整数倍加1，例如1、5、9、13、17、21等都是H数。H数的乘法运算是闭合的。
与常规整数一样可以将H数划分为单元、H素数和H合数。1是唯一的单元，如果一个H数h不是单元，并且它仅有一种方式表示为两个H数的乘积，即1×h，则h为H素数，其余为H合数。例如，前几个H合数是5×5=25、5×9=45、5×13=65、9×9=81、5×17=85。
请编程累计H半素数的个数。H半素数是一个H数，它正好是两个H素数的乘积，这两个H素数可以相等或不同。在上面的示例中，5个数字均为H半素数，而125=5×5×5不是H半素数，因为它是3个H素数的乘积。
输入格式： 输入的每一行包含一个H数h(h≤1000001)。输入的最后一行包含0，并且不需要处理此行。
输出格式： 对于每个输入的H数h，输出一行，包含h和1~h(含1和h)的H半素数个数，以空格分隔。
输入样例： 

21

85

789

0

输出样例： 

21 0

85 5

789 62

参考博客： https://blog．csdn．net/qq_36651153/article/details/77740460
解： 置最大整数MAXN为1000005，设计solve()算法求出1~MAXN的H半素数个数的前缀和数组a(采用类似第1章中1．7节的在线编程题3的素数筛选法)。对于给定的h，a［h］就是1~h的H半素数个数，直接输出即可。对应的程序如下： 

#include <iostream>

#include <cstring>

using namespace std;

const int MAXN=1000005;

int prime［MAXN］;						　　//用于存放所有的H素数

bool isprime［MAXN］;					　　//isprime［i］为true表示整数i为H素数

int a［MAXN］;

void solve()							　　//求H半素数个数的前缀和数组a

{int k=0;

memset(isprime,true,sizeof(isprime));

memset(a,0,sizeof(a));

for(int i=5;i<MAXN;i+=4)			　　//求5~MAXN的H素数

{if(isprime［i］)						　　//i为H素数

{prime［k++］=i;				　　//将H素数i添加到prime中

for(int j=2*i;j<MAXN;j+=i)	　　//置所有i的倍数的H数为非H素数

{if((j-1)%4==0)			　　//若j是H数

isprime［j］=false;		　　//j不是H素数，而是H合数

}

}

}

for(int i=0;i<k;i++)					　　//k为小于MAXN的H素数的个数

{if(prime［i］>1000) break;			　　//h≤1000001，其最小因子不可能大于1000

for(int j=i;j<k;j++)

{int tmp=prime［i］*prime［j］;	　　//tmp是两个H素数的乘积

if(tmp>MAXN) break;

a［tmp］=1;					　　//表示tmp是一个H半素数

}

}

for(int i=0;i<MAXN;i++)				　　//a作为前缀和

a［i］+=a［i-1］;

}

int main()

{solve();

int h;

while(~scanf("%d",&h) && h)

printf("%d %d＼n",h,a［h］);

} 

上述程序是AC代码，运行时间为32ms，占用的空间为5340KB，编译语言为C++。