Codeforces Round #522 (Div. 2) (A-E)

发表于 | 更新于 | 分类于 | 阅读次数：

分类讨论场么..

地址

A. Kitchen Utensils

水签到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int n, k, a[105];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        a[x]++;
    }
    int num = 0;
    for (int i = 1; i <= 100; i++) num = max(num, ((a[i]-1)/k+1)*k);
    int ans = 0;
    for (int i = 1; i <= 100; i++)
        if (a[i]) ans += num-a[i];
    cout << ans << endl;
}

B. Personalized Cup

先算出行数列数，再竖着填’*'，横着填字符呗。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
char s[N], ans[N][N];
int main() {
    scanf("%s", s);
    int n = strlen(s);
    int r = (n-1)/20+1;
    int c = (n-1)/r+1;
    int m = r*c;
    for (int i = 0; i < c; i++) {
        if (m == n) break;
        for (int j = 0; i < r; j++) {
            if (m == n) break;
            ans[j][i] = '*';
            m--;
        }
    }
    int x = 0;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++) {
            if (ans[i][j] == '*') continue;
            ans[i][j] = s[x++];
        }
    for (int i = 0; i < r; i++) ans[i][c] = '\0';
    printf("%d %d\n", r, c);
    for (int i = 0; i < r; i++) printf("%s\n", ans[i]);
}

C. Playing Piano

dp[i][j] 表示 第 i 位填 j 是否可行，一遍 dp 顺便记录前驱即可。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, a[N];
int dp[N][6];
int cal(int x, int l, int r) {
    for (int i = l; i <= r; i++)
        if (dp[x][i]) return i;
    return 0;
}
int b[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= 5; i++) dp[1][i] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= 5; j++) {
            if (a[i] < a[i-1]) dp[i][j] = cal(i-1, j+1, 5);
            else if (a[i] > a[i-1]) dp[i][j] = cal(i-1, 1, j-1);
            else dp[i][j] = max(cal(i-1, 1, j-1), cal(i-1, j+1, 5));
        }
    }
    for (int i = 1; i <= 5; i++)
        if (dp[n][i]) {
            b[n] = i; break;
        }
    if (!b[n]) puts("-1");
    else {
        for (int i = n-1; i >= 1; i--) {
            b[i] = dp[i+1][b[i+1]];
        }
        for (int i = 1; i <= n; i++) {
            printf("%d", b[i]);
            if (i == n) puts("");
            else printf(" ");
        }
    }
}

D. Barcelonian Distance

借用直线和不借用直线都算一遍，借用直线就是延 x 轴或者 y 轴先走到直线。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
double a, b, c, x1, y1, x2, y2;
double ans;
double solve(double x3, double y3, double x4, double y4) {
    return fabs(x3-x1)+fabs(y3-y1)+hypot(fabs(x3-x4), fabs(y3-y4))+fabs(x4-x2)+fabs(y4-y2);
}
int main() {
    scanf("%lf%lf%lf%lf%lf%lf%lf", &a, &b, &c, &x1, &y1, &x2, &y2);
    ans = fabs(x1-x2)+fabs(y1-y2);
    if (b) ans = min(ans, solve(x1, -(a*x1+c)/b, x2, -(a*x2+c)/b));
    if (a) ans = min(ans, solve(-(b*y1+c)/a, y1, -(b*y2+c)/a, y2));
    if (a&&b) {
        ans = min(ans, solve(x1, -(a*x1+c)/b, -(b*y2+c)/a, y2));
        ans = min(ans, solve(-(b*y1+c)/a, y1, x2, -(a*x2+c)/b));
    }
    printf("%.10f\n", ans);
}

E. The Unbearable Lightness of Weights

题意

给你 n 个物体的重量和 n 个物体，你只能问你朋友一次 (a,b)，朋友会选 b 个物体总重为 a。

问你最多能确定几个物体的重量。

分析

如果只有两个重量，就都可以确定。

有三个以上的重量，只能确定一种重量，即全部选同一种重量的物体且其总重的组成方案唯一。

dp[i][j] 表示总重为 i 的 j 个物体的方案数，多重背包即可。

复杂度 1e8

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
#include <bits/stdc++.h>
using namespace std;
int n, a[105];
bool check() {
    int cnt = 0;
    for (int i = 1; i <= 100; i++)
        if (a[i]) cnt++;
    return cnt <= 2;
}
int dp[2][10001][101];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        a[x]++;
    }
    if (check()) {
        int ans = 0;
        for (int i = 1; i <= 100; i++) ans += a[i];
        cout << ans << endl;
        return 0;
    }
    dp[0][0][0] = 1;
    for (int i = 1; i <= 100; i++) {
        memcpy(dp[1], dp[0], sizeof(dp[0]));
        for (int j = 1; j <= a[i]; j++) {
            for (int k = i*j; k <= 10000; k++)
                for (int l = j; l <= 100; l++)
                    dp[1][k][l] = min(2, dp[1][k][l]+dp[0][k-i*j][l-j]);
        }
        memcpy(dp[0], dp[1], sizeof(dp[0]));
    }
    int ans = 0;
    for (int i = 1; i <= 100; i++)
        for (int j = 1; j <= a[i]; j++)
            if (dp[0][i*j][j] == 1) {
                ans = max(ans, j);
            }
    cout << ans << endl;
}