# 2023-02-12：给定正数N，表示用户数量，用户编号从0~N-1， 给定正数M，表示实验数量

2023-02-12：给定正数N，表示用户数量，用户编号从0N-1，

M-1，

A[i] = { a, b, c }表示，用户i报名参加了a号、b号、c号实验，

B[i] = { e, f }表示，第i条查询想知道e号、f号实验，一共有多少人(去重统计)。

1 <= N <= 10^5，
1 <= M <= 10^2，
1 <= Q <= 10^4。

``````use rand::Rng;
use std::collections::HashMap;
use std::collections::HashSet;
use std::iter::repeat;
fn main() {
let N = 100;
let M = 20;
let Q = 50;
let testTime = 5000;
println!("功能测试开始");
for i in 0..testTime {
let n = rand::thread_rng().gen_range(0, N) + 1;
let m = rand::thread_rng().gen_range(0, M) + 1;
let mut A = randomMatrix(n, rand::thread_rng().gen_range(0, m) + 1, m);
let q = rand::thread_rng().gen_range(0, Q) + 1;
let mut B = randomMatrix(q, rand::thread_rng().gen_range(0, m) + 1, m);
let ans1 = record1(n, m, q, &mut A, &mut B);
let ans2 = record2(n, m, q, &mut A, &mut B);
let mut pass = true;
for j in 0..q {
if ans1[j as usize] != ans2[j as usize] {
pass = false;
break;
}
}
if !pass {
println!("出错了!");
break;
}
}
println!("功能测试结束");
}

// 暴力方法
// 为了验证
fn record1(n: i32, m: i32, q: i32, A: &mut Vec<Vec<i32>>, B: &mut Vec<Vec<i32>>) -> Vec<i32> {
let mut expUsersMap: HashMap<i32, HashSet<i32>> = HashMap::new();
for i in 0..m {
expUsersMap.insert(i, HashSet::new());
}
for i in 0..n {
for exp in A[i as usize].iter() {
let mut a = expUsersMap.get_mut(exp).unwrap();
a.insert(i);
}
}
let mut ans: Vec<i32> = repeat(0).take(q as usize).collect();
let mut help: HashSet<i32> = HashSet::new();
for i in 0..q {
help.clear();
for exp in B[i as usize].iter() {
for user in expUsersMap.get(exp).unwrap().iter() {
help.insert(*user);
}
}
ans[i as usize] = help.len() as i32;
}
return ans;
}

// 正式方法
fn record2(n: i32, m: i32, q: i32, A: &mut Vec<Vec<i32>>, B: &mut Vec<Vec<i32>>) -> Vec<i32> {
// n 一共有多少人
// 任何一个实验，需要几个整数，能表示所有人谁出现谁没出现？
let parts = (n + 31) / 32;
// m    0 ~ m -1
// [i]  [.........]
let mut bitMap: Vec<Vec<i32>> = repeat(repeat(0).take(parts as usize).collect())
.take(m as usize)
.collect();
for i in 0..n {
// i 人的编号 : a b c
for exp in A[i as usize].iter() {
bitMap[*exp as usize][(i / 32) as usize] |= 1 << (i % 32);
}
}
let mut ans: Vec<i32> = repeat(0).take(q as usize).collect();
for i in 0..q {
// i号查询 ： a、c、e，一共有多少去重的人
// a[0] | c[0] | e[0] -> 几个1
// a[1] | c[1] | e[1] -> 几个1
let mut all = 0;
for j in 0..parts {
let mut status = 0;
for exp in B[i as usize].iter() {
status |= bitMap[*exp as usize][j as usize];
}
all += countOnes(status);
}
ans[i as usize] = all;
}
return ans;
}

// 大厂刷题班，32节，leetcode专题 : https://leetcode.com/problems/number-of-1-bits/
fn countOnes(mut n: i32) -> i32 {
let mut n2: u32;
if n < 0 {
n2 = (u32::MAX as i64 + n as i64 + 1) as u32;
} else {
n2 = n as u32;
}
let mut n = n2;
n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
return n as i32;
}

// 为了测试
fn randomMatrix(n: i32, m: i32, v: i32) -> Vec<Vec<i32>> {
let mut ans: Vec<Vec<i32>> = repeat(repeat(0).take(m as usize).collect())
.take(n as usize)
.collect();
for i in 0..n {
for j in 0..m {
ans[i as usize][j as usize] = rand::thread_rng().gen_range(0, v);
}
}
return ans;
}
``````

(=￣ω￣=)··· 暂无内容！

227

11

20

6