ABC F题求 hack

ppip @ 2022-12-24 21:44:22

#include <bits/stdc++.h>
using namespace std;
const int N(2e5);
int P[N+5],D[N+5];
int dis(int x,int y) {
    return abs(x-y)+abs(P[x]-P[y]);
}
int main() {
    int n;scanf("%d",&n);
    for (int i{1};i<=n;++i) scanf("%d",P+i),D[i]=n;
    for (int i{1};i<=n;++i) {
        for (int j{i+1};j-i<D[i]&&j<=n;++j)
            D[i]=min(D[i],dis(i,j)),D[j]=min(D[j],dis(i,j));
        for (int j{i-1};i-j<D[i]&&j>=1;--j)
            D[i]=min(D[i],dis(i,j));
        printf("%d ",D[i]);
    }
    return 0;
}

by lzyqwq @ 2022-12-24 21:47:15

@ppip 啥原理啊，我一开始以为 D 有啥对称是特殊性质，然后后来发现不行qwq

by ppip @ 2022-12-24 21:47:40

@蒟蒻·廖子阳

暴力从每个点出发向两边枚举

如果当前答案不可能再被更新（下标太远）就停止

我总感觉不可能构造答案使得每个点答案都很大

by lzyqwq @ 2022-12-24 21:48:32

@ppip 但是这个复杂度如何确保

by 郑朝曦zzx @ 2022-12-24 21:49:27

@ppip 我也这么写的，也过了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read()
{
    char c=getchar(); int x=0, s=1;
    while(c<'0'||c>'9') { if(c=='-')s=-1;c=getchar();}
    while(c>='0'&&c<= '9') { x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*s;
}
int num[200010];
int main()
{
    int n = read();
    for (int i = 1; i <= n; ++i)
        num[i] = read();
    for (int i = 1; i <= n; ++i)
    {
        int step = n + 1;
        for (int j = 1; j <= step && i - j >= 1; ++j)
        {
            int pos = i - j;
            step = min(step, j + abs(num[i] - num[pos]));
        }
        for (int j = 1; j <= step && i + j <= n; ++j)
        {
            int pos = i + j;
            step = min(step, j + abs(num[i] - num[pos]));   
        }
        printf("%d ", step);
    }
    return 0;
}

不知道是数据水了还是我们的均摊复杂度是对的。

by ppip @ 2022-12-24 21:49:30

@蒟蒻·廖子阳 不会，所以求hack或证明啊

by Micnation_AFO @ 2022-12-24 21:51:09

啊靠，有这个想法以为会超时所以没写/kk

by Ginger_he @ 2022-12-24 22:02:43

@ppip 数据问题吧

https://atcoder.jp/contests/abc283/submissions/37512765

这个代码也过了，我实在是不理解

by 奇犽 @ 2022-12-24 22:03:07

笑了我就这么写的 因为是个排序嘛，时间复杂度不会太坏，至少O（能过）

by ppip @ 2022-12-24 22:03:57

@Ginger_he 原理一样的

by Ginger_he @ 2022-12-24 22:05:12

话说有没有人交一发纯暴力试试（