Metacamp 2022

补题地址 & 官方题解:Online A , Solution | Online B , Solution

复读机

\(n\) 个人,每个人有一个 \(a_i,b_i\) ,每次可以让 \(a_i\leftarrow a_{b_i}\) ,求最小操作次数使得所有数字都一样。

图是一个内向基环树森林,显然只有环内的颜色有可能成为最终颜色,因此求一下所有环上颜色的交。

假设最终的颜色是 \(w\) ,那么最终需要的操作次数就是 \(n-cnt_w\) ,每次把一条不是 \(w\) 的链依次染色即可。

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 1000007

int a[N], b[N], deg[N];

bool vis[N];

queue<int> q;

map<int, int> cnt, tmpcnt;

int tot;

void dfs(int u) {
vis[u] = 1;
if (tmpcnt[a[u]] != tot) {
if (tmpcnt[a[u]] < tot - 1) tmpcnt[a[u]] = 0;
else tmpcnt[a[u]] = tot;
}
if (!vis[b[u]]) dfs(b[u]);
}

inline void work() {
tot = 0;
int n = rd();
cnt.clear(); tmpcnt.clear();
for (int i = 1; i <= n; ++i) {
++cnt[a[i] = rd()]; deg[i] = 0; vis[i] = false;
}
for (int i = 1; i <= n; ++i) ++deg[b[i] = rd()];
for (int i = 1; i <= n; ++i)
if (!deg[i]) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
--deg[b[u]]; vis[u] = true;
if (!deg[b[u]]) q.push(b[u]);
}
for (int i = 1; i <= n; ++i)
if (!vis[i]) {++tot; dfs(i);}
int ans = 1e9;
for (int u = 1; u <= n; ++u)
if (tmpcnt[a[u]] == tot) {
ans = min(ans, n - cnt[a[u]]);
}
printf("%d\n", ans < 1e9 ? ans : -1);
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}

石头剪刀布

两个剪刀石头布的等长序列,每次可以把自己的序列的某个数移到最后,求赢的次数减操作次数的最大值。

性质是被移到后面的数字顺序任意,因此被移到后面的数字可以尽量匹配赢。

\(f[i][a][b][c]\) 表示前 \(i\) 个,把 \(a\) 个剪刀、\(b\) 个石头、\(c\) 个布移动到后面,剩余的最大赢次数。

最后对每个状态扫描的时候统计被操作的数字能赢多少即可,对每种记个后缀和即可。

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define per(i, x, y) for (int i = (x); i >= (y); --i)

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 107

char A[N], B[N];

int f[N][N][N][N], a[N], b[N];

inline int tr(char c) {
if (c == 'r') return 2;
if (c == 's') return 1;
return 0;
}

inline int win(int a, int b) {
if (a == 2 && b == 1) return 1;
if (a == 1 && b == 0) return 1;
if (a == 0 && b == 2) return 1;
return 0;
}

int suf[3][N];

int main() {
int n; scanf("%d", &n);
scanf("%s", A + 1);
scanf("%s", B + 1);
for (int i = 1; i <= n; ++i) {
a[i] = tr(A[i]); b[i] = tr(B[i]);
}
for (int i = n; i; --i) {
for (int j = 0; j < 3; ++j) suf[j][i] = suf[j][i + 1];
suf[b[i]][i]++;
}
memset(f, 0xcf, sizeof(f));
f[0][0][0][0] = 0;
for (int i = 1; i <= n; ++i)
for (int x = 0; x <= i; ++x)
for (int y = 0; y <= i - x; ++y)
for (int z = 0; z <= i - x - y; ++z) {
int p = i - x - y - z;
f[i][x][y][z] = max(f[i][x][y][z], f[i - 1][x][y][z] + win(a[i], b[p]));
if (a[i] == 0 && x) f[i][x][y][z] = max(f[i][x][y][z], f[i - 1][x - 1][y][z]);
if (a[i] == 1 && y) f[i][x][y][z] = max(f[i][x][y][z], f[i - 1][x][y - 1][z]);
if (a[i] == 2 && z) f[i][x][y][z] = max(f[i][x][y][z], f[i - 1][x][y][z - 1]);
}
int ans = 0;
for (int x = 0; x <= n; ++x)
for (int y = 0; y <= n - x; ++y)
for (int z = 0; z <= n - x - y; ++z) {
int tot = x + y + z;
int nw = f[n][x][y][z] + min(x, suf[2][n - tot + 1]) + min(y, suf[0][n - tot + 1]) + min(z, suf[1][n - tot + 1]);
ans = max(ans, nw - tot);
}
printf("%d\n", ans);
return 0;
}

KSharpe

给定一个 \(01\) 序列,求所有区间权值 =(均值 / 标准差)的第 \(k\) 大,特殊的如果标准差为 \(0\) 则权值也定义为 \(0\)

推一推发现权值的平方 = 区间 \(1\) 的个数 / 区间 \(0\) 的个数,二分权值的平方第 \(k\) 大为 \(w\) ,即统计多少个 \(l,r\) 满足:

\[ \frac{sum_r-sum_{l-1}}{(r - sum_r) - (l-1 - sum_{l-1})}\ge w \]\(f(x) =sum_x-w(x - sum_x)\) ,所求即 \(f(r)\ge f(l-1)\) ,离散化 + 树状数组统计顺序对即可。

特殊的全 \(1\) 区间会认为大于 \(w\) 恒成立,所以需要扣掉。提前数一下即可。

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define per(i, x, y) for (int i = (x); i >= (y); --i)

inline ll rd() {
ll x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 100007

ll k;

int n, sum[N];

ll c[N];

vector<pair<double, int> > s;

inline int lowbit(int x) {return x & -x;}

inline void add(int x) {
for (; x < N; x += lowbit(x)) ++c[x];
}

inline ll calc(int x) {
ll res = 0;
for (; x; x -= lowbit(x)) res += c[x];
return res;
}

ll cntint1 = 0;

int ha[N];

inline bool valid(double x) {
s.clear();
s.pb(mp(0, 0));
for (int i = 1; i <= n; ++i) s.pb(mp(sum[i] - x * (i - sum[i]), i));
sort(s.begin(), s.end());
int cnt = 0; ha[s[0].sc] = ++cnt;
for (int i = 1; i <= n; ++i) {
if (s[i].fr != s[i - 1].fr) ++cnt;
ha[s[i].sc] = cnt;
}
memset(c, 0, sizeof(c));
add(ha[0]);
ll tot = 0;
for (int i = 1; i <= n; ++i) {
tot += calc(ha[i]); add(ha[i]);
}
return tot - cntint1 >= k;
}

int main() {
n = rd(); k = rd();
int cnt1 = 0;
for (int i = 1; i <= n; ++i) {
int w = rd();
sum[i] = sum[i - 1] + w;
if (w == 1) ++cnt1;
else {cntint1 += 1ll * cnt1 * (cnt1 + 1) / 2; cnt1 = 0;}
}
cntint1 += 1ll * cnt1 * (cnt1 + 1) / 2;
double l = 0, r = n;
for (int i = 1; i <= 100; ++i) {
double mid = (r + l) / 2;
valid(mid) ? l = mid : r = mid;
}
printf("%.10lf\n", sqrt(l));
return 0;
}