代码中的il或i64均表示long long类型。

Problem A. Order Something Else

题意

一瓶饮料的正常价格是$P$元，现在有一张优惠券，使得你可以以$Q$元的价格购买这瓶饮料，条件是是必须从给出的$N$道菜中选择一道菜一并购买，第$i$道菜的价格是$D_i$。求出购买这瓶饮料的最低价格。

题解

我们可以使用优惠券也可以不使用优惠券。

如果我们使用优惠券，则需要再购买一份小菜，我们肯定选择最便宜的小菜，那么买下这瓶饮料的价格最低是$Q+min(D_1, D_2,..,D_n)$。

如果不使用优惠券，那么会以原价$P$买下这瓶饮料。

答案就是上面两式的较小者。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void impl() {
    int n, p, q;
    cin >> n >> p >> q;
    int m, c;
    cin >> m;
    for (int i = 1;i < n;i++) {
        cin >> c;
        m = std::min(m, c);
    }
    if (q + m < p) {
        cout << (q + m);
    } else {
        cout << p;
    }
}

Problem B. Strictly Superior

题意

有$N$种商品，$M$种功能。每个商品$P_i$有$C_i$种功能，由$F_{i,j}$给出，且满足$1\le F_{i,j}\le M$。

现在定义商品$P_j$严格优于$P_i$需要满足下面三个条件：

  • $P_i\ge P_j$
  • 第$j$个商品具有第$i$个商品的所有功能
  • $P_i>P_j$或者第$j$个商品由比第$i$个商品更多的功能

题解

屁话不说，直接暴力枚举比较即可

代码

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

struct Prod {
    int p, c;
    bool f[150];
} v[200];
int n, m, b;
bool check(int i, int j) {
    if (v[i].p >= v[j].p) {
        int u = 0;
        for (int k = 1;k <= m;k++) {
            if (v[i].f[k] && !v[j].f[k]) {
                return false;
            } else if (!v[i].f[k] && v[j].f[k]) {
                u ++;
            }
        }
        return v[i].p > v[j].p || u;
    }
    return false;
}
void impl() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> v[i].p >> v[i].c;
        for (int j = 0;j < v[i].c;j++) {
            cin >> b;
            v[i].f[b] = true;
        }
        for (int j = 1;j < i;j++) {
            if (check(i, j) || check(j, i)) {
                cout << "Yes";
                return;
            }
        }
    }
    cout << "No";
}

Problem C. Reversible

题意

有$N$根棍子，每根棍子上按照顺序写下了一串字符，每根棍子都可以反转，使得它上面的字符序列也翻转。问是否有两根棍子上的字符串能完全相同（棍子可以反转也可以不反转）。

题解

按顺序处理每一根棍子，维护一个字符串集合。

对于一根棍子，

  • 首先检查它上面的字符串和翻转的字符串是否在集合中，如果是，直接输出Yes并退出
  • 否则，将这个字符串加入到集合中

最后，如果为退出，则输出No

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

std::unordered_set<string> st;
void impl() {
    int n;
    cin >> n;
    string s;
    for (int i = 0;i < n;i++) {
        cin >> s;
        if (st.find(s) == st.end()) {
            std::reverse(s.begin(), s.end());
            if (st.find(s) == st.end()) {
                st.insert(s);
            }
        }
    }
    cout << st.size();
}

Problem D. Peaceful Teams

题意

有$N$个人，你需要把他们分成$T$组，每个人都属于其中一个组别，每个组至少有一个人。

其中有$M$对人，每对中的两个人不能分到同一组。现在求划分方案总数，注意是划分。

题解

$N$和$T$都比较小，直接dfs所有可能的分组。在搜索中，可能出现划分相同，但是分组编号不同的情况，我们使用set去重。

代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

int u[20][20];
int cnt[20];
int ans, n, t, m;
int v[20][20];
std::unordered_set<string> st;
void dfs(int curr) {
    if (curr == n + 1) {
        for (int i = 1; i <= t;i++) {
            if (!cnt[i]) {
                return;
            }
        }
        std::vector<string> lst;
        for (int i = 1;i <= t;i++) {
            string s;
            char buf[2] = {};
            for (int j = 1;j <= n;j++) {
                if (u[i][j]) {
                    buf[0] = (char) j;
                    s.append(buf);
                }
            }
            lst.push_back(s);
        }
        std::sort(lst.begin(), lst.end());
        string s;
        for (const auto & i : lst) {
            s.append(i);
            s.append("|");
        }
        if (st.insert(s).second) {
            ans ++;
        }
        return;
    }
    for (int i = 1; i <= t;i++) {
        int flag = 1;
        // check conflict
        for (int j = 1;j <= n && flag;j++) {
            if (v[curr][j] && u[i][j]) {
                flag = 0;
            }
        }
        if (flag) {
            u[i][curr] = 1;
            cnt[i] ++;
            dfs(curr + 1);
            u[i][curr] = 0;
            cnt[i] --;
        }
        if (!cnt[i]) {
            break;
        }
    }
}
void impl() {
    cin >> n >> t >> m;
    int a, b;
    for (int i = 0;i < m;i++) {
        cin >> a >> b;
        v[a][b] = v[b][a] = 1;
    }
    dfs(1);
    cout << ans;
}

Problem E. NAND Repeatly

题意

给定一个长度为$N$的01串，其第$i$位为$A_i$，求出
$$
\sum\limits^N_{i=1}\sum\limits^N_{j=i}f(i, j)\quad(1\le i\le j\le N)
$$

其中

$$
f(i,j)=\left\{
\begin{array} \\
A_i & (i=j) & \\
f(i, j - 1)\overline{\wedge}A_j & (i<j) \\
\end{array}
\right.
$$

定义运算NAND（$\overline{\wedge}$）如下：
$$
0\overline{\wedge}0=1,0\overline{\wedge}1=1,1\overline{\wedge}0=1,1\overline{\wedge}1=0
$$

题解

由于$N$最大可以到$10^6$，直接暴力计算肯定会超时。我们考虑如何批量统计答案。

考虑到每次运算的结果只有0和1，运算也是从左向右进行的，$a\overline{\wedge}b\overline{\wedge}c=(a\overline{\wedge}b)\overline{\wedge}c$，对于位置$i$，我们可以记录区间$[1,i],[2,i],…[i,i]$这些区间的运算结果中的01个数，记为$f[i][0]$和$f[i][1]$，每到一个位置就把当前位置1的个数加到答案中，这样我们就能得到这$C^2_n$个区间的运算结果，换句话来说，我们维护了左端点的信息，枚举右端点，统计了答案。

从前一个位置转移到后一个位置，只需要：

  • 首先,将$i-1$位置的01个数通过NAND运算，加到当前位置的数量中

    $f[i][NAND(0,A_i)] = f[i-1][0], f[i][NAND(1,A_i)] = f[i-1][1]$

  • 然后，把自己的值统计进去($因为f(i)=A_i$当$i=j$)，也就是区间$[i,i]$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string s;
int n, x[1000100];
i64 f[1000100][2];
inline int nand(int a, int b) {
    if (a == b && a) {
        return 0;
    }
    return 1;
}
void impl() {
    cin >> n >> s;
    i64 ans = 0;
    for (int i = 1;i <= n;i++) {
        x[i] = s[i - 1] - '0';
        f[i][x[i]] ++;
        f[i][nand(1, x[i])] += f[i - 1][1];
        f[i][nand(0, x[i])] += f[i - 1][0];
        ans += f[i][1];
    }
    cout << ans;
}

Problem F. Make 10 Again

题意

有$N$个骰子，第$i$个骰子上的数是$1\sim A_i$，且该骰子投出每个数的概率是相等的。

现在求：各投一次这$N$个骰子，能够从这$N$个骰子中选出一些骰子（可以全选），使得这几个骰子上面的数加起来是10的概率，并对$998244353$取模。

题解

题目要求的目标数字很小，是10。因此， 我们的状态设计中主要考虑$[0,10]$的可及性，考虑10以上的数的可及性对答案没有贡献。我们可以逐个考虑每个骰子的情况。由于需要维护一个关于$[0,10]$可及性的集合，我们可以用一个数字表示该集合中的数的存在情况，即用数字$s$表示集合，用$s\&(1<<k)$获取数字$k$是否可及。

最开始时（没有投出任何骰子时，$i=0$），我们能得到的数字只有$0$，概率为$1$，设$dp[0][1<<0]$为$1$。

然后我们逐个考虑投第$i=1,2,3,\dots$个骰子的情况。

  • 如果第$i$个骰子投出的是$1\sim 10$的数$k$，那么原来可及数字集合为$s$的考虑这个骰子投出的数之后，集合变为$(s | (s << k))$（注意实际运算中只取最后10位，和$mask=(1<<11)-1$）做与运算
  • 如果第$i$个骰子投出的数大于$10$，那么原来可及数字集合为$s$的在考虑这个骰子投出的数之后，集合仍然为$s$

这样我们就能通过前一个骰子状态转移到后一个骰子状态。

最后，我们只需要统计第$N$个骰子的状态中，能够达到$10$的状态的概率的和即可。

代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
constexpr i64 M = 998244353;

i64 quickPow(i64 base, i64 t) {
    if (t == 1) {
        return base;
    }
    base %= M;
    i64 res = quickPow(base, t / 2) % M;
    res = res * res % M;
    if (t & 1) {
        res = res * base % M;
    }
    return res;
}

i64 inv(int v) { return quickPow(v, M - 2); }

int n;
int a[110];
constexpr int mask = 0b11111111111;
i64 st[110][4096];

void impl() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    st[0][1] = 1;
    for (int i = 1; i <= n; i++) {
        i64 p = 1 * inv(a[i]);
        for (int j = 1; j <= std::min(a[i], 10); j++) {
            for (int s = 0; s <= mask; s++) {
                i64 v = st[i - 1][s] * p % M;
                int idx = (s | (s << j)) & mask;
                st[i][idx] += v;
                st[i][idx] %= M;
            }
        }
        if (a[i] > 10) {
            for (int s = 0; s <= mask; s++) {
                i64 v = (st[i - 1][s] * p % M) * (a[i] - 10) % M;
                st[i][s] += v;
                st[i][s] %= M;
            }
        }
    }
    i64 ans = 0;
    for (int i = 0;i <= mask;i++) {
        if (i & (1 << 10)) {
            ans += st[n][i];
            ans %= M;
        }
    }
    cout << ans;
}