AtCoder Beginner Contest 311

AtCoder Beginner Contest 311

First ABC

思路：找到第一个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;
}

Vacation Together

思路：找到最大的连续'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;
}

Find it!

思路：每个点都指向一点，那么一定有环，从一点开始搜，搜到搜过的点即找到环

#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;
}

Grid Ice Floor

思路：从（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;
}

 Defect-free Squares

思路：把洞的地方标为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;
}