题解：CF980B Marlin

yzm6677 · 2026-02-08 23:04:10 · 题解

首先我们不难观察到一个性质：构造上下对称或左右对称的局面是一定正确的。证明也不难，对于上下，每条从 (1,1) 到 (4,n) 的路径都可以上下翻转一下变成从 (4,1) 到 (1,n) 的路径，两种路径是一一对应的，所以数量相同。左右基本同理。

所以接下来就好构造了。

• 对于 k 是偶数的情况，构造上下对称。
• 对于 k 是奇数且一行排不满的情况。直接在这一行居中放构造左右对称。
• 对于 k 是奇数且会排满第一行（即题意的第二行，因为第一行不可放所以这里直接称为“第一行”，下同）的情况，此时不能直接在第二行居中放，因为这样奇偶性不符。稍加思考，容易发现将剩下的旅馆分成两拨个数相同的，左右对称排布在第二行即可（也就是一段连续 #、一段中间为这一行中间位置的 .、一段个数与第一段相同的 #）。

光这样说比较难理解，下面举三个对应的例子来直观感受一下，假设样例的 4\times7 网格：

.......
.##....
.##....
.......

.......
..###..
.......
.......

.......
.#####.
.#...#.
.......

所以这道题实际上不可能输出 No（题目也保证了 k 的范围），骗你的。

码风比较猎奇，可以结合上面的例子食用，手模一下好理解一些。

cout << "Yes\n";
for(int i = 1; i <= n; i++) cout << '.'; cout << '\n';
if(k & 1) {
    if(k <= n - 2) {
        for(int i = 1; i <= (n - k) / 2; i++) cout << '.';
        for(int i = 1; i <= k; i++) cout << '#';
        for(int i = 1; i <= (n - k) / 2; i++) cout << '.'; cout << '\n';
        for(int i = 1; i <= n; i++) cout << '.'; cout << '\n';
    } else {
        cout << '.';
        for(int i = 1; i <= n - 2; i++) cout << '#';
        cout << '.' << '\n' << '.';
        for(int i = 1; i <= (k - n + 2) / 2; i++) cout << '#';
        for(int i = 1; i <= n - (k - n + 2) - 2; i++) cout << '.';
        for(int i = 1; i <= (k - n + 2) / 2; i++) cout << '#'; cout << '.' << '\n';
    }
} else {
    for(int i = 1; i <= 2; i++) {
        cout << '.';
        for(int j = 1; j <= k / 2; j++) cout << '#';
        for(int j = 1; j <= n - k / 2 - 1; j++) cout << '.';
        cout << '\n'; 
    }
}
for(int i = 1; i <= n; i++) cout << '.';