Educational Codeforces Round#109

Educational Codeforces Round#109

C. Robot Collisions

Solution

可以發現相遇一定會在一個週期內(經過一次反彈),並且如果兩個原本相向而行的機器人不會相遇,反彈後也一定不會。同樣的,如果是同向的,如果某一個反彈後不能相遇,將永不可能相遇。

其實同向可以認為是到了“墻”的位置變為了相向,於是只需要仔細考慮相向問題。可以發現兩個機器人相遇的充要條件是距離是偶數,並且很顯然的,靠得越近就會越先發生相遇,此後一同被消滅。

所以簡單利用數學的一些技巧,利用優先隊列(堆)來實現。將點從左至右排序,每次加入一個點判斷前面最近的點與之匹配(用兩個堆,以別奇偶),記錄答案為 $(x_{now}-x_{last})/2$。對於一個未能和前面點匹配的點,如果向右,直接將 $x$ 加入優先隊列,否則將 $-x$ 加入。

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
#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

struct Node {
int x, d, idx;
bool operator<(const Node &u) {
return x < u.x;
}
};

const int MAX_N = 3e5 + 7;
int ans[MAX_N];
Node a[MAX_N];
bool vis[MAX_N];
priority_queue<pii> q[2];
int T, n, m;

int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
while (!q[0].empty()) q[0].pop();
while (!q[1].empty()) q[1].pop();
for (int i = 1; i <= n; ++i) scanf("%d", &a[i].x);
for (int i = 1; i <= n; ++i) ans[i] = -1, vis[i] = false;
string s;
for (int i = 1; i <= n; ++i) {
cin >> s;
if (s == "L") a[i].d = 0;
else a[i].d = 1;
a[i].idx = i;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n * 2; ++i) {
bool flag = true;
pii p;
int ni = i > n ? n * 2 - i + 1 : i;
int np = i > n ? m * 2 - a[n * 2 - i + 1].x : a[i].x;
int t = a[ni].x & 1;
if (vis[ni]) continue;
while (!q[t].empty() && (q[t].top().second == ni ||
vis[q[t].top().second])) q[t].pop();
if (!q[t].empty()) {
if ((i > n && a[ni].d) || (i <= n && !a[ni].d)) {
p = q[t].top(); q[t].pop();
ans[a[p.second].idx] = ans[a[ni].idx] = (np - p.first) / 2;
vis[p.second] = vis[ni] = true;
flag = false;
}
}
if (flag) {
if (a[ni].d) {
q[t].push(pii(a[ni].x, ni));
} else {
q[t].push(pii(-a[ni].x, ni));
}
}
}
for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
puts("");
}
return 0;
}

D. Armchairs

Solution

動態規劃,用 $f[i][j]$ 表示考慮了前 $i$ 個需要調換的座位,最後一個放在 $j$ 的最小代價。則有轉移:

$$ f[i][j]=\min\{f[i-1][k](k但是這樣是 $O(n^3)$ 的,利用單調棧維護即可:$O(n^2)$。

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
#include <bits/stdc++.h>
#define INF (1e9 + 7)
#define pii pair<int, int>

using namespace std;

const int MAX_N = 5e3 + 7;
int w[MAX_N], a[MAX_N], dp[MAX_N][MAX_N];
int n, tot;
stack<pii> stk;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", w + i);
if (w[i]) a[++tot] = i;
}
for (int i = 0; i <= tot; ++i) {
for (int j = 0; j <= n; ++j) {
dp[i][j] = INF;
}
}
dp[0][0] = 0;
stk.push(pii(0, 0));
for (int i = 1; i <= tot; ++i) {
for (int j = n; j >= 1; --j) {
while (!stk.empty() && stk.top().first >= j) stk.pop();
if (!w[j]) {
if (!stk.empty()) {
dp[i][j] = stk.top().second + abs(a[i] - j);
}
}
}
while (!stk.empty()) stk.pop();
for (int j = 1; j <= n; ++j) {
if (dp[i][j] < INF) {
if (stk.empty()) stk.push(pii(j, dp[i][j]));
else if (!stk.empty() && stk.top().second > dp[i][j]) {
stk.push(pii(j, dp[i][j]));
}
}
}
}
int ans = INF;
for (int i = 0; i <= n; ++i) ans = min(ans, dp[tot][i]);
printf("%d\n", ans);
return 0;
}

E. Assimilation IV

Solution

考慮每個 point 在幾個排列中有貢獻,最後累加除以 $n!$ 即可。

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MOD = 998244353;
const int MAX_N = 27;
const int MAX_M = 5e4 + 7;
int fac[MAX_N];
vector<int> e[MAX_M];
int n, m, ans;

int f_pow(int base, int b, int mod = MOD) {
int res = 1;
while (b) {
if (b & 1) res = base * res % mod;
base = base * base % mod;
b >>= 1;
}
return res;
}

signed main() {
scanf("%lld%lld", &n, &m);
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int a;
scanf("%lld", &a);
e[j].push_back(a);
}
fac[i] = fac[i - 1] * i % MOD;
}
for (int i = 1; i <= m; ++i) {
sort(e[i].begin(), e[i].end());
ans = (ans + fac[n]) % MOD;
int tmp = 1;
for (int j = 0; j < n; ++j) {
if (e[i][j] - 1 - j >= 0) {
tmp = tmp * (e[i][j] - 1 - j) % MOD;
} else {
tmp = 0;
}
}
ans = (ans - tmp) % MOD;
}
ans = (ans + MOD) % MOD;
printf("%lld\n", ans * f_pow(fac[n], MOD - 2) % MOD);
return 0;
}
#

評論

Your browser is out-of-date!

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

×