总结

• 好久没做acw了，挺难的。
• T1 模拟
• T2 前缀和以及优化。
• T3 贪心
• 

5295. 三元组

链接: 5295. 三元组

1. 题目描述

2. 思路分析

• 设a=sum(0,x),b=sum(y,z)。那么best=a+b-(s-a-b)=2(a+b)-s。
• 那么其实是找最大的a+b。用前缀和来处理这个事情。
• 即pre[x] + (pre[z] - pre[y]),注意其实可以用左闭右开写法。
• 由于数据量5000，可以枚举y和z，记录y之前的最大x即可。

---

• 也可以优化成O(n),有点类似状态机DP。

3. 代码实现

def solve():"""best = (0~x)+(y~z) - (s-(0~x)-(y~z)) = 2((0~x)+(y~z)) - s因此是 找最大的两段和， pre[x] + pre[z] - pre[y],其中x<=y<=z,记录y之前最大的pre[x]，z之前最大的pre[x]-pre[y]即可"""n, = RI()a = RILST()p = 0mx = [0, 0, 0, 0]  # best,x,y,zpx = [0, 0]  # prex,xpy = [0, 0, 0]  # pre[x]-pre[y]for z, v in enumerate(a, start=1):p += vpx = max(px, [p, z])py = max(py, [px[0] - p, px[1], z])mx = max(mx, [p + py[0], py[1], py[2], z])       print(*mx[1:])def solve1():n, = RI()a = RILST()pre = [0] + list(accumulate(a))mx = [0, 0, 0, 0]pm = [(i, v) for i, v in enumerate(pre)]for i in range(1, n + 1):if pm[i][1] <= pm[i - 1][1]:pm[i] = pm[i - 1][:]for y in range(0, n):for z in range(y, n):mx = max(mx, [pre[z + 1] - pre[y] + pm[y][1], pm[y][0], y, z + 1])print(*mx[1:])

5296. 边的定向

链接: 5296. 边的定向

1. 题目描述

2. 思路分析

貌似很难，但其实贪心能过。

• 最大访问数就是尽量向外延伸，把所有访问到的边都朝外指。
• 最小访问数就是遇到的边超里指，只走本来就有的有向边。
• 代码实现时，建图记录边的id，遇到时判断当前方向和输入方向是否一致决定方向。
• 注意有的边可能不会遇到，可以是任意方向。

3. 代码实现

def solve():n, m, s = RI()g = [[] for _ in range(n + 1)]edges = []for i in range(m):t, u, v = RI()edges.append((u, v, t))g[u].append((v, i))if t == 2:g[v].append((u, i))q = deque([s])  # 把遇到的边都变成正向vis = {s}d = [0] * mwhile q:u = q.popleft()for v, i in g[u]:if v not in vis:vis.add(v)q.append(v)if edges[i][2] == 2:  # 如果是无向边，让他u->vd[i] = '+' if u == edges[i][0] else '-'print(len(vis))ans = []for x, (_, _, t) in zip(d, edges):if t == 2:ans.append(x if x else '+')print(''.join(ans))q = deque([s])  # 把遇到的边都变成负向vis = {s}d = [0] * mwhile q:u = q.popleft()for v, i in g[u]:if v not in vis:if edges[i][2] == 1:  # 有向边必须走vis.add(v)q.append(v)else:  # 无向边不走，u<-vd[i] = '-' if u == edges[i][0] else '+'print(len(vis))ans = []for x, (_, _, t) in zip(d, edges):if t == 2:ans.append(x if x else '+')print(''.join(ans))

六、参考链接

• 无