CF#742 div2

Posted on Edited on In Views:
Symbols count in article: 8.7k
题目 A B C D E F
通过情况 AC AC O O O X
难度 - - - - - -

A. Domino Disaster

题面

略

题解

略

代码

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
/*
 * @题目: A. Domino Disaster
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-09-05 22:34:55
 * @LastEditors: Blore
 * @LastEditTime: 2021-09-05 22:38:59
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
char s[maxn];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read();
        scanf("%s", s + 1);
        rep(i, 1, n)
        {
            if (s[i] == 'L' || s[i] == 'R')
                putchar(s[i]);
            else if (s[i] == 'D')
                putchar('U');
            else if (s[i] == 'U')
                putchar('D');
        }
        puts("");
    }
    return 0;
}

B. MEXor Mixup

题面

略

题解

略

代码

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
/*
 * @题目: 
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-09-05 22:34:55
 * @LastEditors: Blore
 * @LastEditTime: 2021-09-05 22:49:54
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 300010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int pre[maxn];
int main()
{
    int t = read();
    rep(i, 1, 300000) pre[i] = pre[i - 1] ^ i;
    while (t--)
    {
        int b = read(), a = read();
        if (pre[b - 1] != a && pre[b] == a)
            printf("%d\n", b + 2);
        else if (pre[b - 1] != a)
            printf("%d\n", b + 1);
        else
            printf("%d\n", b);
    }
    return 0;
}

C. Carrying Conundrum

题面

略

题解

隔位分成两个数进行讨论

代码

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
/*
 * @题目: C. Carrying Conundrum
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-09-05 23:05:14
 * @LastEditors: Blore
 * @LastEditTime: 2021-09-05 23:41:35
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int main()
{
    int t = read();
    while (t--)
    {
        int n = read();
        ll ans1 = 0, ans2 = 0, p = 0, base = 1;
        while (n)
        {
            if (p % 2 == 0)
                ans1 = ans1 + n % 10 * base;
            else
                ans2 = ans2 + n % 10 * base, base *= 10;
            n /= 10, p++;
        }
        // printf("%lld %lld ", ans1, ans2);
        ll ans = 0;
        if (ans1 == 0)
        {
            ans2--;
            printf("%lld\n", ans2);
        }
        else if (ans2 == 0)
        {
            ans1--;
            printf("%lld\n", ans1);
        }
        else
        {
            ll ans = 0;
            ans = 2 * (ans1 - 1) + 2 * (ans2 - 1) + 2 + (ans1 - 1) * (ans2 - 1);
            printf("%lld\n", ans);
        }
    }
    return 0;
}

D. Expression Evaluation Error

题面

略

题解

略

代码

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
106
107
108
109
110
111
112
113
/*
 * @题目: D. Expression Evaluation Error
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-09-05 23:46:49
 * @LastEditors: Blore
 * @LastEditTime: 2021-09-06 09:19:07
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
vector<ll> curr;
ll split(ll n)
{
    ll pow10 = 1;
    while (pow10 <= n)
    {
        if (pow10 == n)
        {
            return pow10 / 10;
        }
        pow10 *= 10;
    }
    return pow10 / 10;
}
bool isPow10(ll n)
{
    ll pow10 = 1;
    while (pow10 <= n)
    {
        if (pow10 == n)
        {
            return true;
        }
        pow10 *= 10;
    }
    return false;
}

int main()
{
    int t = read();
    while (t--)
    {
        ll n = read();
        int k = read();
        curr.clear();
        curr.pb(n);
        rep(j, 1, k - 1)
        {
            ll x = -1;
            for (int i = 0; i < curr.size(); i++)
            {
                if (!isPow10(curr[i]))
                {
                    x = curr[i];
                    curr.erase(curr.begin() + i);
                    break;
                }
            }
            if (x == -1)
            {
                ll mn = inf;
                for (int i = 0; i < curr.size(); i++)
                {
                    if (curr[i] != 1)
                    {
                        mn = min(mn, curr[i]);
                    }
                }
                for (int i = 0; i < curr.size(); i++)
                {
                    if (curr[i] == mn)
                    {
                        x = curr[i];
                        curr.erase(curr.begin() + i);
                        break;
                    }
                }
            }
            curr.pb(split(x));
            curr.pb(x - split(x));
        }
        for (int i = 0; i < curr.size(); i++)
            printf("%lld ", curr[i]);
        puts("");
    }
    return 0;
}

E. Non-Decreasing Dilemma

题面

略

题解

线段树维护区间前缀最长非降序列长度、后缀最长非降序列长度、非前后缀非降子序列个数、区间整个是否为非降序列

代码

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
/*
 * @题目: E. Non-Decreasing Dilemma
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-09-06 12:46:49
 * @LastEditors: Blore
 * @LastEditTime: 2021-09-06 13:29:51
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
ll sum(ll x)
{
    return x * (x + 1) / 2;
}
int seg[maxn << 2][4];
int a[maxn];
void pushup(int rt, int l, int r)
{
    int m = (l + r) >> 1;
    if (seg[rt << 1][3] && seg[rt << 1 | 1][3])
    {
        if (a[m] > a[m + 1])
        {
            seg[rt][0] = 0;
            seg[rt][1] = m - l + 1;
            seg[rt][2] = r - m;
            seg[rt][3] = 0;
        }
        else
        {
            seg[rt][1] = seg[rt][2] = seg[rt][0] = 0;
            seg[rt][3] = 1;
        }
    }
    else if (seg[rt << 1][3])
    {
        if (a[m] > a[m + 1])
        {
            seg[rt][0] = seg[rt << 1 | 1][0] + sum(seg[rt << 1 | 1][1]);
            seg[rt][1] = m - l + 1;
            seg[rt][2] = seg[rt << 1 | 1][2];
            seg[rt][3] = 0;
        }
        else
        {
            seg[rt][0] = seg[rt << 1 | 1][0];
            seg[rt][1] = m - l + 1 + seg[rt << 1 | 1][1];
            seg[rt][2] = seg[rt << 1 | 1][2];
            seg[rt][3] = 0;
        }
    }
    else if (seg[rt << 1 | 1][3])
    {
        if (a[m] > a[m + 1])
        {
            seg[rt][0] = seg[rt << 1][0] + sum(seg[rt << 1][2]);
            seg[rt][1] = seg[rt << 1][1];
            seg[rt][2] = r - m;
            seg[rt][3] = 0;
        }
        else
        {
            seg[rt][0] = seg[rt << 1][0];
            seg[rt][1] = seg[rt << 1][1];
            seg[rt][2] = r - m + seg[rt << 1][2];
            seg[rt][3] = 0;
        }
    }
    else
    {
        if (a[m] > a[m + 1])
        {
            seg[rt][0] = seg[rt << 1][0] + seg[rt << 1 | 1][0] + sum(seg[rt << 1][2]) + sum(seg[rt << 1 | 1][1]);
            seg[rt][1] = seg[rt << 1][1];
            seg[rt][2] = seg[rt << 1 | 1][2];
            seg[rt][3] = 0;
        }
        else
        {
            seg[rt][0] = seg[rt << 1][0] + seg[rt << 1 | 1][0] + sum(seg[rt << 1][2] + seg[rt << 1 | 1][1]);
            seg[rt][1] = seg[rt << 1][1];
            seg[rt][2] = seg[rt << 1 | 1][2];
            seg[rt][3] = 0;
        }
    }
}
void build(int rt, int l, int r)
{
    if (l == r)
    {
        seg[rt][3] = 1;
        return;
    }
    int m = (l + r) >> 1;
    build(rt << 1, l, m);
    build(rt << 1 | 1, m + 1, r);
    pushup(rt, l, r);
}
void update(int rt, int l, int r, int x, int y)
{
    if (l == r)
    {
        a[x] = y;
        return;
    }
    int m = (l + r) >> 1;
    if (x <= m)
        update(rt << 1, l, m, x, y);
    else
        update(rt << 1 | 1, m + 1, r, x, y);
    pushup(rt, l, r);
}
ll k, ans;
void query(int rt, int l, int r, int ql, int qr)
{
    if (r < ql || qr < l)
        return;
    if (ql <= l && r <= qr)
    {
        if (seg[rt][3])
        {
            if (a[l - 1] > a[l])
            {
                ans += sum(k);
                k = r - l + 1;
            }
            else
                k += r - l + 1;
        }
        else
        {
            if (a[l - 1] > a[l])
                ans += seg[rt][0] + sum(k) + sum(seg[rt][1]);
            else
                ans += seg[rt][0] + sum(k + seg[rt][1]);
            k = seg[rt][2];
        }
        return;
    }
    int m = (l + r) >> 1;
    query(rt << 1, l, m, ql, qr);
    query(rt << 1 | 1, m + 1, r, ql, qr);
}
int main()
{
    int n = read(), q = read();
    rep(i, 1, n) a[i] = read();
    build(1, 1, n);
    while (q--)
    {
        int opt = read(), l = read(), r = read();
        if (opt == 1)
            update(1, 1, n, l, r);
        else
        {
            ans = k = 0;
            query(1, 1, n, l, r);
            printf("%lld\n", ans + sum(k));
        }
    }
    return 0;
}