做的太糟糕了。。。第一题看成两人都取最优策略,写了个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;
} |
第五题:
官方题解给的是线段树。
我用树状数组离线搞的。