ICPC 2018 ASIA YOKOHAMA REGIONAL
看看这里： 😃 别人的好题解
B. Arithmetic Progressions
题意：从给定的集合中选出最多的数构成等差数列。
题解：数字排序后，设
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 表示等差数列最后一个数字为
a
[
i
]
a[i]
a[i],倒数第二个数字为
a
[
j
]
a[j]
a[j] 的最大个数。然后对于每一位枚举 i，
l
o
w
e
r
_
b
o
u
n
d
(
)
lower\_bound()
lower_bound() 找有无合法的 j 即可。复杂度
O
(
n
2
l
o
g
(
n
)
)
O(n^2log(n))
O(n2log(n))。
#include<cstdio>
#include<algorithm>
using namespace std
;
const int maxn
= 5010;
int N
, a
[maxn
], dp
[maxn
][maxn
];
int main() {
scanf("%d", &N
);
for (int i
= 0; i
< N
; i
++) {
scanf("%d", &a
[i
]);
}
sort(a
, a
+ N
);
int ans
= 0;
for (int i
= 0; i
< N
; i
++) {
for (int j
= 0; j
< i
; j
++) {
int idx
= lower_bound(a
, a
+ N
, a
[j
] - (a
[i
] - a
[j
])) - a
;
if (a
[i
] - a
[j
] == a
[j
] - a
[idx
]) {
dp
[i
][j
] = max(dp
[i
][j
], dp
[j
][idx
] + 1);
}
ans
= max(ans
, dp
[i
][j
]);
}
}
printf("%d\n", ans
+ 2);
return 0;
}
D. Shortest Common Non-Subsequence
题意：给出两个01串
s
s
s 和
t
t
t，求最短的 01 序列，不是 s 和 t 的子序列。多组答案输出字典序最小的。这个题的思路是：预处理出s和t每个位置上后面第一个1和第一个0的位置。设当前在s和t的位置分别为
(
x
,
y
)
(x,y)
(x,y)，则可以由
(
n
e
x
t
s
[
x
]
[
1
]
,
n
e
x
t
t
[
y
]
[
1
]
)
(next_s[x][1],next_t[y][1])
(nexts[x][1],nextt[y][1]) 和
(
n
e
x
t
s
[
x
]
[
0
]
,
n
e
x
t
t
[
y
]
[
0
]
)
(next_s[x][0],next_t[y][0])
(nexts[x][0],nextt[y][0]) 转移到，分别代表当前位放1和0。则答案就是从
(
0
,
0
)
(0,0)
(0,0) 到
(
l
e
n
s
+
1
,
l
e
n
t
+
1
)
(len_s+1,len_t+1)
(lens+1,lent+1) 的字典序最小的最短路。其实 next 数组建了一个拓扑图，然后从 (0, 0) 到
(
l
e
n
s
,
l
e
n
t
)
(len_s, len_t)
(lens,lent) 跑一个最短路。答案长度就是最短路的长度 + 1。然后在这些最短路中选一个字典序最小的。代码中还有一些注释。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std
;
const int maxn
= 4010;
char s
[maxn
], t
[maxn
];
int nexts
[maxn
][2], nextt
[maxn
][2], fa
[maxn
][maxn
], dp
[maxn
][maxn
];
int lens
, lent
;
vector
<int> ans
;
int dfs(int x
, int y
) {
if (x
== lens
+ 1 && y
== lent
+ 1) return 0;
if (dp
[x
][y
]) return dp
[x
][y
];
int res1
= dfs(nexts
[x
][0], nextt
[y
][0]);
int res2
= dfs(nexts
[x
][1], nextt
[y
][1]);
if (res1
> res2
) fa
[x
][y
] = 1;
return dp
[x
][y
] = min(res1
, res2
) + 1;
}
void find_path(int x
, int y
){
if (x
== lens
+ 1 && y
== lent
+ 1) return;
int res
= fa
[x
][y
];
ans
.push_back(res
);
find_path(nexts
[x
][res
], nextt
[y
][res
]);
}
int main() {
scanf("%s%s", s
+ 1, t
+ 1);
lens
= strlen(s
+ 1), lent
= strlen(t
+ 1);
nexts
[lens
+ 1][1] = nexts
[lens
+ 1][0] = lens
+ 1;
nextt
[lent
+ 1][1] = nextt
[lent
+ 1][0] = lent
+ 1;
for (int i
= lens
; i
>= 0; i
--) {
if (s
[i
+ 1] == '1') nexts
[i
][1] = i
+ 1, nexts
[i
][0] = nexts
[i
+ 1][0];
else nexts
[i
][1] = nexts
[i
+ 1][1], nexts
[i
][0] = i
+ 1;
}
for (int i
= lent
; i
>= 0; i
--) {
if (t
[i
+ 1] == '1') nextt
[i
][1] = i
+ 1, nextt
[i
][0] = nextt
[i
+ 1][0];
else nextt
[i
][1] = nextt
[i
+ 1][1], nextt
[i
][0] = i
+ 1;
}
dfs(0, 0);
find_path(0, 0);
for (auto p
: ans
) printf("%d", p
);
printf("\n");
return 0;
}
G. What Goes Up Must Come Down
这道题的思路就是，对于每一个数，找到原序列中，在它前面有多少个比它大的数（记为 x），在它后面有多少个比它大的数（记为 y），则答案就是所有 min(x, y) 之和。
求x和y的值，可以用归并排序，也可以用树状数组。
归并排序：
#include<cstdio>
#include<algorithm>
using namespace std
;
const int maxn
= 100010;
typedef pair
<int, int> P
;
typedef long long ll
;
P a
[maxn
], tmp
[maxn
];
int res
[maxn
], sorted
[maxn
], N
;
void merge_sort(P a
[], int l
, int r
) {
if (l
>= r
) return;
int mid
= (l
+ r
) / 2;
merge_sort(a
, l
, mid
);
merge_sort(a
, mid
+ 1, r
);
int k
= 0, i
= l
, j
= mid
+ 1;
while (i
<= mid
&& j
<= r
) {
if (a
[i
].first
<= a
[j
].first
) tmp
[k
++] = a
[i
++];
else res
[a
[j
].second
] += mid
- i
+ 1, tmp
[k
++] = a
[j
++];
}
while (i
<= mid
) tmp
[k
++] = a
[i
++];
while (j
<= r
) tmp
[k
++] = a
[j
++];
for (int i
= l
, j
= 0; i
<= r
; i
++, j
++) a
[i
] = tmp
[j
];
}
int binary_search(int x
) {
int l
= 0, r
= N
- 1;
while (r
- l
> 1) {
int mid
= (l
+ r
) / 2;
if (x
>= a
[mid
].first
) l
= mid
;
else r
= mid
;
}
return l
;
}
int main() {
scanf("%d", &N
);
for (int i
= 0; i
< N
; i
++) {
scanf("%d", &a
[i
].first
);
a
[i
].second
= i
;
}
merge_sort(a
, 0, N
- 1);
ll ans
= 0;
for (int i
= 0; i
< N
; i
++) {
ans
+= min(N
- binary_search(a
[i
].first
) - 1 - res
[a
[i
].second
], res
[a
[i
].second
]);
}
printf("%lld\n", ans
);
return 0;
}
树状数组：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std
;
const int maxn
= 100010, MAX_A
= 100000;
typedef long long ll
;
int a
[maxn
], tri
[maxn
], N
, gre_pre
[maxn
], gre_la
[maxn
];
int lowbit(int x
) {
return x
& -x
;
}
void add(int id
, int c
) {
for (int i
= id
; i
<= MAX_A
; i
+= lowbit(i
)) tri
[i
] += c
;
}
int sum(int id
) {
int res
= 0;
for (int i
= id
; i
; i
-= lowbit(i
)) res
+= tri
[i
];
return res
;
}
int main() {
scanf("%d", &N
);
for (int i
= 1; i
<= N
; i
++) scanf("%d", &a
[i
]);
for (int i
= 1; i
<= N
; i
++) {
gre_pre
[i
] = sum(MAX_A
) - sum(a
[i
]);
add(a
[i
], 1);
}
memset(tri
, 0, sizeof tri
);
for (int i
= N
; i
>= 1; i
--) {
gre_la
[i
] = sum(MAX_A
) - sum(a
[i
]);
add(a
[i
], 1);
}
ll ans
= 0;
for (int i
= 1; i
<= N
; i
++) {
ans
+= min(gre_pre
[i
], gre_la
[i
]);
}
printf("%lld\n", ans
);
return 0;
}
