Kick Start 2019 Round F Teach Me

题目链接

题目大意

有 $N$ 个人，$S$ 项技能，这些技能用 $1, 2, 3, \dots, S$ 表示 。第 $i$ 个人会 $c_i$ 项技能（$ 1 \le c_i \le 5 $）。对于两个人 $i$, $j$，若 $i$ 会某项技能而 $j$ 不会，则称 $i$ 可以辅导 $j$ 。试问有多少个有序数对 $(i, j)$ 满足 $i$ 可以辅导 $j$ 。

数据范围

• 多组测试数据（不超过 100 组）
• $ 2 \le N \le 5 \times 10^4 $
• $ 1 \le S \le 1000 $
• Time limit: 20 s
• Memory limit: 1 GB

分析

考虑 $i$ 不能辅导 $j$，即 $i$ 的技能集是 $j$ 的技能集的子集（凡是 $i$ 会的 $j$ 都会）。

固定 $i$，我们来求满足 $i$ 不能辅导 $j$ 的二元组 $(i, j)$ 的数量。

枚举 $i$ 的技能集的非空子集 $t$，计算技能集等于 $t$ 的人有多少个。

实现

比赛时我没多想，用 std::vector<int> 表示技能集，用 std::map<std::vector<int>>, int> 统计人数；结果在大数据上超时了。
虽然至少 std::map 常数大，但是看到时限是 20 秒就没太在意。本来能打进前 30 名的，太可惜了。这道题是最后写的，提交时距离比赛结束还有 72 分钟 :( 。

下面是超时的实现

    int T; scan(T);

    rep (T) {
        int n, s;
        scan(n, s);
        vv<int> a; // 1
        map<vector<int>,int> cnt;
        rep (n) {
            int c; scan(c);
            vi x(c); scan(x);

            sort(all(x));
            a.push_back(x);  // 2
            ++cnt[x]; // 3
        }
        ll tot = 0;
        rng (i, 0, n) {
            int c = SZ(a[i]);
            rng (s, 0, 1 << c) { // 4
                vi tmp;
                rng (j, 0, c) {
                    if (s & 1 << j) {
                        tmp.pb(a[i][j]);
                    }
                }
                tot += cnt[tmp]; // 5
            }
        }
        kase();
        println(1LL * n * n - tot);
    }

改进

不用 std::map 计数。
将 a 排序。从而用 tot += std::upper_bound(a.begin(), a.end(), tmp) - std::lower_bound(a.begin(), a.end(), tmp); 取代 tot += tmp; 。（5）

(1) 处，声明 a 时指定 size，从而 (2) 处用赋值取代 push_back。

(4）处，枚举子集时从 1 开始。

    int T; scan(T);

    rep (T) {
        int n, s;
        scan(n, s);
        vv<int> a(n);
        rng (i, 0, n) {
            int c; scan(c);
            vi x(c); scan(x);

            sort(all(x));
            a[i] = std::move(x); // (1)
        }

        sort(all(a));

        ll tot = 0;
        rng (i, 0, n) {
            int c = SZ(a[i]);
            rng (s, 1, 1 << c) {
                vi tmp;
                rng (j, 0, c) {
                    if (s & 1 << j) {
                        tmp.pb(a[i][j]);
                    }
                }
                tot += upper_bound(all(a), tmp) - lower_bound(all(a), tmp);
            }
        }
        kase();
        println(1LL * n * n - tot);
    }

问题

(1) 处若写成 a[i] = x; ，在开 -O2 的情况下，编译器会选择调用 std::vector<int> 的 move assignment operator 吗？