Yoshino-nya's blog

主题

AtCoder Beginner Contest 395

2025-03-01

AtCoder Beginner Contest 395 ​

赛时只出了ABCD，E其实也只是个绿题，刚才补的时候倒是很快就A了，赛时写得时候没多少时间了，且方法错了，我怎么上来直接写dfs，想吃TLE了。

A ​

直接判断就行了。我没注意还不能相等，然后用了is_sorted()，且只测了前两个样例喜提WA。

cpp
void solve()
{
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=1;i<n;i++){
        if(a[i]<=a[i-1]){
            cout<<"No\n";
            return;
        }
    }
    cout<<"Yes\n";
}

B ​

直接模拟就行了。

cpp
void solve()
{
    int n;
    cin>>n;
    vector<vector<char>>s(n+1,vector<char>(n+1));
    for(int i=1;i<=n;i++){
        int j=n-i+1;
        if(j<i) continue;
        for(int k=i;k<=j;k++)
            for(int l=i;l<=j;l++){
                if(i&1) s[k][l]='#';
                else s[k][l]='.'; 
            }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<s[i][j];
        }
        cout<<'\n';
    }
}

C ​

记一下上一次出现的位置，然后每次遇到就更新就行了。

cpp
constexpr int N = 1e6;

int lst[N+1];

void solve()
{
    int n;
    cin>>n;
    vector<int>a(n+1);
    int ans=n+1;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(lst[x]){
            ans=min(ans,i-lst[x]+1);
        }
        lst[x]=i;
    }
    cout<<(ans==n+1?-1:ans)<<'\n';
}

D ​

稍微有点操作啊，控了我一个小时。

其实主要就是思路没想明白，非常的混乱，现在来稍微整理一下。

这个操作 2 需要交换 a 和 b 里面装的鸟。我们肯定不能真的去换，因为更新每个鸟的家复杂度非常高。

我们可以只改变它们代表的值，比如说原本每个人的家就是 i ，那我现在交换 1 和 2 ，怎么能使得不用改每一个成员的家呢？

我们其实相当于可以只用改这两个巢的编号，比如说我们要交换 a 和 b 这两个巢的内容，那其实也相当于把 a 的编号改成 b ，b 改成 a 。

我们可以先设 homei 代表的是第 i 只鸟的家。假设我们需要交换 1 和 2 ，我们可以想办法修改它们映射的值。即用一个数组表示原始的第 i 个巢穴现在它的位置是多少。比如 pi 代表第 i 个巢穴的位置。

那么我们要输出 i 的家需要输出 phomei ，homei 代表第 i 只鸟，它现在的家的最开始的位置。然后 pi 就可以表示当初第 i 个位置的巢现在所在的位置。

那么我们如果要交换两个巢，只需要交换它们对应的 p 值。

但是我们需要交换巢 a 和 b 时，这里给的是巢的位置，我们的 p 记的是最开始的位置的巢的现在的位置。所以我们还需要记一下每个位置当前放的是哪一个巢。

这个更简单实现，直接用一个 pos 数组实现，只有操作 2 会移动鸟巢。那么我们就交换 posa 和 posb 代表就换 a 和 b 位置上的鸟巢。

然后再交换 homeposa 和 homeposb ，即交换两个实际的鸟巢的对应的值。

cpp
void solve()
{
    int n,q;
    cin>>n>>q;
    vector<int>home(n+1);
    vector<int>p(n+1),pos(n+1);
    for(int i=1;i<=n;i++)
        home[i]=p[i]=pos[i]=i;
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int a,b;
            cin>>a>>b;
            home[a]=pos[b];
            //我们还得知道 哪个pi 等于 b...
            //这样好像也不对，纯乱写了一坨。。。
        }else if(op==2){
            int a,b;
            cin>>a>>b;
            //p[30]不就是8吗？
            swap(p[pos[a]],p[pos[b]]);
            //p[rev[b]] p[xx]=b
            swap(pos[a],pos[b]);
            // cerr<<p[a]<<" "<<p[b]<<'\n';
            // rev[p[p[a]]]=p[a],p[p[b]]=p[b];
        }else{
            int a;
            cin>>a;
            cout<<p[home[a]]<<'\n';
        }
        // for(int i=1;i<=n;i++)
        //     cerr<<p[i]<<" \n"[i==n];
        // for(int i=1;i<=n;i++)
        //     cerr<<rev[i]<<" \n"[i==n];
    }
    // cerr<<rev[7]<<" "<<rev[8]<<" "<<rev[30]<<'\n';
}

E ​

感觉确实 dijkstra 板题。只是稍微记一下每一个点的状态就行了。

cpp
void solve()
{
    int n, m, x;
    cin >> n >> m >> x;
    set<pair<int, int>> edges;
    vector<vector<int>> adj(n + 1, vector<int>());
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        edges.insert({ u, v });
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<long long> cost(n + 1, 1e18);
    vector<vector<long long>> dis(n + 1, vector<long long>(2, 1e18));
    dis[1][0] = 0;
    auto dijkstra = [&]() {
        priority_queue<array<long long, 3>, vector<array<long long, 3>>, greater<>> pq;
        pq.push({ 0, 1, 0 }); // 距离 编号 状态
        while (!pq.empty()) {
            auto [d, u, rev] = pq.top();
            pq.pop();
            if (d > dis[u][rev])
                continue;
            for (auto v : adj[u]) {
                if (rev) {
                    if (edges.contains({ v, u })) {
                        if (dis[u][rev] + 1 < dis[v][rev]) {
                            dis[v][rev] = dis[u][rev] + 1;
                            pq.push({ dis[v][rev], v, rev });
                        }
                    } else {
                        if (dis[u][rev] + x + 1 < dis[v][rev ^ 1]) {
                            dis[v][rev ^ 1] = dis[u][rev] + x + 1;
                            pq.push({ dis[v][rev ^ 1], v, rev ^ 1 });
                        }
                    }
                } else {
                    if (edges.contains({ u, v })) {
                        if (dis[u][rev] + 1 < dis[v][rev]) {
                            dis[v][rev] = dis[u][rev] + 1;
                            pq.push({ dis[v][rev], v, rev });
                        }
                    } else {
                        if (dis[u][rev] + x + 1 < dis[v][rev ^ 1]) {
                            dis[v][rev ^ 1] = dis[u][rev] + x + 1;
                            pq.push({ dis[v][rev ^ 1], v, rev ^ 1 });
                        }
                    }
                }
            }
        }
    };
    dijkstra();
    cout << min(dis[n][0], dis[n][1]) << '\n';
}

明天再把 F 看了，是个青题。

F ​

看出来了是二分，但是check不太会写。

我本来记每个的 [l,r] ，然后看每个相邻的能不能相交，但我判的 [l,r] 就是简单的看它自己的高度。其实可以整体考虑。

用一个 [L,R] 来记一下当前的合法的区间，每次可以被扩展到 [L−x,R+x] , 然后当前的 u 的范围是 [max(0,H−d),U] 。

一直扩展区间然后判有没有交集就可以了。

cpp
void solve()
{
    int n, x;
    cin >> n >> x;
    vector<int> u(n), d(n);
    for (int i = 0; i < n; i++)
        cin >> u[i] >> d[i];
    long long lo = 0, hi = 2e9 + 1;
    auto check = [&](long long H) {
        long long L = 0, R = H;
        for (int i = 0; i < n; i++) {
            //:之前的区间 [L-X,R+X]
            //:当前的区间 [max(0,H-D),U]
            L = max({L-x,H-d[i],0LL});
            R = min(R + x, 1LL*u[i]);
            if(L>R) return false;
        }
        return true;
    };
    while (lo < hi - 1) {
        long long mid = (lo + hi) >> 1;
        if (check(mid))
            lo = mid;
        else
            hi = mid;
    }
    // cout<<check(2)<<'\n';
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += u[i] + d[i] - lo;
    }
    cout << ans << '\n';
}