2019.8.13 集训解题报告

为什么我觉得今天的题这么水,恐怕要被打脸 qwq,是不是我题读错了….


考试

rank

题意有点问题,我赌输出 $k$ 个答案是对的 qwq


JZOJ 我问候你家人,nmsl ! cnm!评测吃了我 50 分

$Test’s$ $Code$:100%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int MAXN = 5e6 + 5;
const int MAXM = 1e5 + 5;

int n, a[MAXN], k;
int main() {
scanf ("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf ("%d", &a[i]);
}

sort (a + 1, a + n + 1);

for (int i = 1; i <= k; i++) {
printf ("%d ", a[i]);
}
return 0;
}

seek

考试的时候用 $KMP$ 生成 next[i] 数组的方式,再加了一个检测,这样瞎搞了以后应该是 0 分吧 qwq


瞎搞搞了 20 分 qwq

好像暴力也有 40 分,早知道分段写了 qwq,说不定可以 60 分 > _ <


上面是闲话:$\Uparrow \Uparrow$

这道题有两种方法,第一种就是 $KMP$ ,但是用来做这种变形我不会 qwq,我到现在只会生成普通的 next[i] ….

第二种是直接生成前缀、后缀哈希,然后再枚举一遍,扫 3 遍就可以了 qwq

我就喜欢像第二种这种简单粗暴的方法……

$Test’s$ $Code$:20%

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
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 4e5 + 5;

char ch[MAXN], len, kmp[MAXN];

bool book[MAXN];

int main() {
scanf ("%s", ch);
len = strlen (ch);

int k=0;
for(int i = 1; i < len; i++){

if (k && ch[i] != ch[k]) {
bool flag = true;
for (int j = 0; j < k; j++) {
if (ch[j] != ch[len - k + j]) {
flag = false;
break;
}
}
if (flag) {
book[k] = true;
}
}

while(k && ch[i] != ch[k])
k = kmp[k];
if(ch[i] == ch[k]) {
kmp[i + 1] = ++k;
}
}

bool flag = true;
for (int j = 0; j < k; j++) {
if (ch[j] != ch[len - k + j]) {
flag = false;
break;
}
}
if (flag) {
book[k] = true;
}

//book[k] = true;
book[len] = true;

for (int i = 1; i <= len; i++) {
if (book[i]) {
printf ("%d ", i);
}
}
return 0;
}

$Fixed$ $Code$:100%(哈希)

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
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 4e5 + 5;

unsigned long long len, lhash[MAXN], rhash[MAXN];

char ch[MAXN];

int main() {
scanf ("%s", ch + 1);
len = strlen (ch + 1);

for (int i = 1; i <= len; i++) {
lhash[i] = (lhash[i - 1] * 17 + ch[i] - 'a' + 1);
}
unsigned long long t = 1;
for (int i = len; i >= 1; i--) {
rhash[i] = ((ch[i] - 'a' + 1) * t + rhash[i + 1]);
t = t * 17;
}

for (int i = 1; i <= len; i++) {
if (lhash[i] == rhash[len - i + 1]) {
printf ("%d ", i);
}
}
return 0;
}

这题有一些细节,就是进行哈希加密的时候,需要选质数,不然可能会有问题…….

这题不知道为什么我取模之后会出错,可能哈希就是不能取模吧……

可能因为我太菜了…..

pot

打了一个线段树,但是没有打完,最后因为答案要求不能全取,然后我就一直想怎么用 $O(\log n)$ 的方法搜出答案 qwq

这题用线段树维护 最大字段和 和 最小子段和 就可以了。因为不能取一整个环,所以最后答案在 $(1,n]$ 和 $[1,n)$ 这两个区间中取一个 $Max$ 就可以了。对于这个最长子段和,@lzc 是这么求的,直接引用了。。。(不会侵权吧。。。)

在线段树每个结点上维护这个区间的和、最大前缀和、最大后缀和、最大子段和。
那么合并儿子信息的时候,区间和很简单;最大前缀和有两种选择,一种是左儿子的区间和 + 右儿子的最大前缀和,一种是左儿子的最大前缀和;后缀和类似;最大子段和要么是左儿子的最大子段和,要么是右儿子的最大子段和,要么是左儿子的最大后缀和 + 右儿子的最大前缀和。

—— lzc

嗯,就酱紫吧?

$Test’s$ $Code$: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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int INF = 2e9;
int n, m, rt, a[MAXN << 1];

struct Tree {
#define lson (x << 1)
#define rson (x << 1) + 1
int size[MAXN << 2], Max[MAXN << 2], num[MAXN << 2], sum[MAXN << 2];

inline void pushup_normal (int x) {
size[x] = size[lson] + size[rson];
sum[x] = sum[lson] + sum[rson];
Max[x] = max (Max[lson], Max[rson]);
Max[x] = max (Max[x], sum[x]);
return;
}

inline void pushup_ans (int x) {
size[x] = size[lson] + size[rson];
Max[x] = max (Max[lson], Max[rson]);
return;
}

void insert (int x, int l, int r) {
if (l == r) {
size[x] = 1;
sum[x] = 1;
return;
}
int mid = (l + r) >> 1;
insert (lson, l, mid);
insert (rson, mid, r);
if (r - l + 1 > n) {
pushup_ans (x);
}

else {
pushup_normal (x);
}
return;
}

void Change (int x, int l, int r, int k, int val) {
if (l == r) {
Max[x] = val;
sum[x] = val;
return;
}

int mid = (l + r) >> 1;
if (mid < k) {
Change (rson, mid, r, k, val);
}
else {
Change (lson, l, mid, k, val);
}
pushup_normal (x);
return;
}

};
Tree T;

int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; i++) {
scanf ("%d", &a[i]);
a[n + i] = a[i];
}
T.insert (rt, 1, 2 * n);

scanf ("%d", &m);
for (int i = 1; i <= m; i++) {
int k, val;
scanf ("%d%d", &k, &val);
T.Change (rt, 1, 2 * n, k, val);
T.Change (rt, 1, 2 * n, n + k, val);
int MAX = -INF;
for (int i = 1; i <= n; i++) {
MAX = max (MAX, T.query (rt, 1, 2 * n, i, n + i - 2));
}
printf ("%d\n", MAX);
}
return 0;
}

$Fixed$ $Code$:

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e5 + 5;

struct Tree {
#define lson (x << 1)
#define rson (x << 1) + 1
int presum_Max[MAXN << 2], sufsum_Max[MAXN << 2], Max[MAXN << 2];
int presum_Min[MAXN << 2], sufsum_Min[MAXN << 2], Min[MAXN << 2];
int sum[MAXN << 2], Min_val[MAXN << 2], rt;

inline void pushup (int x) {
presum_Max[x] = max (presum_Max[lson], sum[lson] + presum_Max[rson]);
sufsum_Max[x] = max (sufsum_Max[rson], sufsum_Max[lson] + sum[rson]);
presum_Min[x] = min (presum_Min[lson], sum[lson] + presum_Min[rson]);
sufsum_Min[x] = min (sufsum_Min[rson], sufsum_Min[lson] + sum[rson]);
sum[x] = sum[lson] + sum[rson];
Max[x] = max (Max[lson], Max[rson]);
Max[x] = max (Max[x], sufsum_Max[lson] + presum_Max[rson]);
Min[x] = min (Min[lson], Min[rson]);
Min[x] = min (Min[x], sufsum_Min[lson] + presum_Min[rson]);
Min_val[x] = min (Min_val[lson], Min_val[rson]);
return;
}

void insert (int x, int l, int r) {
if (l == r) {
scanf ("%d", &sum[x]);
presum_Max[x] = sum[x];
sufsum_Max[x] = sum[x];
presum_Min[x] = sum[x];
sufsum_Min[x] = sum[x];
Max[x] = sum[x];
Min[x] = sum[x];
Min_val[x] = sum[x];
return;
}
int mid = (l + r) >> 1;
insert (lson, l, mid);
insert (rson, mid + 1, r);
pushup(x);
return;
}

void change (int x, int l, int r, int k, int val) {
if (l == r) {
sum[x] = val;
presum_Max[x] = val;
sufsum_Max[x] = val;
presum_Min[x] = val;
sufsum_Min[x] = val;
Max[x] = val;
Min[x] = val;
Min_val[x] = val;
return;
}
int mid = (l + r) >> 1;
if (k > mid) {
change (rson, mid + 1, r, k, val);
}
else {
change (lson, l, mid, k, val);
}
pushup(x);
return;
}
};
Tree T;

int n, m;
int main() {
scanf ("%d", &n);
T.rt = 1;
T.insert (T.rt, 1, n);

scanf ("%d", &m);
for (int i = 1; i <= m; i++) {
int k, val;
scanf ("%d%d", &k, &val);
T.change (T.rt, 1, n, k, val);
int temp;
if (T.sum[T.rt] != T.Max[T.rt]) {
temp = T.Max[T.rt];
}
else {
temp = T.sum[T.rt] - T.Min_val[T.rt];
}
printf ("%d\n", max (temp, T.sum[T.rt] - T.Min[T.rt]));
}
return 0;
}

这题改了很久,有一点,需要注意。因为不能取全部,所以如果最后有两种情况:

  • 最长子段和 $=$ 总和:答案有两种情况取 $Max$ :总和 $-$ 最小的单点值;总和 $-$ 最小子段和。
  • 最长子段和 $\not=$ 总和:答案有两种情况取 $Max$ :最长子段和;总和 $-$ 最小子段和(最长子段和的区间和最小子段和的区间可能在环的交界处)

游戏节目(show)

算了一下,$C_{34}^{17} \approx 5 \times 10^7$,如果剪枝可以的话,应该可以卡过 qwq(这是我考试后口胡的,不用管)

为什么只有 40 分鸭 qwq,成功翻车……


这道题远没有我考试时想的那么简单….

好像说要用什么树套树,折半搜索……信息量有点大,以后再订这道题…..

$Test’s$ $Code$:40%

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 40;
const int MAXK = 7;

long long n, k, ans, a[MAXN], b[MAXN], c[MAXN];
long long A, B, C;

void dfs (int now, int K, int last, int cnt) {
if (now >= cnt) {
if (A > B && A > C) {
ans ++;
}
return;
}

for (int i = last + 1; i <= n - K + 1; i++) {
A += a[i];
B += b[i];
C += c[i];
dfs (now + 1, K - 1, i, cnt);
A -= a[i];
B -= b[i];
C -= c[i];
}
return;
}
int main () {
freopen ("show.in", "r", stdin);
freopen ("show.out", "w", stdout);

scanf ("%lld%lld", &n, &k);
for (int i = 1; i <= n; i++) {
scanf ("%lld", &a[i]);
}
for (int i = 1; i <= n; i++) {
scanf ("%lld", &b[i]);
}
for (int i = 1; i <= n; i++) {
scanf ("%lld", &c[i]);
}

for (int i = k; i <= n; i++) {
dfs (0, i, 0, i);
}

printf ("%lld\n", ans);
fclose (stdin);
fclose (stdout);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×