即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Hihocoder-小Hi的烦恼

编程语言 Snow_Me 19℃ 0评论

解题思路:

其实题目自带的题解已经交代的比较清楚了。但是如果完全按照题目自带的解法来计算,肯定是会超时的。因为无论如何还是O(n^2)的解法,当然也可能是彩笔我比较菜只能写出这样的。

所以需要一些转换。

这个题目给的内存空间为1024M,显然我们要用空间换时间了。

就以单个科目为例吧。假设a[i]表示第i个学生在语文这个科目上的排名,index[a[i]] = i表示语文排名为a[i]的是第i个学生。这个时候,设置bitset yuwen[maxn],其中yuwen[i]表示在语文成绩排名为i的前面的学生集合。

所以可以O(n)得到整个yuwen集合,然后再利用前面索引出来的index,就可以整体O(n)的求出结果了。




代码:

#include 
using namespace std;

const int maxn = 3e4 + 5;

int a[maxn][5], inx[maxn][5];
bitset bs[maxn][5], ans;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for ( int i = 1; i <= n; ++i ) {
        for ( int j = 0; j < 5; ++j ) {
            cin >> a[i][j];
            inx[ a[i][j] ][j] = i;
        }
    }
    for ( int i = 2; i <= n; ++i ) {
        for ( int j = 0; j < 5; ++j ) {
            bs[i][j] = bs[i-1][j];
            bs[i][j].set(inx[i-1][j], 1);
        }
    }
    for ( int i = 1; i <= n; ++i ) {
        ans.set();
        for ( int j = 0; j < 5; ++j ) {
            ans &= bs[ a[i][j] ][j];
        }
        cout << ans.count() << endl;
    }
    return 0;
}



顺便附一个,根据题目自带题解写的东西...最后只有80/100这样的结果= =还是超时了

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 3e4 + 5;
bitset num[5], ans;
int rak[maxn][5], inx[maxn][5];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, bef[5] = {1, 1, 1, 1, 1};
    cin >> n;
    for ( int i = 1; i <= n; ++i ) {
        for ( int j = 0; j < 5; ++j ) {
            cin >> rak[i][j];
            inx[ rak[i][j] ][j] = i;
        }
    }
    for (int i = 0; i < 5; ++i) num[i].reset();
    for ( int i = 1; i <= n; ++i ) {
        for ( int k = 0; k < 5; ++k ) {
            if ( bef[k] < rak[i][k] ) {
                for ( int j = bef[k]; j < rak[i][k]; ++j )
                    num[k][ inx[j][k] ] = 1;
            } else {
                for ( int j = bef[k]; j >= rak[i][k]; --j )
                    num[k][ inx[j][k] ] = 0;
            }
        }
        ans.set();
        for ( int k = 0; k < 5; ++k ) {
            ans &= num[k];
            bef[k] = rak[i][k];
        }
        cout << ans.count() << endl;
    }
    return 0;
}

转载请注明:CodingBlog » Hihocoder-小Hi的烦恼

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情