练习记录-AtCoder Beginner Contest 311-(A-E)

写的还挺顺的 F之后补

A - First ABC

找abc三个字母什么时候出现了一次 输出即可

B - Vacation Together

题意：最长的几个人一排里面均有时间

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
string s[MAXN];
void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=" "+s[i]; 
    }
    int cnt=0,maxs=0;
    for(int i=1;i<=m;i++){
        int flag=1;
        for(int j=1;j<=n;j++){
            if(s[j][i]=='x') flag=0; 
        }
        if(flag==1){
            cnt++;
        }
        else cnt=0;
        maxs=max(cnt,maxs);
    }
    cout<<maxs;
}
signed main(){
    solve();
}

C - Find it!

题意：输出任意一个环

解法：暴力找每个点，找到环就输出，最坏情况复杂度O(n)

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
int a[MAXN];
int vis[MAXN];
vector<int> ans;
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        //pre[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
         if(vis[i]) continue;
         vis[i]=1;
         int k=i;
         while(1){
             k=a[k];
             if(!vis[a[k]])
             vis[a[k]]=1;
             else{
                 int now=k;
                 ans.push_back(now);
                 while(a[k]!=now){
                     ans.push_back(a[k]);
                     k=a[k];
                 }
                 return;
             }
         }
    }
}
signed main(){
    solve();
    cout<<ans.size()<<"\n";
    for(auto &it:ans) cout<<it<<" ";
}

D - Grid Ice Floor

题意：从（2，2）开始模拟溜冰，求可以划过的冰的块数

解法：对每个各自，存4个方向的状态的vis，一个点由上面一个点递推来的时候，方向是不变的，如果（x,y)递推的下一个点是墙，那么把这个(x,y)换3个方向重新push进队列类似bfs处理方式

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
char mp[300][300];
int fx[4][2]={-1,0,1,0,0,-1,0,1};
int vis[300][300][4];
void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cin>>mp[i][j];
    }
    queue<array<int,3> > que;
    que.push({2,2,0});
    que.push({2,2,1});
    que.push({2,2,2});
    que.push({2,2,3});
    for(int i=0;i<4;i++) vis[2][2][i]=1;
    while(que.size()){
        int x=que.front()[0],y=que.front()[1],z=que.front()[2];
        que.pop();
        int xx=x+fx[z][0],yy=y+fx[z][1];
        if(xx<1||yy<1||xx>n||yy>m||vis[xx][yy][z]) continue;
        vis[xx][yy][z]=1;
        if(mp[xx][yy]=='.'){
            que.push({xx,yy,z});
        }
        else{
            for(int i=0;i<4;i++){
                if(vis[x][y][i]==0&&i!=z) {
                    que.push({x,y,i});
                    vis[x][y][i]=1;
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mp[i][j]=='.'&&(vis[i][j][0]||vis[i][j][1]||vis[i][j][2]||vis[i][j][3])) ans++; 
        }
    }
    cout<<ans;
}
signed main(){
    solve();
}

E - Defect-free Squares

题意：统计没有洞的正方形数量，题目给出洞的位置；

解法：考虑二分+二位前缀和预处理

枚举一个点(i,j)作为左上角顶点，那么以这个顶点为左上角构成的最大方块数量就是最大的没有洞的正方形边长。对于边长我们可以用二分答案降低时间复杂度。用二维前缀和可以维护任意一个矩形内洞的数量

时间复杂度O(n^2logn)

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
int mp[3010][3010];
int pre[3010][3010];
bool check(int x,int y,int mid){
    int xx=x+mid-1;
    int yy=y+mid-1;
    int ans=pre[xx][yy]-pre[x-1][yy]-pre[xx][y-1]+pre[x-1][y-1];
    if(ans==0) return true;
    else return false;
}
void solve(){
    int n,m,q;cin>>n>>m>>q;
    int ans=0;
    for(int i=1;i<=q;i++){
        int x,y;cin>>x>>y;
        mp[x][y]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            pre[i][j]=pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1]+mp[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mp[i][j]==1) continue;
            int l=1,r=min(n-i+1,m-j+1);
            while(l<=r){
                int mid=l+r>>1;
                if(check(i,j,mid)){
                    l=mid+1;
                }
                else r=mid-1;
            }
            ans+=r;
        }
    }
    cout<<ans;
}
signed main(){
    solve();
}

注意存图用数组 map会超时