[ABC271Ex] General General Solution

更好的阅读体验戳此进入

题面

给定终点 $(A,B)$$(A, B)$，存在向量集合 $S=\{(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)\}$$S = \{ (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1) \}$，每次给定一个长度为 $8$$8$ 的 $01$$01$ 串表示对应的向量是否可以被使用且无限次使用，你需要用可以使用的向量从起点 $(0,0)$$(0, 0)$ 到达终点 $(A,B)$$(A, B)$，最小化使用的向量的个数，输出最小值，无解输出 -1。

Solution

首先这道题应该很明显是分类讨论，但是找到的性质的多少也就决定了式子最终的复杂程度。

首先这八个向量分别对应了右、右上、上、$\cdots$$\cdots$、右下，也就是逆时针顺序的八向移动，这里我们称右、上、左、下为四向向量，右上、左上、左下、右下为八向向量。

首先我们想到，若终点可以被一个向量表示，那么一定可以只用这个向量表示（废话）。

其次一个显而易见的性质，显然两个相邻的四向向量可以表示出其夹着的八向向量（但贡献会多 $1$$1$）两个八向向量可以表示出其夹着的四向向量（贡献不变），而这个性质普遍地讲可以认为就是平面向量基本定理，也就是平面任意向量都可以用两个不共线向量的 $a\overrightarrow{x}+b\overrightarrow{y}$$a\vec{x} + b\vec{y}$ 表示，但是这里显然我们需要要求 $a,b$$a, b$ 非负且为整数，对于非负可以转化为向量只能表示出其夹角内的所有向量，整数则需要具体讨论一下了。

所以不难想到，如果一个向量可以被任意两个向量表示，那么就变成了一个简单的解方程的问题，而若解出来的解全都不合法（有负数或者不为整数），就说明这个向量无法被仅用两个向量表示。

而这里我们可以思考一下，对于某个象限内的终点，若我们可以用其对应的两个四向向量，那么是一定可以表示出来的，所以无法表示就说明我们一定不是有对应的两个四向向量的情况。

而如果是选择的一个四向向量和一个八向向量，那么我们再选一个四向向量上去是没意义的，因为都可以更优地被之前的一个四向向量和一个八向向量表示，所以我们可以考虑一下再选一个八向向量的情况，这个时候我们发现，若这个四向向量用了达到两次，那么就可以在不增加贡献的情况下用另外两个八向向量表示，所以对于这个情况我们可以转化为使用一个四向向量后再用另外两个八向向量解方程。

而对于初始选择两个八向向量在选择一个四向向量的情况与上一种情况本质相同。

同时我们继续思考就会发现再没有更多情况了。

于是我们现在梳理一下共有哪些可能：

1. 用一个向量表示。
2. 用两个向量表示（应该是两个不共线的向量，但是范围较小这里无需剪枝，可以强行枚举）。
3. 用一个四向向量且只使用一次，和任意两个相邻的八向向量表示。

令种类数 $d=8$$d = 8$，复杂度大概是 $O(d^{2}T)$$O(d^2T)$ 的，可以通过。

Tips：上文很多部分的再选一个等语言可能已经默认了额外选择的是相邻的或夹着的，因为其它部分情况的错误性过于显然，故不赘述了。

Code

xxxxxxxxxx
99
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define EPS (1e-10)
24
#define INFLL (0x3f3f3f3f3f3f3f3fll)
25

26
template < typename T = int >
27
inline T read(void);
28

29
ll A, B;
30
ll ans(INFLL);
31
ll dx[10] = {0,  1, 1, 0, -1, -1, -1, 0, 1};
32
ll dy[10] = {0,  0, 1, 1, 1, 0, -1, -1, -1};
33
bitset < 10 > exists;
34

35
bool isInteger(ld v){
36
    return fabs(ld(ll(v)) - v) < EPS;
37
}
38
void Check(int i, int j, int base = 0){
39
    if(dx[i] * dy[j] - dx[j] * dy[i] == 0)return;
40
    ld v1 = (ld)(B * dx[i] - A * dy[i]) / (dx[i] * dy[j] - dx[j] * dy[i]);
41
    if(v1 <= -EPS || !isInteger(v1))return;
42
    ld v2 = (ld)(B * dx[j] - A * dy[j]) / (dx[j] * dy[i] - dx[i] * dy[j]);
43
    if(v2 <= -EPS || !isInteger(v2))return;
44
    ans = min(ans, ll(v1) + ll(v2) + base);
45
}
46

47
int main(){
48
    // freopen("in.txt", "r", stdin);
49
    // freopen("out.txt", "w", stdout);
50
    int T = read();
51
    while(T--){
52
        A = read(), B = read();
53
        for(int i = 1; i <= 8; ++i){
54
            char c = getchar(); while(!isdigit(c))c = getchar();
55
            exists[i] = c == '1';
56
        }ans = INFLL;
57
        if(!A && !B){printf("0\n"); continue;}
58
        for(int i = 1; i <= 8; ++i)
59
            if(exists[i]){
60
                if(A * dx[i] < 0 || B * dy[i] < 0)continue;
61
                if((!dx[i] && (A || !isInteger((ld)B / dy[i]))) || (!dy[i] && (B || !isInteger((ld)A / dx[i]))))continue;
62
                if(!dx[i])ans = min(ans, B / dy[i]);
63
                if(!dy[i])ans = min(ans, A / dx[i]);
64
                ld v1 = (ld)A / dx[i], v2 = (ld)B / dy[i];
65
                if(!isInteger(v1) || !isInteger(v2) || (ll)v1 != (ll)v2)continue;
66
                ans = min(ans, (ll)v1);
67
            }
68
        for(int i = 1; i <= 8; ++i)for(int j = i + 1; j <= 8; ++j)
69
            if(exists[i] && exists[j])Check(i, j);
70
        for(int i = 2; i <= 8; i += 2){
71
            if(!exists[i] || !exists[i == 2 ? 8 : i - 2])continue;
72
            for(int j = 1; j <= 8; j += 2){
73
                if(!exists[j])continue;
74
                A -= dx[j], B -= dy[j];
75
                Check(i == 2 ? 8 : i - 2, i, 1);
76
                A += dx[j], B += dy[j];
77
            }
78
        }
79
        printf("%lld\n", ans == INFLL ? -1ll : ans);
80
    }
81
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
82
    return 0;
83
}
84

85
template < typename T >
86
inline T read(void){
87
    T ret(0);
88
    int flag(1);
89
    char c = getchar();
90
    while(c != '-' && !isdigit(c))c = getchar();
91
    if(c == '-')flag = -1, c = getchar();
92
    while(isdigit(c)){
93
        ret *= 10;
94
        ret += int(c - '0');
95
        c = getchar();
96
    }
97
    ret *= flag;
98
    return ret;
99
}

UPD

update-2023_02_09 初稿