Tenka1 Programmer Contest (C,D,E)

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

第一把 AtCoder，可以说是真的菜了，E 题调到死都没调出来...

地址

C - Align

题意

给定 n 个数字，要求排成一排后任意两个数字之差的绝对值之和最大，求最大值

分析

一定是将数列排序后分成两半，前一半和后一半交替排列。绝对值符号可以去掉，然后每个数字计算次数只跟其位置有关，最后分类讨论一下就好了。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n, a[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a+1, a+1+n);
    if (n%2 == 0) {
        ll ans = 0;
        for (int i = 1; i < n/2; i++) ans -= 2*a[i];
        ans -= a[n/2];
        ans += a[n/2+1];
        for (int i = n/2+2; i <= n; i++) ans += 2*a[i];
        cout << ans << endl;
    } else {
        ll ans = 0;
        ans -= a[n/2];
        ans -= a[n/2+1];
        for (int i = 1; i < n/2; i++) ans -= 2*a[i];
        for (int i = n/2+2; i <= n; i++) ans += 2*a[i];
        ll ans2 = 0;
        for (int i = 1; i <= n/2; i++) ans2 -= 2*a[i];
        ans2 += a[n/2+2];
        ans2 += a[n/2+1];
        for (int i = n/2+3; i <= n; i++) ans2 += 2*a[i];
        ans = max(ans, ans2);
        cout << ans << endl;
    }
}

D - Crossing

题意

给定 n，问是否存在这样的集合组：

  • 1-n 每个数字都恰好被包含在两个集合中
  • 任意两个集合仅有一个相同数字

分析

n 条边的完全图

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
#include <bits/stdc++.h>
using namespace std;
int n;
int check(int n) {
    for (int i = 1; i*(i-1)/2 <= n; i++) 
        if (i*(i-1)/2 == n) return i;
    return 0;
}
int mp[505][505];
int main() {
    scanf("%d", &n);
    int k = check(n);
    if (!k) puts("No");
    else {
        puts("Yes");
        for (int i = 1; i <= k; i++)
            for (int j = i+1; j <= k; j++)
                mp[i][j] = mp[j][i] = n--;
        printf("%d\n", k);
        for (int i = 1; i <= k; i++) {
            printf("%d", k-1);
            for (int j = 1; j <= k; j++) {
                if (j == i) continue;
                printf(" %d", mp[i][j]);
            }
            puts("");
        }
    }
}

E - Equilateral

题意

给出一张仅含 '#' 和 '*' 的矩阵，问位置三元组的数目，其满足每个位置上的字符都是 '#' 且任意两点的麦哈顿距离相同

分析

跟题解大致相同的思路。

中心红点是三点麦哈顿距离的交点。a 和 b 长度相同，第三个点坐落在蓝线上。故先枚举中间的红点，再枚举另外俩红点的位置，统计蓝线上的点的数目即可。预处理斜线前缀和，复杂度O(n^3)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 305;
int n, m;
char mp[3*N][3*N];
int suml[3*N][3*N], sumr[3*N][3*N];
ll solve(int x, int y) {
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int num = 0;
        if (mp[x-i][y] == '#') num++;
        if (mp[x+i][y] == '#') num++;
        if (mp[x][y-i] == '#') num++;
        if (mp[x][y+i] == '#') num++;
        if (num == 3) ans++;
        else if (num == 4) ans += 4;
    }
    for (int i = 2; x-i >= N+1 && y-i >= N+1; i++) {
        if (mp[x-i][y] == '.' || mp[x][y-i] == '.') continue;
        int sx = x+1, sy = y+i-1;
        int ex = x+i-1, ey = y+1;
        ans += suml[ex][ey] - suml[sx-1][sy+1];
    }
    for (int i = 2; x-i >= N+1 && y+i <= N+m; i++) {
        if (mp[x-i][y] == '.' || mp[x][y+i] == '.') continue;
        int sx = x+1, sy = y-i+1;
        int ex = x+i-1, ey = y-1;
        ans += sumr[ex][ey] - sumr[sx-1][sy-1];
    }
    for (int i = 2; x+i <= N+n && y+i <= N+m; i++) {
        if (mp[x+i][y] == '.' || mp[x][y+i] == '.') continue;
        int sx = x-i+1, sy = y-1;
        int ex = x-1, ey = y-i+1;
        ans += suml[ex][ey] - suml[sx-1][sy+1];
    }
    for (int i = 2; x+i <= N+n && y-i >= N+1; i++) {
        if (mp[x+i][y] == '.' || mp[x][y-i] == '.') continue;
        int sx = x-i+1, sy = y+1;
        int ex = x-1, ey = y+i-1;
        ans += sumr[ex][ey] - sumr[sx-1][sy-1];
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = N+1; i <= N+n; i++) scanf("%s", mp[i]+1+N);
    for (int i = 1; i <= 2*N+n; i++)
        for (int j = 1; j <= 2*N+m; j++)
            suml[i][j] = sumr[i][j] = (mp[i][j] == '#');
    for (int i = 1; i <= 2*N+n; i++)
        for (int j = 1; j <= 2*N+m; j++) {
            sumr[i][j] += sumr[i-1][j-1];
            suml[i][j] += suml[i-1][j+1];
        }
    ll ans = 0;
    for (int i = N+1; i <= N+n; i++)
        for (int j = N+1; j <= N+m; j++)
            ans += solve(i, j);
    cout << ans << endl;
}