欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

HihoCoder#1509 : 异或排序(二进制)

程序员文章站 2022-09-21 23:14:32
题意 "题目链接" Sol 挺简单的吧。考虑两个元素什么时候不满足条件 设$a_i$与$a_i + 1$最高的不同位分别为 ,显然$S$的这一位必须为$0$,否则这一位必须为$1$ 剩下的就没有限制条件了 时间复杂度:$nlogn$??????!!!!!! cpp include using nam ......

题意

sol

挺简单的吧。考虑两个元素什么时候不满足条件

\(a_i\)\(a_i + 1\)最高的不同位分别为0 1,显然\(s\)的这一位必须为\(0\),否则这一位必须为\(1\)

剩下的就没有限制条件了

时间复杂度:\(nlogn\)??????!!!!!!

#include<bits/stdc++.h>
using namespace std;
const int maxn = 30001;
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, a[5][maxn], rak[5][maxn], base = 1;
bitset<maxn> b[5][175];
main() {
    n = read(); base = sqrt(n);
    for (int i = 1; i <= n; i++) for (int j = 0; j < 5; j++) a[j][i] = read(), rak[j][a[j][i]] = i;
    for (int j = 0; j < 5; j++) 
        for (int i = 1; i * base <= n; i++) 
            for(int k = 1; k <= i * base; k++) b[j][i].set(rak[j][k]);  
    for (int i = 1; i <= n; i++) {
        bitset<maxn> tmp, cal; tmp.set();
        for(int j = 0; j < 5; j++) {
            cal.reset();
            int now = a[j][i] / base;
            cal |= b[j][now];
            for(int k = now * base + 1; k <= a[j][i]; k++) cal.set(rak[j][k]); 
            tmp &= cal;
        }
        printf("%d\n", tmp.count() - 1);
    }
}