数据过水,请求加强
查看原帖
数据过水,请求加强
35379
Scarlet_Hypoc楼主2020/11/2 16:33

原本是想看看rk1是如何写的那么快的,点进去发现是个假做法,主要部分的代码是这样的:

#define lowbit(x) ((x) & -(x))
const int N = 1e5 + 20;
const int mod = 99999997;
int n, x, ans, a[N], b[N], c[N];
inline void Add(int x) {
    for (; x; x -= lowbit(x)) c[x]++;
}
inline int Getsum(int x) {
    int cnt = 0;
    for (; x <= n; x += lowbit(x)) cnt += c[x];
    return cnt;
}
int main() {
    int i, j, k;
    read(n);
    for (i = 1; i <= n; i++) {
        read(x);
        a[x] = i;
    }
    for (i = 1; i <= n; i++) {
        read(x);
        b[i] = a[x];
    }
    for (i = 1; i <= n; i++) {
        ans = (ans + Getsum(b[i] + 1)) % mod;
        Add(b[i]);
    }
    printf("%d\n", ans);
    return 0;
}

很明显存在问题,随便一组数据就能卡掉:

input:
4
1 2 3 4
8 7 6 5
output:
6

这个代码会输出 00,但是居然能AC,这个数据真的太水了,怕不是直接random_shuffle两个 11 ~ nn 的排列造的数据。

不过现在第一是我了,因为我一开始不信邪交了一发rk1的代码……

2020/11/2 16:33
加载中...