- js24007 的博客
小紫本:永远铭记
-
js24007
LV 5
@
2026-10-3 15:21:54
- 不会给vector用sort:
sort(vec.begin(),vec.end()); - 不看数据范围
- 不用记忆化优化
- 模板题不背板
神人代码记录
查找文献
1.0:不排序 $\color{red}{WA}$
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=(1LL<<30);
int n,m;
bool f[N];
vector<int> g[N];
void dfs(int d){
for(auto v:g[d]){
if(f[v])continue;
f[v]=true;
cout<<v<<' ';
dfs(v);
}
return;
}
void bfs(int d){
queue<int> q;
q.push(d);
while(!q.empty()){
int u=q.front();
q.pop();
for(auto v:g[u]){
if(f[v])continue;
f[v]=true;
cout<<v<<' ';
q.push(v);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
}
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
f[1]=true;
cout<<1<<' ';
dfs(1);
cout<<endl;
memset(f,0,sizeof(f));
f[1]=true;
cout<<1<<' ';
bfs(1);
return 0;
}
1.1:不会给vector用sort,直接手搓冒泡 $\color{green}{AC}$
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=(1LL<<30);
int n,m;
bool f[N];
vector<int> g[N];
void dfs(int d){
for(auto v:g[d]){
if(f[v])continue;
f[v]=true;
cout<<v<<' ';
dfs(v);
}
return;
}
void bfs(int d){
queue<int> q;
q.push(d);
while(!q.empty()){
int u=q.front();
q.pop();
for(auto v:g[u]){
if(f[v])continue;
f[v]=true;
cout<<v<<' ';
q.push(v);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
}
for(int k=1;k<=n;++k)
for(int len=g[k].size(),i=len-1;i>0;--i)
for(int j=0;j<i;++j)
if(g[k][j]>g[k][j+1])
swap(g[k][j],g[k][j+1]);
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
f[1]=true;
cout<<1<<' ';
dfs(1);
cout<<endl;
memset(f,0,sizeof(f));
f[1]=true;
cout<<1<<' ';
bfs(1);
return 0;
}
1.2:原来是这样用的 $\color{green}{AC}$
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+5;
int n,m,k;
vector<int> g[N];
int c[N];
int cnt=0;
bool check(int d,int cl){
for(auto v:g[d])
if(c[v]==cl){
// cout<<'#';
return false;
}
// cout<<'@';
return true;
}
void dfs(int d){
if(d>n){
++cnt;
return;
}
for(int i=1;i<=k;++i){
if(check(d,i)){
c[d]=i;
dfs(d+1);
c[d]=0;
}
}
return;
}
//void bfs(int d){
// queue<int> q;
// q.push(d);
// while(!q.empty()){
// int u=q.front();
// q.pop();
// for(auto v:g[u]){
// if(f[v])continue;
// f[v]=true;
// cout<<v<<' ';
// q.push(v);
// }
// }
//
//}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
cout<<cnt;
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
return 0;
}
图的遍历
1.0:普通dfs+不看数据范围 $\color{blue}{RE}$
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+5;
int n,m;
vector<int> g[N];
int c[N];bool f[N];
int ans;
void dfs(int d){
for(auto v:g[d]){
if(f[v])continue;
ans=max(ans,v);
f[v]=true;
dfs(v);
}
return;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
// g[v].push_back(u);
}
for(int i=1;i<=n;++i){
ans=i;
memset(f,0,sizeof(f));
dfs(i);
cout<<ans<<' ';
}
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
return 0;
}
1.1:普通dfs+改对数据范围 $\color{orange}{TLE}$
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> g[N];
int c[N];bool f[N];
int ans;
void dfs(int d){
for(auto v:g[d]){
if(f[v])continue;
ans=max(ans,v);
f[v]=true;
dfs(v);
}
return;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
// g[v].push_back(u);
}
for(int i=1;i<=n;++i){
ans=i;
memset(f,0,sizeof(f));
dfs(i);
cout<<ans<<' ';
}
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
return 0;
}
1.2：记忆化优化dfs $\color{orange}{TLE}$
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> g[N];
int c[N];bool f[N];
int mr[N];
int ans;
void dfs(int d){
if(mr[d]){
ans=max(ans,mr[d]);
return;
}
for(auto v:g[d]){
if(f[v])continue;
ans=max(ans,v);
f[v]=true;
dfs(v);
}
return;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
// g[v].push_back(u);
}
for(int i=1;i<=n;++i){
ans=i;
memset(f,0,sizeof(f));
dfs(i);
mr[i]=ans;
cout<<ans<<' ';
}
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
return 0;
}
2.0：记忆化优化bfs $\color{orange}{TLE}$
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> g[N];
int c[N];bool f[N];
int mr[N];
int ans;
//void dfs(int d){
// if(mr[d]){
// ans=max(ans,mr[d]);
// return;
// }
// for(auto v:g[d]){
// if(f[v])continue;
// ans=max(ans,v);
// f[v]=true;
// dfs(v);
// }
// return;
//}
void bfs(int d){
queue<int> q;
q.push(d);
while(!q.empty()){
int u=q.front();
q.pop();
if(mr[u]){
ans=max(ans,mr[u]);
continue;
}
for(auto v:g[u]){
if(f[v])continue;
ans=max(ans,v);
f[v]=true;
q.push(v);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
// g[v].push_back(u);
}
for(int i=1;i<=n;++i){
ans=i;
memset(f,0,sizeof(f));
// dfs(i);
bfs(i);
mr[i]=ans;
cout<<ans<<' ';
}
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
return 0;
}
不是这记忆化的啥玩意?
1.4：意识到了mr[n]=n; $\color{orange}{TLE}$
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> g[N];
int c[N];bool f[N];
int mr[N];
int ans;
void dfs(int d){
if(mr[d]){
ans=max(ans,mr[d]);
return;
}
for(auto v:g[d]){
if(f[v])continue;
ans=max(ans,v);
f[v]=true;
dfs(v);
}
return;
}
//void bfs(int d){
// queue<int> q;
// q.push(d);
// while(!q.empty()){
// int u=q.front();
// q.pop();
// if(mr[u]){
// ans=max(ans,mr[u]);
// continue;
// }
// for(auto v:g[u]){
// if(f[v])continue;
// ans=max(ans,v);
// f[v]=true;
// q.push(v);
// }
// }
//}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
// g[v].push_back(u);
}
mr[n]=n;
for(int i=1;i<=n;++i){
ans=i;
memset(f,0,sizeof(f));
f[i]=true;
dfs(i);
// bfs(i);
mr[i]=ans;
cout<<ans<<' ';
}
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
return 0;
}
1.6:把超时归咎于输入输出 $\color{orange}{TLE}$
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> g[N];
int c[N];bool f[N];
int mr[N];
int ans;
void dfs(int d){
if(mr[d]){
ans=max(ans,mr[d]);
return;
}
for(auto v:g[d]){
if(f[v])continue;
ans=max(ans,v);
f[v]=true;
dfs(v);
}
return;
}
//void bfs(int d){
// queue<int> q;
// q.push(d);
// while(!q.empty()){
// int u=q.front();
// q.pop();
// if(mr[u]){
// ans=max(ans,mr[u]);
// continue;
// }
// for(auto v:g[u]){
// if(f[v])continue;
// ans=max(ans,v);
// f[v]=true;
// q.push(v);
// }
// }
//}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
// g[v].push_back(u);
}
mr[n]=n;
for(int i=1;i<=n;++i){
ans=i;
memset(f,0,sizeof(f));
f[i]=true;
dfs(i);
// bfs(i);
mr[i]=ans;
cout<<ans<<' ';
}
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
return 0;
}
1.8:啥子 $\color{red}{WA}$
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> g[N];
int c[N];bool f[N];
int mr[N];
int ans;
void dfs(int d){
if(mr[d]){
ans=max(ans,mr[d]);
return;
}
for(auto v:g[d]){
if(f[v])continue;
if(ans<v){
ans=v;
f[v]=true;
dfs(v);
}
}
return;
}
//void bfs(int d){
// queue<int> q;
// q.push(d);
// while(!q.empty()){
// int u=q.front();
// q.pop();
// if(mr[u]){
// ans=max(ans,mr[u]);
// continue;
// }
// for(auto v:g[u]){
// if(f[v])continue;
// ans=max(ans,v);
// f[v]=true;
// q.push(v);
// }
// }
//}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
// g[v].push_back(u);
}
mr[n]=n;
for(int i=1;i<=n;++i){
ans=i;
memset(f,0,sizeof(f));
f[i]=true;
dfs(i);
// bfs(i);
mr[i]=ans;
cout<<ans<<' ';
}
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
return 0;
}
1.9:记忆化优化+剪棍木 $\color{orange}{TLE}$
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> g[N];
int c[N];bool f[N];
int mr[N];
int ans;
void dfs(int d){
if(mr[d]){
ans=max(ans,mr[d]);
return;
}
for(auto v:g[d]){
if(f[v])continue;
if(mr[v]&&ans>mr[v])continue;
ans=max(ans,v);
f[v]=true;
dfs(v);
}
return;
}
//void bfs(int d){
// queue<int> q;
// q.push(d);
// while(!q.empty()){
// int u=q.front();
// q.pop();
// if(mr[u]){
// ans=max(ans,mr[u]);
// continue;
// }
// for(auto v:g[u]){
// if(f[v])continue;
// ans=max(ans,v);
// f[v]=true;
// q.push(v);
// }
// }
//}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
// g[v].push_back(u);
}
mr[n]=n;
for(int i=1;i<=n;++i){
ans=i;
memset(f,0,sizeof(f));
f[i]=true;
dfs(i);
// bfs(i);
mr[i]=ans;
cout<<ans<<' ';
}
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
return 0;
}
1.92:开始思考倒序计算 $\color{orange}{TLE}$
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> g[N];
int c[N];bool f[N];
int mr[N];
int ans;
void dfs(int d){
if(mr[d]){
ans=max(ans,mr[d]);
return;
}
for(auto v:g[d]){
if(f[v])continue;
ans=max(ans,v);
f[v]=true;
dfs(v);
}
return;
}
//void bfs(int d){
// queue<int> q;
// q.push(d);
// while(!q.empty()){
// int u=q.front();
// q.pop();
// if(mr[u]){
// ans=max(ans,mr[u]);
// continue;
// }
// for(auto v:g[u]){
// if(f[v])continue;
// ans=max(ans,v);
// f[v]=true;
// q.push(v);
// }
// }
//}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
// g[v].push_back(u);
}
mr[n]=n;
for(int i=n;i>0;--i){
ans=i;
memset(f,0,sizeof(f));
f[i]=true;
dfs(i);
// bfs(i);
mr[i]=ans;
}
for(int i=1;i<=n;++i)
cout<<mr[i]<<' ';
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
return 0;
}
3.0：半开智 $\color{orange}{TLE}$
通过反向存边,逆向反推可到达较大节点的节点，记录其答案为较大节点#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> g[N];
int c[N];bool f[N];
int mr[N];
void dfs(int d){
for(auto v:g[d]){
if(f[v]||mr[d]<mr[v])continue;
f[v]=true;
mr[v]=mr[d];
dfs(v);
}
return;
}
//void bfs(int d){
// queue<int> q;
// q.push(d);
// while(!q.empty()){
// int u=q.front();
// q.pop();
// if(mr[u]){
// ans=max(ans,mr[u]);
// continue;
// }
// for(auto v:g[u]){
// if(f[v])continue;
// ans=max(ans,v);
// f[v]=true;
// q.push(v);
// }
// }
//}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
// g[u].push_back(v);
g[v].push_back(u);
}
for(int i=n;i>0;--i){
mr[i]=max(mr[i],i);
memset(f,0,sizeof(f));
f[i]=true;
dfs(i);
// bfs(i);
}
for(int i=1;i<=n;++i)
cout<<mr[i]<<' ';
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
return 0;
}
3.1：开智 $\color{green}{AC}$
锁定较大节点赋予的答案，较小节点遍历时直接跳过#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> g[N];
int c[N];bool f[N];
int mr[N];
void dfs(int d){
for(auto v:g[d]){
if(f[v]||mr[d]<mr[v])continue;
f[v]=true;
mr[v]=mr[d];
dfs(v);
}
return;
}
//void bfs(int d){
// queue<int> q;
// q.push(d);
// while(!q.empty()){
// int u=q.front();
// q.pop();
// if(mr[u]){
// ans=max(ans,mr[u]);
// continue;
// }
// for(auto v:g[u]){
// if(f[v])continue;
// ans=max(ans,v);
// f[v]=true;
// q.push(v);
// }
// }
//}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
// g[u].push_back(v);
g[v].push_back(u);
}
for(int i=n;i>0;--i){
if(mr[i])continue;
mr[i]=i;
memset(f,0,sizeof(f));
f[i]=true;
dfs(i);
// bfs(i);
}
for(int i=1;i<=n;++i)
cout<<mr[i]<<' ';
// for(int i=1;i<=n;++i){//
// for(auto j:g[i]){//
// cout<<j<<' ';
// }cout<<endl;
// }
return 0;
}