SGU150-159 Solution

更好的阅读体验戳此进入

题面链接

150. Mr. Beetle II

题面

给定平面直角坐标系中的起点坐标 $(x_1,y_1)$$(x_1, y_1)$，和终点坐标 $(x_2,y_2)$$(x_2, y_2)$，求起点到终点构成线段穿过的第 $n$$n$ 个格子左下角的坐标（格子的边界和角点不算做格子）。无解输出 no solution。

$1\le n\le 400,|x|,|y|\le {10}^6$$1 \le n \le 400, \lvert x \rvert, \lvert y \rvert \le 10^6$。

输入格式

$x_1,y_1,x_2,y_2,n$$x_1, y_1, x_2, y_2, n$

Examples

Input_1

1
2 3 4 -1 3

Output_1

xxxxxxxxxx
1
1
3 0

Solution

难度不高，但细节颇多。

不难想到数据范围较小，可以枚举区间内的所有横坐标，然后通过斜率和分类讨论计算横坐标对应的纵坐标的数量和范围，找到对应的方格即可。同时不难想到若 $x_1=x_2\vee y_1=y_2$$x_1 = x_2 \vee y_1 = y_2$ 则无解，经过方格数不足 $n$$n$ 亦无解。同时需要考虑好 $x_1,x_2$$x_1, x_2$ 的大小关系，以确定枚举方向，思路很显然但实现细节颇多。

Code

​x
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22
#define NXTX (T.x > 0 ? 1 : -1)
23
#define NXTY (T.y > 0 ? 1 : -1)
24

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

28
struct Coord{int x, y;}S, T;
29
int N;
30

31
int main(){
32
    S.x = read(), S.y = read(), T.x = read(), T.y = read(); N = read();
33
    if(S.x == T.x || S.y == T.y)printf("no solution\n"), exit(0);
34
    T.x -= S.x, T.y -= S.y;
35
    // printf("T : %d, %d\n", T.x, T.y);
36
    int cur(0);
37
    for(int X = 0; X != T.x; X += NXTX){
38
        ll Y1 = (ll)X * T.y / T.x + (T.y < 0 ? NXTY : 0);
39
        ll Y2 = (ll)(X + NXTX) * T.y / T.x + (T.y < 0 ? ((ll)(X + NXTX) * T.y % T.x ? NXTY : 0) : ((ll)(X + NXTX) * T.y % T.x ? 0 : -NXTY));
40
        // printf("%d -> %lld, %lld\n", X, Y1, Y2);
41
        cur += abs(Y2 - Y1) + 1;
42
        if(cur >= N)printf("%d %lld\n", S.x + X + (T.x < 0 ? -1 : 0), S.y + (Y2 - NXTY * (cur - N))), exit(0);
43
    }printf("no solution\n"), exit(0);
44
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
45
    return 0;
46
}
47

48
template < typename T >
49
inline T read(void){
50
    T ret(0);
51
    int flag(1);
52
    char c = getchar();
53
    while(c != '-' && !isdigit(c))c = getchar();
54
    if(c == '-')flag = -1, c = getchar();
55
    while(isdigit(c)){
56
        ret *= 10;
57
        ret += int(c - '0');
58
        c = getchar();
59
    }
60
    ret *= flag;
61
    return ret;
62
}

151. Construct a triangle

题面

对于 $\mathrm{△}ABC$$\triangle ABC$，令 $M$$M$ 为 $AB$$AB$ 中点，令 $|AB|=c,|AC|=b,|AM|=m$$\lvert AB \rvert = c, \lvert AC \rvert = b, \lvert AM \rvert = m$。给定实数 $c,b,m$$c, b, m$，构造该三角形，输出 $A,B,C$$A, B, C$ 的坐标，以浮点数形式输出，每个数的绝对值不超过 ${10}^4$$10^4$，输出小数点后 $5$$5$ 位，若无解输出 Mission impossible。

特别地，对于本题的数据，允许 $A,B,C$$A, B, C$ 三点共线，即若你构造的三个点共线仍算作一组解。

$0<c,b,m<{10}^3$$0 \lt c, b, m \lt 10^3$。

Examples

Input_1

xxxxxxxxxx
1
1
5 5 3

Output_1

xxxxxxxxxx
3
1
0.00000 3.00000
2
-4.00000 0.00000
3
4.00000 0.00000

Solution

首先不难想到该三角形可以任意平移，所以考虑固定点 $A$$A$ 在原点。不难发现三角形可以任意绕 $A$$A$ 旋转，所以可以再任意固定一个点的一个坐标，则不失一般性，可以设 $B(0,c),C(x,y)$$B(0, c), C(x, y)$，即 $M({\displaystyle \frac{x}{2}},{\displaystyle \frac{y+c}{2}})$$M(\dfrac{x}{2}, \dfrac{y + c}{2})$，则有方程：

不难发现方程非线性，可解，仅需额外判断是否有解即可。

仍需注意一个额外的细节，判断无解时需要和 $-eps$$-eps$ 判断，且若误差范围内为 $0$$0$ 需要强制设为 $0$$0$，否则可能输出 $-0.00000$$-0.00000$，额外还需要注意判断需要在最后开方之前判断是否误差范围内为 $0$$0$，否则会出现对负数开方导致答案变得奇怪。

Code

xxxxxxxxxx
57
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22
#define EPS (ld)(1e-6)
23

24
template < typename T = int >
25
inline T read(void);
26

27
ld c, b, m;
28

29
int main(){
30
    scanf("%Lf%Lf%Lf", &c, &b, &m);
31
    ld y = (ld)(4 * m * m - b * b - c * c) / (ld)(2 * c);
32
    ld x = (ld)b * b - y * y;
33
    if(x < -EPS)printf("Mission impossible\n"), exit(0);
34
    if(fabs(x) <= EPS)x = 0.0;
35
    if(fabs(y) <= EPS)y = 0.0;
36
    x = sqrt(x);
37
    printf("0.00000 0.00000\n0.00000 %.5Lf\n", c);
38
    printf("%.5Lf %.5Lf\n", x, y);
39
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
40
    return 0;
41
}
42

43
template < typename T >
44
inline T read(void){
45
    T ret(0);
46
    int flag(1);
47
    char c = getchar();
48
    while(c != '-' && !isdigit(c))c = getchar();
49
    if(c == '-')flag = -1, c = getchar();
50
    while(isdigit(c)){
51
        ret *= 10;
52
        ret += int(c - '0');
53
        c = getchar();
54
    }
55
    ret *= flag;
56
    return ret;
57
}

152. Making round

题面

给定序列 $A_n$$A_n$ 表示 $n$$n$ 个人的选票情况，现你需要将其选票转化为百分制并输出百分制的整数部分，换言之即转换后的所有数之和恰好为 $100$$100$，转换时可以独立任意选择向上取整或向下取整，输出转换后的序列。无解输出 No solution。

$1\le n,a_i\le {10}^4$$1 \le n, a_i \le 10^4$。

Examples

Input_1

xxxxxxxxxx
2
1
2
2
10 10

Output_1

xxxxxxxxxx
1
1
50 50

Solution

钦定均为向下取整，令钦定后的和为 $tot$$tot$，计算一下有多少数转化后有余数，然后将有余数的数分配 $100-tot$$100 - tot$ 个改为向上取整即可，不足即为无解。

Code

xxxxxxxxxx
58
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
int a[11000];
27
int sum(0);
28
int tot(0);
29
basic_string < int > rem;
30

31
int main(){
32
    N = read();
33
    for(int i = 1; i <= N; ++i)sum += a[i] = read();
34
    for(int i = 1; i <= N; ++i){
35
        if(a[i] * 100 % sum)rem += i;
36
        tot += a[i] = (a[i] * 100 / sum);
37
    }if(100 - tot > (int)rem.size())printf("No solution\n"), exit(0);
38
    for(int i = 1; i <= 100 - tot; ++i)a[rem.at(i - 1)]++;
39
    for(int i = 1; i <= N; ++i)printf("%d%c", a[i], i == N ? '\n' : ' ');
40
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
41
    return 0;
42
}
43

44
template < typename T >
45
inline T read(void){
46
    T ret(0);
47
    int flag(1);
48
    char c = getchar();
49
    while(c != '-' && !isdigit(c))c = getchar();
50
    if(c == '-')flag = -1, c = getchar();
51
    while(isdigit(c)){
52
        ret *= 10;
53
        ret += int(c - '0');
54
        c = getchar();
55
    }
56
    ret *= flag;
57
    return ret;
58
}

153. Playing with matches

题面

存在 $n$$n$ 根火柴，两人轮流取，每次可以取 $1,P_1,P_2,\cdots ,P_m$$1, P_1, P_2, \cdots, P_m$ 根火柴，将火柴全部取完者输，若先手必胜输出 FIRST PLAYER MUST WIN，后手必胜输出 SECOND PLAYER MUST WIN。存在 $T$$T$ 组数据。

$1\le n\le {10}^9,2\le P_i\le 9,0\le m\le 8$$1 \le n \le 10^9, 2 \le P_i \le 9, 0 \le m \le 8$。（原题中未对 $T$$T$ 做出限制，理论上 $1s$$1s$ 内可以通过 $T\le {10}^2$$T \le 10^2$）

Examples

Input_1

xxxxxxxxxx
3
1
1
2
5 3
3
2 3 5

Output_1

xxxxxxxxxx
1
1
SECOND PLAYER MUST WIN

Solution

一道挺好的博弈论的题。

对于这种类型题不难想到 $SG$$SG$ 函数解决，且由于本题仅有一堆石子，以及后面我们需要求循环节，则无需记录 $SG$$SG$ 的具体值，仅需记录是否不为 $0$$0$。显然存在 $SG(0)=\mathtt{\text{true}}$$SG(0) = \texttt{true}$，即空集时必胜。我们假设 $P_0=1$$P_0 = 1$，不难想到转移：

转移显然，即考虑是否所有子状态均为必胜，是则此状态必输，反之必胜。

发现这个的复杂度是 $O(Tnm)$$O(Tnm)$ 的无法通过，则发现由于 $P_i\le 9$$P_i \le 9$，则对于一个 $SG(i)$$SG(i)$ 最多由其之前九个数决定，由于 $SG$$SG$ 为布尔类型则最多有 $2^{P_i}=512$$2^{P_i} = 512$ 种状态，所以最多经过 $512$$512$ 个数后将会出现重复状态，即进入循环，故得证 $SG$$SG$ 存在长度最多为 $512$$512$ 的循环节，则可以通过枚举每一个长度并验证证明，同时可以证明循环节一定从 $0$$0$ 开始，证明未知，在论文 GAME Theory Thomas S Ferguson (University of California at Los Angeles) 种 1.4 Subtraction Games. 亦提及了此现象，但似乎并未对该现象进行证明。于是最终复杂度 $O(T{2}^{2P_i})$$O(T2^{2P_i})$，可以通过。

Code

xxxxxxxxxx
70
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22
template < typename T = int >
23
inline T read(void);
24

25
int N, M;
26
int P[10];
27
bitset < 1300 > SG;
28

29
int main(){
30
    int T = read();
31
    while(T--){
32
        SG.reset();
33
        N = read(), M = read();
34
        P[0] = 1;
35
        for(int i = 1; i <= M; ++i)P[i] = read();
36
        SG[0] = true;
37
        for(int i = 1; i <= 1200; ++i)
38
            for(int p = 0; p <= M; ++p)
39
                if(i - P[p] >= 0)
40
                    SG[i] = SG[i] | (SG[i - P[p]] ^ 1);
41
        int rlen(-1);
42
        for(int len = 1; len <= 520; ++len){
43
            bool flag(true);
44
            for(int s = 0; s <= 1100 - len * 2 + 10; s += len)
45
                for(int i = s; i <= s + len - 1; ++i)
46
                    if(SG[i] != SG[i + len]){flag = false; break;}
47
            if(flag){rlen = len; break;}
48
        }//printf("rlen = %d\n", rlen);
49
        // for(int i = 0; i <= 20; ++i)printf("SG[%d] = %d\n", i, SG[i] ? 1 : 0);
50
        printf("%s\n", SG[N % rlen] ? "FIRST PLAYER MUST WIN" : "SECOND PLAYER MUST WIN");
51
    }
52
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
53
    return 0;
54
}
55

56
template < typename T >
57
inline T read(void){
58
    T ret(0);
59
    int flag(1);
60
    char c = getchar();
61
    while(c != '-' && !isdigit(c))c = getchar();
62
    if(c == '-')flag = -1, c = getchar();
63
    while(isdigit(c)){
64
        ret *= 10;
65
        ret += int(c - '0');
66
        c = getchar();
67
    }
68
    ret *= flag;
69
    return ret;
70
}

154. Factorial

题面

给定 $Q$$Q$，求最小的自然数 $N$$N$ 满足 $N!$$N!$ 的结尾有 $Q$$Q$ 个 $0$$0$。无解输出 No solution。

$0\le Q\le {10}^8$$0 \le Q \le 10^8$。

Examples

Input_1

xxxxxxxxxx
1
1
2

Output_1

xxxxxxxxxx
1
1
10

Solution

简单数论，经典套路。

显然从式子里拆出来 $2$$2$ 和 $5$$5$ 的数量取个 $min$$\min$ 即可，且显然阶乘中 $5$$5$ 会比 $2$$2$ 多，故只需要记录 $5$$5$ 的数量即可。

显然 $n$$n$ 单调，则二分答案 $n$$n$，对于 $n$$n$ 的上界可以无脑一些，不妨设为 $5\times {10}^8$$5 \times 10^8$，此时显然存在远大于 ${10}^8$$10^8$ 个 $5$$5$。

具体式子显然为：

注意：需要特判 $Q=0$$Q = 0$ 的情况。（否则会卡在第三个点，这个东西我调了半天）

Code

xxxxxxxxxx
62
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22
template < typename T = int >
23
inline T read(void);
24

25
ll Q;
26
ll ctot;
27

28
ll Check(ll n){
29
    ll cur(5), tot(0);
30
    while(cur <= n)tot += n / cur, cur *= 5;
31
    return tot;
32
}
33

34
int main(){
35
    Q = read();
36
    if(!Q)printf("1\n"), exit(0);
37
    ll l = 0, r = (int)(5e8), ans(-1);
38
    while(l <= r){
39
        ll mid = (l + r) >> 1;
40
        if(Check(mid) >= Q)ans = mid, r = mid - 1;
41
        else l = mid + 1;
42
    }if(!~ans || Check(ans) != Q)printf("No solution\n"), exit(0);
43
    printf("%lld\n", ans);
44
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
45
    return 0;
46
}
47

48
template < typename T >
49
inline T read(void){
50
    T ret(0);
51
    int flag(1);
52
    char c = getchar();
53
    while(c != '-' && !isdigit(c))c = getchar();
54
    if(c == '-')flag = -1, c = getchar();
55
    while(isdigit(c)){
56
        ret *= 10;
57
        ret += int(c - '0');
58
        c = getchar();
59
    }
60
    ret *= flag;
61
    return ret;
62
}

155. Cartesian Tree

题面

给定 $n$$n$ 个键值二元组，要求以这些键值作为映射构造一棵笛卡尔树。即 $value$$value$ 满足小根堆性质的 $key$$key$ 的二叉搜索树。数据满足 $key$$key$ 互不相同且 $value$$value$ 互不相同。

$1\le n\le 5\times {10}^4,|k_i|,|a_i|\le 3\times {10}^4$$1 \le n \le 5 \times 10^4, \lvert k_i \rvert, \lvert a_i \rvert \le 3 \times 10^4$。

Examples

Input_1

xxxxxxxxxx
8
1
7
2
5 4
3
2 2
4
3 9
5
0 5
6
1 3
7
6 6
8
4 11

Output_1

xxxxxxxxxx
8
1
YES
2
2 3 6
3
0 5 1
4
1 0 7
5
5 0 0
6
2 4 0
7
1 0 0
8
3 0 0

Solution

笛卡尔树模板，处理好各种映射之间的关系即可。

Code

xxxxxxxxxx
74
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
struct Node{
27
    int idx, k, v;
28
    friend const bool operator < (const Node &a, const Node &b){
29
        return a.k < b.k;
30
    }
31
}nod[51000];
32
unordered_map < int, int > mp, idx;
33
int lson[51000], rson[51000], fa[51000];
34
stack < int > cur;
35

36
int main(){
37
    N = read();
38
    for(int i = 1; i <= N; ++i){
39
        int k = read(), v = read();
40
        nod[i] = Node{i, k, v};
41
        mp.insert({k, v});
42
        idx.insert({k, i});
43
    }sort(nod + 1, nod + N + 1);
44
    for(int i = 1; i <= N; ++i){
45
        while(!cur.empty() && mp[cur.top()] > nod[i].v)
46
            lson[nod[i].idx] = idx[cur.top()], cur.pop();
47
        if(!cur.empty())rson[idx[cur.top()]] = nod[i].idx;
48
        cur.push(nod[i].k);
49
    }for(int i = 1; i <= N; ++i)
50
        fa[lson[i]] = i, fa[rson[i]] = i;
51
    int cnt(0);
52
    for(int i = 1; i <= N; ++i)if(!fa[i])++cnt;
53
    if(cnt > 1)printf("NO\n"), exit(0);
54
    printf("YES\n");
55
    for(int i = 1; i <= N; ++i)printf("%d %d %d\n", fa[i], lson[i], rson[i]);
56
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
57
    return 0;
58
}
59

60
template < typename T >
61
inline T read(void){
62
    T ret(0);
63
    int flag(1);
64
    char c = getchar();
65
    while(c != '-' && !isdigit(c))c = getchar();
66
    if(c == '-')flag = -1, c = getchar();
67
    while(isdigit(c)){
68
        ret *= 10;
69
        ret += int(c - '0');
70
        c = getchar();
71
    }
72
    ret *= flag;
73
    return ret;
74
}

156. Strange Graph

题面

给定 $n$$n$ 个点 $m$$m$ 条边的无向图，保证对于其中任意一个点 $v$$v$ 满足以下性质：

• 点 $v$$v$ 的度数 $de{g}_v\ge 2$$deg_v \ge 2$。

• 若点 $v$$v$ 的度数 $de{g}_v=2$$deg_v = 2$，那么其两个邻接点之间无边相连。

• 若点 $v$$v$ 的度数 $de{g}_v>2$$deg_v > 2$，那么在其邻接点集 $N$$N$ 中存在点 $u\in N$$u \in N$ 满足：

  • 点 $u$$u$ 的度数 $de{g}_u=2$$deg_u = 2$。
  • 点集 $N$$N$ 中除点 $u$$u$ 外任意两个不同的点有边相连。

你需要判断该图是否存在哈密尔顿回路，若存在则输出任意一个，反之输出 -1。

Examples

Input_1

xxxxxxxxxx
2
1
4 4
2
1 2 2 3 3 4 4 1

Output_1

xxxxxxxxxx
1
1
1 2 3 4

Input_2

xxxxxxxxxx
3
1
9 12
2
1 2 2 3 3 1 1 4 2 5 3 6
3
4 7 5 8 6 9 7 8 8 9 9 7

Output_2

xxxxxxxxxx
1
1
-1

Solution

一道十分高妙的题，思路不难但是构造方案还是需要亿些细节的。

首先根据题意，若 $de{g}_v>2$$deg_v \gt 2$，则 $N(v)/u$$N(v) / u$ 为完全图，即一定符合构造哈密尔顿回路的条件，即任意两个节点的度数和不小于 $n$$n$。于是可以考虑将 $N(v)/u$$N(v) / u$ 缩点。显然缩点之后的点之间只会被一些度数为 $2$$2$ 的点相连，此时我们每经过一条边就会经过一个新的点，则可以将问题转化为在新图中找欧拉回路，这样的话存在性显然，仅需判断新图中是否所有点的度数均为偶数即可。但是方案就难以构造了。

如果按照一般的构造欧拉回路的思路，我们会发现将欧拉回路还原回哈密尔顿回路是复杂的，因为我们是需要考虑缩完的两个点之间的边在原图中是哪些点，似乎可以维护但极为复杂，细节过多，所以这里有一个特别高妙的做法。

可以参考代码中 SetAns 函数，如此实现是可以保证，对于缩点后的没有连向其它新图中的点的旧点，当遍历到其之后就不会接着遍历，然后直接记录，反之则会继续找到新的点。可以画个图理解一下，这个思路确实很巧妙。

Tips：网上有的题解写法是直接判断原图中的度数是否均为偶数，我认为这个是错误的，反例易得，但是似乎可以通过？

Code

xxxxxxxxxx
155
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22

23

24
template < typename T = int >
25
inline T read(void);
26

27
struct Edge{
28
    Edge* nxt;
29
    int to;
30
    OPNEW;
31
}ed[210000];
32
ROPNEW(ed);
33
Edge* head[11000];
34

35
int N, M;
36
int deg[11000];
37

38
namespace New{
39
    int cnt(0);
40
    int ddeg[11000];
41
    int belong[11000];
42
    // basic_string < int > pts[11000];
43
    // Edge* head[11000];
44
    bitset < 11000 > vis;
45
    basic_string < int > ans;
46
    // void SetGraph(int p, int idx){
47
    //     vis[p] = true;
48
    //     if(deg[p] == 2){belong[p] = ++cnt/*, pts[cnt] += p;*/ return;}
49
    //     belong[p] = idx;//, pts[idx] += p;
50
    //     for(auto i = ::head[p]; i; i = i->nxt)
51
    //         if(!vis[SON])SetGraph(SON, idx);
52
    // }
53
    void SetAns(int p = 1, bool flag = false){
54
        vis[p] = true;
55
        for(auto i = ::head[p]; i; i = i->nxt){
56
            if(vis[SON])continue;
57
            if(flag && belong[SON] == belong[p])SetAns(SON, false);
58
            else if((!flag && belong[SON] != belong[p]) || deg[p] == 2)SetAns(SON, true);
59
        }ans += p;
60
    }
61
    void Build(void){
62
        for(int i = 1; i <= N; ++i)
63
            if(deg[i] > 2 && !vis[i]){//vis[i] = true, SetGraph(i, ++cnt);
64
                belong[i] = ++cnt, vis[i] = true;
65
                for(auto j = ::head[i]; j; j = j->nxt){
66
                    if(deg[j->to] == 2)continue;
67
                    vis[j->to] = true;
68
                    belong[j->to] = cnt;
69
                    // pts[cnt] += j->to;
70
                }
71
            }
72
            else if(deg[i] == 2 && !vis[i])vis[i] = true, belong[i] = ++cnt;//, pts[cnt] += i;
73
        for(int p = 1; p <= N; ++p)
74
            for(auto i = ::head[p]; i; i = i->nxt)
75
                if(belong[p] != belong[SON])
76
                    // printf("from %d to %d, belong : %d -> %d\n", p, SON, belong[p], belong[SON]),
77
                    ++ddeg[belong[p]], ++ddeg[belong[SON]];
78
                    // head[belong[p]] = new Edge{head[belong[p]], belong[SON]},
79
                    // head[belong[SON]] = new Edge{head[belong[SON]], belong[p]};
80
    }
81
    void Make(void){
82
        // int tot(0);
83
        // vis.reset();
84
        // int cur = 1;
85
        // while(true){
86
        //     vis[cur] = true, ++tot; //ans += cur;//pts[cur];
87
        //     bool flag(false);
88
        //     for(auto i = head[cur]; i; i = i->nxt)
89
        //         if(!vis[SON]){cur = SON, flag = true; break;}
90
        //     if(!flag)break;
91
        // }printf("tot = %d, cnt = %d\n", tot, cnt);
92
        // if(tot != cnt)printf("-1\n"), exit(0);
93
        // basic_string < int > rans;
94
        // for(int i = 1; i <= (int)ans.size(); ++i){
95
        //     if(i == 1)
96
        // }
97
        // vis.reset();
98
        // for(int i = 1; i <= (int)ans.size(); ++i){
99
        //     if(vis[i])continue;
100
        //     vis[i] = true;
101
        //     if(i == ans.size()){rans += ans.at(i - 1); break;}
102
        //     bool flag(false);
103
        //     for(auto j = ::head[ans.at(i - 1)]; j; j = j->nxt)
104
        //         if(j->to == ans.at(i)){flag = true; break;}
105
        //     if(flag){rans += ans.at(i - 1); break;}
106
        //     for(int j = i + 2; j <= (int)ans.size(); ++j){
107
        //         bool fflag(false);
108
        //         for(auto k = ::head[ans.at(i - 1)]; k; k = k->nxt)
109
        //             if(k->to == ans.at(j - 1)){fflag = true; rans += ans.at(j - 1), vis[j] = true; break;}
110
        //         if(fflag)break;
111
        //     }
112
        // }
113
        // for(auto p : ans)printf("%d ", p);
114
        // printf("\n");
115
        for(int i = 1; i <= cnt; ++i)
116
            if((ddeg[i] >> 1) & 1)printf("-1\n"), exit(0);
117
        // for(int i = 1; i <= cnt; ++i)printf("ddeg[%d] = %d\n", i, ddeg[i]);
118
        vis.reset();
119
        SetAns();
120
        // if((int)ans.size() != N)printf("-1\n"), exit(0);
121

122
        for(auto p : ans)printf("%d ", p);
123
        printf("\n");
124
    }
125
}
126

127
int main(){
128
    N = read(), M = read();
129
    for(int i = 1; i <= M; ++i){
130
        int s = read(), t = read();
131
        head[s] = new Edge{head[s], t};
132
        head[t] = new Edge{head[t], s};
133
        ++deg[s], ++deg[t];
134
    }
135
    New::Build();
136
    New::Make();
137
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
138
    return 0;
139
}
140

141
template < typename T >
142
inline T read(void){
143
    T ret(0);
144
    int flag(1);
145
    char c = getchar();
146
    while(c != '-' && !isdigit(c))c = getchar();
147
    if(c == '-')flag = -1, c = getchar();
148
    while(isdigit(c)){
149
        ret *= 10;
150
        ret += int(c - '0');
151
        c = getchar();
152
    }
153
    ret *= flag;
154
    return ret;
155
}

157. Patience

题面

Patience 游戏。存在有序的 14 个空位，和 $1$$1$ 到 $K$$K$ 共 $13$$13$ 张牌，将 $A$$A$ 放到第 $1$$1$ 个格子上，第 $2$$2$ 个空位留空，剩下的牌随机排列放到 $3-14$$3-14$ 格子中。然后你可以进行若干次操作，每次可以将空位前的牌 $+1$$+1$ 对应的牌移动到空位上，其原本位置变为空位。若若干次操作后可以将前 $13$$13$ 个空位变为有序的 $A-K$$A-K$，那么称游戏胜利。给定 $n$$n$，现在已固定前 $14-n$$14-n$ 个空位是有序合法的，求有多少种序列是有可能胜利的。

$1\le n\le 13$$1 \le n \le 13$。

Examples

Input_1

xxxxxxxxxx
1
1
3

Output_1

xxxxxxxxxx
1
1
5

Input_2

xxxxxxxxxx
1
1
4

Output_2

xxxxxxxxxx
1
1
14

Solution

一个显而易见的思路就是 $O(n\cdot n!)$$O(n \cdot n!)$ 枚举并验证，然后打个表即可，时间可能长一点不过也是可以接受的。

Code

xxxxxxxxxx
47
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22
template < typename T = int >
23
inline T read(void);
24

25
int ans[20] = {0, 1, 2, 5, 14, 47, 189, 891, 4815, 29547, 203173, 1548222, 12966093, 118515434};
26

27
int main(){
28
    printf("%d\n", ans[read()]);
29
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
30
    return 0;
31
}
32

33
template < typename T >
34
inline T read(void){
35
    T ret(0);
36
    int flag(1);
37
    char c = getchar();
38
    while(c != '-' && !isdigit(c))c = getchar();
39
    if(c == '-')flag = -1, c = getchar();
40
    while(isdigit(c)){
41
        ret *= 10;
42
        ret += int(c - '0');
43
        c = getchar();
44
    }
45
    ret *= flag;
46
    return ret;
47
}

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

UPD

update-2022_12_16 初稿