AtCoder Beginner Contest 250 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

abc三道题太水了就跳了

[ABC250D] 250-like Number

题面

给定 $n$$n$，求有多少正整数 $k$$k$ 满足 $k\le n$$k \le n$ 且 $k=p\times q^3$$k = p \times q^3$，其中 $p,q$$p, q$ 为质数且 $p<q$$p \lt q$。

Solution

看数据范围和题意不难想到，枚举 $q$$q$。显然 $n$$n$ 的范围在 ${10}^{18}$$10^{18}$，那么 $q$$q$ 的范围就在 ${10}^6$$10^6$。或者说 $q\le n^{\frac{1}{3}}$$q \le n^{\frac{1}{3}}$，所以我们先预处理出来 $n^{\frac{1}{3}}$$n^{\frac{1}{3}}$ 的所有质数，然后枚举每个质数，自然有 $p\le min(\lfloor {\displaystyle \frac{n}{q^3}}\rfloor ,q-1)$$p \le \min(\lfloor \dfrac{n}{q^3} \rfloor, q - 1)$，所以范围内每一个 $p$$p$ 都是合法的。发现这个东西做个前缀和之后即可 $O(1)$$O(1)$ 查询，线性筛素数的话最终就是 $O(n^{\frac{1}{3}})$$O(n^{\frac{1}{3}})$。

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

25
ll N;
26
ll ans(0);
27
basic_string < int > prime;
28
bool notPrime[1100000];
29
int sum[1100000];
30

31
int main(){
32
    N = read < ll >();
33
    ll lim = (ll)powl(N, 1.0 / 3.0) + 10;
34
    for(int i = 2; i <= lim; ++i){
35
        if(!notPrime[i])prime += i;
36
        for(auto p : prime){
37
            if(i * p > lim)break;
38
            notPrime[i * p] = true;
39
            if(i % p == 0)break;
40
        }
41
    }for(int i = 2; i <= lim; ++i)sum[i] = sum[i - 1] + (!notPrime[i] ? 1 : 0);
42
    for(auto p : prime){
43
        ll base = (ll)p * p * p;
44
        ans += sum[min(N / base, (ll)p - 1)];
45
    }printf("%lld\n", ans);
46
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
47
    return 0;
48
}
49

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

[ABC250E] Prefix Equality

题面

给定两个长为 $N$$N$ 的数列 $A,B$$A,B$ 与 $Q$$Q$ 次询问，每次询问给出 $x_i,y_i$$x_i,y_i$，求出 $A$$A$ 的前 $x_i$$x_i$ 项去重后是否与 $B$$B$ 的前 $y_i$$y_i$ 项相同。

Solution

水题。最容易想到的是莫队，没什么可说的，但是写着麻烦。

简单思考一下可以想到类似双指针的写法，大概就是对于一个 $sum{a}_i$$suma_i$ 一定会对应一段合法的 $sum{b}_i$$sumb_i$，且存在单调性。

然后有个人类智慧的写法就是随便实现一个满足交换律的哈希即可。

Code

xxxxxxxxxx
73
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
int N;
28
int a[210000], b[210000];
29
unll suma[210000], sumb[210000];
30
unordered_set < int > exta, extb;
31

32
int main(){
33
    N = read();
34
    for(int i = 1; i <= N; ++i){
35
        a[i] = read();
36
        suma[i] = suma[i - 1] ^ (
37
            exta.find(a[i]) == exta.end()
38
                ? exta.insert(a[i]), (unll)a[i] * (114514123ll)
39
                : 0ll
40
        );
41
    }
42
    for(int i = 1; i <= N; ++i){
43
        b[i] = read();
44
        sumb[i] = sumb[i - 1] ^ (
45
            extb.find(b[i]) == extb.end()
46
                ? extb.insert(b[i]), (unll)b[i] * (114514123ll)
47
                : 0ll
48
        );
49
    }
50
    int Q = read();
51
    while(Q--){
52
        int x = read(), y = read();
53
        printf("%s\n", suma[x] == sumb[y] ? "Yes" : "No");
54
    }
55
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
56
    return 0;
57
}
58

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

[ABC250F] One Fourth

题面

给定凸包，逆时针给定凸包的每个顶点。你需要通过连结两个顶点将凸包划分为两部分并选择其中一个。令凸包面积为 $a$$a$，选定部分面积为 $b$$b$，需要最小化 $8\times |{\displaystyle \frac{a}{4}}-b|$$8 \times \lvert \dfrac{a}{4} - b \rvert$，求最小值。易证该值为整数。

Solution

发现这东西类似旋转卡壳，于是按照旋转卡壳的思想跑一下，或者说类似在环形上维护一个双指针，固定 $l$$l$ 移动 $r$$r$，显然我们是想让 $8b$$8b$ 尽量和 $2a$$2a$ 相同，所以我们在 $8b$$8b$ 小于 $2a$$2a$ 的时候让 $r$$r$ 一直增大，这样会让面积一直变大，到超过 $2a$$2a$ 之后停止，然后移动 $l$$l$，类似这样跑一下即可，最终复杂度 $O(n)$$O(n)$。

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
struct Coord{
26
    ll x, y;
27
    friend const ll operator * (const Coord &a, const Coord &b){
28
        return abs(a.x * b.y - a.y * b.x);//2S
29
    }
30
};
31
ll CalS(Coord a, Coord b, Coord c){
32
    Coord vec1{b.x - a.x, b.y - a.y}, vec2{c.x - a.x, c.y - a.y};
33
    return vec1 * vec2;
34
}
35
Coord p[110000];
36
int N;
37
ll tot(0);
38
ll ans(LONG_LONG_MAX);
39
//abs(2A - 8B)
40
int main(){
41
    N = read();
42
    for(int i = 1; i <= N; ++i)p[i].x = read(), p[i].y = read();
43
    for(int i = 2; i <= N - 1; ++i)tot += CalS(p[1], p[i], p[i + 1]); //2S
44
    int r(2);
45
    ll cur(0);
46
    for(int l = 1; l <= N; ++l){
47
        while(cur * 4 < tot){
48
            ans = min(ans, abs(tot - cur * 4));
49
            cur += CalS(p[l], p[r], p[r % N + 1]);
50
            (r %= N) += 1;
51
            // printf("l = %d, r = %d, B = %lld, A = %lld\n", l, r, cur * 4, tot);
52
        }ans = min(ans, abs(tot - cur * 4));
53
        cur -= CalS(p[l], p[l + 1], p[r]);
54
        // ans = min(ans, abs(tot - cur * 4));
55
    }printf("%lld\n", ans);
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
}

[ABC250G] Stonks

题面

给定序列 $P_n$$P_n$ 表示 $n$$n$ 天里的股价，每天可以买入或卖出一股，本金无限，求最多能赚多少钱。

Solution

明显反悔贪心。

不失一般性，令 $a<b<c$$a \lt b \lt c$，则若某天存在如下决策，即买 $a$$a$ 卖 $b$$b$，那么赚的钱为 $b-a$$b - a$，而显然对于 $a$$a$ 来说，若买 $a$$a$ 卖 $c$$c$，那么贡献为 $c-a>b-a$$c - a \gt b - a$，差为 $c-b$$c - b$，则不难想到当买 $a$$a$ 卖 $b$$b$ 的时候再将 $b$$b$ 插入，此时如果存在 $c$$c$ 取了插入的 $b$$b$，其实际意义即为撤销买 $a$$a$ 卖 $b$$b$ 并改为买 $a$$a$ 卖 $c$$c$，但此时 $b$$b$ 天就无操作了，所以我们此时需要再额外插入一个 $b$$b$，表示后面若需要可以执行一次买 $b$$b$ 卖 $d$$d$ 的操作。不难想到可以用小根堆维护，假设堆顶元素为 $top$$top$，当前元素为 $x$$x$，若 $x-top>0$$x - top > 0$ 那么贡献为 $x-top$$x - top$，反之将 $x$$x$ 压入小根堆即可。

双倍经验 CF865D Buy Low Sell High。

Code

xxxxxxxxxx
1
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 P[210000];
27
ll ans(0);
28
priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > cur;
29

30
int main(){
31
    N = read();
32
    for(int i = 1; i <= N; ++i){
33
        P[i] = read();
34
        if(!cur.empty() && P[i] > cur.top().first){
35
            int val, idx; tie(val, idx) = cur.top(); cur.pop();
36
            ans += P[i] - val, cur.push({P[i], P[i]});
37
            if(idx)cur.push({idx, 0});
38
        }else cur.push({P[i], 0});
39
    }printf("%lld\n", ans);
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
}

[ABC250Ex] Trespassing Takahashi

题面

给定一张 $n$$n$ 个点 $m$$m$ 条边的无向连通简单图。每条边存在 $a_i,b_i,c_i$$a_i, b_i, c_i$，表示 $a_i\to b_i$$a_i \rightarrow b_i$ 或 $b_i\to a_i$$b_i \rightarrow a_i$ 耗时 $c_i$$c_i$。给定 $k$$k$，定义 $n$$n$ 个点中只有前 $k$$k$ 个点有房子，$q$$q$ 次询问，每次给定 $x,y,t$$x, y, t$，求从 $x$$x$ 到 $y$$y$ 连续的不在房子中的时间是否一定会超过 $t$$t$，超过输出 No，反之输出 Yes。保证询问中 $t$$t$ 满足升序。

Solution

考虑维护对于走每条边时需要多长时间才能连通最近的两个房子，换句话说，满足这个时间的时候这条边就一定可以被走。具体维护可以考虑建一个超级源点并向所有房子连个边，然后跑个 Dijk 即可，当然直接往队列里把所有房子点都塞进去也行。然后我们可以令 $c_i\leftarrow c_i+di{s}_{a_i}+di{s}_{b_i}$$c_i \leftarrow c_i + dis_{a_i} + dis_{b_i}$ 即可，然后显然可以用并查集维护。

具体地，每次询问将边集里所有新的 $c_i$$c_i$ 满足 $c_i\le t$$c_i \le t$ 的边加上，用并查集维护，然后查询一下 $x,y$$x, y$ 是否连通即可，这个复杂度是 $O(mq)$$O(mq)$ 的，当然发现 $t$$t$ 符合升序，所以给边排个序跑一边即可，最终复杂度应该是卡在排序和 Dijk 上，也就是 $O(n\log n+m\log m)$$O(n \log n + m \log m)$。

同时不难想到即使 $t$$t$ 不符合升序也可以离线排个序再跑，复杂度多个 $O(q\log q)$$O(q \log q)$ 而已。至此本题已经结束，下面是一道加强版的双倍经验。

存在一道双倍经验 CF1253F Cheap Robot，略有区别，这里简单说一下：这道题的区别就在于询问的是最小的 $t$$t$，这样的话实际上是不太好用刚才的思路离线下来维护的，有一个复杂度不太正确但能过的思路，就是将每个询问的 $a,b$$a, b$ 分别挂在两个点上，然后将 $c_i$$c_i$ 排序，从小到大依次加边，同时更新所有挂在连通块根上的答案，再对应的把询问合上去。但是这个的并查集一定需要按秩合并，否则如果 clear() 之后 shrink_to_fit() 就会 TLE，否则会 MLE，按秩合并会保证合并询问的时候不会复制太多次以保证空间。这个东西的复杂度理论上似乎可以被卡到 $O(mq)$$O(mq)$，但是本题没卡。当然还有一个我口糊的剪枝，就是挂在点上的询问我们用链表维护，然后贪心地取第一次更新这个点时的答案，显然不劣，于是更新后 $O(1)$$O(1)$ 删除即可，但是这个东西理论上也能被卡到 $O(mq)$$O(mq)$，不过需要精细设计数据。当然正确的做法最后应该是建出最小生成树然后树剖或者倍增之类的实现。

Code

xxxxxxxxxx
1
96
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
struct Edge{
26
    Edge* nxt;
27
    int to;
28
    ll val;
29
    OPNEW;
30
}ed[410000];
31
ROPNEW(ed);
32
Edge* head[210000];
33

34
int N, M, K;
35
bitset < 210000 > vis;
36
ll dis[210000];
37
priority_queue < tuple < ll, int, int >, vector < tuple < ll, int, int > >, greater < tuple < ll, int, int > > > edgs;
38

39
class UnionFind{
40
private:
41
    int fa[210000];
42
public:
43
    UnionFind(void){for(int i = 1; i <= 201000; ++i)fa[i] = i;}
44
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
45
    void Union(int origin, int son){fa[Find(son)] = Find(origin);}
46
}uf;
47

48
void Dijk(void){
49
    memset(dis, 0x3f, sizeof dis);
50
    priority_queue < pair < ll, int >, vector < pair < ll, int > >, greater < pair < ll, int > > > cur;
51
    for(int i = 1; i <= K; ++i)cur.push({dis[i] = 0, i});
52
    while(!cur.empty()){
53
        int p = cur.top().second; cur.pop();
54
        if(vis[p])continue;
55
        vis[p] = true;
56
        for(auto i = head[p]; i; i = i->nxt)
57
            if(dis[p] + i->val < dis[SON])
58
                dis[SON] = dis[p] + i->val, cur.push({dis[SON], SON});
59
    }
60
}
61
int main(){
62
    N = read(), M = read(), K = read();
63
    for(int i = 1; i <= M; ++i){
64
        int s = read(), t = read(), v = read();
65
        head[s] = new Edge{head[s], t, v};
66
        head[t] = new Edge{head[t], s, v};
67
    }Dijk();
68
    for(int p = 1; p <= N; ++p)
69
        for(auto i = head[p]; i; i = i->nxt)
70
            edgs.push({i->val + dis[p] + dis[SON], p, SON});
71
    int Q = read();
72
    while(Q--){
73
        int s = read(), t = read(); ll lim = read < ll >();
74
        while(!edgs.empty() && get < 0 >(edgs.top()) <= lim)
75
            uf.Union(get < 1 >(edgs.top()), get < 2 >(edgs.top())), edgs.pop();
76
        printf("%s\n", uf.Find(s) == uf.Find(t) ? "Yes" : "No");
77
    }
78
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
79
    return 0;
80
}
81

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

UPD

update-2022_12_20 初稿