当前位置：首页 > news >正文

距离我成为炎帝的一次（比较近的一次）

news 2025/8/9 2:45:17

sj登录—专业IT笔试面试备考平台_牛客网

这是dfs的一道基础题，可惜我还是没有学会

但是有时候错误也是一种成长方式

我的代码E题带路

#include<bits/stdc++.h>
//#define int long long
using namespace std;const long long MAX=1e3+10;
//long   a[MAX],bian[MAX],q[MAX],n,m,minn=MAX;//res=0;
int res=0,cnt=0,n,m;
int a[MAX][MAX];
bool vis[MAX][MAX];
int dis[4][4]={{-1,-1},{1,1},{0,1},{0,-1}};
void check(int x,int y){int dx,dy;memset(vis,0,sizeof(vis));if(vis[x][y]==0){if(a[x][y]==1){res++;vis[x][y]=1;return ;}}//keyint fla=0;for(int i=x;x<=n;i++){if(a[x][y]==1){fla=1;}}for(int j=1;j<=m;j++){if(a[x][y]==1){fla=1;}}if(fla==0){res=0;}while(y>0&&x<=n)check(x+1,y);//upwhile(x>0&&y<=m)check(x-1,y);//downwhile(y>0&&x<=n)check(x,y-1);//lwhile(x>0&&y<=m)check(x,y+1);//r
}
int main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m;cin>>n>>m;//int temx,temy;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char c;cin>>c;if(c=='.'){a[i][j]=1;//temx=i;temy=j;}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]==1){check( i, j);res=max(res,-1);	}	}}cout<<res;
}

当时写着写着，本来是比较想写dfs的但是我自己不太熟练所以还是写了，一个其他的方式，但是在那个阻隔那里困扰了我好久，不知道如何去跳到一个新的地方解决这个问题，然后我想用到防火墙一样的东西，看看是否有一排或者是一行全是0的数嘛，多练还是要多练的，其次是我不太能熟练使用我的爆步，并结合我的吸掌来使用。

正确代码使用dfs深度优先搜索

#include<bits/stdc++.h>
using namespace std;
#define int long long
int disx[4]={-1,1,0,0},disy[4]={0,0,1,-1};
int st[1010][1010],res;
string s[1001];int n,m;
void dfs(int x,int y,int ans){//int xx,yy;res=max(res,ans);for(int i=0;i<4;i++){int xx=disx[i]+x,yy=disy[i]+y;if(xx<1||xx>n||yy<1||yy>m||s[xx][yy]=='#'||st[xx][yy]) continue;st[xx][yy]=1;dfs(xx,yy,ans+1);st[xx][yy]=0;}
}
signed main(){cin>>n>>m;for(int i=1;i<=n;i++){string x;cin>>x;x=" "+x;//string x;x=""+s;s[i]=x;}for(int i = 1; i <= n; i ++ ){for(int j = 1; j <= m; j ++ ){if(s[i][j] == '.'){st[i][j] = 1;dfs(i, j, 1);st[i][j] = 0;}}}cout << res << '\n';return 0;
}

在这里遇到一个边界判断语句，是判断上下左右是否有”.“的一个语句，也就是所谓的围墙，方便数数。这里也是我的能力一大不足之处，好好学习一下！

K题质量检测登录—专业IT笔试面试备考平台_牛客网

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const long long MAX=1e6+10;
long   a[MAX],bian[MAX],q[MAX],n,m,minn=MAX;//res=0;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}/*for(int j=1;j<=m;j++){minn=min(minn,a[j]);}*///printf("%d\n",minn);int u=m,o=1;for(;u<=n;){minn=MAX;for(int i=o;i<=u;i++){minn=min(minn,a[i]);}printf("%d\n",minn);u+=1;o+=1;}/*for(int i=1;i<=n-m+1;i++){printf("%d\n",q[i+m-1]);}*/
}

在这里我虽然知道会运行超时（时间0（nm）），但是自己也没有想到什么好的方式来解决这个问题，今天了解到了ST表什么时候去深入去了解一下，说这个方式可以大大解决时间复杂度的关系了解到http://t.csdn.cn/44l0W还有就是那个log2算法我也不知道如何解决的，本蒟蒻

#include "bits/stdc++.h"using namespace std;
using i64 = long long;template <class T>
struct SparseTable {int n;vector<vector<T>> a;SparseTable(const vector<T> &init) : n(init.size()) {int lg = __lg(n);a.assign(lg + 1, vector<T>(n));a[0] = init;for (int i = 1; i <= lg; i++) {for (int j = 0; j <= n - (1 << i); j++) {a[i][j] = min(a[i - 1][j], a[i - 1][(1 << (i - 1)) + j]);}}  	    }T get(int l, int r) {// [l, r)int lg = __lg(r - l);return min(a[lg][l], a[lg][r - (1 << lg)]);}
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}SparseTable<int> mn(a);for (int i = 0; i + m <= n; i++) {cout << mn.get(i, i + m) << '\n';}return 0;
}

说ST表也是优化了时间复杂度的关系，其中还有一个模板之类的，找时间好好看看（0n（log2m））

J题登录—专业IT笔试面试备考平台_牛客网

我的dabian

#include<bits/stdc++.h>
//#define int long long
using namespace std;const long long MAX=1e6+10;
//long   a[MAX],bian[MAX],q[MAX],n,m,minn=MAX;//res=0;
int res=0,cnt=0,n,m;
void check(int x){}
int main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n-1;i++){res=0;if(i<m){res++;}else if(i>=m){res=0;if(i==m){res=1;}else {res=(i-m);res=res+1;}}cnt=max(cnt,res);}cout<<cnt;
}

再看一下大佬的真是，满眼的羡慕啊，写得真好，我好喜欢，真牛逼

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int num[MAXN],ans;
int n,k,goal;
int vis[MAXN];
void dfs(int now,int step)
{int a=(now+1)%n;int b=(now+k)%n;if(num[a]>step) {num[a]=step;dfs(a,step+1);}if(num[b]>step) {num[b]=step;dfs(b,step+1);	}}
int main()
{cin>>n>>k;for (int i=1;i<=n;i++){num[i]=MAXN;}dfs(0,1);for (int i=1;i<n;i++){ans=max(ans,num[i]);}cout<<ans<<endl;return 0;
}

D题签到了登录—专业IT笔试面试备考平台_牛客网

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAX=1000000;
int a[MAX];
signed main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}int flag=0;for(int i=1;i<=m;i++){int x,y,z;cin>>x>>y>>z;for(int j=y;j<=z;j++){a[j]=a[j]-x;if(a[j]<0){printf("-1\n");printf("%d",i);flag=1;return 0;}}}if(flag==0){printf("0");}
}

经常感觉就是签到了，不过就是重在参与嘛，蒟蒻成长，总不会一帆风顺的！！

查看全文

http://www.lryc.cn/news/137571.html