[acwing周赛复盘] 第 94 场周赛20230311
[acwing周赛复盘] 第 94 场周赛20231118
- 总结
- 5295. 三元组
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 5296. 边的定向
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 六、参考链接
总结
- 好久没做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))
六、参考链接
- 无