Day53 日志统计（滑动窗口） bfsflood fill算法

日志统计 显然这题用滑动窗口 然后一开始想着滑动窗口就是队列嘛 然后一直想着队列 殊不知可以直接用cnt记录id个数 然后直接用cnt完成滑动 每一个日志条目都完成一次入队，多次出队 每一次入队多次出队完就判断赞数目是否达到

以st做热帖的标记

我一开始还想用set

#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<set> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x%10+'0'); } const int N=1e5+10; ll T; bool st[N]; int cnt[N]; pair<int,int>tex[N]; void solve(){ int n,d,k; cin>>n>>d>>k; int tx,id; for(int i=0;i<n;i++){ cin>>tex[i].first>>tex[i].second; } sort(tex,tex+n); for(int i=0,j=0;i<n;i++){ id=tex[i].second; cnt[id]++; while(tex[i].first-tex[j].first>=d){ cnt[tex[j].second]--; j++; } if(cnt[id]>=k){ st[id]=1; } } for(int i=0;i<=100000;i++){ if(st[i]){ cout<<i<<endl; } } } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } return 0; }

献给阿尔吉侬的花束 我用的是结构体里存储时间 y总是用了dist数组 我觉得我的更好写一些

#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x%10+'0'); } const int N=210; #define PII pair<int,int> ll T; char maze[N][N]; int sx,sy,ex,ey; struct node{ int x,y,t; }; int dx[]={0,0,-1,1},dy[]={1,-1,0,0}; int n,m; bool vis[N][N]; int bfs(){ memset(vis,0,sizeof(vis)); queue<node>q; q.push({sx,sy,0}); while(q.size()){ node now=q.front(); if(now.x==ex&&now.y==ey){ cout<<now.t<<endl; return 1; } q.pop(); for(int i=0;i<4;i++){ int tx=now.x+dx[i],ty=now.y+dy[i]; if(!vis[tx][ty]&&tx>=0&&tx<n&&ty>=0&&ty<m&&maze[tx][ty]!='#'){ vis[tx][ty]=1; q.push({tx,ty,now.t+1}); } } } return 0; } void solve(){ cin>>n>>m; for(int i=0;i<n;i++)cin>>maze[i]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(maze[i][j]=='S'){ sx=i,sy=j; } if(maze[i][j]=='E'){ ex=i,ey=j; } } } if(!bfs()) cout<<"oop!"<<endl; } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); //T=1; cin>>T; while(T--){ solve(); } return 0; }

红与黑 bfs写法

#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x%10+'0'); } #define PII pair<int,int> #define N 30 ll T; int n,m; int ans=0,dx[]={0,0,-1,1},dy[]={1,-1,0,0}; bool vis[N][N]; char maze[N][N]; int bfs(int x,int y){ queue<PII>q; q.push({x,y}); vis[x][y]=1; ans=1; while(!q.empty()){ PII now=q.front(); q.pop(); for(int i=0;i<4;i++){ int tx=now.first+dx[i],ty=now.second+dy[i]; if(tx>=0&&tx<n&&ty>=0&&ty<m&&!vis[tx][ty]&&maze[tx][ty]!='#'){ vis[tx][ty]=1; q.push({tx,ty}); ans++; } } } } void solve(){ for(int i=0;i<n;i++){ cin>>maze[i]; } int sx,sy; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(maze[i][j]=='@'){ sx=i,sy=j; } } } memset(vis,0,sizeof(vis)); bfs(sx,sy); cout<<ans<<endl; } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); //T=1; //cin>>T; while(cin>>m>>n){ if(m==0&&n==0)break; solve(); } return 0; }

dfs写法

#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x%10+'0'); } const int N=30; ll T; char maze[N][N]; int n,m; int sx,sy,ans=0,dx[]={0,0,1,-1},dy[]={1,-1,0,0}; bool vis[N][N]; int dfs(int x,int y){ int cnt=1; vis[x][y]=1; for(int i=0;i<4;i++){ int tx=dx[i]+x,ty=dy[i]+y; if(!vis[tx][ty]&&tx>=0&&tx<n&&ty>=0&&ty<m&&maze[tx][ty]!='#'){ cnt+=dfs(tx,ty); } } return cnt; } void solve(){ for(int i=0;i<n;i++){ cin>>maze[i]; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(maze[i][j]=='@'){ sx=i,sy=j; } } } memset(vis,0,sizeof(vis)); ans=0; cout<<dfs(sx,sy)<<endl; } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(cin>>m>>n){ if(m==0&&n==0){ break; } solve(); } return 0; }