AtCoder Beginner Contest 311
思路:找到第一个a,b,c都出现的位置
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; void solve(){ int n;cin>>n; string s; cin>>s; int a=0,b=0,c=0; for(int i=0;i<n;++i){ if(s[i]=='A')a=1; if(s[i]=='B')b=1; if(s[i]=='C')c=1; if(a&&b&&c){ cout<<i+1; return ; } } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //init(); //cin>>t; while(t--){ solve(); } return 0; }
思路:找到最大的连续'o'的列长度
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; void solve(){ int n,d,ans=0;cin>>n>>d; vector<string>ve(n); for(int i=0;i<n;++i)cin>>ve[i]; char pre='o'; for(int i=0,c=0;i<d;++i){ bool ok=true; for(int j=1;j<n;++j)if(ve[j][i]!=ve[j-1][i]){ ok=false;break; } if(ok&&ve[0][i]==pre)c++; else c=0; ans=max(ans,c); } cout<<ans; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //init(); //cin>>t; while(t--){ solve(); } return 0; }
思路:每个点都指向一点,那么一定有环,从一点开始搜,搜到搜过的点即找到环
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; int n; vector<int>ve(N); vector<int>st(N); int dfs(int u){ if(st[u]){ return u; } st[u]=1; return dfs(ve[u]); } void solve(){ cin>>n; for(int i=1;i<=n;++i){ cin>>ve[i]; } st[1]=1; int res=dfs(ve[1]); vector<int>ans; int p=ve[res]; ans.push_back(res); while(p!=res){ ans.push_back(p); p=ve[p]; } cout<<ans.size()<<'\n'; for(auto v:ans)cout<<v<<' '; } signed main(){ //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //init(); //cin>>t; while(t--){ solve(); } return 0; }
思路:从(1,1)开始bfs,一个方向要搜到底,标记搜过的点,最后统计
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; int n,m,ans=0; vector<string>s(205); int st[205][205],vis[205][205]; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; void bfs(int x,int y){ queue<PII>q; q.push({x,y}); st[1][1]=vis[1][1]=1; while(q.size()){ auto [u,v]=q.front();q.pop(); for(int i=0;i<4;++i){ int xx=u,yy=v; while(s[xx+dx[i]][yy+dy[i]]!='#'){ xx+=dx[i],yy+=dy[i]; vis[xx][yy]=1; } if(!st[xx][yy]){ q.push({xx,yy}); st[xx][yy]=1; } } } for(int i=0;i<n;++i) for(int j=0;j<m;++j)ans+=vis[i][j]; } void solve(){ cin>>n>>m; for(int i=0;i<n;++i){ cin>>s[i]; } bfs(1,1); cout<<ans; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //init(); //cin>>t; while(t--){ solve(); } return 0; }
思路:把洞的地方标为1,用前缀和判断是否为正方形。枚举每个点,二分找到以该点为右下角的最大正方形
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=3e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const int inf=0x3f3f3f3f3f3f; const double eps=1e-6; const int dx[4]={-1,0,1,0}; const int dy[4]={0,1,0,-1}; int h,w,n; int a[N][N]; void solve(){ cin>>h>>w>>n; for(int i=0,u,v;i<n;++i){ cin>>u>>v; a[u][v]=1; } int res=0; for(int i=1;i<=h;++i) for(int j=1;j<=w;++j){ if(!a[i][j]){ a[i][j]+=(a[i-1][j]+a[i][j-1]-a[i-1][j-1]); int l=0,r=min(i,j)-1,k; while(l<=r){ int mid=l+r>>1; auto check=[&](int x){ int ii=i-x,jj=j-x; int s=a[i][j]-a[i][jj-1]-a[ii-1][j]+a[ii-1][jj-1]; return !s; }; if(check(mid))k=mid,l=mid+1; else r=mid-1; } //cout<<i<<' '<<j<<':'<<k<<'\n'; res+=(k+1); } else a[i][j]+=(a[i-1][j]+a[i][j-1]-a[i-1][j-1]); } cout<<res; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; //init(); //cin>>T; while(T--){ solve(); } return 0; }
- Beginner AtCoder Contest 311beginner atcoder contest 311 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310