526互联

AtCoder Beginner Contest 复盘合集

发布时间 2023-12-06 22:04:53作者: gsczl71

AtCoder Beginner Contest 复盘合集

2023.12.6 ABC312 VP（OI赛制）

这次的ABC相对比较难：红橙黄黄蓝绿绿，Ex(蓝)

A：

#include <bits/stdc++.h>
using namespace std;
vector<string> v;
signed main(){
    v.push_back("ACE");
    v.push_back("BDF");
    v.push_back("CEG");
    v.push_back("DFA");
    v.push_back("EGB");
    v.push_back("FAC");
    v.push_back("GBD");
    string s;
    cin>>s;
    for(auto it:v){
        if(it==s){
            cout<<"Yes\n";
            return 0;
        }
    }cout<<"No\n";
    return 0;
}

B：稍微麻烦一点。

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 225;
int n,m;
string s[N];
bool check(int x,int y){
    for(int i = x;i <= x+2;i++){
        for(int j = y;j <= y+2;++j){
            if(s[i][j] != '#')return false;
        }
    }for(int i = x;i <= x+3;++i){
        if(s[i][y+3] != '.') return false;
    }for(int i = y;i <= y+3;++i){
        if(s[x+3][i] != '.') return false;
    }

    for(int i = x+6;i<= x+8;i++){
        for(int j = y+6;j<= y+8;j++){
            if(s[i][j] != '#') return false;
        }
    }
    for(int i = x+5;i <= x+8;i++){
        if(s[i][y+5] != '.') return false;
    }
    for(int i = y+5;i <= y+8;i++){
        if(s[x+5][i] != '.') return false;
    }return true;
}
signed main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> s[i];
        s[i] = ' '+s[i];
    } 
    for(int i = 1;i <= n-8;i++){
        for(int j = 1;j <= m-8;j++){
            if(check(i,j)){
                cout<<i<<" "<<j<<endl;
            }
        }
    }
    return 0;
}

C：很水，直接Sort一遍即可。

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 4e5+5;
struct node{
    int x,id;
}a[N];
bool cmp(node a,node b){
    return a.x<b.x; 
}
signed main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> a[i].x;
        a[i].id=0;
    }for(int i = n+1;i <= n+m;i++){
        cin >> a[i].x;
        a[i].x++;
        a[i].id=1;
    }n = n + m;
    sort(a+1,a+1+n,cmp);
    int cnt1=m,cnt2=0;
    for(int i = 1;i <= n;i++){
        if(a[i].id){
            cnt1--;
        }else{
            cnt2++;
        }if(cnt1 <= cnt2){
            cout<<a[i].x;
            exit(0);
        }
    }
    return 0;
}

D：稍微思考，可以得出一个DP，准确来说不太像DP

#include <bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
string s;
int dp[3005][3005];
signed main(){
    cin >>s;
    int n=s.size();
    s=' '+s;
    dp[0][0]=1;
    for(int i = 1;i <= n;i++){
        if(s[i] == '('){
            for(int j = n;j >= 0;j--){
                dp[i][j+1] = dp[i-1][j] % mod;
            }
        }else if(s[i] == ')'){
            for(int j=1;j <= n;j++){
                dp[i][j-1] = dp[i-1][j] % mod;
            }
        }else{
            for(int j=1;j <= n;j++){
                dp[i][j-1] += dp[i-1][j] % mod;
            }for(int j = n;j >= 0;j--){
                dp[i][j+1] += dp[i-1][j] % mod;
            }
        }
    }cout<<dp[n][0] % mod <<endl;
    return 0;
}

我非常的弱智，\(n <= 3000\) 赛时写成1000。因为OI赛制，所以很弱智的挂分。

赛时因为无脑写压维被卡，换成二维即可过掉。

E：其实我一开始也是认为要维护每一个面，也就是每一个坐标，然后进行前缀和或者差分，但是觉得很复杂。后面突然间想到，其实暴力即可。为什么？因为如果你 \(n\) 个输入都直接遍历他的每一个 \(x,y,z\) 都是没有问题的。理论上会达到 \(n * 100^3\) 肯定会TLE。但是题目中有一个条件 每一个长方体的题解没有相交。意味着我们最多只会遍历 \(100^3\) 。非常nice。然后存到一个三维的数组当中后：

我们可以通过六个面来看周围是不是其他长方体，但是我们发现如果你往 \((x+1,y,z)\) 和 \((x-1,y,z)\) 是等价的。这是啥意思呢？因为你的 \(x-1\) 可以由 \(x-1\) 来判断它的 \(x+1\)(也就是 \(x\))来解决。

于是呢我们就可以通过三个if来判断。我真聪明。

然后再用一个set维护即可。

时间充裕：$O(100^3\times \log n) $ 非常轻松水了一道蓝。。

准确来说这应该是绿吧。

const int N = 1e5+5;
const int M = 105;
int n;
int a[M][M][M];
set<int> st[N];
void solve(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        int x1,y1,z1,x2,y2,z2;
        cin >> x1 >> y1>> z1>>x2>>y2>>z2;
        for(int x = x1+1;x<=x2;x++){
            for(int y = y1+1;y<=y2;y++){
                for(int z = z1+1;z<=z2;z++){
                    a[x][y][z] = i;
                }
            }
        }
    }
    for(int x = 1;x <= 100;x++){
        for(int y = 1;y <= 100;y++){
            for(int z = 1;z <= 100;z++){
                if(a[x][y][z] == 0) continue;
                if(a[x+1][y][z] != a[x][y][z] && a[x+1][y][z]) st[a[x][y][z]].insert(a[x+1][y][z]),st[a[x+1][y][z]].insert(a[x][y][z]);
                if(a[x][y+1][z] != a[x][y][z] && a[x][y+1][z]) st[a[x][y][z]].insert(a[x][y+1][z]),st[a[x][y+1][z]].insert(a[x][y][z]);
                if(a[x][y][z+1] != a[x][y][z] && a[x][y][z+1]) st[a[x][y][z]].insert(a[x][y][z+1]),st[a[x][y][z+1]].insert(a[x][y][z]);
            }
        }
    }

    for(int i = 1;i <= n;i++){
        cout<<st[i].size()<<endl;
    }
}

F：赛后发现巨水。可以说是思考10s，码量2min，调1.5h

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
const int N = 2E5+5;
int a[N],b[N],c[N];
int f[N],g[N];
bool cmp(int a,int b){
    return a > b;
}
signed main() {
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        int t,x;
        cin >> t >> x;
        if(t==0) a[++a[0]] = x;//先分类
        else if(t==1) b[++b[0]] = x;
        else c[++c[0]] = x;
    }
    sort(a+1,a+1+a[0],cmp);//排序
    sort(b+1,b+1+b[0],cmp);
    sort(c+1,c+1+c[0],cmp);

    for(int i = 1;i <= a[0];i++){//前缀和a
        f[i] = f[i-1] + a[i];
    }    
    int res=0,ci=0;
    int cnt=0;
    for(int i = 1;i <= b[0];i++){//g[i]记录当取i个b或c时的最大收获。
    //res为ci个c能够开多少个b
        while(res < i && ci < c[0]) res += c[++ci];
        if(res<i) break;
        g[ci+i-1] = max(g[ci+i-1],cnt);
        cnt+=b[i];
        g[ci+i]=cnt;
    }
    for(int i =1;i <= m;i++){
        f[i] = max(f[i],f[i-1]);
    }
    int ans=0;
    for(int i = 0;i <= m;i++){
        ans=max(ans,g[i]+f[m-i]);
    }
    cout<<ans;
    return 0;
}

甚至还请了何竺凌来帮我调。。。

最后发现的问题是在：

for(int i =1;i <= m;i++){
        f[i] = max(f[i],f[i-1]);
}

整体思路是算t=0的部分的答案，和t=1，t=2的答案，然后最后组合在一起即可。

但是会发现如果需要选6个，但是只有2个可以选，那么会出现中间是空的，无法组合 ，这样，我们只需要把f数组渲染一遍即可。

总结：

这次其实F挺水的。大概是正常的D。赛时没切F主要是时间不够，而且一直认F是很难的。所以没搞F。然后D耽误了一点时间，总体来说发挥不太好。（OI赛制嘛，一般来说正常AT我都是罚时吃饱。。