AtCoder Beginner Contest 250

发表于2022-05-12更新于2023-09-16字数统计2.2k阅读时长23分作者Shane

比赛链接

D 250-like Number

Description

题目链接

Solution

显然 qq 一定是 [1,N3][1, \sqrt[3]{N}] 内的质数。

首先筛出这个范围内的质数，从小到大存入数组 aa 中。

设质数个数为 nn, 记 i=1,j=ni = 1, j = n。考虑到 qq 增大时 pp 的取值范围一定减小，反复进行如下操作直到 i=n+1i = n + 1 或 j=0j=0：

  • 当 ai3∗aj>Na_i^3*a_j>N 时，令 j=j−1j = j - 1；
  • 取 q=aiq = a_i ，则满足条件的 250250 数有 min(i−1,j)min(i - 1, j) 个，记入答案；
  • i=i+1i = i + 1；

Code

250-like Number
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 1E6 + 5;
const int MOD = 1E9 + 7;
LL n;
vector<int> prime, isprime;

void getPrime(int m) {
    isprime.resize(m + 1);
    fill(isprime.begin() + 2, isprime.end(), 1);
    for (int i = 2; i <= m; i++) {
        if (isprime[i]) prime.push_back(i);
        for (int j = 0; j < prime.size() && prime[j] * i <= m; j++) {
            isprime[i * prime[j]] = 0;
            if (i % prime[j] == 0) break;
        }
    }
}

signed main() {
    cin >> n;
    int m = pow(n, 1.0 / 3) + 1;
    getPrime(m);
    int i = 0, j = prime.size() - 1;
    LL ans = 0;
    while (i <= (int)prime.size() - 1 && j >= 0) {
        while (j >= 0 && 1ll * prime[i] * prime[i] * prime[i] * prime[j] > n)
            j--;
        ans += min(i, j + 1);
        i++;
    }
    cout << ans;
    return 0;
}

E Prefix Equality

Description

题目链接

Solution

官方题解给出了一种用 setset 的做法，这种做法还是比较易懂的，但是有一个问题是不能处理区间查询，即询问集合 {ax,ax+1,...,ay}\{a_x,a_{x+1},...,a_y\} 和 {bz,bz+1,...,bw}\{b_z,b_{z+1},...,b_w\} 是否相同。

这里给出基于哈希的做法。

先讲下本题怎么做。首先对 aa 和 bb 中所有不同的数分别生成一个 64 位的随机数，再分别求前缀异或和（注意，只在第一次遇到某个数时才加入异或和），最后查询的时候判断前缀异或和是否相同即可。这种做法可能会有误判，但概率很低，怕出错可以多跑几次。

再讲下区间查询怎么做。我们要查询的实际上是区间内不同数的异或和，用可持久化线段树便可求解，也可以离线后用树状数组。对于每个数，我们只记录它在区间内最后出现的位置。

Code

Prefix Equality
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

template <class T>
void write(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, T;
int a[MAXN], b[MAXN];
uint64_t f[MAXN], g[MAXN];

unordered_set<int> s;

signed main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]), s.insert(a[i]);
    for (int i = 1; i <= n; i++) read(b[i]), s.insert(b[i]);

    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    mt19937_64 engine(seed);

    unordered_map<int, uint64_t> h;
    for (auto& v : s) h[v] = engine();

    unordered_map<int, bool> visa, visb;

    for (int i = 1; i <= n; i++) {
        if (!visa[a[i]]) {
            f[i] = (f[i - 1] ^ h[a[i]]);
            visa[a[i]] = 1;
        } else {
            f[i] = f[i - 1];
        }

        if (!visb[b[i]]) {
            g[i] = (g[i - 1] ^ h[b[i]]);
            visb[b[i]] = 1;
        } else {
            g[i] = g[i - 1];
        }
    }
    read(m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        read(x, y);
        puts(f[x] == g[y] ? "Yes" : "No");
    }
    return 0;
}

F One Fourth

Description

题目链接

Solution

维护一段凸壳，要求将凸壳两端连起来后，得到的凸多边形面积尽可能接近整个多边形面积的四分之一。如果某凸壳对应凸多边形面积恰好超过四分之一，当凸壳右端点顺时针移动时，左端点一定不会逆时针移动，否则答案不会更优。根据这一单调性，考虑使用双指针，始终保持凸壳对应凸多边形面积恰好超过四分之一。至于面积，我们维护凸壳上相邻点的叉积和便能以 O(1)O(1) 的复杂度更新和计算。

Code

One Fourth
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

template <class T>
void write(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;

int n;

struct Vec2 {
    Vec2() = default;
    Vec2(LL _x, LL _y) : x(_x), y(_y) {}

    friend inline Vec2 intersect(const Vec2&, const Vec2&, const Vec2&,
                                 const Vec2&);

    friend inline bool operator<(const Vec2& a, const Vec2& b) {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    }

    friend inline Vec2 operator-(const Vec2& a, const Vec2& b) {
        return Vec2(a.x - b.x, a.y - b.y);
    }

    friend inline Vec2 operator+(const Vec2& a, const Vec2& b) {
        return Vec2(a.x + b.x, a.y + b.y);
    }
    /*@return cross product of two Vec2*/
    friend inline LL operator*(const Vec2& a, const Vec2& b) {
        return a.x * b.y - a.y * b.x;  //×
    }
    /*@return 向量与数乘后的向量*/
    friend inline Vec2 operator*(const Vec2& a, LL num) {
        return Vec2(a.x * num, a.y * num);
    }
    /*@param a 2D vector @return norm of the vector*/
    friend inline LL norm(const Vec2& a) { return sqrt(a.x * a.x + a.y * a.y); }
    /*@param a 2D vector @return square norm of the vector*/
    friend inline LL normSquare(const Vec2& a) { return a.x * a.x + a.y * a.y; }
    LL x = 0, y = 0;
} vec[MAXN];

LL getArea() {
    LL ans = 0;
    for (int i = 1; i <= n; i++) ans += vec[i] * vec[i % n + 1];
    return ans;
}

signed main() {
    read(n);
    for (int i = 1; i <= n; i++) read(vec[i].x, vec[i].y);
    LL area = getArea();
    LL ans = LONG_LONG_MAX;
    LL sum = 0;
    for (int i = 1, j = 1; i <= n; i++) {
        LL b = sum + (vec[j] * vec[i]);
        if (i != j)
            ans = min({ans, abs(area - b * 4), abs(area - (area - b) * 4)});
        while ((sum + (vec[j] * vec[i])) * 4 <= area) {
            sum += vec[j] * vec[j % n + 1];
            j = j % n + 1;
            LL b = sum + (vec[j] * vec[i]);
            if (i != j)
                ans = min({ans, abs(area - b * 4), abs(area - (area - b) * 4)});
        }
        sum -= vec[i] * vec[i % n + 1];
    }
    write(ans);
    return 0;
}

G Stonks

Description

题目链接

Solution

做法参考这篇题解。

证明的话，考虑一个 aia_i 原本可以从 11 修改为 00，但是却没有修改，且后续在某一位置 jj 进行了修改，满足 pj<=pip_j <= p_i，j>ij > i，且 jj 是最小的，那么可以取消对 aja_j 的修改，将其作用于 aia_i，答案不会减小。类似的，当 aia_i 可以从 11 改为 −1-1 时，我们没有理由保持 aia_i 不变，或者改为 00。

Code

Stonks
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;

int n;
int p[MAXN], s[MAXN];
LL sum = 0;

#define lid id << 1
#define rid id << 1 | 1

struct node {
    int l, r;
    int mi, lazy;
} tr[MAXN << 2];

void update(int id) { tr[id].mi = min(tr[lid].mi, tr[rid].mi); }

void build(int id, int l, int r) {
    tr[id].l = l, tr[id].r = r;
    tr[id].lazy = 0;
    if (l == r) {
        tr[id].mi = s[l];
        return;
    }
    int mid = l + r >> 1;
    build(lid, l, mid);
    build(rid, mid + 1, r);
    update(id);
}

void pushdown(int id) {
    if (tr[id].lazy) {
        tr[lid].mi += tr[id].lazy;
        tr[rid].mi += tr[id].lazy;
        tr[lid].lazy += tr[id].lazy;
        tr[rid].lazy += tr[id].lazy;
        tr[id].lazy = 0;
    }
}

void modify(int id, int l, int r, int v) {
    if (tr[id].l == l && tr[id].r == r) {
        tr[id].mi += v;
        tr[id].lazy += v;
        return;
    }
    pushdown(id);
    int mid = tr[id].l + tr[id].r >> 1;
    if (r <= mid)
        modify(lid, l, r, v);
    else if (l > mid)
        modify(rid, l, r, v);
    else
        modify(lid, l, mid, v), modify(rid, mid + 1, r, v);
    update(id);
}

int qmin(int id, int l, int r) {
    if (tr[id].l == l && tr[id].r == r) return tr[id].mi;
    pushdown(id);
    int mid = tr[id].l + tr[id].r >> 1;
    if (r <= mid)
        return qmin(lid, l, r);
    else if (l > mid)
        return qmin(rid, l, r);
    else
        return min(qmin(lid, l, mid), qmin(rid, mid + 1, r));
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    LL sum = 0;
    set<pair<int, int>> sp;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        sum -= p[i];
        s[i] = s[i - 1] + 1;
        sp.insert({-p[i], -i});
    }
    build(1, 1, n);
    while (sp.size()) {
        auto [val, id] = *sp.begin();
        sp.erase(sp.begin());
        val = -val;
        id = -id;
        int tmp = qmin(1, id, n);
        if (tmp >= 2) {
            sum += val * 2;
            modify(1, id, n, -2);
        } else if (tmp >= 1) {
            sum += val;
            modify(1, id, n, -1);
        }
    }
    cout << sum;
    return 0;
}