当前位置: 代码迷 >> 综合 >> 第四天补题
  详细解决方案

第四天补题

热度:33   发布时间:2024-01-18 23:39:38.0

签到题:卡字符的读取

给定一个字符矩阵,判断是否对角线上字符全部相同,对角线外字符全部相同,且它们不同

这里主要考察字符矩阵的读取

如果直接用scanf("%c")会读入空格和换行

换成整数:

cin>>c 会导致cin错误 scanf(“%d”)也会导致scanf错误(不能直接从字符读入转换成整数,只有printf的时候可以有多种转换方式)

最后的解决:

while(cin>>a){
if(a==' '||a=='\n')
continue;
else break;}
matrix[i][j]=a;


memset逐字节赋值的效率

和总体直接初始化的效率相比,经过前人测试:

测试结果表明:memset比普通的初始化快7倍,所以应该多用memset来完成初始化工作。但,最根本还是应该减少计算机的计算量。


2.C题目

C题:给定一个0,1矩阵,相邻如果都是1则可以建造一座桥

然后问一个方块矩阵内可以建造多少座桥。(查询次数比较多)

<span style="font-size:18px;">bfs 超时。。</span>
<span style="font-size:18px;">#include <iostream>
#include <queue>
using namespace std;
const int maxn=520;
int N,M,Q;
bool connect[maxn][maxn];
int x1,y1,x2,y2;
bool isvisited[maxn][maxn];
typedef pair<int,int> Point;
int cnt;
void bfs(){queue<Point> Q;int NumOfChecked=0;while(NumOfChecked<(x2-x1+1)*(y2-y1+1)){bool out_flag=false;for(int i=x1;i<=x2;i++){for(int j=y1;j<=y2;j++){if(isvisited[i][j]) continue;isvisited[i][j]=true;NumOfChecked++;if(connect[i][j]){Q.push(make_pair(i,j));out_flag=true;break;}}if(out_flag) break;}while(!Q.empty()){Point out=Q.front(); Q.pop();//cout<<"x1=="<<out.first<<"y1=="<<out.second<<endl;if(out.first+1<=x2){if(!isvisited[out.first+1][out.second]){NumOfChecked++;isvisited[out.first+1][out.second]=true;if(connect[out.first+1][out.second]){Q.push(make_pair(out.first+1,out.second));cnt++;}}else{if(connect[out.first+1][out.second]){cnt++;}}}if(out.second+1<=y2){if(!isvisited[out.first][out.second+1]){NumOfChecked++;isvisited[out.first][out.second+1]=true;if(connect[out.first][out.second+1]){Q.push(make_pair(out.first,out.second+1));cnt++;}}else{if(connect[out.first][out.second+1]){cnt++;}}}}
}
}
int main(int argc, char const *argv[])
{int cases;cin>>cases;while(cases--){cin>>N>>M;for(int i=1;i<=N;i++){for(int j=1;j<=M;j++){cin>>connect[i][j];}}// for(int i=1;i<=N;i++){// 	for(int j=1;j<=M;j++){// 		cout<<connect[i][j]<<" ";// 	}// 	cout<<endl;// }cin>>Q;for(int k=1;k<=Q;k++){cnt=0;cin>>x1>>y1>>x2>>y2;for(int i=x1;i<=x2;i++){for(int j=y1;j<=y2;j++){isvisited[i][j]=false;}}bfs();//cout<<"here"<<endl;cout<<cnt<<endl;}}return 0;
}</span>



zcy学长说了一种前缀和的方式:

班长认为可以只考虑向右和向下的连通性(显然这样可以做到不重复计算一座桥),对于每个点,F[i][j]为向右向下联通数量

sum[i][j]为1,1到i,j的F[i][j]的和

那么为了计算x1,y1,x2,y2区间内的连通数,需要做的是sum[x2][y2]-sum[x1-1][y2]-sum[x2][y2-1]+sum[x1-1][y1-1](左上部分减了两次)

当然,还有x2行和y2列向右向下的连通性,这个只需要O(N)扫描一遍就可以了。

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=520;
int N,M,Q;
bool connect[maxn][maxn];
int x1,y1,x2,y2;
bool R[maxn][maxn];
bool D[maxn][maxn];
int sum[maxn][maxn];
int cnt;int main(int argc, char const *argv[])
{int cases;cin>>cases;while(cases--){cin>>N>>M;for(int i=1;i<=N;i++){for(int j=1;j<=M;j++){cin>>connect[i][j];R[i][j]=D[i][j]=false;}}for(int i=1;i<=N;i++){for(int j=1;j<=M;j++){if(i+1<=N&&connect[i][j]&&connect[i+1][j])D[i][j]=true;if(j+1<=M&&connect[i][j]&&connect[i][j+1])R[i][j]=true;}}for(int i=1;i<=N;i++){for(int j=1;j<=M;j++){sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+R[i][j]+D[i][j];//	printf("sum[%d][%d]=%d  ",i,j,sum[i][j] );}//正确性显然,比如我们要获得[1][1]到[i][j]内的连通数//我们只要获得到[i-1][j]的连通数,[i][j]这一点的连通性//再考虑i这一行的连通数即可,但是这一行的连通数就是sum[i][j-1]-sum[i-1][j-1]//printf("\n");}cin>>Q;for(int k=1;k<=Q;k++){cin>>x1>>y1>>x2>>y2;cnt=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];//cout<<"original"<<cnt<<endl;for(int i=x1;i<=x2;i++){cnt-=R[i][y2];}for(int i=y1;i<=y2;i++){cnt-=D[x2][i];}cout<<cnt<<endl;}}return 0;
}



3._int128的使用 ??

大约能够支持10^40级别的运算

As an extension the integer scalar type __int128 is supported for targets which have an integer mode wide enough to hold 128 bits. Simply write __int128 for a signed 128-bit integer, or unsigned __int128 for an unsigned 128-bit integer. There is no support in GCC for expressing an integer constant of type __int128 for targets with long long integer less than 128 bits wide.

  相关解决方案