目录

• 1238. 日志统计 【双指针】
• 1101. 献给阿尔吉侬的花束 【BFS】
• 1113. 红与黑 【BFS】
• 1224. 交换瓶子 【思维 / 环】
• 1240. 完全二叉树的权值 【规律】
• 1096. 地牢大师 【BFS】
• 1233. 全球变暖 【BFS】
• 1207. 大臣的旅费 【树的直径】
• 826. 单链表

1238. 日志统计 【双指针】

题目详解

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
int n,d,k,a[N];
vector<PII> ve;
map<int,int>mp;
int main(void)
{cin>>n>>d>>k;while(n--){int t,id; cin>>t>>id;ve.push_back({t,id});}sort(ve.begin(),ve.end());for(int i=0,j=0;i<ve.size();i++){a[ve[i].second]++;while(ve[i].first>=ve[j].first+d) {a[ve[j].second]--,j++;}if(a[ve[i].second]>=k) mp[ve[i].second]++;}for(auto i=mp.begin();i!=mp.end();i++) cout<<i->first<<endl;return 0;
}

1101. 献给阿尔吉侬的花束 【BFS】

https://www.acwing.com/problem/content/1103/

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
char mp[N][N];
int vis[N][N],n,m,t,startx,starty,endx,endy,ans;
bool flag;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
struct node
{int x,y,step;
}Node;
void bfs(int x,int y)
{vis[x][y]=1;Node.x=x,Node.y=y,Node.step=0;queue<node> q;  q.push(Node);while(q.size()){auto t=q.front(); q.pop();x=t.x;y=t.y;int d=t.step;for(int i=0;i<4;i++){int tempx=x+dx[i];int tempy=y+dy[i];if(tempx>=0&&tempx<n&&tempy>=0&&tempy<m&&!vis[tempx][tempy]&&mp[tempx][tempy]!='#'){Node.x=tempx,Node.y=tempy,Node.step=d+1;vis[tempx][tempy]=1;q.push(Node);if(Node.x==endx&&Node.y==endy){ans=Node.step;flag=true;return;}}}}
}
int main(void)
{cin>>t;while(t--){flag=false;ans=0;memset(vis,0,sizeof vis);cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>mp[i][j];if(mp[i][j]=='S') startx=i,starty=j;if(mp[i][j]=='E') endx=i,endy=j;}}bfs(startx,starty);if(flag) cout<<ans<<endl;else puts("oop!");}
}

y总的写法:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>#define x first
#define y secondusing namespace std;typedef pair<int,int>PII;const int N=210;int n,m;
char g[N][N];
int dist[N][N];int bfs(PII start,PII end)
{queue<PII> q;memset(dist,-1,sizeof dist);dist[start.x][start.y]=0;q.push(start);int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};while(q.size()){auto t=q.front();q.pop();for(int i=0;i<4;i++){int x=t.x+dx[i],y=t.y+dy[i];if(x<0||x>=n||y<0||y>=m) continue;//过界了if(g[x][y]=='#') continue;//墙if(dist[x][y]!=-1) continue;//走过了dist[x][y]=dist[t.x][t.y]+1;if(end==make_pair(x,y)) return dist[x][y];q.push({x,y});}}return -1;
}
int main(void)
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++) scanf("%s",g[i]);PII start,end;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(g[i][j]=='S') start={i,j};else if(g[i][j]=='E') end={i,j};int distance=bfs(start,end);if(distance==-1) puts("oop!");else printf("%d\n",distance);}return 0;
}

1113. 红与黑 【BFS】

https://www.acwing.com/problem/content/1115/

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;const int N=210;int m,n;
int ans;
char map[N][N];
bool vis[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
struct node
{int x,y;
}Node;
void bfs(int x,int y)
{Node.x=x;Node.y=y;ans=1;vis[x][y]=true;queue<node>q;q.push(Node);while(!q.empty()){node top=q.front();q.pop();for(int i=0;i<4;i++){int tempx=top.x+dx[i];int tempy=top.y+dy[i];if(tempx>=1&&tempx<=n&&tempy>=1&&tempy<=m&&map[tempx][tempy]!='#'&&!vis[tempx][tempy]) {node m;m.x=tempx;m.y=tempy;ans++; vis[tempx][tempy]=true;q.push(m);}}}
}
int main(void)
{while(cin>>m>>n,m||n){int startx,starty;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>map[i][j]; if(map[i][j]=='@'){startx=i;starty=j;}}	}ans=0;bfs(startx,starty);memset(vis,0,sizeof vis);cout<<ans<<endl;}return 0;
}

DFS写法:

#include<string>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;const int N=25;int n,m;
char g[N][N];
bool st[N][N];int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};int dfs(int x,int y)
{int cnt=1;st[x][y]=true;for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if(a<0||a>=n||b<0||b>=m) continue;if(g[a][b]!='.') continue;if(st[a][b]) continue;cnt+=dfs(a,b);}return cnt;
}
int main(void)
{while(cin>>m>>n,n||m){for(int i=0;i<n;i++) cin>>g[i];int x,y;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(g[i][j]=='@'){x=i;y=j;}memset(st,0,sizeof st);cout<<dfs(x,y)<<endl;}return 0;
}

#include<bits/stdc++.h>
using namespace std;
char mp[30][30];
int vis[30][30];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int cnt,n,m,startx,starty;
void dfs(int x,int y)
{vis[x][y]=1;for(int i=0;i<4;i++){int tempx=x+dx[i],tempy=y+dy[i];if(tempx>=0&&tempx<m&&tempy>=0&&tempy<n&&!vis[tempx][tempy]&&mp[tempx][tempy]=='.'){dfs(tempx,tempy);cnt++;}}
}
int main(void)
{while(cin>>n>>m,n||m){cnt=0;memset(vis,0,sizeof vis);for(int i=0;i<m;i++){for(int j=0;j<n;j++){cin>>mp[i][j];if(mp[i][j]=='@') startx=i,starty=j;}}dfs(startx,starty);cout<<cnt+1<<endl;}return 0;
}

1224. 交换瓶子 【思维 / 环】

题目详解

#include<iostream>
using namespace std;const int N=10010;
int s[N];
int vis[N];
int n,cnt;int main()
{cin>>n;for(int i=1;i<=n;i++) scanf("%d",&s[i]);for(int i=1;i<=n;i++){if(!vis[s[i]]){for(int j=s[i];!vis[j];j=s[j]) vis[j]=1;cnt++;}}cout<<n-cnt;return 0;
}

1240. 完全二叉树的权值 【规律】

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=1e5+10;
LL a[N],n,ans,h;
int main(void)
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];LL j=1;ans=-1e18;for(LL i=1;i<=n;i++){LL temp=0;LL k=j;if(i!=1) k+=pow(2,i-1),k--;for(;j<=min(n,k);j++) temp+=a[j];if(temp>ans) ans=temp,h=i;if(j>n) {cout<<h<<endl;return 0;}}return 0;
}

1096. 地牢大师 【BFS】

https://www.acwing.com/problem/content/description/1098/
y总代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;const int N=110;struct Point
{int x,y,z;
};int L,R,C;
char g[N][N][N];
Point q[N*N*N];
int dist[N][N][N];int dx[6]={1,-1,0,0,0,0};
int dy[6]={0,0,1,-1,0,0};
int dz[6]={0,0,0,0,1,-1};int bfs(Point start,Point end)
{int hh=0,tt=0;q[0]=start;memset(dist,-1,sizeof dist);dist[start.x][start.y][start.z] = 0;while(hh<=tt){auto t=q[hh++];//取队首元素，并出队for(int i=0;i<6;i++){int x=t.x+dx[i],y=t.y+dy[i],z=t.z+dz[i];if(x<0||x>=L||y<0||y>=R||z<0||z>=C) continue;if(g[x][y][z]=='#') continue;if(dist[x][y][z]!=-1) continue;dist[x][y][z]=dist[t.x][t.y][t.z]+1;if(x==end.x&&y==end.y&&z==end.z) return dist[x][y][z];q[++tt]={x,y,z};//入队}}return -1;
}
int main(void)
{while(scanf("%d%d%d",&L,&R,&C),L||R||C){Point start,end;for(int i=0;i<L;i++){for(int j=0;j<R;j++){scanf("%s",g[i][j]);for(int k=0;k<C;k++){char c=g[i][j][k];if(c=='S') start={i,j,k};else if(c=='E') end={i,j,k};}}}int distance=bfs(start,end);if(distance==-1) puts("Trapped!");else printf("Escaped in %d minute(s).\n",distance);}return 0;
} 

#include<bits/stdc++.h>
using namespace std;
const int N=105;
char mp[N][N][N];
int vis[N][N][N];
bool flag;
int n,m,k,ans;
int startx,starty,startz,endx,endy,endz;
int dx[6]={0,0,-1,0,1,0};
int dy[6]={0,0,0,1,0,-1};
int dz[6]={-1,1,0,0,0,0};
struct node
{int x,y,z,step;
}Node;
void bfs(int x,int y,int z)
{vis[z][x][y]=1;Node.x=x,Node.y=y,Node.z=z,Node.step=0;queue<node> q; q.push(Node);while(q.size()){auto t=q.front(); q.pop();x=t.x,y=t.y,z=t.z;int d=t.step;for(int i=0;i<6;i++){int tempx=x+dx[i];int tempy=y+dy[i];int tempz=z+dz[i];if(tempx>=0&&tempx<n&&tempy>=0&&tempy<m&&tempz>=0&&tempz<k&&!vis[tempz][tempx][tempy]){if(mp[tempz][tempx][tempy]!='#'){Node.x=tempx,Node.y=tempy,Node.z=tempz,Node.step=d+1;q.push(Node);vis[tempz][tempx][tempy]=1;if(tempx==endx&&tempy==endy&&tempz==endz){ans=Node.step;flag=true;return;}}}}   }
}
int main(void)
{while(scanf("%d%d%d",&k,&n,&m),k||n||m){ans=0;memset(vis,0,sizeof vis);flag=false;for(int i=0;i<k;i++){for(int j=0;j<n;j++){for(int z=0;z<m;z++){cin>>mp[i][j][z];if(mp[i][j][z]=='S') startx=j,starty=z,startz=i;if(mp[i][j][z]=='E') endx=j,endy=z,endz=i;}}}bfs(startx,starty,startz);if(flag) printf("Escaped in %d minute(s).\n",ans);else puts("Trapped!");}return 0;
}

1233. 全球变暖 【BFS】

https://www.acwing.com/problem/content/1235/
经典的BFS，不过要写一个check()函数来判断当前块是不是挨着海的。同时记录当前一个连通块的总的块数。
总的块数-挨着海的块数等于0说明淹没了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;const int N=1010;char map[N][N];
bool vis[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int n;
int ans1,ans2;//ans1  一个陆地总的块数  ans2一个陆地挨着海的块数 
int sum;
struct node
{int x,y;
}Node;
bool check(int x,int y)
{for(int i=0;i<4;i++){int tempx=x+dx[i];int tempy=y+dy[i];if(tempx>=1&&tempx<=n&&tempy>=1&&tempy<=n&&map[tempx][tempy]=='.'){return true;}}return false;
}
void bfs(int x,int y)
{Node.x=x;Node.y=y;vis[x][y]=true;ans1++;if(check(x,y)) ans2++; queue<node>q;q.push(Node);while(!q.empty()){node top=q.front();q.pop();for(int i=0;i<4;i++){int tempx=top.x+dx[i];int tempy=top.y+dy[i];if(tempx>=1&&tempx<=n&&tempy>=1&&tempy<=n&&map[tempx][tempy]=='#'&&!vis[tempx][tempy]){node m;m.x=tempx;m.y=tempy;vis[tempx][tempy]=true;ans1++;if(check(tempx,tempy)) ans2++;q.push(m);}}}
}
int main(void)
{cin>>n;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)cin>>map[i][j];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(map[i][j]=='#'&&!vis[i][j]){ans1=ans2=0;bfs(i,j);if(ans1-ans2==0) sum++;}}}cout<<sum<<endl;return 0;
}

y总代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 1010;int n;
char g[N][N];
bool st[N][N];
PII q[N * N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};void bfs(int sx, int sy, int &total, int &bound)
{int hh = 0, tt = 0;q[0] = {sx, sy};st[sx][sy] = true;while (hh <= tt){PII t = q[hh ++ ];total ++ ;bool is_bound = false;for (int i = 0; i < 4; i ++ ){int x = t.x + dx[i], y = t.y + dy[i];if (x < 0 || x >= n || y < 0 || y >= n) continue;  // 出界if (st[x][y]) continue;if (g[x][y] == '.'){is_bound = true;continue;}q[ ++ tt] = {x, y};st[x][y] = true;}if (is_bound) bound ++ ;}
}int main()
{scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);int cnt = 0;for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )if (!st[i][j] && g[i][j] == '#'){int total = 0, bound = 0;bfs(i, j, total, bound);if (total == bound) cnt ++ ;}printf("%d\n", cnt);return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char mp[N][N];
int vis[N][N],n,sum,ans;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool check(int x,int y)
{for(int i=0;i<4;i++){int tempx=x+dx[i];int tempy=y+dy[i];if(tempx>=0&&tempx<n&&tempy>=0&&tempy<n&&mp[tempx][tempy]!='#') return false;}return true;
}
void dfs(int x,int y)
{vis[x][y]=1;if(check(x,y)) ans++;for(int i=0;i<4;i++){int tempx=x+dx[i];int tempy=y+dy[i];if(tempx>=0&&tempx<n&&tempy>=0&&tempy<n&&!vis[tempx][tempy]&&mp[tempx][tempy]=='#')dfs(tempx,tempy);}return;
}
int main(void)
{cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>mp[i][j];for(int i=0;i<n;i++){for(int j=0;j<n;j++){ans=0;if(vis[i][j]) continue;if(mp[i][j]=='#'){dfs(i,j);if(ans==0) sum++;}}}cout<<sum;return 0;
}

1207. 大臣的旅费 【树的直径】

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct edge
{int id,w;
};
vector<edge> h[N];
int n,dist[N];
void dfs(int u,int father,int d)
{dist[u]=d;for(int i=0;i<h[u].size();i++){if(h[u][i].id!=father) dfs(h[u][i].id,u,d+h[u][i].w);}
}
int main(void)
{cin>>n;for(int i=0;i<n-1;i++){int a,b,c; cin>>a>>b>>c;h[a].push_back({b,c});h[b].push_back({a,c});}dfs(1,-1,0);int u=1;for(int i=1;i<=n;i++) if(dist[i]>dist[u]) u=i;dfs(u,-1,0);for(int i=1;i<=n;i++) if(dist[i]>dist[u]) u=i;int s=dist[u];printf("%lld\n",s*10+(s+1ll)*s/2);return 0;
}

826. 单链表

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],idx,head,n;
void init()
{head=-1;idx=0;
}
void head_add(int a)
{e[idx]=a,ne[idx]=head,head=idx++;
}
void add(int a,int b)
{e[idx]=b,ne[idx]=ne[a],ne[a]=idx++;
}
void remove(int x)
{ne[x]=ne[ne[x]];
}
int main(void)
{init();cin>>n;while(n--){string op; cin>>op;if(op=="H"){int x; cin>>x; head_add(x);}if(op=="D"){int x; cin>>x;if(x)remove(x-1);else head=ne[head];}if(op=="I"){int a,b; cin>>a>>b;add(a-1,b);}}for(int i=head;i!=-1;i=ne[i]) cout<<e[i]<<" ";return 0;
}