8.17集训笔记
上午二维数组/函数
- B2101 计算矩阵边缘元素之和
分析：尽量对每个元素只遍历一次，如果发现是边缘元素，那么加入即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,a[N][N];
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) cin>>a[i][j];
int ans=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
if(i==1 || j==1 || i==n || j==m)
ans += a[i][j];
}
cout<<ans;
return 0;
}
- P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles
分析：方法1：从上到下，最后一行的最大值就是答案；
方法2：从下到上，第一个就是答案；
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,a[N][N];
int main(){
cin>>n;
for(int i=1; i<=n; i++)
for(int j=1; j<=i; j++) cin>>a[i][j];
// 从上到下
// for(int i=1; i<=n; i++)
// for(int j=1; j<=i; j++)
// a[i][j] += max(a[i-1][j], a[i-1][j-1]);
// int ans=0;
// for(int j=1; j<=n; j++) ans=max(ans, a[n][j]);
// cout<<ans;
// 从下到上
for(int i=n-1; i>=1; i--){
for(int j=1; j<=i; j++){
a[i][j] += max(a[i+1][j], a[i+1][j+1]);
}
}
cout<<a[1][1];
return 0;
}
- P1002 [NOIP2002 普及组] 过河卒
分析：根据数据找规律，使用偏移数组和标记数组，对马儿能到的位置进行标记，该位置的方案一定为0，至于规律一定要自己模拟一下，比如写出对于 4*4 的矩阵，每个点的方案数，然后找到规律：a[i][j] = a[i-1][j] + a[i][j-1];
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,a[N][N];
int dx[9]={0,2,1,-1,-2,-2,-1, 1, 2};
int dy[9]={0,1,2, 2, 1,-1,-2,-2,-1};
bool st[N][N];
int main(){
int n,m,x,y;
cin>>n>>m>>x>>y;
a[1][0]=1;
for(int i=0; i<9; i++) {
int tx=x+dx[i], ty=y+dy[i];
st[tx][ty] = 1;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++) cout<<st[i][j]<<" "; cout<<endl;
}cout<<endl;
for(int i=1; i<=n+1; i++){
for(int j=1; j<=m+1; j++){
a[i][j] = a[i-1][j] + a[i][j-1];
if(st[i-1][j-1]) a[i][j]=0;
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++) cout<<a[i][j]<<" "; cout<<endl;
}cout<<endl;
cout<<a[n+1][m+1];
return 0;
}
函数笔记：
函数练习、递归入门