NOI2023春测题解

更好的阅读体验戳此进入

游记戳此进入

T1 LG-P9117 [春季测试 2023] 涂色游戏

题面

给定矩阵，多次操作整行推平或整列推平，最后查询整个矩形。

Solution

给每行每列维护一个最后的推平并标记时间戳，查询时取行列最晚的推平作为答案即可。

考虑如果行列的区间推平以及随时查询并且强制在线，可以考虑对每行每列共 $n+m$$n + m$ 个 ODT，同时记录时间戳，这样复杂度应该也是正确的。

Code

xxxxxxxxxx
60
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
template < typename T = int >
24
inline T read(void);
25

26
int N, M, Q;
27
pair < int, int > lstx[110000], lsty[110000];
28

29
int main(){
30
    int T = read();
31
    while(T--){
32
        memset(lstx, 0, sizeof lstx), memset(lsty, 0, sizeof lsty);
33
        N = read(), M = read(), Q = read();
34
        for(int i = 1; i <= Q; ++i){
35
            int opt = read(), p = read(), v = read();
36
            if(opt == 0)lstx[p] = {v, i};
37
            else lsty[p] = {v, i};
38
        }
39
        for(int i = 1; i <= N; ++i)
40
            for(int j = 1; j <= M; ++j)
41
                printf("%d%c", lstx[i].second > lsty[j].second ? lstx[i].first : lsty[j].first, j == M ? '\n' : ' ');
42
    }
43
    return 0;
44
}
45

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

T2 LG-P9118 [春季测试 2023] 幂次

题面

给定 $n$$n$，$k$$k$，求在 $[1,n]$$[1, n]$ 中有多少数可以表示为 $a^b$$a^b$，其中 $b\ge k$$b \ge k$。

Solution

感觉差不多是绿题的难度，不卡精度的话应该算黄题难度，赛时的阴间思路在游记里了，这里说一下正解。

不难发现对于任意的合法的 $b$$b$，一定满足 $a\le {}^k\sqrt{n}$$a \le {^k\sqrt{n}}$，则对于 $k\ge 3$$k \ge 3$ 的情况，$a$$a$ 最大也是在 ${10}^6$$10^6$ 的范围，那么我们直接枚举所有的 $a$$a$，并枚举其所有合法的 $a^b$$a^b$，然后将其全部丢到 unordered_set 里，最后直接输出其 size() 即可，考虑这样的复杂度，显然枚举 $a$$a$ 是 $O(n^{\frac{1}{k}})$$O(n^{\frac{1}{k}})$ 的，枚举幂次是 $O(\log n)$$O(\log n)$ 的，则复杂度 $O(n^{\frac{1}{k}}\log n)$$O(n^{\frac{1}{k}} \log n)$，对于 $k\ge 3$$k \ge 3$ 的情况是随便过的。

考虑对于 $k=2$$k = 2$ 的情况，不难发现这东西也是很显然的，枚举一下 unordered_set 中的所有数，若其为完全平方数的话贡献 $-1$$-1$，然后最后在答案中加上 $\lfloor \sqrt{n}\rfloor$$\lfloor \sqrt{n} \rfloor$ 即可。不难发现此时复杂度为 $O(n^{\frac{1}{3}}\log n)$$O(n^{\frac{1}{3}} \log n)$，可以通过。

同时不难发现对于 $\sqrt{n}$$\sqrt{n}$，这个东西如果直接朴素的用 double 的 sqrt() 函数的话会丢失精度，所以此时需考虑使用二分或 long double 或 __float128，前者会多一个 $\log$$\log$，对于上述 $k=2$$k = 2$ 的理论复杂度也是正确的。而用 __float128 会多一个十分巨大的甚至高于 $\log$$\log$ 的常数，不建议使用。当然我们也可以朴素地使用 sqrt() 然后取其返回值一段较小的邻域进行验证，一般 $\pm 1$$\pm 1$ 就够用了。

Code

xxxxxxxxxx
72
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
template < typename T = int >
24
inline T read(void);
25

26
ll N, K;
27
unordered_set < ll > legal;
28
ll ans(0);
29

30
int main(){
31
    auto qpow_with_lim = [](ll a, ll b)->ll{
32
        ll ret(1), mul(a);
33
        while(b){
34
            if(b & 1)
35
                ret = (__int128_t)ret * mul > N ? N + 1 : ret * mul;
36
            b >>= 1;
37
            mul = (__int128_t)mul * mul > N ? N + 1 : mul * mul;
38
        }return ret;
39
    };
40

41
    N = read < ll >(), K = read();
42
    if(K == 1)printf("%lld\n", N), exit(0);
43
    legal.insert(1);
44
    for(ll i = 2; i <= (ll)1e6; ++i){
45
        auto cur = (__int128_t)qpow_with_lim(i, K == 2 ? 3 : K);
46
        while(cur <= N)
47
            legal.insert(cur), cur *= i;
48
    }ans += legal.size();
49
    if(K == 2){
50
        for(auto v : legal)
51
            if((ll)sqrt((ld)v) * (ll)sqrt((ld)v) == v)--ans;
52
        ans += (ll)floor(sqrt((ld)N));
53
    }printf("%lld\n", ans);
54
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
55
    return 0;
56
}
57

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

T3 LG-P9119 [春季测试 2023] 圣诞树

题面

给定平面内凸包，最小化从其最高点开始的任意哈密尔顿路径（认为任意两点之间均可到达）的欧几里得距离，输出最小化的方案。存在 SPJ。

Solution

首先对于 $n\le 18$$n \le 18$，不难发现其为经典的 TSP 问题，状压后简单转移一下即可。对于性质 B，顺序输出即可。对于性质 A，目前没想到什么正确的思路。

考虑正解，发现对于任意两条路径一定不相交，证明是显然的，考虑任意四个点：

显然由于三角形两边之和大于第三边，前者一定优于后者。

所以对于逆时针给定的若干个点，当处于 $i$$i$ 时，最优决策一定只能是下一步到 $i-1$$i - 1$ 或 $i+1$$i + 1$，否则将会存在一个点被隔离，导致最终去往该点时一定形成交叉路径。

于是此时问题显然地转化为了区间 DP，考虑将原序列倍长，设状态 $dp(l,r,0/1)$$dp(l, r, 0/1)$ 表示当前已经走过了 $[l,r]$$[l, r]$ 的点，且最后停在了 $l$$l$ 或 $r$$r$ 的最小的总距离，则显然对于起点 $s$$s$ 有 $dp(s,s,0)=0,dp(s,s,1)=0$$dp(s, s, 0) = 0, dp(s, s, 1) = 0$。

转移也十分显然，与 [ABC273F] Hammer 2 类似，即：

Code

xxxxxxxxxx
97
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
template < typename T = int >
24
inline T read(void);
25

26
int N;
27
pair < ld, ld > pts[2100];
28
ld dis[2100][2100];
29
ld dp[2100][2100][2];
30
tuple < int, int, int > frm[2100][2100][2];
31
int top(-1); ld topy(-1e8);
32

33
int main(){
34
    auto CalDis = [](pair < ld, ld > a, pair < ld, ld > b)->ld{
35
        return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
36
    };
37
    auto Update = [](int l, int r, int k, int sl, int sr, int sk, int dl, int dr)->void{
38
        if(dp[sl][sr][sk] >= 1e12)return;
39
        if(dp[sl][sr][sk] + dis[dl][dr] < dp[l][r][k])
40
            dp[l][r][k] = dp[sl][sr][sk] + dis[dl][dr], frm[l][r][k] = {sl, sr, sk};
41
    };
42

43
    for(int i = 0; i <= 2010; ++i)for(int j = 0; j <= 2010; ++j)for(int k = 0; k <= 1; ++k)dp[i][j][k] = 1e12;
44
    N = read();
45
    for(int i = 1; i <= N; ++i){
46
        scanf("%Lf%Lf", &pts[i].first, &pts[i].second);
47
        pts[i + N] = pts[i];
48
        if(pts[i].second > topy)topy = pts[i].second, top = i;
49
    }
50
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)
51
        dis[i][j] = dis[i + N][j] = dis[i][j + N] = dis[i + N][j + N] = CalDis(pts[i], pts[j]);
52
    dp[top][top][0] = dp[top][top][1] = dp[top + N][top + N][0] = dp[top + N][top + N][1] = 0.0;
53
    for(int len = 2; len <= N; ++len)
54
        for(int l = 1; l <= (N << 1) - len + 1; ++l){
55
            int r = l + len - 1;
56
            Update(l, r, 0, l + 1, r, 0, l + 1, l);
57
            Update(l, r, 0, l + 1, r, 1, r, l);
58
            Update(l, r, 1, l, r - 1, 0, l, r);
59
            Update(l, r, 1, l, r - 1, 1, r - 1, r);
60
        }
61
    ld ansv(1e12); tuple < int, int, int > curp(0, 0, 0);
62
    for(int l = 1; l < N; ++l){
63
        int r = l + N - 1;
64
        if(dp[l][r][0] < ansv)ansv = dp[l][r][0], curp = {l, r, 0};
65
        if(dp[l][r][1] < ansv)ansv = dp[l][r][1], curp = {l, r, 1};
66
    }
67
    basic_string < int > rans;
68
    auto [l, r, k] = curp;
69
    auto lst = curp; curp = frm[l][r][k];
70
    while(get < 0 >(curp)){
71
        auto [l, r, k] = lst;
72
        auto [cl, cr, ck] = curp;
73
        if(l != cl)rans += l;
74
        else rans += r;
75
        lst = curp;
76
        curp = frm[cl][cr][ck];
77
    }rans += get < 0 >(lst);
78
    for_each(rans.rbegin(), rans.rend(), [rans](auto val)->void{printf("%d%c", val > N ? val - N : val, val == *prev(rans.rend()) ? '\n' : ' ');});
79
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
80
    return 0;
81
}
82

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

T4 LG-P9120 [春季测试 2023] 密码锁

$k=1,k=2$$k = 1, k = 2$ 十分朴素，$k=3$$k = 3$ 考虑二分答案后钦定全局最大最小值的位置后枚举另外一列的值域解决，$k=4$$k = 4$ 较为复杂略了。

UPD

update-2023_03_06 初稿