做的太糟糕了。。。第一题看成两人都取最优策略，写了个n^2的dp，还好pre-test良心，让我反复过不去，仔细看题原来是取两边最大的啊！！！前30分钟就这样度过了。。。题目的分数啊刷刷掉啊( ˙灬˙ )。用了8分钟搞完第二题，然后第三题。第五题在1：20左右的时候开始写一个树状数组，1：29的时候写完了，结果样例不过，仔细看看居然是树状数组修改时从1开始修改的，无语啊。于是就。。。。。。只做上了3道题，被虐的好惨啊。。。
第一题：模拟。。
第二题：水题
第三题：暴力到100000（l[i]的最大值）
|
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 |
/* * Problem: C. Sereja and Prefixes * Author: Shun Yao */#include <string.h>#include <stdlib.h>#include <limits.h>#include <assert.h>#include <stdio.h>#include <ctype.h>#include <math.h>#include <time.h>#include <map>#include <set>#include <list>#include <stack>#include <queue>#include <deque>#include <string>#include <vector>#include <bitset>#include <utility>#include <iomanip>#include <numeric>#include <sstream>#include <iostream>#include <algorithm>#include <functional>//using namespace std;int
m, n, a[100010], b[100010], c[100010], e[100010];long
long
d[100010];int
main(/*int argc, char **argv*/) { int
i, j, k; long
long
len; scanf("%d", &m); for
(i = 1; i <= m; ++i) { scanf("%d", &a[i]); if
(a[i] == 1) scanf("%d", &b[i]); else scanf("%d %d", &b[i], &c[i]); } scanf("%d", &n); for
(i = 1; i <= n; ++i) scanf("%I64d", &d[i]); j = 1; len = 0; for
(i = 1; i <= m; ++i) { if
(a[i] == 1) { ++len; if
(len <= 100000) e[len] = b[i]; while
(j <= n && d[j] == len) { ++j; printf("%d ", b[i]); } } else
{ if
(len < 100000) { for
(k = len + 1; k <= 100000 && k <= len + b[i] * c[i]; ++k) e[k] = e[(k - len) % b[i] == 0 ? b[i] : (k - len) % b[i]]; } while
(j <= n && d[j] <= len + b[i] * c[i]) { printf("%d ", e[(d[j] - len) % b[i] == 0 ? b[i] : (d[j] - len) % b[i]]); ++j; } len += b[i] * c[i]; } } fclose(stdin); fclose(stdout); return
0;} |
第四题：分层记录线段（即l,r,x),依次查询每层，记录出现过的颜色。（不用__builtin_clz会tle的。。）
|
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 |
/* * Problem: Sereja and Tree * Author: Shun Yao */#include <string.h>#include <stdlib.h>#include <limits.h>#include <assert.h>#include <stdio.h>#include <ctype.h>#include <math.h>#include <time.h>#include <map>#include <set>#include <list>#include <stack>#include <queue>#include <deque>#include <string>#include <vector>#include <bitset>#include <utility>#include <iomanip>#include <numeric>#include <sstream>#include <iostream>#include <algorithm>#include <functional>//using namespace std;int
n, m, z[7010];int
u;std::map<int, int> rn;class
Data {public: int
first, second, third; Data() {} Data(int
f, int
s, int
t) : first(f), second(s), third(t) {}} ;std::vector<Data> g[7010];int
main(/*int argc, char **argv*/) { int
i, t, l, r, x; // freopen("D.in", "r", stdin);// freopen("D.out", "w", stdout); scanf("%d%d", &n, &m); u = 0; for
(i = 1; i <= m; ++i) { scanf("%d", &t); if
(t == 1) { scanf("%d%d%d%d", &t, &l, &r, &x); g[t].push_back(Data(l, r, rn.count(x) ? rn[x] : rn[x] = u++)); } else
{ scanf("%d%d", &t, &l); for
(r = l; t <= n; ++t) { for
(x = 0; x < static_cast<int>(g[t].size()); ++x) if
(std::max(g[t][x].first, l) <= std::min(g[t][x].second, r)) z[g[t][x].third] = i; if
(l > 1) l += 32 - __builtin_clz(l - 1); r += 32 - __builtin_clz(r); } x = 0; for
(t = 0; t < u; ++t) x += z[t] == i; printf("%d\n", x); } } fclose(stdin); fclose(stdout); return
0;} |
第五题：
官方题解给的是线段树。
我用树状数组离线搞的。
原文：http://www.cnblogs.com/hsuppr/p/3517994.html