AtCoder Beginner Contest 439

A

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
signed main() {
25
    // ios::sync_with_stdio(0);
26
    // cin.tie(0);
27
    // cout.tie(0);
28
    int n;
29
    cin >> n;
30
    cout << (1ll << n) - 2 * n << endl;
31
    return 0;
32
}

B

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
int v[5000];
25
int calc(int n) {
26
    int res = 0;
27
    while(n) {
28
        res += (n % 10) * (n % 10);
29
        n = n / 10;
30
    }
31
    return res;
32
}
33
signed main() {
34
    ios::sync_with_stdio(0);
35
    cin.tie(0);
36
    cout.tie(0);
37
    int n;
38
    cin >> n;
39
    while(n != 1 && !v[n]) {
40
        v[n] = 1;
41
        n = calc(n);
42
    }
43
    if(n == 1) cout << "Yes" << endl;
44
    else cout << "No" << endl;
45
    return 0;
46
}

C

先把平方数筛出来，然后平方枚举一遍，记录次数就行了。

注意实现的方法，不要超过 $O(n)$ 。

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 1e7 + 5;
25
int n, m;
26
vector<int> p;
27
int v[N];
28
signed main() {
29
    ios::sync_with_stdio(0);
30
    cin.tie(0);
31
    cout.tie(0);
32
    cin >> n;
33
    for(int i = 1;i * i < n;i++) p.pb(i * i);
34
    m = p.size();
35
    int ans = 0;
36
    for(int i = 0;i < m;i++) {
37
        for(int j = i + 1;j < m;j++) {
38
            if(p[i] + p[j] > n) break;
39
            if(!v[p[i] + p[j]]) {
40
                ans++;
41
                v[p[i] + p[j]] = 1;
42
            } else if(v[p[i] + p[j]] == 1) {
43
                ans--;
44
                v[p[i] + p[j]] = -1;
45
            }
46
        }
47
    }
48
    cout << ans << endl;
49
    for(int x = 1;x <= n;x++) if(v[x] == 1) cout << x << " ";
50
    cout << endl;
51
    return 0;
52
}

D

这个很简单，分两种情况枚举 $j$ ，用std::unordered_map维护一下就好了。

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 3e5 + 5;
25
int n, a[N];
26
unordered_map<int, int> p, q;
27
signed main() {
28
    ios::sync_with_stdio(0);
29
    cin.tie(0);
30
    cout.tie(0);
31
    cin >> n;
32
    for(int i = 1;i <= n;i++) {
33
        cin >> a[i];
34
    }
35
    for(int i = 1;i <= n;i++) {
36
        ++p[a[i]], ++q[a[i]];
37
    }
38
    ll ans = 0;
39
    for(int j = 1;j <= n - 2;--p[a[j]], j++) if(a[j] % 5 == 0) {
40

41
        ans += 1ll * (p[a[j] / 5 * 3]) * (p[a[j] / 5 * 7] );
42
    }
43
    for(int j = n;j >= 3;--q[a[j]], j--) if(a[j] % 5 == 0) {
44
        ans += 1ll * (q[a[j] / 5 * 3]) * (q[a[j] / 5 * 7]);
45
    }
46
    cout << ans << endl;
47
    return 0;
48
}

E

这里只讲我的做法，没有思维难度，但比正解复杂得多。

我们按照斜率是否 $\ge 0$ ，把线段分为两类，称为 1 类和 2 类线段。

手玩一下不难发现以下结论：

两个 1 类线段 $i, j$ 可以同时选择，当且仅当 $[A_i, B_i]$ 与 $[A_j, B_j]$ 没有包含关系。
两个 2 类线段 $i, j$ 可以同时选择，当且仅当 $[B_i, A_i]$ 与 $[B_j, A_j]$ 没有包含关系。
1 类线段 $i$ 和二类线段 $j$ 可以同时选择，当且仅当 $[A_i, B_i]$ 和 $[B_j, A_j]$ 无交。

然后我们就转化成了线段问题。

先给所有线段按照右端点递增排个序，这样无包含和无交都只需要维护一维坐标。

设 $f_i$ 考虑前 $i$ 条线段，必须选 $i$ ，最多能选出几条线段。枚举 $j$ ，根据线段类型判断一下就能转移。

这个 DP 对吗？评判标准就是一个偏序关系：如果 $i$ 与 $j$ 合法，那么 $i$ 与之前所有的线段都合法。

如果 $i, j$ 无交，其它线段的右端点又小于 $j$ 的，所以更不可能与 $i$ 交。

如果 $i$ 不包含 $j$ ，但存在一个之前选出的 $k$ 被 $i$ 包含，那么 $k$ 一定被 $j$ 包含；或者右端点大于 $j$ ，出现矛盾。如图

于是满足偏序关系，DP 成立。

然后考虑优化。

把坐标离散化了，开四棵线段树，然后把 $f_i$ 值挂在 $A_i, B_i$ 对应的端点上。无交就在右端点线段树上查小于左端点的，无包含就在左端点线段树上查小于左端点的。

复杂度 $O(n \log n)$ ，常数被正解秒杀。

注意，相同右端点的线段必须在处理完函数值后一同被插入线段树，否则可能被它们的左端点更新（而右端点重合非法）。

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 2e5 + 5;
25
int n, m, b[N << 1];
26
int f[N];
27
struct node {
28
    int l, r, type;
29
} a[N];
30
bool cmp(node& a, node& b) {
31
    if(a.r != b.r) return a.r < b.r;
32
    return a.l < b.l;
33
}
34
void lsh() {
35
    sort(b + 1, b + m + 1);
36
    m = unique(b + 1, b + m + 1) - (b + 1);
37
    for(int i = 1;i <= n;i++) {
38
        a[i].l = lower_bound(b + 1, b + m + 1, a[i].l) - b;
39
        a[i].r = lower_bound(b + 1, b + m + 1, a[i].r) - b;
40
    }
41
}
42
struct SEG {
43
    int t[(N << 1) << 2];
44
    void pushup(int x) {
45
        t[x] = max(t[x << 1], t[x << 1 | 1]);
46
    }
47
    void build(int x = 1, int l = 1, int r = m) {
48
        if(l == r) {
49
            t[x] = 0;
50
            return;
51
        }
52
        int mid = (l + r) >> 1;
53
        build(x << 1, l, mid);
54
        build(x << 1 | 1, mid + 1, r);
55
        pushup(x);
56
    }
57
    void upd(int p, int d, int x = 1,int l = 1, int r = m) {
58
        if(l == r) {
59
            t[x] = d;
60
            return;
61
        }
62
        int mid = (l + r) >> 1;
63
        if(p <= mid) upd(p, d, x << 1, l, mid);
64
        else upd(p, d, x << 1 | 1, mid + 1, r);
65
        pushup(x);
66
    }
67
    int query(int L, int R, int x = 1, int l = 1, int r = m) {
68
        if(L > R) return -1;
69
        if(L <= l && r <= R) return t[x];
70
        int mid = (l + r) >> 1;
71
        int res = 0;
72
        if(L <= mid) res = max(res, query(L, R, x << 1, l, mid));
73
        if(R > mid) res = max(res, query(L, R, x << 1 | 1, mid + 1, r));
74
        return res;
75
    }
76
} seg[4];
77
signed main() {
78
    ios::sync_with_stdio(0);
79
    cin.tie(0);
80
    cout.tie(0);
81
    cin >> n;
82
    for(int i = 1;i <= n;i++) {
83
        cin >> a[i].l >> a[i].r;
84
        b[++m] = a[i].l, b[++m] = a[i].r;
85
        a[i].type = 1;
86
        if(a[i].l > a[i].r) {
87
            swap(a[i].l, a[i].r);
88
            a[i].type = -1;
89
        }
90
    }
91
    sort(a + 1, a + n + 1, cmp);
92
    lsh();
93
    int ans = 0;
94
    for(int i = 0;i < 4;i++) seg[i].build();
95
    vector<int> v;
96
    for(int i = 1;i <= n;i++) {
97
        f[i] = 1;
98
        if(a[i].type == 1) {
99
            f[i] = max(f[i], seg[0].query(1, a[i].l - 1) + 1);
100
            f[i] = max(f[i], seg[3].query(1, a[i].l - 1) + 1);
101
        } else {
102
            f[i] = max(f[i], seg[1].query(1, a[i].l - 1) + 1);
103
            f[i] = max(f[i], seg[2].query(1, a[i].l - 1) + 1);
104
        }
105
        ans = max(ans, f[i]);
106
        v.pb(i);
107
        if(a[i].r != a[i + 1].r) {
108
            for(auto x : v) {
109
                if(a[x].type == 1) {
110
                    seg[0].upd(a[x].l, f[x]);
111
                    seg[1].upd(a[x].r, f[x]);
112
                } else {
113
                    seg[2].upd(a[x].l, f[x]);
114
                    seg[3].upd(a[x].r, f[x]);
115
                }
116
            }
117
            v.clear();
118
        }
119
    }
120
    cout << ans << endl;
121
    return 0;
122
}

F

todo

G

…

Nanami^2

A

B

C

D

E

F

G

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

A

B

C

D

E

F

G

觉得这篇文章怎么样？

分享这篇文章

评论区