ACM 粗心永远AC不了系列——小Hi的烦恼|“五维数点”问题

4
1 1 2 2 1
2 3 3 3 2
3 2 1 1 3
4 4 4 4 4

1.按输入建立个人排名pr[][]、各科排名sr[][]

2.生成排名比较表rc[][]，rc[i][j]表示第j科比i名靠前的同学学号是什么，用位表示

第n位为1表示n号同学在第i名之前

这样子每n行只需要考虑比n-1行1位1就行了，而这个1可以从sr中得到 耗时O(5N)

3.根据排名比较表rc[][]和个人排名表pr[][]对应生成所有科目比自己强的人的集合

这个用betset数据结构就可以表示对位操作，很方便

源代码

import java.util.BitSet;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner cin = new Scanner(System.in);while (cin.hasNext()) {int n = cin.nextInt();int pr[][] = new int[n][5];// 第a号学生第b科排rank[i][j]名int sr[][] = new int[n + 1][5];// 第a科排第b名的学生是id[j][i]号BitSet rc[][] = new BitSet[n + 1][5];// 比a号学生第b科排名靠前的学生的集合BitSet[i][j],第i位为1表示i号学生比a号学生第b科靠前for (int i = 0; i < n; i++) {for (int j = 0; j < 5; j++) {int k = cin.nextInt();pr[i][j] = k;// 个人排名，i号学生的j科排第 k 名sr[k][j] = i;// 科目排名，j科的排第k名是i号学生}}for (int j = 0; j < 5; j++) {// 构建排名详情表 j表示第j科rc[1][j] = new BitSet(n);// j科排名在第k名之上的学生为0for (int k = 2; k <= n; k++) {// k表示第k名 j科排名在第k名之上的学生是那几个rc[k][j] = new BitSet(n);rc[k][j].or(rc[k - 1][j]);// 获取第排名在k-1名的之上的学生复制过来rc[k][j].set(sr[k - 1][j]);// 把第k-1名的学生设置为true}}for (int i = 0; i < n; i++) {// i表示第i号学生 输出结果int k = 0, lastk = 0;for (int j = 3; j >= 0; j--) {// j表示第j科，从倒数第二科开始向后与k = pr[i][j];// k表示学号为i的学生第j科排第k名lastk = pr[i][j + 1];// lastk表示学号为i的学生第j + 1科排第lastk名rc[k][j].and(rc[lastk][j + 1]);}System.out.println(rc[k][0].cardinality());}}}
}