别看了……bitset入门题……

bitset就是将32个01位操作整合成一个32位整数,一次位操作。
作为一个位运算的优化方法,可以省去 2^5的时间复杂度。
有些大佬 sb 就故意让你 O ( n^2 )过不了,加个 bitset 优化就可以卡过去了。
不过也可以说是一个很巧妙的操作。

这题是今晚出去撸串的时候听其他三个沙雕吹的一道题,今晚补上。

题意:
给你一群学生每门功课的排名,总共 5 门学科,问你对于每个学生,所有成绩排名都比他高的学生数有多少。

不存在共列一个名次的数据。

思路:
很暴力……
直接n^2 + bitset 优化就可以卡过

但是不知道为什么,我的循环在 [ 1, n ] 就 T 了,[0, n ) 就 A 了……

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 3e4 + 5;

bitset<maxn> up[5][maxn], res;
int rnk[maxn], rrnk[5][maxn];

int main()
{
    int n;
    scanf("%d", &n);
    each(i, n) each(j, 5) scanf("%d", &rrnk[j][i]);
    each(c, 5)
    {
        each(i, n) rnk[rrnk[c][i]] = i + 1;
        range(i, 2, n)
        {
            up[c][rnk[i]] = up[c][rnk[i - 1]];
            up[c][rnk[i]][rnk[i - 1]] = 1;
        }
    }
    range(i, 1, n)
    {
        res = up[0][i] & up[1][i] & up[2][i] & up[3][i] & up[4][i];
        printf("%ld\n", res.count());
    }
    return 0;
}
Categories: 暴力

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

暴力

CodeForces 398A Cards

昨天搬了一下午的原博客…… 晚上玩了一下就没写了 今天补上这道 题意: Read more…