网站affiliate怎么做,企业网站的建设公司价格,自己做网站能赚钱么,网站怎么做构成[acwing周赛复盘] 第 94 场周赛20231118 总结5295. 三元组1. 题目描述2. 思路分析3. 代码实现 5296. 边的定向1. 题目描述2. 思路分析3. 代码实现 六、参考链接 总结
好久没做acw了#xff0c;挺难的。T1 模拟T2 前缀和以及优化。T3 贪心
5295. 三元组
链接: 5295. 三元组… [acwing周赛复盘] 第 94 场周赛20231118 总结5295. 三元组1. 题目描述2. 思路分析3. 代码实现 5296. 边的定向1. 题目描述2. 思路分析3. 代码实现 六、参考链接 总结
好久没做acw了挺难的。T1 模拟T2 前缀和以及优化。T3 贪心
5295. 三元组
链接: 5295. 三元组
1. 题目描述 2. 思路分析
设asum(0,x),bsum(y,z)。那么bestab-(s-a-b)2(ab)-s。那么其实是找最大的ab。用前缀和来处理这个事情。即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],其中xyz,记录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, start1):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))六、参考链接
无
