\(ITA\) 十月月赛答案（纯C大一友好版）

作者：胡鑫

\(A\) 数字矩阵（语法签到题）

#include <stdio.h>

int a[15][15];

int main() {
    int n, k = 1, x = 1, y = 0;
    scanf("%d", &n);
    while (k <= n * n) {
        while (y < n && !a[x][y + 1]) a[x][++y] = k++;
        while (x < n && !a[x + 1][y]) a[++x][y] = k++;
        while (y > 1 && !a[x][y - 1]) a[x][--y] = k++;
        while (x > 1 && !a[x - 1][y]) a[--x][y] = k++;
    }
    for (int i = 1; i <= n; i++, printf("\n")) {
        for (int j = 1; j <= n; j++) {
            printf("%3d", a[i][j]);
        }
    }
    return 0;
}

\(B\) 整数序列（压轴题，差分，线段树）\(O(nlog_2n+m)\)

#include <stdio.h>
#include <math.h>

int n, m, a[200010], stf[200010][20], q[200010][3], f[200010][20];

int gcd(int x, int y) {
    return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y) {
    return x * y / gcd(x, y);
}

int query(int l, int r) {
    int k = log2(r - l + 1);
    return gcd(stf[l][k], stf[r - (1 << k) + 1][k]);
}

signed main() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; i++) {
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        q[i][0] = l, q[i][1] = r, q[i][2] = x;
        f[l][x]++, f[r + 1][x]--;
    }

    for (int i = 1; i <= n; i++) {
        int k = 1;
        for (int j = 1; j <= 16; j++) {
            f[i][j] += f[i - 1][j];
            if (f[i][j]) k = lcm(k, j);
        }
        a[i] = k;
    }

    for (int len = 0; len < 20; len++) {
        for (int i = 1; i + (1 << len) - 1 <= n; i++) {
            if (!len) {
                stf[i][len] = a[i];
            } else {
                stf[i][len] = gcd(stf[i][len - 1], stf[i + (1 << (len - 1))][len - 1]);
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        if (query(q[i][0], q[i][1]) != q[i][2]) {
            printf("Impossible");
            return 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        printf("%d ", a[i]);
    }

    return 0;
}

\(C\) 排序（模板题，手写堆为例）\(O(nlog_2n)\)

#include <stdio.h>

int n, h[100010];

void down(int x) {
    int u = x, l = x << 1, r = l + 1;
    if (l <= n && h[l] < h[u]) u = l;
    if (r <= n && h[r] < h[u]) u = r;
    if (u != x) {
        int tmp = h[u];
        h[u] = h[x];
        h[x] = tmp;
        down(u);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d ", h + i);
    for (int i = n >> 1; i; i--) down(i);

    while (n) {
        printf("%d ", h[1]);
        h[1] = h[n--];
        down(1);
    }
}

\(D\) 阶乘之和(思维转换，高精度乘法) \(O(n)\)

#include <stdio.h>

int n, f[110][110], res[110];

int main() {
    scanf("%d", &n);

    f[1][0] = 1;
    for (int i = 2; i <= n; i++) {
        f[i][0] = f[i - 1][0] * i;
        for (int j = 1; j < 110; j++) {
            f[i][j] = f[i - 1][j] * i + f[i][j - 1] / 10;
            f[i][j - 1] %= 10;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 110; j++) {
            res[j] += f[i][j];
        }
    }

    for (int i = 1; i < 110; i++) {
        res[i] += res[i - 1] / 10;
        res[i - 1] %= 10;
    }

    int pos = 109;
    while (res[--pos] == 0);

    for (int i = pos; ~i; i--) {
        printf("%d", res[i]);
    }
}

\(E\) 石头剪刀布（经典题，带权并查集） \(O(m)\)

#include <stdio.h>

int res = 0, d[100010], p[100010];

int find(int x) {
    if (x != p[x]) {
        int tmp = find(p[x]);
        d[x] += d[p[x]];
        p[x] = tmp;
    }
    return p[x];
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        p[i] = i;
    }

    while (m--) {
        int r, a, b;
        scanf("%d %d %d", &r, &a, &b);

        if (a > n || b > n) {
            res++;
            continue;
        }

        int dif = r - 1, pa = find(a), pb = find(b);

        if (pa == pb) {
            res += ((d[a] - d[b]) % 3 + 3) % 3 != dif;
            continue;
        }

        p[pa] = p[pb];
        d[pa] = d[b] - d[a] + dif;
    }

    printf("%d", res);
}

\(F\) 团建座位（破环成链，前缀和）\(O(n)\)

#include <stdio.h>
#include <string.h>

const int N = 2e6 + 10;

char s[N];
int cnt[3], f[3][N];

int get(int l, int r, int t) {
    return f[t][r - 1] - f[t][l - 1];
}

int min(int a, int b) {
    return a < b ? a : b;
}

int work(int u, int x, int y, int z) {
    int c1 = cnt[x], c2 = cnt[y], c3 = cnt[z];
    int c11 = c1 - get(u, u + c1, x);
    int c22 = c2 - get(u + c1, u + c1 + c2, y);
    int c12 = get(u, u + c1, y);
    int c21 = get(u + c1, u + c1 + c2, x);
    return c11 + c22 - min(c12, c21);
}

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);

    memcpy(s + 1 + n, s + 1, n);
    for (int i = 1; i <= n; i++) {
        cnt[s[i] - 'A']++;
    }

    for (int i = 1; i <= n * 2; i++) {
        for (int j = 0; j < 3; j++) {
            f[j][i] = f[j][i - 1];
        }
        f[s[i] - 'A'][i]++;
    }

    int res = N;
    for (int i = 1; i <= n; i++) {
        res = min(res, min(work(i, 0, 1, 2), work(i, 0, 2, 1)));
    }

    printf("%d", res);
    return 0;
}

\(H\) ITA的会议（三分查找）

#include <stdio.h>
#include <stdlib.h>

#define int long long

int n, res = 1e18, l = -1e9, r = 1e9, p[200010], w[200010], d[200010];

int dis(int pos) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += abs(pos - p[i]) > d[i] ? w[i] * (abs(pos - p[i]) - d[i]) : 0L;
    }

    if (ans < res) res = ans;
    return ans;
}

signed main() {
    scanf("%lld", &n);

    for (int i = 0; i < n; i++) scanf("%lld %lld %lld", &p[i], &w[i], &d[i]);

    while (r >= l) {
        int mid1 = (2 * l + r) / 3, mid2 = (l + r * 2) / 3;

        if (dis(mid1) < dis(mid2)) {
            r = mid2 - 1;
        } else {
            l = mid1 + 1;
        }
    }

    printf("%lld", res);
}

\(I\) 桌面清理（差分） \(O(n)\)

#include <stdio.h>

int n, m, l, r, d[100010], res;

int main() {
    scanf("%d %d", &n, &m);

    while (m--) {
        scanf("%d %d", &l, &r);
        d[l]--, d[r + 1]++;
    }

    d[0]++;

    for (int i = 1; i <= n; i++) {
        d[i] += d[i - 1];
    }

    for (int i = 0; i <= n; i++) {
        res += d[i] > 0;
    }

    printf("%d", res);
}

\(J\) 牢大的最强大脑节目 \((DFS)\)

#include<stdio.h>
#include <string.h>

char g[110][110], s[20];

int n, m, e, res = 0;
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[8] = {1, -1, 0, 0, -1, 1, 1, -1};

void dfs(int d, int x, int y, int cnt, int tx, int ty, int f) {

    if (x < 1 || y < 1 || x > n || y > m || g[x][y] != s[d] || cnt > 1) return;

    res += d == e;

    for (int i = 0 + f; i < 4 + f; i++) {
        if ((tx == 0 && ty == 0) || (tx == dx[i] && ty == dy[i])) {
            dfs(d + 1, x + dx[i], y + dy[i], cnt, dx[i], dy[i], f);
        } else {
            dfs(d + 1, x + dx[i], y + dy[i], cnt + 1, dx[i], dy[i], f);
        }
    }
}

signed main() {
    scanf("%s %d %d", s, &n, &m);
    
    e = strlen(s) - 1;
    for (int i = 1; i <= n; i++) {
        memset(g[i], ' ', sizeof g[i]);
        for (int j = 1; j <= m; j++) {
            while (g[i][j] == ' ' || g[i][j] == '\n') {
                g[i][j] = getchar();
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dfs(0, i, j, 0, 0, 0, 0);
            dfs(0, i, j, 0, 0, 0, 4);
        }
    }
    printf("%d", res);
}