CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
队伍人不齐打这场真心累啊…
BE, GE or NE
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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000 + 10;
int f[maxn][210];
int a[maxn], b[maxn], c[maxn];
int n, m, k, l;
int main()
{
scanf("%d%d%d%d", &n, &m, &k, &l);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &a[i], &b[i], &c[i]);
for (int i = 0; i <= l + 100; i++)
f[n + 1][i] = -1;
for (int i = l + 101; i < k + 100; i++)
f[n + 1][i] = 0;
for (int i = k + 100; i <= 200; i++)
f[n + 1][i] = 1;
for (int i = n; i >= 1; i--)
{
// for (int w=90;w<110;w++) printf("%d",f[i+1][w]);
// printf("\n");
for (int j = 0; j <= 200; j++)
{
int x = -1, y = -1, z = -1;
if (a[i])
{
x = j + a[i];
if (x > 200)
x = 200;
}
if (b[i])
{
y = j - b[i];
if (y < 0)
y = 0;
}
if (c[i])
z = 200 - j;
if (i & 1)
{
if ((x >= 0) && (f[i + 1][x] == 1))
{
f[i][j] = 1;
continue;
}
if ((y >= 0) && (f[i + 1][y] == 1))
{
f[i][j] = 1;
continue;
}
if ((z >= 0) && (f[i + 1][z] == 1))
{
f[i][j] = 1;
continue;
}
if (((x < 0) || ((x >= 0) && (f[i + 1][x] == -1))) && ((y < 0) || ((y >= 0) && (f[i + 1][y] == -1))) && ((z < 0) || ((z >= 0) && (f[i + 1][z] == -1))))
{
f[i][j] = -1;
continue;
}
f[i][j] = 0;
}
else
{
if ((x >= 0) && (f[i + 1][x] == -1))
{
f[i][j] = -1;
continue;
}
if ((y >= 0) && (f[i + 1][y] == -1))
{
f[i][j] = -1;
continue;
}
if ((z >= 0) && (f[i + 1][z] == -1))
{
f[i][j] = -1;
continue;
}
if (((x < 0) || ((x >= 0) && (f[i + 1][x] == 1))) && ((y < 0) || ((y >= 0) && (f[i + 1][y] == 1))) && ((z < 0) || ((z >= 0) && (f[i + 1][z] == 1))))
{
f[i][j] = 1;
continue;
}
f[i][j] = 0;
}
}
}
if (f[1][m + 100] == 1)
printf("Good Ending");
else if (f[1][m + 100] == 0)
printf("Normal Ending");
else
printf("Bad Ending");
}
Features Track
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
#include <cstdio>
#include <unordered_map>
using namespace std;
int t, n;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d", &n);
unordered_map<int, unordered_map<int, pair<int, int>>> mp;
int ans = 0;
for (int i = 1, k, x, y; i <= n; ++i)
for (scanf("%d", &k); k--;)
{
scanf("%d%d", &x, &y);
pair<int, int> &p = mp[x][y];
if (p.first == i)
continue; //坑
if (p.first != i - 1)
p.second = 0;
p.first = i, ans = max(ans, ++p.second);
}
if (ans == 1)
ans = 0; //坑
printf("%d\n", ans);
}
}
Trace
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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200000 + 10;
struct node
{
int l, r, mx;
} t[maxn * 4];
int n;
long long ans;
int x[maxn], y[maxn], tmp1[maxn], tmp2[maxn];
void build(int cur, int l, int r)
{
t[cur].l = l;
t[cur].r = r;
t[cur].mx = 0;
if (l == r)
return;
int mid = (l + r) / 2;
build(cur * 2, l, mid);
build(cur * 2 + 1, mid + 1, r);
}
void update(int cur, int l, int r, int v)
{
if ((t[cur].l == l) && (t[cur].r == r))
{
t[cur].mx = max(t[cur].mx, v);
return;
}
t[cur * 2].mx = max(t[cur * 2].mx, t[cur].mx);
t[cur * 2 + 1].mx = max(t[cur * 2 + 1].mx, t[cur].mx);
t[cur].mx = 0;
int mid = (t[cur].l + t[cur].r) / 2;
if (r <= mid)
update(cur * 2, l, r, v);
else if (l > mid)
update(cur * 2 + 1, l, r, v);
else
update(cur * 2, l, mid, v), update(cur * 2 + 1, mid + 1, r, v);
}
int query(int cur, int pos)
{
if (t[cur].l == t[cur].r)
return t[cur].mx;
t[cur * 2].mx = max(t[cur * 2].mx, t[cur].mx);
t[cur * 2 + 1].mx = max(t[cur * 2 + 1].mx, t[cur].mx);
t[cur].mx = 0;
int mid = (t[cur].l + t[cur].r) / 2;
if (pos <= mid)
return query(cur * 2, pos);
else
return query(cur * 2 + 1, pos);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &x[i], &y[i]);
for (int i = 1; i <= n; i++)
tmp1[i] = x[i];
sort(tmp1 + 1, tmp1 + n + 1);
for (int i = 1; i <= n; i++)
x[i] = lower_bound(tmp1 + 1, tmp1 + n + 1, x[i]) - tmp1;
for (int i = 1; i <= n; i++)
tmp2[i] = y[i];
sort(tmp2 + 1, tmp2 + n + 1);
for (int i = 1; i <= n; i++)
y[i] = lower_bound(tmp2 + 1, tmp2 + n + 1, y[i]) - tmp2;
ans = 0;
build(1, 1, n);
for (int i = n; i >= 1; i--)
{
int k = query(1, y[i]);
ans += tmp1[x[i]] - tmp1[k];
update(1, 1, y[i], x[i]);
}
build(1, 1, n);
for (int i = n; i >= 1; i--)
{
int k = query(1, x[i]);
ans += tmp2[y[i]] - tmp2[k];
update(1, 1, x[i], y[i]);
}
printf("%lld", ans);
return 0;
}
Ryuji doesn’t want to study
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
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct SegmentTree
{
struct Node
{
ll set, sum, ans;
};
vector<Node> v;
int LAST, L, R;
SegmentTree(int n) : LAST(n), v(2 * n + 1) {}
void build(ll a[], int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
build(a, l, m), build(a, m + 1, r);
lv(l, r).set = INF;
}
else
lv(l, r).set = a[l];
maintain(l, r);
}
Node &lv(int l, int r)
{
return v[l + r | l != r];
}
void push_down(Node &lc, Node &rc, Node &fa)
{
if (fa.set != INF)
lc.set = rc.set = fa.set, fa.set = INF;
}
void push_up(const Node &lc, const Node &rc, Node &fa, int l, int r, int m)
{
fa.sum = lc.sum + rc.sum;
fa.ans = lc.ans + rc.ans + lc.sum * (r - m);
}
void maintain(int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
push_up(lv(l, m), lv(m + 1, r), lv(l, r), l, r, m);
}
if (lv(l, r).set != INF)
{
int len = r - l + 1;
lv(l, r).sum = len * lv(l, r).set;
lv(l, r).ans = (1LL + len) * len / 2 * lv(l, r).set;
}
}
Node ask(int l, int r, ll val = 0, bool out = 1)
{
if (out)
return L = l, R = r, ask(1, LAST, val, 0);
if (lv(l, r).set != INF)
{
int len = min(R, r) - max(l, L) + 1;
v[0].sum = len * lv(l, r).set;
v[0].ans = (1LL + len) * len / 2 * lv(l, r).set;
}
else if (L <= l && r <= R)
v[0] = lv(l, r);
else
{
int m = l + (r - l) / 2;
if (R <= m)
return ask(l, m, val, 0);
if (L > m)
return ask(m + 1, r, val, 0);
push_up(ask(l, m, val, 0), ask(m + 1, r, val, 0), v[0], max(L, l), min(R, r), m);
}
return v[0];
}
void set(int l, int r, ll val, bool out = 1)
{
if (out)
return L = l, R = r, set(1, LAST, val, 0);
if (L <= l && r <= R)
lv(l, r).set = val;
else
{
int m = l + (r - l) / 2;
push_down(lv(l, m), lv(m + 1, r), lv(l, r));
if (L <= m)
set(l, m, val, 0);
else
maintain(l, m);
if (R > m)
set(m + 1, r, val, 0);
else
maintain(m + 1, r);
}
maintain(l, r);
}
};
ll n, q, a[100009];
int main()
{
scanf("%lld%lld", &n, &q);
for (ll i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
SegmentTree tree(n);
tree.build(a, 1, n);
for (ll i = 0, a, b, c; i < q; ++i)
{
scanf("%lld%lld%lld", &a, &b, &c);
if (a == 1)
printf("%lld\n", tree.ask(b, c).ans);
if (a == 2)
tree.set(b, b, c);
}
}
Characters with Hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
using namespace std;
char s[1000009], z[9];
int t, n, ans;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%s%s", &n, z, s);
for (int i = ans = 0, tmp, flag = 0; i < n; ++i)
{
if (tmp = (int)z[0] - (int)s[i], tmp < 0)
tmp = -tmp;
if (flag)
ans += 2;
else if (tmp)
for (flag = 1; tmp; tmp /= 10)
++ans;
}
if (ans == 0)
ans = 1; //坑
printf("%d\n", ans);
}
}