ABC310(A-F)

freee Programming Contest 2023（AtCoder Beginner Contest 310） - AtCoder

这场质量很高，然而官方解答很多地方讲的不是很清楚。

A - Order Something Else

一种商品有两种购买方式，第一种方式是以 \(p\) 元直接购买，第二种方式是先在给定的 \(n\) 种捆绑商品中买一个，然后以 \(q\) 元的优惠价购买。输出购买该商品的最低价格。

找出n个捆绑商品中的最低价，然后进行比较即可

#include <iostream>

using namespace std;

int n, p, q, x, m = 1E9;

int main()
{
    cin >> n >> p >> q;
    while(n--)
    {
        cin >> x;
        m = min(m, x);
    }
    cout << min(m + q, p);
    return 0;
}

---

B - Strictly Superior

有 \(N\) 种功能饮料，每一种功能饮料的售价是 \(P_i\) , 每一种饮料都具有 \(C_i\) 种功能，饮料的功能用数字表示。

如果满足以下条件，则称饮料 \(i\) 严格好于饮料 \(j\) 。

• \(P_i ≤ P_j\)

• 饮料 \(i\) 拥有饮料 \(j\) 的所有功能。

• \(P_i < P_j\) 或 饮料 \(i\) 至少存在一种饮料 \(j\) 所不具有的功能。

判断是否存在饮料 \(i\) 严格好于饮料 \(j\) ，若存在则输出 Yes 否则输出 No

数据范围： \(C_i, N ≤ 100\)，饮料的功能都是1-100间的整数。

每种饮料的功能用一个bitset表示，位运算计算包含关系。

由于 \(N\) 比较小，可以两层循环直接判断，这里我是按照价格排序，然后直接扫一轮的。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>

using namespace std;

const int maxn = 110;
int n, m;

struct Node {
    int p;
    bitset<110> st;  
    bool operator < (const Node &y) const
    {return p < y.p;}
    bool good(const Node &y) const
    {
        if((st & y.st) != y.st)
            return 0;
        if(p == y.p && st == y.st)
            return 0;
        return 1;
    }
}a[maxn];


int main()
{
    cin >> n >> m;
    int c, x;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i].p >> c;
        while(c--)
        {
            cin >> x;
            a[i].st[x] = 1;
        }
    }
    sort(a, a+n);
    bool flag = 0;
    for(int i = 0; i < n && !flag; i++)
    {
        for(int j = i + 1; j < n; j++)
            if(a[i].good(a[j]))
            {
                flag = 1;
                break;
            }
    }
    if(flag)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

---

C - Reversible

有 \(N\) 个字符串，用 \(R(S)\) 表示字符串 \(S\) 的反转字符串， 若\(S_i == S_j\) 或 \(S_i == R(S_j)\) 则称 \(S_i\) 与 \(S_j\) 是本质相同的。

求出 \(N\) 个字符串中有个本质不同的字符串。

对于每个字符串 \(S_i\)，取 \(S_i\) 和 \(R(S_i)\) 中字典序较小的一个加入哈希表中，最终哈希表的大小就是答案。

#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

int main()
{
    int n;
    string s, t;
    unordered_set<string> vis;
    cin >> n;
    while(n--)
    {
        cin >> s;
        t = s;
        reverse(t.begin(), t.end());
        vis.insert(s < t ? s : t);
    }
    cout << vis.size();
    return 0;
}

---

D - Peaceful Teams

有 \(N\) 个人，现在需要将他们分成 \(T\) 组，每个人都必须属于某1组，每个组都至少要有1个人。此外，有 \(M\) 对人的关系是不好的，不能将两个关系不好的人分到同一组中。

问：有多少种不同的分组方式？

数据范围：\(T ≤ N ≤ 10\)

首先要明白分组方式和组之间排列的顺序是无关的，也就是说，{1, 4, 5}, {2, 3} 和 {2, 3}, {1, 4, 5} 是同一种分组方式（因为仅仅只有组之间排列顺序的不同）。为了确定顺序（如同C题中选用字典序较小的作为代表一样），对于不同的排列顺序也需要确定一种代表顺序：

• 每个组中最小的号码作为这个组的代表号码，例如{1, 4, 5}的代表号码是1，{2, 3}的代表号码是2
• 代表号码越小的组，顺序越靠前

上述规则就能保证了不同的排列顺序实际对应的只有一种，在计算分组方式时只要满足这个规则就不会重复。

接下来考虑求解问题，显然，第1个人一定是在第1组的，接下来从第2个人开始：要么加入之前已经建立好的组，要么建立一个新的组。若加入某个组必须满足组内相容，使用位运算，即：将每个组的人员分布用bit串表示，group[i]表示第i个组有哪些人的bit串。当前的人用cur表示，hate[cur]表示与第cur个人有矛盾的人的bit串。若(group[i] & hate[cur])==0表示cur可以融入group[i]。

上述过程DFS即可，时间复杂度为 \(O(T*N!)\)，由于有剪枝以及位运算，实际这是一个很松的上界。

#include <iostream>

using namespace std;

const int maxn = 11;
int n, t, m, ans;
int hate[maxn], group[maxn];

void dfs(int cur, int g)
{
    if(n - cur + g < t)//如果分组凑不齐t个，及时剪掉
        return;
    if(cur == n)
    {
        ans++;
        return;
    }
    for(int i = 0; i < g; i++)
        if((group[i] & hate[cur]) == 0)
        {
            group[i] ^= 1 << cur;
            dfs(cur+1, g);
            group[i] ^= 1 << cur;
        }
    if(g < t)
    {
        group[g] = 1 << cur;
        dfs(cur+1, g+1);
    }
}

int main()
{
    cin >> n >> t >> m;
    for(int u, v; m--;)
    {
        cin >> u >> v;
        u--, v--;
        hate[v] |= 1 << u;//u < v 只需考虑v讨厌u
    }
    dfs(0, 0);
    cout << ans;
    return 0;
}

---

上面的dfs解法，是对每一个人考虑分配到哪一个组。下面介绍另一种dp方法，这种方法是直接按一个组来考虑的

\(dp[s][k]\) : 将bit串为s的这些人分成k组，且前k组已经固定下来（即：不再向前k组中加人）有多少种分配方式。

这里解释固定的含义，对于dp[s][k]来说，s中的1表示已经分在前k组中的人，0表示未分组的人，由于这里是一次性的按组考虑，所以是把若干个未分组的0组成第k+1组，而不是把这些未分组的0加入到前k组中(因为前k组已经固定下来了，也就是已经分好了)。

由于是分组考虑的，还要先预处理出来ok数组，ok[s]表示bit串为s的这些人能不能在一个组当中。

dp转移为 \(dp[ns][k+1] += dp[s][k]\), 其中ns是包含s且比s更大的一个集合，即ns是s中的某些0变成1之后形成的。

dp的时候还要考虑分组顺序的一致性，也就是说，s的最右边的那个0一定要包含在k+1组当中，这里的beg就是这个作用。

总的时间复杂度 \(O(T * 3^N)\)，关于这种枚举方式的复杂度证明，见这篇博客二进制集合操作

#include <iostream>

using namespace std;

const int maxl = 1024 + 10;
const int maxn = 11;
int n, t, m, len;
bool ok[maxl];
int hate[maxn], dp[maxl][maxn];

int main()
{
    cin >> n >> t >> m;
    len = 1 << n;
    for(int u, v; m--;)
    {
        cin >> u >> v;
        u--, v--;
        hate[v] |= 1 << u;
    }
    for(int s = 0; s < len; s++)
    {
        int h = 0;
        for(int i = 0; i < n; i++)
            if(s >> i & 1)
                h |= hate[i];
        if(!(s & h))
            ok[s] = 1;//ok[s]表示状态为s的队伍能否相容
    }
    dp[0][0] = 1;
    for(int s = 0; s < len; s++)
    {
        int beg = s | (s + 1);
        for(int ns = beg; ns < len; ++ns |= beg)
            if(ok[s ^ ns])
            {
                for(int i = 0; i < t; i++)
                    dp[ns][i+1] += dp[s][i];
            }
    }
    cout << dp[len-1][t];
    return 0;
}

---

E - NAND repeatedly

给定一个长度为 \(N\) 的序列 \(A = (A_0,\ A_1,\ ...\ A_{N-1})\) ，\(A_i\) 的值为0或1。定义一种运算：

\[ f(i, j) = \left\{ \begin{matrix} A_j& \quad (i=j) \\ f(i, j-1) \ \overline{\land} \ A_j & \quad (i < j) \end{matrix} \right.\]

其中 \(\overline{\land}\) 表示“与非”运算， 即 \(x \overline{\land} y = \lnot(x \land y)\)，\(0 \overline{\land} 0 = 1 \quad 0 \overline{\land} 1 = 1 \quad 1 \overline{\land} 0 = 1 \quad 1 \overline{\land} 1 = 0\)

求出 \(\sum\limits_{i=0}^{N-1}\sum\limits_{j=i}^{N-1}f(i,j)\)的值

数据范围：\(N ≤ 10^6\)

与非运算不满足结合率，因此前缀和之类的方法失效...暴力做法需要\(O(N^2)\)的时间复杂度。

考虑 \(dp[j]\): \(\sum\limits_{i=0}^{j}f(i,j)\)的值，由于 \(f(i, j)\) 的值是0或1，因此\(dp[j]\) 相当于记录了 \(f(0, j)\) 到 \(f(j, j)\) 之间1的个数，则 \(j - dp[j]+1\) 相当于0的个数。

考虑dp转移：根据与非运算的性质，

• 若 \(A_{j}\) 为0，则 \(f(0, j-1)\ \overline{\land} \ A_{j}\) 到 \(f(j-1, j-1)\ \overline{\land} \ A_{j}\) 的值都是1
• 若 \(A_{j}\) 为1，则只有前j-1个中的0才能变成1，此外还有 \(f(j,j)=A_{j}\)本身是1

因此dp转移式为：

\[ dp[j] = \left\{\begin{matrix} j \quad &(A_j = 1)\\ j-dp[j-1]+1 \quad &(A_j = 1) \end{matrix}\right. \]

由于 \(dp[j+1]\) 只和 \(dp[j]\) 有关，也没必要开数组了，用一个变量记录即可，答案就是 \(\sum dp[j]\) ，时间复杂度 \(O(N)\)。

#include <iostream>

using namespace std;
typedef long long LL;

int main()
{
    int n;
    string s;
    cin >> n >> s;
    int dpj = s[0] - '0';
    LL ans = dpj;
    for(int j = 1; j < n; j++)
    {
        if(s[j] - '0')
            dpj = j + 1 - dpj;
        else
            dpj = j;
        ans += dpj;
    }
    cout << ans << endl;
    return 0;
}

---

F - Make 10 Again

有 \(N\) 个骰子，每个骰子都可以等概率的扔出 \([1, A_i]\)之间的其中一个整数，\(N\) 个骰子同时投掷，求出满足以下条件的概率：

• 至少存在一种方案，使得从中挑选一些骰子的点数之和等于10。

求出这个概率 mod 998244353 的值。

数据范围：

\(N ≤ 100\)

\(A_i ≤ 10^6\)

经典的概率dp。因为只要凑出10，只考虑0-10点能不能凑出，类似背包dp+状压dp的思路，首先引入一个可以“凑出来”的集合的概念，用一个长度为11的bit串表示当前我们能凑出哪些数字，显然，在所有骰子还没扔的时候，我们只能凑出0,因此这个bit串的值为1(00000000001)，假设第一个骰子丢出了2，我们就能凑出2和0当前bit串值就为5(0000000101)，以此类推。

考虑 \(dp[i][s]\) ：前i个骰子的投掷完成后，当前能凑出来的数字bit串为s的概率。

初始时，dp[0][1] = 1，其余为0

dp的转移就是枚举第i枚骰子丢出了多少，然后用位运算更新集合即可。

时间复杂度 \(O(2^{11}*N)\)

#include <iostream>

using namespace std;

typedef long long LL;
const int maxn = 110;
const int len = 1 << 11;
const int mask = len - 1;
const LL mod = 998244353;

void exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b)
        x = 1, y = 0;
    else
        exgcd(b, a % b, y, x), y -= a / b * x;
}
LL getinv(LL a)
{
    LL x, y;
    exgcd(a, mod, x, y);
    return (x + mod) % mod;
}

int n, x;
LL p;
LL dp[maxn][len];

int main()
{
    cin >> n;
    dp[0][1] = 1;
    for(int i = 0; i < n; i++)
    {
        cin >> x;
        p = getinv(x);
        for(int s = 1; s < len; s++)
        {
            if(!dp[i][s])
                continue;
            for(int k = 1; k <= min(x, 10); k++)
            {
                int ns = s | (s << k) & mask;
                dp[i+1][ns] += dp[i][s] * p;
                dp[i+1][ns] %= mod;
            }
            if(x > 10)
            {
                dp[i+1][s] += dp[i][s] * (p * (x - 10) % mod);
                dp[i+1][s] %= mod;
            }
        }
    }
    LL ans = 0;
    for(int s = 1 << 10; s < len; s++)
        ans = (ans + dp[n][s]) % mod;
    cout << ans << endl;
    return 0;
}

---

最后更新: 2023-08-18
创建日期: 2023-08-17