# # SnarkNews Summer Series 2020 Round 2 题解

## # Problem B - Sequence Analysis (opens new window)

### # 题解

#include <cstring>
#include <iostream>
#define MAXN 1005
#define MOD 998244353

using namespace std;
typedef long long ll;

int a[MAXN], b[MAXN], dp[MAXN][MAXN];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= m; ++i)
cin >> b[i];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
dp[i][j] =
((ll)dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + MOD) % MOD;
if (a[i] == b[j])
dp[i][j] = ((ll)dp[i][j] + dp[i - 1][j - 1] + 1) % MOD;
}
cout << dp[n][m];
}
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

## # Problem D - Meet Readers (opens new window)

### # 题目描述

$N$个作家，每个人可以在$[l_i,r_i)$的时间范围内参加会议，参会的不满度是$W_i$。问，要使得$[L,R)$的范围内都有人，并使得不满度的最大值最小的情况下，应该怎么安排（不要求作家的人数最少）。

### # 题解

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
struct Author {
ll l, r, w, idx;
bool operator<(const Author &other) const {
return l < other.l || (l == other.l && r > other.r);
}
};
int main() {
int n;
cin >> n;
vector<Author> a;
for (int i = 0; i < n; ++i) {
ll l, r, w;
cin >> l >> r >> w;
a.push_back(Author{l, r, w, i + 1});
}
sort(a.begin(), a.end());
ll L, R;
cin >> L >> R;
ll lo = 0, hi = 1e18;
while (lo <= hi) {
ll mid = lo + (hi - lo) / 2;
ll l = -1, r = -1;
bool ok = true;
for (int i = 0; i < n; ++i) {
if (a[i].w > mid)
continue;
if (r < a[i].l)
l = a[i].l;
r = max(r, a[i].r);
if (r >= R)
break;
}
if (l != -1 && l <= L && r >= R)
hi = mid - 1;
else
lo = mid + 1;
}
if (lo >= 1e18) {
cout << -1;
return 0;
}
vector<int> ans;
for (int i = 0; i < n; ++i)
if (a[i].w <= lo && a[i].l < R)
ans.emplace_back(a[i].idx);
cout << ans.size() << endl;
for (int i : ans)
cout << 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

## # Problem E - Distance in Line (opens new window)

### # 题目描述

$Q$个人按照LRUD的顺序排队，问相隔$N$位的两个人总共有多少次相邻。

### # 题解

#include <iostream>
#include <map>
#include <vector>

using namespace std;
int main() {
int q, n;
string s;
cin >> q >> s >> n;
vector<pair<int, int>> pos;
pos.emplace_back(0, 0);
int cx = 0, cy = 0;
map<char, int> dx = {{'L', -1}, {'R', 1}, {'U', 0}, {'D', 0}},
dy = {{'L', 0}, {'R', 0}, {'U', -1}, {'D', 1}};
for (char c : s) {
cx += dx[c], cy += dy[c];
pos.emplace_back(cx, cy);
}
int ans = 0;
for (int i = 0; i + n < q; ++i) {
if (abs(pos[i].first - pos[i + n].first) <= 1 &&
abs(pos[i].second - pos[i + n].second) <= 1)
ans++;
}
cout << ans;
}
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