网易互娱 4.12 笔试真题

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    grid = [input().strip() for _ in range(n)]

    light = [[0] * m for _ in range(n)]

    # 方向编号: L=0, R=1, U=2, D=3
    DR = [0, 0, -1, 1]
    DC = [-1, 1, 0, 0]
    # '/' 反射查表: L->D, R->U, U->R, D->L
    REF_SLASH = [3, 2, 1, 0]
    # '\' 反射查表: L->U, R->D, U->L, D->R
    REF_BACK = [2, 3, 0, 1]

    DIR_MAP = {'L': 0, 'R': 1, 'U': 2, 'D': 3}
    LAMPS = set('LRUD')

    for r in range(n):
        for c in range(m):
            if grid[r][c] not in LAMPS:
                continue
            # 从灯出发追踪光线
            d = DIR_MAP[grid[r][c]]
            cr, cc = r, c
            visited = set()
            while True:
                nr, nc = cr + DR[d], cc + DC[d]
                if nr < 0 or nr >= n or nc < 0 or nc >= m:
                    break
                ch = grid[nr][nc]
                # 障碍物和其他灯会挡住光线
                if ch == '#' or ch in LAMPS:
                    break
                if ch == '.':
                    light[nr][nc] += 1
                    cr, cc = nr, nc
                else:
                    # 镜子：记录(位置,方向)防止无限循环
                    key = (nr, nc, d)
                    if key in visited:
                        break
                    visited.add(key)
                    d = REF_SLASH[d] if ch == '/' else REF_BACK[d]
                    cr, cc = nr, nc

    # 空地输出光照强度，非空地输出-1
    lines = []
    for r in range(n):
        row = []
        for c in range(m):
            row.append(str(light[r][c]) if grid[r][c] == '.' else '-1')
        lines.append(' '.join(row))
    print('\n'.join(lines))

main()

import sys
from collections import deque
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    w = [int(input()) for _ in range(N)]

    # dep_mask[i]的第j位为1表示任务i依赖任务j
    dep_mask = [0] * N
    deps = [[] for _ in range(N)]
    children = [[] for _ in range(N)]
    in_deg = [0] * N

    for _ in range(K):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        dep_mask[v] |= (1 << u)
        deps[v].append(u)
        children[u].append(v)
        in_deg[v] += 1

    # 拓扑排序检测环
    q = deque(i for i in range(N) if in_deg[i] == 0)
    cnt = 0
    temp = in_deg[:]
    while q:
        u = q.popleft()
        cnt += 1
        for v in children[u]:
            temp[v] -= 1
            if temp[v] == 0:
                q.append(v)

    if cnt != N:
        print(-1)
        return

    full = (1 << N) - 1
    best = sum(w)
    finish = [0] * N

    def dfs(mask, t1, t2):
        nonlocal best
        # 对称性剪枝：保证 t1 <= t2
        if t1 > t2:
            t1, t2 = t2, t1
        # 最优性剪枝
        if t2 >= best:
            return
        if mask == full:
            best = t2
            return
        for i in range(N):
            if mask >> i & 1:
                continue
            # 检查依赖是否全部满足
            if dep_mask[i] & mask != dep_mask[i]:
                continue
            ready = max((finish[j] for j in deps[i]), default=0)
            old = finish[i]
            # 尝试分配到线程1
            s1 = max(t1, ready)
            finish[i] = s1 + w[i]
            dfs(mask | (1 << i), s1 + w[i], t2)
            finish[i] = old
            # 尝试分配到线程2（去重剪枝：开始时间相同则跳过）
            s2 = max(t2, ready)
            if s2 != s1:
                finish[i] = s2 + w[i]
                dfs(mask | (1 << i), t1, s2 + w[i])
                finish[i] = old

    dfs(0, 0, 0)
    print(best)

main()