Codeforces 664Div2
2024-02-05 20:53:09 # Before-2024 #Contests #Codeforces #Algorithm

664 Div2

SB.jpg：

CFRound664Div2

A题瞎写WA一次；B题瞎写FST on Test45，最后发现自己的算法假的离谱，一个5×5的矩阵就能叉掉（就算如此还混过了pretest）；D题瞎写，计数的时候要把所用东西加起来，ans的初始值写-1（写0就行了），而且在莫名其妙的位置还爆了个int（两个1e5乘起来了）。

下次要注意细节了，不能再想当然。

B. Boboniu Plays Chess

题意

给出一个矩阵，有一个棋子（走法同国际象棋中的车），给出矩阵的大小和棋子的初始位置，输出把每个位置走一遍，要求输出路径。

题解

这题没啥好说的，看代码就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
int read() {
    int x; scanf("%d", &x); return x;    
}
const int maxn = 1e6 + 10;
const int INF = 1e9;
int mod = 1e9 + 7;
#define ll long long 
int main() {
    #ifdef LOCAL
        freopen("1.in", "r", stdin);
    #endif
    int n = read(), m = read(), x = read(), y = read();
    cout << x << ' ' << y << endl;
    for (int i = 1; i <= n; ++i) if (i != x) cout << i << ' ' << y << endl;
    int t = 1;
    for (int i = 1; i <= m; ++i) {
        if (i == y) continue;
        if (t & 1) for (int j = n; j >= 1; --j) cout << j << ' ' << i << endl;
        else for (int j = 1; j <= n; ++j) cout << j << ' ' << i << endl;
        t++;
    }
    return 0;
}

奇怪的东西

比赛的时候写的假算法是一直往一个方向走，然后把种方向的排列都试验一下。

然后愉快的FST on test45

错的原因是没用到这个题的性质，然后我发现有些情况按照我的想法是没有可行的方案的。

那么有了这么一个问题：

如果这个棋子每次只能走到相邻四联通的位置（上下左右），那么什么情况下是不存在走法的。

首先给一个结论：只要是长和宽都是奇数的矩阵就不行。

比说说给出3×3的矩阵，规定你起点是2 3，就不存在方案。

你可能觉得是因为起点在最外面一圈所以不行（因为这题规定起点不会在矩阵的最外圈）。

其实给出5×5的矩阵里面打叉这些位置作为起点都是不行的。

事实上这属于一个哈密顿路径问题，是一个图论问题。

参考资料

（英文资料都啃不动，看的全是中文的）

哈密顿图(Hamilton)定义

  • 哈密顿通路(Hamilton path)：经过所有顶点的初级通路（经过所有点有且仅有一次）

  • 哈密顿回路(Hamilton circuit/cycle)：经过所有顶点的初级回路

  • 哈密顿图(Hamiltonian)：有哈密顿回路的图

  • 半哈密顿图(semi- Hamiltonian)：有哈密顿通路的图

无向图中的必要条件

无向图是哈密顿图，则的任意非空真子集有

其中表示图G删去V1后的联通分支数。

如果是半哈密顿图则有

由于没学过太多的图论知识，这个东西好像不太好证明，但是可以考虑：如果是Hamiltonian/semi-Hamiltonian删除相邻的，剩下的联通数一点是最大的，但是不会大于|V1|。

回到这题

知道这个以后，可以发现，在长宽都是奇数的矩阵里面，只要删除个点，那么矩阵中剩下个点，但是为了规定起点，所以要新建一个点，只要这个点链接了被删除的点中的一个，那么就又多了一个联通分支，也就是说比删除的点的个数多了个，这个不符合半哈密顿图的必要条件。

正因如此，类似这种（1，2）（2，1），在行列都为奇数的矩阵中，以行列和为奇数的点作为起点，不存在哈密顿路径。

Prev
2024-02-05 20:53:09 # Before-2024 #Contests #Codeforces #Algorithm
Next