http://codeforces.com/contest/1321

B. Journey Planning

 

题意:给定一个数组,要求找到一个子序列,满足每个元素的值的差等于坐标的差,要求序列总和最大。

对于每个满足条件的序列,它们的第一个元素的下标一定确定了,所以用map维护类似并查集一样,最后找map里的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e4+ 10;
const int INF = 0x3f3f3f3f;
map<int, ll>mp;
int n;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
mp[x - i] += x;
}
ll ans = 0;
for (auto p : mp) {
ans = max(ans, p.second);
}
cout << ans << endl;
return 0;
}

 

C. Remove Adjacent

 

题意:给定一个仅含小写字母的字符串,仅当某个位置的相邻两个位置中存在比这个位置的字母字典序小1的字母时,这个位置可以删除,删除后两边靠拢,填补空缺。

字典序最大的字母一定无法再删除其它字母,也就是说它们留着也没用了,那么思路就是按照字典序倒序枚举每个字母,尽量把这个字母删干净,就是个贪心模拟的过程。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e4+ 10;
const int INF = 0x3f3f3f3f;
int n;
vector<char>vc;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
char c;
scanf(" %c", &c);
vc.push_back(c);
}
int ans = 0;
int n = (int)vc.size();
for (int i = 25; i > 0; i--) {
char c = 'a' + i, pre = 'a' + i - 1;
for (int j = 0; j < n; j++) {
if (vc[j] == pre) {
while (j > 0 && vc[j - 1] == c) {
vc.erase(vc.begin() + j - 1);
ans++;
j--, n--;
}
while (j < n - 1 && vc[j + 1] == c) {
vc.erase(vc.begin() + j + 1);
ans++;
n--;
}
}
}
}
cout << ans << endl;
return 0;
}

 

D. Navigation System

 

题意:有向图,已知从起点到终点的一条路径,沿着这条路径走,导航会不断规划最短的路径,(就和实际的导航类似,只不过只考虑距离最优),问沿着给定的路径走最多/最少重新规划几次。

首先要搞清楚什么时候会重新规划。

graph 8.png

如上图,当序列为 1-2-3-4-5 时,走 1-2-3 的过程中不会重新规划路线,因为每一步都是从当前点到终点的最优解,但是在 3-4 时,由于不是3到5的最优解,所以会重新规划,而在 4-5 又是4到5的最优解,所以也不会重新规划。

所以判断是否规划并不是看点到终点的距离是否是序列里的距离,而是看走的每一条边是否是出点到终点的最优解。

最优解也就是梯度方向,按照距离每次-1走。

在有多个最优解的情况下,最大值要+1.

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+ 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
int n, m, k;
vector<int>G[N], gg[N];
int p[N];
int d[N], cnt[N];
priority_queue<pii,vector<pii>,greater<pii> >que;
void bfs(int s) {
memset(d, 0x3f, sizeof(d));
d[s] = 0;
que.push(pii(0, s));
while (!que.empty()) {
int u = que.top().second, dis = que.top().first; que.pop();
if (dis > d[u])continue;
for (int v : G[u]) {
if (d[v] > d[u] + 1) {
d[v] = d[u] + 1;
que.push(pii(d[v], v));
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[v].push_back(u);
gg[u].push_back(v);
}
cin >> k;
for (int i = 1; i <= k; i++)scanf("%d", &p[i]);
bfs(p[k]);
for (int i = 1; i <= n; i++) {
for (int v : gg[i]) {
if (d[i] == d[v] + 1)cnt[i]++;
}
}
int mx = 0, mn = 0;
for (int i = 1; i < k; i++) {
int u = p[i];
if (d[u] != d[p[i + 1]] + 1)mn++, mx++;
else if (cnt[u] > 1)mx++;
}
cout << mn << ' ' << mx << endl;
return 0;
}

 

E. World of Darkraft: Battle for Azathoth

 

题意:有n给武器,m个护盾,每个都有价格,武器有攻击力,护盾有防御力,有p个怪物,仅当攻防都大于怪物时,可以打败它,并得到它的奖励。必须且只能选一把武器和一个护盾,求最大净收益。

线段树

就是一个二维偏序问题,把怪物按照第一维排序,处理第二维。

但是要注意并不是每次都贪心地选最靠近怪物的武器和护盾。

如以下样例:

武器:(9,7);护盾:(4,1),(10,5);怪物:(2,7,12),(2,7,1),(4,2,3)

当遍历到最后一个怪物时,只要用 (4,1) 的护盾就够了,但是用 (10,5) 的收益更大。

但是每次都选用最靠近的武器是可以的,因为遍历了怪物,所以所有情况都能达到。

所以线段树维护每个防御值的收益。当然,维护护盾也是一样的,就是离散化了一下。但是本题数据这么小显然是直接维护防御就好了。

之后每次在怪物的防御力和后区间加上奖励,再查询防御大于怪物的收益最大值。

我这里还处理了一下,保证防御小的价格小,也并不需要,直接遍历就好了,就当单调栈练手了。

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
98
99
100
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int n, m, p;
typedef pair<int, int> pii;
pii ta[N], tb[N], a[N], b[N];
int ra[N], rb[N], sb[N];
bool cmp(const pii& a, const pii& b) {
return a.first == b.first ? a.second > b.second:a.first < b.first;
}
struct X
{
int x, y, z;
bool operator<(const X& b)const {
return x < b.x;
}
}mon[N];
int S[N], top;
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int tr[N << 2], laz[N << 2];
void build(int l, int r, int rt) {
if (l == r) {
tr[rt] = -sb[l];
return;
}
build(lson);
build(rson);
tr[rt] = max(tr[rt << 1], tr[rt << 1 | 1]);
}
void down(int rt) {
int& x = laz[rt];
if (x) {
tr[rt << 1] += x;
tr[rt << 1 | 1] += x;
laz[rt << 1] += x;
laz[rt << 1 | 1] += x;
x = 0;
}
}
void add(int l, int r, int rt, int ql, int qr, int x) {
if (ql <= l && qr >= r) {
laz[rt] += x;
tr[rt] += x;
return;
}
down(rt);
if (ql <= mid)add(lson, ql, qr, x);
if (qr > mid)add(rson, ql, qr, x);
tr[rt] = max(tr[rt << 1], tr[rt << 1 | 1]);
}
int query(int l, int r, int rt, int ql, int qr) {
if (ql <= l && qr >= r)return tr[rt];
int ans = -INF;
down(rt);
if (ql <= mid)ans = max(ans, query(lson, ql, qr));
if (qr > mid)ans = max(ans, query(rson, ql, qr));
return ans;
}
int main() {
scanf("%d%d%d", &n, &m, &p);
for (int i = 1; i <= n; i++)
scanf("%d%d", &ta[i].first, &ta[i].second);
for (int i = 1; i <= m; i++)
scanf("%d%d", &tb[i].first, &tb[i].second);
for (int i = 1; i <= p; i++)
scanf("%d%d%d", &mon[i].x, &mon[i].y, &mon[i].z);
sort(ta + 1, ta + n + 1, cmp);
sort(tb + 1, tb + m + 1, cmp);
for (int i = 1; i <= n; i++) {
while (top&&ta[S[top - 1]].second >= ta[i].second)top--;
S[top++] = i;
}
n = top;
while (top)a[top] = ta[S[top - 1]], top--;
for (int i = 1; i <= n; i++)ra[i] = a[i].first;
for (int i = 1; i <= m; i++) {
while (top&&tb[S[top - 1]].second >= tb[i].second)top--;
S[top++] = i;
}
m = top;
while (top)b[top] = tb[S[top - 1]], top--;
memset(sb, 0x3f, sizeof(sb));
for (int i = 1; i <= m; i++)rb[i] = b[i].first, sb[b[i].first] = b[i].second;
for (int i = N - 2; i > 0; i--)sb[i] = min(sb[i], sb[i + 1]);
build(1, N - 1, 1);
int ans = -a[1].second - b[1].second;
sort(mon + 1, mon + p + 1);
for (int i = 1; i <= p; i++) {
add(1, N - 1, 1, mon[i].y + 1, N - 1, mon[i].z);
int p1 = upper_bound(ra + 1, ra + n + 1, mon[i].x) - ra;
int p2 = upper_bound(rb + 1, rb + m + 1, mon[i].y) - rb;
if (p1 == n + 1 || p2 == m + 1)continue;
ans = max(ans, -a[p1].second + query(1, N - 1, 1, rb[p2], N - 1));
}
printf("%d\n", ans);
return 0;
}