每日一题 3.10-3.16
文章目录
题目来自 AcWing
刚说完上周题简单，这周一的题就给我干碎了……
5589. 哞语言逻辑 | 原题链接
首先用 Python 特有的 eval 来试一下：
1true, false = True, False
2n, q = map(int, input().strip().split())
3exp = input().strip().split()
4
5ans = list()
6for _ in range(q):
7 a, b, bl = input().strip().split()
8 a = int(a) - 1
9 b = int(b) - 1
10 if eval(' '.join(exp[:a] + ["true"] + exp[b + 1:])) == eval(bl) or eval(' '.join(exp[:a] + ["false"] + exp[b + 1:])) == eval(bl):
11 ans.append("Y")
12 else:
13 ans.append("N")
14print(''.join(ans))
这样可以通过 8/26 个测试点然后超时，而且这样也没有达到练习的真正目的。
题目给出的一整行布尔语句，根据优先级可以分割为一连串 $and$ 的 $or$，即
$$ (false)\space or\space (true\space and\space false\space and\space false\space and\space true)\space or\space (true\space and\space false)\space or\cdots $$
$or$ 相当于逻辑加，$and$ 相当于逻辑乘。当某个区间内的表达式需要被替换为一个布尔值时，这个区间一定与原表达式中一个或多个连续的 $and$ 段有交集。记这些被修改的段的运算结果为 $seg$，这些段左侧的段的运算结果为 $seg_L$，这些段右侧的段的运算结果为 $seg_R$，因此新的结果可以表示为 $seg_L\space or\space seg\space or\space seg_R$，其中 $seg_L$ 和 $seg_R$ 分别可以用前缀和和后缀和记录以节约时间。
被修改的段 $seg$ 又可以分为三部分：段首到区间左端点 $exp_L$，中间修改后的 $true$ 或 $false$（记作 $exp$），区间右端点到段尾的 $exp_R$，因此 $seg$ 可以表示为 $seg=exp_L\space and\space exp\space and\space exp_R$。每一段里的区间同样可以使用前缀和和后缀和记录。
最后是一些细节上的处理，寻找被修改区间的左右端点用二分查找实现，以及注意使用前后缀和时的边界问题。
1import sys
2
3data = sys.stdin.read().strip().split("\n")
4n, q = map(int, data[0].strip().split())
5exp = data[1].strip().split() + ["or"]
6seg = list()
7l = 0
8curr = 1
9for i in range(n + 1):
10 if exp[i] == "false":
11 curr = 0
12 if exp[i] == "or":
13 seg.append((l, i - 1, curr))
14 l = i + 1
15 curr = 1
16
17pre = [0]
18for i in range(len(seg)):
19 pre.append(pre[-1] | seg[i][2])
20suf = [0]
21for i in range(len(seg))[::-1]:
22 suf.append(suf[-1] | seg[i][2])
23suf = suf[::-1]
24
25segpre = dict()
26segsuf= dict()
27for i, ss in enumerate(seg):
28 p = [1]
29 s = [1]
30 start, end, _ = ss
31 for j in range(start, end + 1):
32 if exp[j] == "true":
33 p.append(p[-1] & 1)
34 elif exp[j] == "false":
35 p.append(p[-1] & 0)
36 segpre[i] = p
37 for j in range(start, end + 1)[::-1]:
38 if exp[j] == "true":
39 s.append(s[-1] & 1)
40 elif exp[j] == "false":
41 s.append(s[-1] & 0)
42 segsuf[i] = s[::-1]
43
44ans = list()
45for ii in range(2, q + 2):
46 a, b, bl = data[ii].strip().split()
47 a = int(a) - 1
48 b = int(b) - 1
49
50 l = 0
51 r = len(seg) - 1
52 while l <= r:
53 mid = (l + r) // 2
54 if seg[mid][0] // 2 > a // 2:
55 r = mid
56 elif seg[mid][1] // 2 < a // 2:
57 l = mid + 1
58 else:
59 sega = mid
60 break
61
62 l = 0
63 r = len(seg) - 1
64 while l <= r:
65 mid = (l + r) // 2
66 if seg[mid][0] // 2 > b // 2:
67 r = mid
68 elif seg[mid][1] // 2 < b // 2:
69 l = mid + 1
70 else:
71 segb = mid
72 break
73
74 left = segpre[sega][(a - seg[sega][0]) // 2]
75 right = segsuf[segb][(b - seg[segb][0]) // 2 + 1]
76
77 T, F = 1, 0
78 if seg[sega][0] != a:
79 T = T & left
80 F = F & left
81 if seg[segb][1] != b:
82 T = T & right
83 F = F & right
84
85 T = pre[sega] | T | suf[segb + 1]
86 F = pre[sega] | F | suf[segb + 1]
87 if bl == "false" and (T == 0 or F == 0):
88 ans.append("Y")
89 elif bl == "true" and (T == 1 or F == 1):
90 ans.append("Y")
91 else:
92 ans.append("N")
93
94print(*ans, sep="")
5590. 沿栅栏散步 | 原题链接
直接打表做，记录 $position\rightarrow step$ 的映射，然后比较顺时针和逆时针哪个距离更短。用 sys.stdin.read 读取数据才能 AC。
1import sys
2
3data = sys.stdin.read().strip().split("\n")
4n, p = map(int, data[0].strip().split())
5step = dict()
6length = 0
7
8def go(x, y, last):
9 global length
10 if x > last[0]:
11 for i in range(last[0], x):
12 step[(i, y)] = length
13 length += 1
14 elif x < last[0]:
15 for i in range(last[0], x, -1):
16 step[(i, y)] = length
17 length += 1
18 elif y > last[1]:
19 for i in range(last[1], y):
20 step[(x, i)] = length
21 length += 1
22 elif y < last[1]:
23 for i in range(last[1], y, -1):
24 step[(x, i)] = length
25 length += 1
26
27for i in range(p):
28 x, y = map(int, data[i + 1].strip().split())
29 if i == 0:
30 first = last = (x, y)
31 continue
32
33 go(x, y, last)
34 last = (x, y)
35
36go(*first, last)
37for i in range(n):
38 xa, ya, xb, yb = map(int, data[1 + p + i].strip().split())
39 sa = abs(step[(xa, ya)] - step[(xb, yb)])
40 sb = length - sa
41 print(min(sa, sb))
这道题也可以记录两点间的距离然后用前缀和做，比较困难的部分是判断要查询的点在哪条线段上，这需要用线段树解决（类似于扫描线）但是对我来说太难了 QAQ
4888. 领导者 | 原题链接
如果一条奶牛想要称为领导者，则他必须满足下面两个条件之一：
- 名单中包含其品种的所有奶牛。
- 名单中包含另一品种的领导者。
因为名单包含了从这头奶牛到他右侧某个位置中间的所有奶牛，因此这两个领导者的名单不可能同时包含对方，也就是说两头领导者要么都是通过规则 1 成为领导者，要么是一个 1 一个 2 成为领导者。
1from bisect import bisect_right as b_r
2
3n = int(input().strip())
4cows = input().strip()
5vote = tuple(map(lambda x:int(x) - 1, input().strip().split()))
6
7s = set()
8g = list()
9h = list()
10for i in range(n):
11 if cows[i] == 'G':
12 g.append(i)
13 else:
14 h.append(i)
15
16if vote[g[0]] >= g[-1] and vote[h[0]] >= h[-1]:
17 s.add((g[0], h[0]))
18
19if vote[g[0]] >= g[-1]:
20 for hh in h:
21 if hh > g[0]:
22 break
23 if vote[hh] >= g[0]:
24 s.add((g[0], hh))
25if vote[h[0]] >= h[-1]:
26 for gg in g:
27 if gg > h[0]:
28 break
29 if vote[gg] >= h[0]:
30 s.add((gg, h[0]))
31print(len(s))
4889. 空调II | 原题链接
这道题的核心思路是枚举，或者说是二进制枚举。空调最多有 10 台，每台空调都有开或者不开两种状态，因此最多也只有 1024 种情况。下面的代码从 for i in range(1 << m) 开始是二进制枚举的核心代码，还算比较好理解。
1n, m = map(int, input().strip().split())
2target = [0] * 101
3for _ in range(n):
4 si, ti, ci = map(int, input().strip().split())
5 for i in range(si, ti + 1):
6 target[i] = ci
7cost, field, effect = list(), list(), list()
8for _ in range(m):
9 ai, bi, pi, mi = map(int, input().strip().split())
10 field.append((ai, bi))
11 effect.append(pi)
12 cost.append(mi)
13
14min_cost = float("inf")
15for i in range(1 << m):
16 c = 0
17 curr = [0] * 101
18 for j in range(m):
19 if i & (1 << j):
20 a, b = field[j]
21 p = effect[j]
22 m = cost[j]
23 c += m
24 for k in range(a, b + 1):
25 curr[k] += p
26 sat = True
27 for j in range(101):
28 if target[j] > curr[j]:
29 sat = False
30 break
31 if not sat:
32 continue
33 else:
34 min_cost = min(c, min_cost)
35
36print(min_cost)
时间复杂度达到了惊人的 $O(2^MMN)$！
4905. 面包店 | 原题链接
这道题最容易想到的做法是先二分查找升级后制作两种糕点花费的总时间，然后通过在这个总时间内遍历制作两种糕点所需时间，进而判断当前方案是否可行。这样做可以通过 4/11 个测试点。
1T = int(input())
2for _ in range(T):
3 input()
4 N, tc, tm = map(int, input().strip().split())
5 orders = list()
6 for _ in range(N):
7 ai, bi, ci = map(int, input().strip().split())
8 if ai * tc + bi * tm > ci:
9 orders.append((ci, ai, bi))
10 orders.sort()
11
12 l, r = 2, tc + tm
13 while l < r:
14 mid = (l + r) >> 1
15 for dc in range(1, mid):
16 dm = mid - dc
17 if dc > tc or dm > tm:
18 continue
19
20 valid = True
21 for ci, ai, bi in orders:
22 if ai * dc + bi * dm > ci:
23 valid = False
24 break
25
26 if valid:
27 ans = mid
28 break
29
30 if valid:
31 l = mid + 1
32 else:
33 r = mid
34 print(tc + tm - ans)
假设在升级后，制作两种糕点的时间分别为 $d_c$ 和 $d_m$，令 $t=d_c+d_m$，题目要找到满足 $\forall a_i\cdot d_c+b_i\cdot d_m\leq c_i$ 的最大 $t$。对于每一组 $a_i,b_i,c_i$ 可以对该式作如下变换：
$$ a_i\cdot d_c+b_i\cdot (t-d_c)\leq c_i \\ (a_i-b_i)\cdot d_c\leq c_i-b_i\cdot t $$
此时对 $d_c$ 分类讨论，当 $a_i-b_i=0$ 时，如果 $d_c>c_i-b_i\cdot t$ 则当前情况不成立；
当 $a_i-b_i>0$ 时，$d_c\leq\frac{c_i-b_i\cdot t}{a_i-b_i}$ 可以得到 $d_c$ 的上界；
当 $a_i-b_i<0$ 时，$d_c\geq\frac{c_i-b_i\cdot t}{a_i-b_i}$ 可以得到 $d_c$ 的下界；
最后如果 $d_c$ 的上界 $c_{hi}$ 大于等于下界 $c_{lo}$（确保 $d_c$ 存在）且 $t-c_{hi}\leq t_m$、$t-c_{lo}\geq 1$（确保 $d_m$ 合法且未越界），则当前的答案合法。对 $t$ 在 $[2,t_c+t_m]$ 范围内二分查找，如果某个 $t$ 对于上面的判定合法，则说明 $t$ 再大一些也可能是合法的（要查找 $t_c+t_m-t$ 的最小值），左边界向右移动，否则右边界左移。
1from math import ceil, floor
2
3T = int(input())
4for _ in range(T):
5 input()
6 N, tc, tm = map(int, input().strip().split())
7 orders = list()
8 for _ in range(N):
9 ai, bi, ci = map(int, input().strip().split())
10 if ai * tc + bi * tm > ci:
11 orders.append((ci, ai, bi))
12
13 l, r = 2, tc + tm
14 while l < r:
15 mid = (l + r) >> 1
16 valid = True
17 c_lo, c_hi = 1, tc
18 for ci, ai, bi in orders:
19 if ai == bi:
20 if bi * mid > ci:
21 valid = False
22 break
23 elif ai > bi:
24 dc = floor((ci - bi * mid) / (ai - bi))
25 c_hi = min(dc, c_hi)
26 else:
27 dc = ceil((ci - bi * mid) / (ai - bi))
28 c_lo = max(dc, c_lo)
29
30 if c_lo > c_hi:
31 valid = False
32 break
33
34 if mid - c_hi > tm or mid - c_lo < 1:
35 valid = False
36 break
37
38 if valid:
39 ans = mid
40 l = mid + 1
41 else:
42 r = mid
43 print(tc + tm - ans)
其他人写的题解中直接查找总升级次数，大体思路一样，但是不需要做 mid - c_hi > tm or mid - c_lo < 1 的判定。