牛客训练赛58

发表于 | 阅读数

记一次“头铁“的比赛

D

题意

给你$n*m$的迷宫，$0$是可以走，$1$是不能走。

  • 如果当前格子右边没有障碍物，牛妹就向右走，否则转到2。
  • 如果当前格子下方没有障碍物，牛妹就向下走，否则转到3。
  • 如果当前格子左边没有障碍物，牛妹就向左走，否则转到4。
  • 如果当前格子上方没有障碍物，牛妹就向上走，否则转到5。

画个草图就知道牛妹只会向右和下走，其他走法都要返回原点，因为左上优先级低。

然后就是简单$dp$。

代码 
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9;
int dp[N][N], n, m;
char a[N][N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", a[i] + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = inf;
    dp[1][1] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            //cout << i << " " << j << " " << a[i + 1][j] << endl;
            if (j + 1 <= m && a[i][j + 1] == '0')
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
            if (i + 1 <= n && (j + 1 > m || a[i][j + 1] == '1') && a[i + 1][j] == '0')
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
            if (i + 1 <= n && (j + 1 <= m && a[i][j + 1] == '0') && a[i + 1][j] == '0')
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
        }
    //cout << dp[2][4] << endl;
    if (dp[n][m] == inf)
        printf("-1");
    else
        printf("%d", dp[n][m]);
}

E

题意

给一个序列$a$,$q$次询问$[l,r]$,区间内$max(x,a_i)$,

$a_i,x,n\leq10^5$

可以对于每个$x$,枚举他的因数$d$是否出现在这个区间。对于单个$d$,将它出现的位子保留下来。只需要判断二分找到$l\leq x_1$,$x_2\leq r$,是否存在$x2\geq x1$。

预处理所有的数的因数$n\log n$,询问为$q\log^2 n$

代码 
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int M = 4e2 + 10;
const int mod = 1e9 + 7;

vector<int> s[N];
vector<int> g[N];
int n, m;
int main()
{
    for (int j = 1; j < N; j++)
        for (int i = j; i < N; i += j)
            s[i].push_back(j);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        for (int j = 0; j < s[x].size(); j++)
            g[s[x][j]].push_back(i);
    }

    for (int i = 1; i <= m; i++)
    {
        int l, r, k;
        int ans = 0;
        scanf("%d%d%d", &l, &r, &k);
        for (int j = 0; j < s[k].size(); j++)
        {
            int d = s[k][j];

            int ll = lower_bound(g[d].begin(), g[d].end(), l) - g[d].begin();
            int rr = upper_bound(g[d].begin(), g[d].end(), r) - 1 - g[d].begin();
            //cout << d << " " << ll << " " << rr << endl;
            if (rr >= ll)
                ans = max(d, ans);
        }
        printf("%d\n", ans);
    }
}

F

题意

原题

维护两个线段树，一个维护链上奇数点，一个维护链上偶数点。
然后发现$deep$的奇偶就是确定了点的奇偶性。

  • $LCA\%2=1$,链上所有点之和
  • $LCA\%2=0$,链上所有偶数点 ，如果链头是偶数点，那么输出维护奇数的线段树，反之。
    代码 
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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 4e5 + 10;

int read()
{
    int x = 0;
    char c = getchar();
    while (c < '0' || c > '9')
        c = getchar();
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x;
}
struct node
{
    int to;
    int next;
} e[N];

struct tr
{
    int l, r, sum;
} tree[3][N * 4];

int head[N], d[N], si[N], son[N], father[N], id[N];
int a[N], w[N], top[N];
int cnt, n, m, root, num;

void push(int pos, int op)
{
    tree[op][pos].sum = (tree[op][pos * 2].sum ^ tree[op][pos * 2 + 1].sum);
}

void build(int pos, int l, int r, int op)
{
    tree[op][pos].l = l;
    tree[op][pos].r = r;
    if (l == r)
    {
        if (op == 2)
            tree[op][pos].sum = a[w[l]];
        if (op == 1)
            tree[op][pos].sum = (d[w[l]] % 2 == 1) ? a[w[l]] : 0;
        if (op == 0)
            tree[op][pos].sum = (d[w[l]] % 2 == 0) ? a[w[l]] : 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(pos * 2, l, mid, op);
    build(pos * 2 + 1, mid + 1, r, op);
    push(pos, op);
}
void add(int pos, int l, int r, int ad, int op)
{
    if (l <= tree[op][pos].l && tree[op][pos].r <= r)
    {
        if (op == 2)
            tree[op][pos].sum = ad;
        if (op == 1)
            tree[op][pos].sum = (d[w[l]] % 2 == 1) ? ad : 0;
        if (op == 0)
            tree[op][pos].sum = (d[w[l]] % 2 == 0) ? ad : 0;

        return;
    }

    int mid = (tree[op][pos].l + tree[op][pos].r) >> 1;
    if (l <= mid)
        add(pos * 2, l, r, ad, op);
    if (r > mid)
        add(pos * 2 + 1, l, r, ad, op);
    push(pos, op);
}
int find(int pos, int l, int r, int op)
{
    if (l <= tree[op][pos].l && tree[op][pos].r <= r)
    {
        return tree[op][pos].sum;
    }

    int mid = (tree[op][pos].l + tree[op][pos].r) >> 1;
    int ans = 0;
    if (l <= mid)
        ans ^= (find(pos * 2, l, r, op));
    if (r > mid)
        ans ^= (find(pos * 2 + 1, l, r, op));
    //push(pos);
    return ans;
}
void add(int x, int y)
{
    e[++cnt].to = y;
    e[cnt].next = head[x];
    head[x] = cnt;
}
void dfs1(int x, int f, int deep)
{
    d[x] = deep;
    father[x] = f;
    si[x] = 1;
    int maxson = -1;
    for (int i = head[x]; i != 0; i = e[i].next)
        if (e[i].to != f)
        {
            dfs1(e[i].to, x, deep + 1);
            si[x] += si[e[i].to];
            if (maxson < si[e[i].to])
            {
                maxson = si[e[i].to];
                son[x] = e[i].to;
            }
        }
}
void dfs2(int x, int topf)
{
    id[x] = ++num;
    w[num] = x;
    top[x] = topf;

    if (!son[x])
        return;
    dfs2(son[x], topf);
    for (int i = head[x]; i != 0; i = e[i].next)
        if (e[i].to != son[x] && e[i].to != father[x])
            dfs2(e[i].to, e[i].to);
}
int qrange(int u, int v, int op)
{
    //cout << op << endl;
    int ans = 0;
    while (top[u] != top[v])
    {
        if (d[top[u]] < d[top[v]])
            swap(u, v);
        ans ^= find(1, id[top[u]], id[u], op);
        u = father[top[u]];
    }
    if (d[u] > d[v])
        swap(u, v);
    ans ^= find(1, id[u], id[v], op);
    return ans;
}

void arange(int x, int ad)
{
    add(1, id[x], id[x], ad, 2);
    add(1, id[x], id[x], ad, d[x] % 2);
}
int f[N][20], dep[N];
void dfs3(int x, int fa)
{
    for (int i = 1; (1 << i) <= n; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for (int i = head[x]; i != 0; i = e[i].next)
    {
        int to = e[i].to;
        if (to == fa)
            continue;
        f[to][0] = x;
        dep[to] = dep[x] + 1;
        dfs3(to, x);
    }
}
int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (dep[f[x][i]] >= dep[y])
            x = f[x][i];
    if (x == y)
        return x;
    for (int i = 19; i >= 0; i--)
        if (f[x][i] != f[y][i])
        {
            x = f[x][i];
            y = f[y][i];
        }
    return f[x][0];
}
int findlca(int x, int y)
{
    int p = lca(x, y);
    //cout << p << endl;
    return dep[x] + dep[y] - 2 * dep[p];
}
int main()
{
    scanf("%d%d", &n, &m);
    root = 1;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    //cout << 1 << endl;
    dfs1(root, 0, 1);
    dfs2(root, root);
    build(1, 1, n, 0);
    build(1, 1, n, 2);
    build(1, 1, n, 1);
    dfs3(1, 0);
    //cout << tree[op][1].sum << endl;
    //cout << m << endl;
    //cout << tree[1][1].sum << endl;
    //cout << (a[5] ^ a[2] ^ a[3] ^ a[4]) << endl;
    for (int i = 1; i <= m; i++)
    {
        int p, x, y, z;
        //cout << 21 << endl;
        scanf("%d", &p);
        //cout << p << endl;
        if (p == 2)
        {
            x = read(), y = read();
            int ll = findlca(x, y);
            //cout << x << " " << y << " " << ll << endl;
            if (ll % 2 == 1)
            {
                printf("%d\n", qrange(x, y, 2));
            }
            else
            {
                printf("%d\n", qrange(x, y, (d[x] + 1) % 2));
            }
        }
        else if (p == 1)
        {
            x = read(), y = read();
            arange(x, y);
        }
    }
}

</details>