T1

预处理出斐波那契数即可。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int fib[N]; 
char ans[N];

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

    fib[1] = fib[2] = 1; ans[1] = ans[2] = 'O';
    for (int i = 3; fib[i-1]+fib[i-2] <= n; ++i)
        fib[i] = fib[i-1] + fib[i-2], ans[fib[i]] = 'O';
    for (int i = 1; i <= n; ++i) {
        if (ans[i] == 'O') putchar('O');
        else putchar('o');  
    }

    return 0;
}

T2

先将 $a$ 数组排序，若 $a_i$ 出现次数 $>1$ 向后查找出第一个可以填的空将其填入。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 3010;

int n, a[N], num[N*2];

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

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int j = i + 1;
        while (num[i] > 1) {
            while (num[j]) j ++;
            ans += j-i;
            num[i] --, num[j] ++;
        }
    }
    printf("%d\n", ans);

    return 0;
}

T3

暴力搜索即可。由于我们搜索时是从大向小搜，所以第一次搜到的结果一定是最大值，直接将其输出即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

const int N = 20;

ll A, B, ans;
int a[N], b[N], cnt[N], lena, lenb;

int dfs(int u, ll numa, ll numb) {
    if (u > lena) {
        cout << numa << endl;
        return 0;
    }

    for (int i = 9; i >= 0; --i) {
        if (!cnt[i] || numa*10+i > numb*10+b[u]) continue;
        cnt[i] --;
        if (!dfs(u+1, numa*10+i, numb*10+b[u])) return 0;
        cnt[i] ++;
    }

    return 1;
}

int main() {
    cin >> A >> B;
    while (A) a[++ lena] = A % 10, A /= 10;
    while (B) b[++ lenb] = B % 10, B /= 10;

    for (int i = 1; i <= lena; ++i) cnt[a[i]] ++;

    if (lenb > lena) {
        sort(a+1, a+lena+1);
        for (int i = lena; i >= 1; --i) printf("%d", a[i]);
        return 0;
    }

    reverse(a+1, a+1+lena), reverse(b+1, b+1+lenb);
    dfs(1, 0, 0);

    return 0;
}

T4

本题的核心算法是 hash. 对于每一个连通块，将其 hash 的值设置为连通块内所有点对的距离之和。若两个连通块的 hash 值相同则视为同一种类型。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

#define x first
#define y second
typedef pair<int, int> pii;

const int N = 110;
const double eps = 1e-6;

int w, h;
char sky[N][N];
double hs[30];
int cnt = 0;
pii q[N*N];
int top;

double dist(pii a, pii b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    double dis = sqrt(dx*dx + dy*dy);
    return dis;
}

double get_hash() {
    double sum = 0;
    for (int i = 0; i < top; ++i) {
        for (int j = i+1; j < top; ++j) 
            sum += dist(q[i], q[j]);
    }
    return sum;
}

char get_letter(double key) {
    for (int i = 0; i < cnt; ++i) {
        if (fabs(hs[i]-key) < eps)
            return i + 'a';
    }
    hs[cnt ++] = key;
    return 'a' + cnt - 1;
}

void dfs(int a, int b) {
    q[top ++] = {a, b};
    sky[a][b] = '0';
    for (int i = a-1; i <= a+1; i ++) {
        for (int j = b-1; j <= b+1; j ++) {
            if (i == a && j == b) continue;
            if (i >= 0 && i < h && j >= 0 && j < w && sky[i][j] == '1')
                dfs(i, j);
        }
    }
}

int main() {
    cin >> w >> h;
    for (int i = 0; i < h; ++i) cin >> sky[i];
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (sky[i][j] == '1') {
                top = 0;
                dfs(i, j);
                char c = get_letter(get_hash());
                for (int k = 0; k < top; k ++) sky[q[k].x][q[k].y] = c;
            }
        }
    }

    for (int i = 0; i < h; ++i) cout << sky[i] << endl;
    return 0;
}

T5

将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。
那么原问题变成：将所有点分成两组，使得各组内边的权重的最大值尽可能小。

可以使用二分 + 染色法判定二分图。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int color[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool dfs(int u, int c, int limit) {
    color[u] = c;
    for (int i = h[u];  i >= 0; i = ne[i])  {
        if (w[i] <= limit) continue;
        int j = e[i];
        if (color[j])
            if (color[j] == c) return false;
        else if (!dfs(j, 3 - c, limit)) return false;
    }

    return true;
}

bool check(int limit) {
    memset(color, 0, sizeof color);

    for (int i = 1; i <= n; i ++ )
        if (color[i] == 0)
            if (!dfs(i, 1, limit))
                return false;
    return true;
}

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

    memset(h, -1, sizeof h);
    while (m -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }

    int l = 0, r = 1e9;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", l);
    return 0;
}