每日一题-20250808

发表于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

Leetcode

808. 分汤/第 78 场周赛 Q3/Rating 2397

  • 概率 dp
  • 诈骗

考虑朴素概率 dp：dpi,jdp_{i, j} 表示汤 AA 剩余 ii ml 且汤 BB 剩余 jj ml 时的答案。

显然有状态转移：

dpi,j=14(dpi−100,j+dpi−75,j−25+dpi−50,j−50+dpi−25,j−75)dp_{i, j} = \frac 14\left(dp_{i - 100, j} + dp_{i - 75, j - 25} + dp_{i - 50, j - 50} + dp_{i - 25, j - 75}\right)

边界情况：

  • i=j=0i = j = 0：此时两种汤只能被同时耗尽，根据题意有 dp0,0=0.5dp_{0, 0} = 0.5；
  • i=0,j>0i = 0, j > 0：此时只能一直选择第一种操作，根据题意有 dp0,j=1dp_{0, j} = 1；
  • i>0,j=0i > 0, j = 0：此时没有可选择的操作，根据题意有 dpi,0=0dp_{i, 0} = 0。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def soupServings(self, n: int) -> float:
        @cache
        def dfs(i: int, j: int) -> float:
            if i <= 0 and j <= 0:
                return 0.5
            if i <= 0:
                return 1.0
            if j <= 0:
                return 0.0
            return (dfs(i - 100, j) + dfs(i - 75, j - 25) + dfs(i - 50, j - 50) + dfs(i - 25, j - 75)) / 4
        return dfs(n, n)

此时并没有考虑 n≤109n \leq 10^9 的数据范围，朴素的状态转移显然会超时。

注意到答案精度要求只有 10−510^{-5}，每次操作后，汤 AA 期望减少 100+75+50+254=62.5\frac{100 + 75 + 50 + 25}{4} = 62.5 ml，汤 BB 期望减少 25+50+754=37.5\frac{25 + 50 + 75}{4} = 37.5 ml。

这说明每回合汤 AA 在期望下比汤 BB 可以多减少 2525 ml，当 nn 足够大时，AA 相对于 BB 先耗尽的概率必然收敛到 11。

考虑到上述 dp 的时间复杂度为 O(n2)\mathcal O(n^2)，不妨直接令上界为 50005000，当 n>5000n > 5000 时，答案直接输出 1（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def soupServings(self, n: int) -> float:
        if n > 5000:
            return 1.0
        @cache
        def dfs(i: int, j: int) -> float:
            if i <= 0 and j <= 0:
                return 0.5
            if i <= 0:
                return 1.0
            if j <= 0:
                return 0.0
            return (dfs(i - 100, j) + dfs(i - 75, j - 25) + dfs(i - 50, j - 50) + dfs(i - 25, j - 75)) / 4
        return dfs(n, n)

虽然 5000 上界并不精确，但是够用了（

Codeforces

easy

CF2014D/Rating 1400

  • 差分
  • 滑动窗口

可以考虑用一个定长 l=dl = d 的滑动窗口来滑。

考虑一个差分做法：对于一个区间 [L,R][L, R]，拜访时间右端点的合法范围是 [L,R+d−1][L, R + d - 1]，只要对这个东西做差分，维护出差分的前缀最值和对应下标即为答案。

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
def solve():
    n, d, k = map(int, input().split())
    segs = []
    for _ in range(k):
        l, r = map(int, input().split())
        segs.append((l, r))
    diff = [0] * (n + d + 1)
    for l, r in segs:
        diff[l] += 1
        diff[r + d] -= 1
    mn, mnPos = k + 1, 0
    mx, mxPos = -1, 0
    for i in range(1, n + 1):
        diff[i] += diff[i - 1]
        l = i - d + 1
        if l <= 0:
            continue
        if diff[i] > mx:
            mx, mxPos = diff[i], l
        if diff[i] < mn:
            mn, mnPos = diff[i], l
    print(mxPos, mnPos)

t = int(input())
for _ in range(t):
    solve()

hard

CF2001D/Rating 1900

  • 栈

本题最终选择的序列长度为原序列中不同元素的个数，且选出的序列要最大化奇数位，最小化偶数位。

先考虑一个弱化问题：从一个序列中选出一个所有元素只出现一次且字典序最小的序列。

这个问题可用栈解决：

  • 如果当前元素比栈顶的更小，就把栈顶弹出，换成当前元素；
  • 如果某个元素在后面没有再出现，那还需要判断：
    • 如果栈里面还有这个数，不用处理；
    • 如果栈里面没有这个数，那就再塞回去。
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
class Solution {
public:
    string smallestSubsequence(string s) {
        int n = s.length();
        std::map<char, int> lst, vis;
        for(int i = 0; i < n; i++)
            lst[s[i]] = i;
        std::deque<int> q;
        for(int i = 0; i < n; i++)
        {
            if(vis[s[i]])
                continue;
            while(!q.empty() && s[q.back()] > s[i] && lst[s[q.back()]] > i)
            {
                vis[s[q.back()]] = 0;
                q.pop_back();
            }
            q.push_back(i);
            vis[s[i]] = 1;
        }
        std::string ans;
        for(int i = 0; i < q.size(); i++)
            ans += s[q[i]];
        return ans;
    }
};

本题需要根据奇偶位置来判断当前元素与栈顶的关系；同时，如果栈里面存在多于两个数，也判断一下能不能弹掉，替换掉两个数中靠前的那一个即可。

时间复杂度为 O(n)\mathcal O(n)。

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
#include<bits/stdc++.h>
#define ioclear std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#define endl '\n'

void solve()
{
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for(int i = 1; i <= n; i++)
        std::cin >> a[i];
    std::vector<int> lst(n + 1), vis(n + 1);
    std::vector<int> stk(n + 1);
    int top = -1;
    for(int i = 1; i <= n; i++)
        lst[a[i]] = i;
    for(int i = 1; i <= n; i++)
    {
        if(vis[a[i]])
            continue;
        while(top >= 0 && (top & 1 ? a[stk[top]] > a[i] : a[stk[top]] < a[i]) && lst[a[stk[top]]] > i)
        {
            vis[a[stk[top]]] = 0;
            top--;
        }
        while(top >= 1 && ((top - 1) & 1 ? a[stk[top - 1]] > a[i] : a[stk[top - 1]] < a[i]) && lst[a[stk[top]]] > i && lst[a[stk[top - 1]]] > i)
        {
            vis[a[stk[top]]] = 0;
            top--;
            vis[a[stk[top]]] = 0;
            top--;
        }
        top++;
        stk[top] = i;
        vis[a[stk[top]]] = 1;
    }
    std::cout << top + 1 << endl;
    for(int i = 0; i <= top; i++)
        std::cout << a[stk[i]] << " \n"[i == top];
}

int main()
{
    #ifdef ONLINE_JUDGE
    ioclear;
    #endif

    int t = 1;
    std::cin >> t;
    while(t--)
        solve();
}