2023CCPC哈尔滨站https://contest.ucup.ac/contest/1412

B. Memory 

int main() {
    int n;
    std::cin >> n;
 
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
 
    std::string res;
 
    int x = 0, Dec = 0;
    // 整数位 x 和 小数位符号 Dec
 
    for (int i = 0; i < n; i++) {
        x += a[i];
 
        if (x != 0)
            res.push_back(x > 0 ? '+' : '-');
        else {
            if (Dec != 0)
                res.push_back(Dec > 0 ? '+' : '-');
            else
                res.push_back('0');
        }
 
        if (std::abs(x) & 1)
            Dec = (x > 0 ? 1 : -1);
        x /= 2;
    }
 
    std::cout << res;
}

G. The Only Way to the Destination

思路：

题意中给出了几个很重要的信息：

1、墙只有纵向
2、爱丽丝确保在放置 k 面墙后，所有空网格都保持连接，迷宫中至少有一个空网格。并且保证不同的墙没有共同的网格
3、保证每对空格之间至少有一条简单路径相连

本来的想法是bfs，但是数据量过大，想想看如果有多条简单路径时会怎么样。

首先对两列，如果左边连续的空网格和右边连续的空网格结合在一起，那么肯定不行，比如第三个样例，第二列两个连续的空网格和第三列两个连续的空网格形成了一个2*2的空格，这时不管其他地方怎么样，一定不可能满足条件了。

因此如果 n > 1 时，每两列必须要有一堵墙，否则两个空列接在一起一定不可能满足条件，这样的话 m 最多只有2k+1，否则一定不可能满足条件。而 n = 1时由于一定会有一条简单路径，而且也不可能出现其他简单路径，这时一定满足条件，特判直接返回即可。