携程编程大赛预赛第二场

A：和食物链做法一样，带权并查集

B：dp，01背包背出所有能组成边情况，在用这些情况去计算面积保留最大值

C：每个点从后往前搜，搜到合适就输出，搜不到就输出255 255 255

D：博弈，如果成对成对出现后手胜，否则先手胜

A：

#include <stdio.h>
#include <string.h>
const int N = 10005;

int t, n, m, parent[N], rank[N];

int find(int x) {
    if (parent[x] == x)
    return x;
    int t = find(parent[x]);
    rank[x] = (rank[parent[x]] + rank[x]) % 3;
    return parent[x] = t;
}

int main() {
    scanf("%d", &t);
    while (t--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    int ans = 0;
    while (m--) {
        int q, x, y;
        scanf("%d%d%d", &q, &x, &y);
        if (x > n || y > n)
        ans++;
        else if (q == 2 && x == y) {
        ans++;
        }
        else {
        int px = find(x);
        int py = find(y);
        if (px == py) {
            if (q == 1 && rank[x] != rank[y])
            ans++;
            else {
            if (q == 2 && rank[y] != (rank[x] + 1) % 3)
                ans++;
            }
        }
        else {
            parent[py] = px;
            rank[py] = (rank[x] - rank[y] + 2 + q) % 3;
        }
        }
    }
    printf("%d\n", ans);
    }
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 805;
int n, num[N], dp[N][N], sum;

double cal(int a, int b, int c) {
    double x = (a * a - b * b + c * c) * 1.0 / (2 * c * 1.0);
    double h = sqrt(a * a * 1.0 - x * x);
    return c * h / 2;
}

int main() {
    while (~scanf("%d", &n) && n) {
    sum = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &num[i]);
        sum += num[i];
    }
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = sum / 2; j >= 0; j--) {
        for (int k = sum / 2; k >= 0; k--) {
            if (j - num[i] >= 0) {
            if (dp[j - num[i]][k])
                dp[j][k] = 1;
            }
            if (k - num[i] >= 0) {
            if (dp[j][k - num[i]])
                dp[j][k] = 1;
            }
        }
        }
    }
    double ans = -INF;
    for (int i = 0; i <= sum / 2; i++) {
        for (int j = 0; j <= sum / 2; j++) {
        if (dp[i][j] == 0) continue;
        int k = sum - i - j;
        if (i + j > k && k + j > i && i + k > j) {
            ans = max(ans, cal(i, j, k));
        }
        }
    }
    if (ans < 0) printf("-1\n");
    else printf("%d\n", (int)(ans * 100));
    }
    return 0;
}

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

const int N = 1005;
int n, m;
struct BIT {
    int x1, y1, x2, y2, r, g, b;
    void scanf_() {
    scanf("%d%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &r, &g, &b);
    }
} b[N];

int main() {
    while (~scanf("%d%d", &n, &m) && n + m) {
    for (int i = 0; i < n; i++)
        b[i].scanf_();
    int x, y;
    while (m--) {
        scanf("%d%d", &x, &y);
        int i;
        for (i = n - 1; i >= 0; i--) {
        if (x >= b[i].x1 && x <= b[i].x2 && y >= b[i].y1 && y <= b[i].y2) {
            printf("%d %d %d\n", b[i].r, b[i].g, b[i].b);
            break;
        }
        }
        if (i == -1) printf("255 255 255\n");
    }
    }
    return 0;
}

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

const int N = 15;

int n, num, vis[105];

bool judge() {
    for (int i = 0; i <= 100; i++)
    if (vis[i] % 2) return true;
    return false;
}

int main() {
    while (~scanf("%d", &n) && n) {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        vis[num]++;
    }
    if (judge()) printf("Win\n");
    else printf("Lose\n");
    }
    return 0;
}

携程编程大赛预赛第二场,布布扣,bubuko.com

携程编程大赛预赛第二场

原文：http://blog.csdn.net/accelerator_/article/details/23514639