ABC465-①C-双端队列②D-最近公共祖先③E-数位DP#

AtCoder Beginner Contest 465 - AtCoder

https://www.wolai.com/o1pzNhXkSre3n5N6EUSikW

C-双端队列#

题意#

给你一个整数 $N$ 和一个长度为 $N$ 的由 o 和 x 组成的字符串 $S$ 。

有一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 。最初为 $A=(1,2,\ldots,N)$ 。

依次对 $A$ 和 $k=1,2,\ldots,N$ 执行以下操作。

如果 $S_k=$ `O则将 $A$ 的前 $k$ 项倒置。具体地说，将 $A$ 替换为 $(A_k,A_{k-1},\ldots,A_1,A_{k+1},A_{k+2},\ldots,A_N)$ 。
如果 $S_k=$ x，则什么也不做。

完成所有运算后，找出 $A$ 。

双端队列#

只关心当前前k个元素的部分

用rev标记反转状态

当遇到"o"时，切换rev的状态

当处理到第k个元素时，如果rev = False，新元素k追加到末尾；反之，插入到开头

对于最后的rev，如果rev为True，则反转整个pre

1
from collections import deque
2
n = int(input())
3
s = input()
4
# for i in range(n):
5
#     if s[i] == 'o':
6
#         a[:i+1] = a[:i+1][::-1]
7
# print(*a)
8
pre = deque()
9
ok = 0
10
for k in range(1,n+1):
11
    if ok:
12
        pre.appendleft(k)
13
    else:
14
        pre.append(k)
15
    if s[k-1] == 'o':
16
        ok ^= 1
17
if ok:
18
    ans = list(pre)[::-1]
19
else:
20
    ans = list(pre)
21
print(*ans)

D-最近公共祖先#

题意#

给你一个整数 $X,Y$ 和一个至少是 $2$ 的整数 $K$ 。

有一个变量 $x$ ，其初始值为 $x=X$ 。您可以对 $x$ 执行以下操作 0 次或多次：

选择一个满足 $\displaystyle \left\lfloor \frac xK \right\rfloor=y$ 或 $\displaystyle \left\lfloor \frac yK \right\rfloor=x$ 的整数 $y$ ，并将 $x$ 的值替换为 $y$ 。

这里， $\displaystyle \left\lfloor z \right\rfloor$ 被定义为实数 $z$ 不超过 $z$ 的最大整数。

求生成 $x=Y$ 所需的最小运算次数。在给定的限制条件下，可以证明总有一种方法可以在有限的运算次数内求出 $x=Y$ 。

给你 $T$ 个测试用例，请逐一求解。

最近公共祖先LCA#

在树中，两点间有且只有一条简单路径。如果路径不经过它们的公共祖先，就必须在某个节点不走父节点方向而走子节点方向，这只会增加不必要的绕路。找到最低公共祖先后，两条向上的路径拼接起来，正是树上两节点间的唯一最短路径。

从 cur = X 开始，不断执行 cur //= K，直到 cur == 0

用字典 ans 记录路径上每个节点到 X 的距离 d

从 cur = Y，d = 0 开始，同样不断执行 cur //= K。

每一步检查当前 cur 是否已经存在于 ans 字典中。

一旦在 ans 中找到 cur，说明找到了 X 向上路径和 Y 向上路径的最低公共祖先。

此时最短距离就是 d + ans[cur]（从 X 到祖先的距离 + 从 Y 到祖先的距离）。

1
for _ in range(int(input())):
2
    x,y,k = map(int,input().split())
3
    if x == y:
4
        print(0)
5
    else:
6
        ans = {}
7
        cur = x
8
        d = 0
9
        while True:
10
            ans[cur] = d
11
            if cur == 0:
12
                break
13
            cur //= k
14
            d += 1
15
        cur = y
16
        d = 0
17
        while True:
18
            if cur in ans:
19
                print(d + ans[cur])
20
                break
21
            cur //= k
22
            d += 1

1
for _ in range(int(input())):
2
    x, y, k = map(int, input().split())
3
    ans = 0
4
    while x != y:
5
        if x < y:
6
            x, y = y, x
7
        x //= k
8
        ans += 1
9
    print(ans)

E-数位DP#

题目#

求模为 $998244353$ 的整数 $x$ 与 $1 \leq x \leq N$ 中，满足以下三个条件中个的整数个数。

$x$ 是 $3$ 的倍数。
$x$ 的十进制表示包含 3。
$x$ 的十进制表示恰好使用了三个不同的数字。

这里，整数的十进制表示不应有不必要的前导 “0”。

数位DP#

1
MOD = 998244353
2

3
def solve():
4
    s = input().strip()
5
    n = len(s)
6

7
    # dp[i][bi][mi][li]
8
    dp = [[[[0] * 2 for _ in range(3)] for _ in range(1 << 10)] for _ in range(n + 1)]
9
    dp[0][0][0][0] = 1
10

11
    for i in range(n):
12
        si = int(s[i])
13

14
        for bi in range(1 << 10):
15
            for mi in range(3):
16
                for li in range(2):
17
                    if dp[i][bi][mi][li] == 0:
18
                        continue
19
                    val = dp[i][bi][mi][li]
20

21
                    max_d = 9 if li == 1 else si
22
                    for d in range(max_d + 1):
23
                        # 处理前导零
24
                        if bi == 0 and d == 0:
25
                            bx = 0
26
                        else:
27
                            bx = bi | (1 << d)
28
                        mx = (mi * 10 + d) % 3
29
                        lx = li or (d < si)
30
                        dp[i + 1][bx][mx][lx] = (dp[i + 1][bx][mx][lx] + val) % MOD
31

32
    ans = 0
33
    for bi in range(1, 1 << 10):  # bi=0 对应数字 0，排除
34
        for mi in range(3):
35
            for li in range(2):
36
                cnt = dp[n][bi][mi][li]
37
                if cnt == 0:
38
                    continue
39

40
                cond = 0
41
                # 条件1：恰好三个不同数字
42
                if bi.bit_count() == 3:
43
                    cond += 1
44
                # 条件2：包含数字 3
45
                if bi & (1 << 3):
46
                    cond += 1
47
                # 条件3：是 3 的倍数
48
                if mi == 0:
49
                    cond += 1
50

51
                if cond == 1:
52
                    ans = (ans + cnt) % MOD
53

54
    print(ans)
55

56
if __name__ == "__main__":
57
    solve()

1
#include <iostream>
2
using std::cin;
3
using std::cout;
4
using std::cerr;
5
using std::endl;
6
#include <vector>
7
using std::vector;
8
#include <string>
9
using std::string;
10
using std::to_string;
11
#include <bit>
12
using std::popcount;
13

14
typedef long long int ll;
15

16
const ll FOD = 998244353;
17

18
string s;
19

20
ll dp[505][1 << 10][3][2];
21
void solve() {
22
  // init dp[0]
23
  for (ll bi = 0; bi < (1<<10); bi++) {
24
    for (ll mi = 0; mi < 3; mi++) {
25
      for (ll li = 0; li < 2; li++) {
26
        dp[0][bi][mi][li] = 0;
27
      }
28
    }
29
  }
30
  dp[0][0][0][0] = 1;
31

32
  for (ll i = 0; i < s.size(); i++) {
33
    ll si = (s[i] - '0');
34

35
    // init dp[i+1]
36
    for (ll bi = 0; bi < (1<<10); bi++) {
37
      for (ll mi = 0; mi < 3; mi++) {
38
        for (ll li = 0; li < 2; li++) {
39
          dp[i+1][bi][mi][li] = 0;
40
        }
41
      }
42
    }
43

44
    // dp[i] -> dp[i+1]
45
    for (ll bi = 0; bi < (1<<10); bi++) {
46
      for (ll mi = 0; mi < 3; mi++) {
47
        // unroll loop for li
48
        for (ll d = 0; d <= 9; d++) {
49
          ll bx = ((bi == 0 && d == 0) ? 0 : (bi | (1LL << d)));
50
          ll mx = (mi * 10 + d) % 3;
51
          // li 0
52
          if (d <= si) {
53
            dp[i+1][bx][mx][(d == si) ? 0 : 1] += dp[i][bi][mi][0];
54
          }
55
          dp[i+1][bx][mx][1] += dp[i][bi][mi][1];
56
        }
57
      }
58
    }
59

60
    // modulo
61
    for (ll bi = 0; bi < (1<<10); bi++) {
62
      for (ll mi = 0; mi < 3; mi++) {
63
        for (ll li = 0; li < 2; li++) {
64
          dp[i+1][bi][mi][li] %= FOD;
65
        }
66
      }
67
    }
68
  }
69

70
  // dp[n] -> ans
71
  ll ans = 0;
72
  for (ll bi = 1; bi < (1<<10); bi++) {
73
    for (ll mi = 0; mi < 3; mi++) {
74
      for (ll li = 0; li < 2; li++) {
75
        ll cond = 0;
76
        if (popcount((uint64_t)bi) == 3) cond++;
77
        if (bi & (1LL << 3)) cond++;
78
        if (mi == 0) cond++;
79

80
        if (cond == 1) {
81
          ans += dp[s.size()][bi][mi][li];
82
        }
83
      }
84
    }
85
  }
86
  ans %= FOD;
87

88
  cout << ans << "\n";
89
}
90

91
int main (void) {
92
  std::cin.tie(nullptr);
93
  std::ios_base::sync_with_stdio(false);
94

95
  cin >> s;
96

97
  solve();
98

99
  return 0;
100
}

音乐

音乐