bestcoder

本文从WordPress迁移而来, 查看全部WordPress迁移文章

比赛链接:bestcoder #79 div.1

题目链接:Claris and XOR

题意 & 题解:

有一种情况,两边都能取01的时候,一开始思考的结果是会影响最后的结果,然后不敢写了,然后向DP的方向思考。

不过再仔细想想,其实是不会影响最后结果的,并且当两边都同时能选01的时候,其实后面的位都可以全部确认了,直接构造完成

代码:

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

const int INF = 0x3f3f3f3f;

int valid[2];
LL a[2], b[2];
LL sa[2], sb[2];
LL value[2];

int work(int id, int bit) {
LL val = 1LL << bit;
if (a[id] & val) {
sa[id] += val;
}
if (b[id] & val) {
sb[id] += val;
}
int ans = 0;
LL v1 = value[id], v2 = value[id] + val;
if (sa[id] <= v1 && v1 <= sb[id]) {
ans = 0;
if (sa[id] <= v2 && v2 <= sb[id]) {
ans = 2;
}
} else {
//printf("???????????\n");
ans = 1;
}
//printf("id=%d, v1=%lld, v2=%lld, ans=%d, sa=%lld, sb=%lld\n", id, v1, v2, ans, sa[id], sb[id]);
return ans;
}

int main() {
int T;
scanf("%d", &T);
while (T--) {
cin >> a[0] >> b[0] >> a[1] >> b[1];
for (int i = 0; i < 2; i++) {
sa[i] = sb[i] = value[i] = 0LL;
}
LL ans = 0LL;
for (int bit = 62; bit >= 0; bit--) {
valid[0] = work(0, bit);
valid[1] = work(1, bit);
//printf("<bit: %d, %d, %d\n", bit, valid[0], valid[1]);
if (valid[0] == 0 || valid[0] == 1) {
if (valid[1] == 2) {
value[0] += valid[0] * (1LL << bit);
value[1] += (1 - valid[0]) * (1LL << bit);
} else {
value[0] += valid[0] * (1LL << bit);
value[1] += valid[1] * (1LL << bit);
}
} else {
//printf("###########################");
if (valid[1] == 0 || valid[1] == 1) {
value[1] += valid[1] * (1LL << bit);
value[0] += (1 - valid[1]) * (1LL << bit);
} else {
//printf(">>>>>>>>>>>>>>");
value[1] += (1LL << bit);
for (int j = bit - 1; j >= 0; j--) {
value[0] += (1LL << j);
}
break;
}
}
//printf("bit:%d, value[0]:%lld, value[1]:%lld\n", bit, value[0], value[1]);
}
//printf("value[0]:%lld, value[1]:%lld\n", value[0], value[1]);
ans = value[0] ^ value[1];
cout << ans << endl;
}
return 0;
}

题目链接:YJQQQAQ and the function

###题意 & 题解:
题意说了一大堆,其实就是把问题分成两个部分来处理就可以了

对于A数组,枚举K从1到n,把A[k], A[2k], A[3k] ….. A[n/k * k] 全部取出来放到B数组里面

枚举K,并且取出数字放到B的复杂度是 n/1+n/2+n/3+…..+n/n = n (1/1+1/2+1/3+1/4…..+1/n) ~= nlogn

每次B数组,复杂度可以在O(n),整个问题的复杂度就是 O(n*logn)

B数组怎么处理?

现在问题转化成了,给B数组,选一个区间,算区间和p,取出区间的最小q,计算pq;怎么选这个区间,使得pq最大
好熟悉的样子

如果反过来想,每次看B数组里面的一个元素B[i],假设它是最小值q,那就可以向左向右延伸,唯一确定一个区间并且算出区间和p,向左向右延伸的停止条件就是遇到了第一个比B[i]小的元素

好熟悉的样子,那不就是在一排长短木板中找出一个面积最大的矩形?单调栈啊。

在B数组的0下标填充一个0,还有B的最后也填充一个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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

const int INF = 0x3f3f3f3f;
const int MAXN = 300010;

LL a[MAXN], b[MAXN], sum[MAXN], n, m;
int stack[MAXN], top;

inline LL get(LL *s, int l, int r) {
return s[r] - s[l - 1];
}

LL cal(LL *arr, int length) {
LL ans = 0LL;

sum[0] = arr[0];
for (int i = 1; i <= length; i++) {
sum[i] = sum[i - 1] + arr[i];
}

stack[top = 0] = 0;
for (int i = 1; i <= length; i++) {
while (top >= 0) {
int id = stack[top];
if (arr[i] == arr[id]) {
top--;
} else if (arr[i] > arr[id]) {
break;
} else {
int L = stack[top - 1] + 1, R = i - 1;
LL result = get(sum, L, R) * arr[stack[top]];
ans = max(ans, result);
top--;
}
}
stack[++top] = i;
}
return ans;
}

int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}

LL ans = 0LL;
for (int k = 1; k <= n; k++) {
for (m = 1; m * k <= n; m++) {
b[m] = a[m * k];
}
b[0] = b[m] = 0LL;
LL result = cal(b, m);
ans = max(ans, result * (LL)floor(sqrt(k + 0.5)));
}
cout << ans << endl;
}
return 0;
}