第十周程序设计课解题报告

我会带着你远行 2022-08-07 13:39 206阅读 0赞

第十周程序设计课解题报告

这周的题目主要想的时候得转个弯，不需要用到高科技，就用老师课堂讲过的内容即可。

1000.

题目大意：矩阵加法。

解：单纯每个格子对应相加即可。但是要注意若干细节，例如行末没有空格，输出的时候是多组数据询问而非固定组数所以需要使用读入判断。

代码：

\#include <cstdio>

\#include <iostream>

\#include <cmath>

\#include <algorithm>

\#include <cstring>

using namespace std;

\#define MAXN 1111

\#define SQR(x) ((x)\*(x))

\#define MIN(a,b) ((a<b)?(a):(b))

\#define MAX(a,b) ((a>b)?(a):(b))

\#define EPS (1e-8)

Int n, m, a\[MAXN\]\[MAXN\], b\[MAXN\]\[MAXN\], c\[MAXN\]\[MAXN\];

int main()\{

while (cin>>n && n>0)\{

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

for (int j=1; j<=n; j++) scanf("%d", &a\[i\]\[j\]);

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

int tmp;

for (int j=1; j<=n; j++)\{

scanf("%d", &tmp);

a\[i\]\[j\]+=tmp;

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

for (int j=1; j<=n; j++)\{

printf("%d", a\[i\]\[j\]);

if (j<n) printf(" ");

printf("\\n");

return 0;

囧我不知道wps抽什么风空格看起来那么长。你们凑合看吧=w=

1001.

题目大意：矩阵乘法

解：大体要注意的跟上一题相同，关键是考验你的线性代数有没有学好了，如果矩阵AB相乘，公式应该是

C(i,j)=A(i,k)\*B(k,j)

代码：

\#include <cstdio>

\#include <iostream>

\#include <cmath>

\#include <algorithm>

\#include <cstring>

using namespace std;

\#define MAXN 1111

\#define SQR(x) ((x)\*(x))

\#define MIN(a,b) ((a<b)?(a):(b))

\#define MAX(a,b) ((a>b)?(a):(b))

\#define EPS (1e-8)

int n, m, a\[MAXN\]\[MAXN\], b\[MAXN\]\[MAXN\], c\[MAXN\]\[MAXN\];

int main()\{

while (cin>>n)\{

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

for (int j=1; j<=n; j++) scanf("%d", &a\[i\]\[j\]);

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

for (int j=1; j<=n; j++) scanf("%d", &b\[i\]\[j\]);

memset(c, 0, sizeof(c));

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

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

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

c\[i\]\[j\]+=a\[i\]\[k\]\*b\[k\]\[j\];

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

for (int j=1; j<=n; j++)\{

printf("%d", c\[i\]\[j\]);

if (j<n) printf(" ");

printf("\\n");

return 0;

1002.

题目大意：给出n个【有序】三元组，再有m组询问，问给出的三元组是否在上面n个当中出现过。

解：核心问题就是求(x,y,z)有没有出现过。其实题目有句话说不要把题目想得太复杂= =，那么我们直接可以利用数组的下标来标示三元组，而数组所存放的值标示三元组是否出现。

例如a\[x\]\[y\]\[z\]==1表示(x,y,z)出现过了

a\[a\]\[b\]\[c\]==0表示(a,b,c)没有出现过

所以我们直接申请一个三维数组即可（申请之前记得估算一下内存消耗啊！）

不过你们有的人非常棒，用的二分去做。我觉得如果从二分去考虑的话我的思路如下：

首先这是一个三元组，但是我们通常跟一维的东西打交道，比如之前一直都是使用一维数组。而变量里保存的一个数字也可以看做一维数轴上的东西。

那么能不能把三维的东西映射到一维上呢？

能！

因为这个三元组每个元都是0~200的数，那么我们把整个三元组当做一个201进制的数就好了。

而进制转换公式为 key=x\*(201)^2+y\*201+z。计算后，我们是不是就得到了这个三元组的十进制标示方法啦？而且可以保证每个三元组和每个十进制数是一一对应的。

然后你们大多数人应该是sort排序再使用二分查找来寻找数字是否出现过

但是= =，不要把问题复杂了！还记得1002第一个做法么？

=================分割防剧透================

其实，直接用一个一维数组标示这个key是否出现过即可，算一下，可知最多需要202\*202\*202约等于 800万个int（bool)<30MB

所以这个问题很好得解决了~

写法二留给你们有兴趣的同学自己写一下吧，如果还想更深入了解这个思想（比如考虑三元组的数在1~10000内，n,m<=10万的时候怎么做呢？），请搜索 hash（哈希）

代码：

\#include <cstdio>

\#include <iostream>

\#include <cmath>

\#include <algorithm>

\#include <cstring>

using namespace std;

\#define MAXN 1111

\#define SQR(x) ((x)\*(x))

\#define MIN(a,b) ((a<b)?(a):(b))

\#define MAX(a,b) ((a>b)?(a):(b))

\#define EPS (1e-8)

int n, m;

bool a\[211\]\[211\]\[211\];

int main()\{

//  freopen("test.txt", "r", stdin);

while (cin>>n>>m)\{

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

int x, y, z;

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

scanf("%d%d%d", &x, &y, &z);

a\[x\]\[y\]\[z\]=true;

for (int i=1; i<=m; i++)\{

scanf("%d%d%d", &x, &y, &z);

if (a\[x\]\[y\]\[z\])\{

printf("Yes\\n");

else printf("No\\n");

return 0;

1003

题目大意：判断a+b是否等于c

解：这个其实是细节题和定义题。为什么对于三个double类型的数a+b==c这样的写法可能错呢？因为对于计算机的浮点类型，他的精度是有限的，比如double只能精确十六位数字（注意是数字！不是十六位小数，比如1234567.123456789是他精度的极限因为他的有效数字为16位）。

关于浮点数的具体原理，你们可以课外自己学习，但是你们通过这题知道，对于浮点数，最好不要直接写等号。如果要判断相等，从工程和竞赛上一般要求他们相差的值在一个范围内即把他们视作相等了。例如这题告诉我们当a+b和c相差十的负十次方就相等了。

所以公式为 |a+b-c|<十的负十次方

为啥我要用汉字写那个数字呢？=w=

一般我们文字会写成10^(-10)

但是但是！！！！！！！！

计算机编程里不可以，至少c++里不可以！因为^在c++里是异或符号，跟\+-\*/一样是一个运算符。反正你这样写就是表示

十 异或 负十，不是十的负十次方！

那么你写成 0.0000000001？啊眼睛好模糊一定是。。。。。。

咳，其实这种写法不太易于debug，我们一般表示十的多少次方会写成   1eX, 比如10的5次方写作 1e5

那么这里就是 1e-10了（后面题目下方新增了提示）

代码：

\#include <cstdio>

\#include <iostream>

\#include <cmath>

\#include <algorithm>

\#include <cstring>

using namespace std;

\#define MAXN 1111

\#define SQR(x) ((x)\*(x))

\#define MIN(a,b) ((a<b)?(a):(b))

\#define MAX(a,b) ((a>b)?(a):(b))

\#define EPS (1e-10)

int n, m;

//bool a\[211\]\[211\]\[211\];

double a, b, c;

double wmz\_abs(double x)\{

if (x<0) return -x;

else return x;

int main()\{

//  freopen("test.txt", "r", stdin);

cin>>n;

while (n--)\{

scanf("%lf%lf%lf", &a, &b, &c);

if (wmz\_abs(a+b-c)<EPS) printf("Yes\\n");

else printf("No\\n");

return 0;

1004.

题目大意：询问区间和，不同的是在询问之余还会新增两个操作：

1.把1~n所有数\+b

2.把1~n所有数取负

解：超时大魔王又来啦~其实你们写程序前先确定一下复杂度，超十倍以上一般别想靠rp交了（虽然以后会碰到一些复杂度明明行不通但是交了还是会ac的题，但是现在，你们先学会写正解，再去学花式暴力)

其实如果这道题单纯问区间和的话，大家回忆一下以前做过的题，应该会写吧。但是问题是多了两个操作，很麻烦。你们大部分人会超我看过是因为每次修改操作后你们都去把整个区间修改了，所以最坏的情况还是n方。

观察性质，你会发现，两个操作都带一个定语：“所有”！

所以我们还需不需要把每个数字一个一个增加呢？

不用！

为何我们不能用一个变量表示“所有”呢？假设为sum为所有数到目前为止都加了sum。那么询问区间\[l,r\]

公式为   \[l,r\] = s\[r\]-s\[l-1\] + sum\*(r-l+1)

对吧？同样的，符号问题也可以用一个变量来实现。

但是特殊的，sum和符号变量lab不能割裂，就是说不要使用sum来表示增减的绝对值单纯用lab来表示求和后的符号。

例如sum=10，lab=-1，那么全体加13的话这个情况很难处理（不是不能写，至少我觉得与其加一堆if来处理这种情况的话不如让sum带符号好了）

所以你们参考一下我的写法吧~如果有更美的写法欢迎提出我贴上来让大家学习学习。

代码：

\#include <cstdio>

\#include <iostream>

\#include <cmath>

\#include <algorithm>

\#include <cstring>

using namespace std;

\#define MAXN 111111

\#define SQR(x) ((x)\*(x))

\#define MIN(a,b) ((a<b)?(a):(b))

\#define MAX(a,b) ((a>b)?(a):(b))

\#define EPS (1e-10)

int n, m;

long long a\[MAXN\], lab, sum;

double wmz\_abs(double x)\{

if (x<0) return -x;

else return x;

int main()\{

//  freopen("test.txt", "r", stdin);

while (cin>>n>>m)\{

a\[0\]=0; lab=1; sum=0;

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

scanf("%lld", &a\[i\]);

a\[i\]+=a\[i-1\];

int x, y, z;

while (m--)\{

scanf("%d", &x);

if (x==1)\{

lab\*=-1; sum\*=-1;

else if (x==2)\{

scanf("%d", &y);

sum+=y;

else if (x==3)\{

long long ans=0;

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

ans=sum\*(y-x+1) + (a\[y\]-a\[x-1\])\*lab;

printf("%lld\\n", ans);

return 0;

第十周程序设计课解题报告

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关第十六周往年期末考试题I解题报告

相关第十五周程序设计作业解题报告

相关第十四周程序设计课解题报告

相关第十二周程序设计课解题报告

相关第十周程序设计课解题报告

相关第十一周程序设计课作业解题报告

相关第八周程序设计课解题报告

相关第七周程序设计课解题报告

相关第十周学习进度报告

相关（第十周）用户使用报告