AtCoder Beginner COntest 289

A - flip [Easy] 题解

B - V [Easy] 题解

C - Coverage [Easy] 题解

D - Step Up Robot [Medium] 题解

E - Swap Places [Medium] 题解

A - flip

A - flip

就是给你一个01字符串，将里面的0改成1，1改成0

思路

模拟。另外用上异或的小技巧

时间复杂度：O(n)
空间复杂度：O(1)

代码

def solve(): 
    s = input()
    for i in s:
        print(int(i)^1, end='')

B - V

B - V

给定一张无向图，n 个点， m 条边。第 i 条边连接点 ci 和 ci+1。

要求输出所有点，从最小的点所在的连通块开始，并从该连通块标号最大的点开始输出。

思路

遍历，每次求出连续的一段点集合，从大到小输出。

在每次遍历前，要先判断前面有没有点还没有输出，如果有，就从小到大输出。

最后还要判断是否n个点都输出完毕。

时间复杂度：O(n)
空间复杂度：O(1)

代码

def solve(): 
    n, m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    i, pre = 0, 0
    while i < m:
        if a[i] != pre+1:
            for k in range(pre+1, a[i]): print(k, end=' ')
        pre = a[i]-1
        for k in range(i, m):
            if a[k] == pre+1: pre += 1
            else: break
        for j in range(pre+1, a[i]-1, -1): print(j, end=' ')
        pre += 1
        i = k
        if a[k]+1 == pre: break
    for i in range(pre+1, n+1): print(i, end=' ')

C - Coverage

C - Coverage

给出m个集合，每个集合存放1~n中的数字。问有多少种选择方式，使得选择的集合的并集覆盖了 1∼n。

思路

范围只有10，二进制枚举暴力判断即可。

时间复杂度：O(nm2^m)
空间复杂度：O(1)

代码

def solve(): 
    n, m = list(map(int, input().split()))
    s = []
    for i in range(m):
        tp = input()
        s.append(set(list(map(int, input().split()))))
    ans = 0
    for i in range(1, (1<<m)):
        cur = set()
        for j in range(m):
            if (i >> j & 1) : cur |= s[j]
        if len(cur) == n: ans += 1
    print(ans)

D - Step Up Robot

D - Step Up Robot

走楼梯，某些阶梯不能踩。每一步可以选择n种步长向上走。并且有 m 个障碍，走的过程中不能经过这些层。

问能不能从第 0 层走到第 x 层。

思路

爬楼梯，经典dp问题。只不过多了一些选择和限制。

时间复杂度：O(nx)
空间复杂度：O(x)

代码

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    m = int(input())
    b = set(list(map(int, input().split())))
    x = int(input())
    dp = [False]*(x+1)
    dp[0] = True
    for i in range(1, x+1):
        for j in range(n):
            if i not in b and i >= a[j]: dp[i] |= dp[i-a[j]]
    print('Yes' if dp[x] else 'No')

E - Swap Places

E - Swap Places

给定一张n个点m条边的无向图，点有红蓝两种颜色。

A从1号点出发，B从 n 号点出发。

每个时刻，两人同时移动至其相邻点，要求每次移动之后，两人所在点的颜色不同。

问两人能否同时抵达n号点和 1号点，若能的话，输出最小耗时。

思路

图里面求最小值，一眼BFS。

设 dis[i][j] 是A走到点 i，B走到点 j 所需的最短距离。（两人都走了 dis[i][j]步）双重循环遍历点 i，j 的所有相邻点 ni, nj 。则 dis[ni][nj] = dis[i][j] + 1。由于是求最短路，对于更新过的点就不要在更新了。

整个过程一共需要遍历 n² 个状态，并且因为更新过的点就不要在更新，所以每个状态不会重复求解。而求解一个状态时，需要循环遍历两个点的所有相邻点，即边的数量，这有 m² 种选择，并且也不会重复求解（假设有一种情况重复求解，就相当于遍历了边ab和边cd两次，这两次起点都是a，c，与 dis[a][c] 只求解一次相悖）。

时间复杂度：O(n² + m²)
空间复杂度：O(n² + m)

代码

static int n, m, c[] = new int[N], dis[][] = new int[N][N];
static List<Integer>[] g = new List[N];
static void solve() throws Exception{
    n = ni(); m = ni();
    for (int i = 1;i <= n;i++){
        g[i] = new ArrayList<>();
        for (int j = 1;j <= n;j++) dis[i][j] = -1;
    }
    for (int i = 1;i <= n;i++) c[i] = ni();
    for (int i = 1;i <= m;i++){
        int u = ni(), v = ni();
        g[u].add(v);
        g[v].add(u);
    }
    Deque<int[]> d = new LinkedList<>();
    d.offerLast(new int[]{1, n});
    dis[1][n] = 0;
    while (!d.isEmpty()){
        int[] cur = d.pollFirst();
        int x = cur[0], y = cur[1];
        for (int nx : g[x]){
            for (int ny : g[y]){
                if (c[nx] != c[ny] && dis[nx][ny] == -1){
                    dis[nx][ny] = dis[x][y]+1;
                    d.offerLast(new int[]{nx, ny});
                }
            }
        }
    }out.println(dis[n][1]);
}