415

A

签到。

B

签到。

C

一开始没有看懂题捏。 混合其实是或运算，给的 binary string 其实是第i种是危险的，由于n不大 所以其实暴力搜索即可。

bfs code

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
 
    // danger[i] 表示状态i是否危险
    vector<int> danger(1 << n, 0);
    for (int i = 1; i < (1 << n); i++)
    {
        danger[i] = (s[i - 1] - '0');
    }
 
    // BFS
    queue<int> q;
    vector<bool> visited(1 << n, false);
 
    q.push(0); // 从空状态开始
    visited[0] = true;
 
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
 
        // 检查是否到达目标状态
        if (cur == (1 << n) - 1)
        {
            cout << "Yes";
            return;
        }
 
        // 尝试添加每种化学试剂
        for (int i = 0; i < n; i++)
        {
            if (cur & (1 << i))
            {
                continue;
            } // 已经包含这种试剂
 
            int next = cur | (1 << i); // 添加第i种试剂
 
            if (!visited[next] && !danger[next]) // 状态安全且未访问过
            {
                visited[next] = true;
                q.push(next);
            }
        }
    }
 
    cout << "No";
}

笔者写到这里，发现自己已经忘记bfs怎么写了… 于是紧急恶补了一下 现在大概搞懂了 原来细节这么多。

但是这样一来 就有优美的位运算版本了

void solve()
{
    int n;
    string s;
    cin >> n >> s;
 
    // dp[mask] 表示状态 mask 是否可达
    vector<int> dp(1 << n, 0);
    dp[0] = 1; // 空状态可达
 
    for (int mask = 0; mask < (1 << n); mask++)
    {
        if (!dp[mask])
        {
            continue;
        }
 
        // 尝试添加每种化学试剂
        for (int i = 0; i < n; i++)
        {
            if (mask & (1 << i))
            {
                // 已经包含这种试剂
                continue;
            }
 
            int next = mask | (1 << i);
            if (s[next - 1] == '0')
            {
                // 新状态安全
                dp[next] = 1;
            }
        }
    }
 
    cout << (dp[(1 << n) - 1] ? "Yes" : "No");
}

D

原问题等价于我们初始拥有 n 个空瓶，现在要最大化答案，而贡献答案的方式就是用多的空瓶 a 去交换比较少的空瓶 b。 也就等价于 我们每次花费 a - b 去贡献答案。 因此 自然可以想到关于 a - b 排序，这样一来我们只需在一次遍历中重复 贡献答案 的 操作 即可 代码如下：

void solve()
{
    int n, m;
    cin >> n >> m;
 
    vector<pair<int, int>> v(m);
    for (int i = 0; i < m; i++)
    {
        cin >> v[i].first >> v[i].second; // a, b
    }
 
    // 按 a - b 排序（损失从小到大）
    sort(all(v), [](auto x, auto y)
         { return x.first - x.second < y.first - y.second; });
 
    int ans = 0;
 
    for (auto [a, b] : v)
    {
 
        int loss = a - b; // 每一次贡献答案的代价
		while (n >= a)
		{
			ans++;
			n -= (a - b);
		}
    }
 
    cout << ans;
}

但是这样做存在超时风险 进而想到 其实可以通过除法优化

假设我们现在有 n 个空瓶 最多可以贡献 k 次答案( k 待求) 那么显然有：

$$n-loss\ast k\ge a$$

那么 k 就满足：

$$k\le \frac{n-a}{loss}$$

上面这个式子真的对吗？ 我们计算的这个 k 是满足 n >= a 的最优结果，但是其实 n >= a 时，我们仍然可以通过更多的一次操作 使 n < a 的同时贡献答案，所以最后要多加一次贡献。

void solve()
{
    int n, m;
    cin >> n >> m;
 
    vector<pair<int, int>> v(m);
    for (int i = 0; i < m; i++)
    {
        cin >> v[i].first >> v[i].second; // a, b
    }
 
    // 按 a-b 排序（损失从小到大）
    sort(all(v), [](auto x, auto y)
         { return x.first - x.second < y.first - y.second; });
 
    int ans = 0;
 
    for (auto [a, b] : v)
    {
 
        int loss = a - b;
 
        // 直接计算最多能交换多少次
        // 需要满足：n - k * loss >= a
        // 即：k <= (n - a) / loss
        if (n >= a)
        {
            int k = (n - a) / loss;
 
            if (k > 0)
            {
                ans += k;
                n -= k * loss;
            }
            if (n >= a)
            {
                ans++;
                n -= loss;
            }
        }
    }
 
    cout << ans;
}

E

到达 [i, j] 的时候应该是 第 i + j - 1 天，不妨记天数为 day ，最后拥有的费用是 dp[i][j] 这一天产生的开销是 v[day] 这个格子上获得的硬币是 a[i][j] 那么我们有： $dp[i][j]+a[i][j]-v[i+j-1]=dp[i+1][j]向右走$ $dp[i][j]+a[i][j]-v[i+j-1]=dp[i][j+1]向下走$

而每一天的钱数都要大于0 这是一个从后往前推的过程： 比方说我今天有 x 元 一番操作之后明天变成了 -1 元 是不是说明我今天起码得有 x+1 元才能够得上这次消费？

所以变成了一次从终点往起点的dp

void solve()
{
    int h, w;
    cin >> h >> w;
 
    vector v(h, vector<int>(w));
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> v[i][j];
        }
    }
 
    vector<int> p(h + w - 1);
    for (int i = 0; i < h + w - 1; i++)
    {
        cin >> p[i];
    }
 
    // dp[i][j] = 到达(i,j)时需要的最少硬币数
    vector dp(h, vector<int>(w, LLONG_MAX));
 
    // 从终点开始倒推
    dp[h - 1][w - 1] = max(0ll, p[h + w - 2] - v[h - 1][w - 1]);
 
    // 处理最后一行（只能从右边来）
    for (int j = w - 2; j >= 0; j--)
    {
        int day = (h - 1) + j;
        dp[h - 1][j] = max(0ll, dp[h - 1][j + 1] + p[day] - v[h - 1][j]);
    }
 
    // 处理最后一列（只能从下面来）
    for (int i = h - 2; i >= 0; i--)
    {
        int day = i + (w - 1);
        dp[i][w - 1] = max(0ll, dp[i + 1][w - 1] + p[day] - v[i][w - 1]);
    }
 
    // 处理其他位置
    for (int i = h - 2; i >= 0; i--)
    {
        for (int j = w - 2; j >= 0; j--)
        {
            int day = i + j;
            int need1 = max(0ll, dp[i + 1][j] + p[day] - v[i][j]); // 从下面来
            int need2 = max(0ll, dp[i][j + 1] + p[day] - v[i][j]); // 从右边来
            dp[i][j] = min(need1, need2);
        }
    }
 
    cout << dp[0][0];
}

写完后 笔者发现这道题其实完全可以二分猜一个起点 毕竟钱币是一直减少的 而我们dp的过程其实已经走完了全部可能。代码就不给了 总之就是把 dp 过程写进二分的check中 然后从开头往终点做dp 如果能到终点的话就可行

F

回到index