【题解】HackerRank-Winning Lottery Ticket

Posted on In Disqus:

题目

https://www.hackerrank.com/challenges/winning-lottery-ticket/problem

题意

给一些只包含数字的字符串，问有多少无序字符串对，使得这两个字符串中包括了 0-9 之间的所有数字。

题解

  • 首先将每个串转为 01 串来表示是否包含该位置对应的数字。
  • 问题就转化为了有多少对 01 串使得它们的位或为 111111111。
  • 利用高维前缀和来计算 c[x]，表示满足 x & t = x 的 t（01 串） 的个数（对 x 的超集求和）。
  • 然后累加答案并除 2。注意要去掉自己和自己匹配的情况，也就是一个串已经包含了 0-9 中的所有数字。
  • 当然这道题只有 0-9 可以 \((2^{10})^2\) 暴力枚举，不用高维前缀和。（其实使用高维前缀和的话，字符集的大小可以出到 20。）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 1E6 + 100;
int a[N];
int c[1 << 10];

string s;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    FOR (i, 0, n) {
        cin >> s;
        for (char& c: s)
            a[i] |= 1 << (c - '0');
        c[a[i]]++;
    }
    FOR (i, 0, 10)
        FOR (j, 0, 1 << 10)
            if ((1 << i) & j)
                c[j ^ (1 << i)] += c[j];
    LL ans = 0;
    int M = (1 << 10) - 1;
    FOR (i, 0, n) ans += c[M ^ a[i]] - (a[i] == M);
    cout << ans / 2 << endl;
}