NOIP2010 提高组 | Actinoi's Blog

机器翻译

队列。

#include <cstdio>
int m, n; //内存容量和文章的长度
int nc[10001], head = 1, tail = 1; //内存中存的单词以及首尾，手写队列
int t[1001]; //查看是否已经出现
int main() {
    scanf("%d %d", &m, &n);
    int word, ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &word);
        if (t[word] == 0) { //还没有存
            ans++;
            if (tail - head < m) { //还没有填满
                nc[tail] = word; //将 word 存入内存中
                tail++;
                t[word] = 1; //标记这个单词
            } else { //已经填满
                t[nc[head]] = 0; //释放头元素
                head++;
                nc[tail] = word;
                tail++;
                t[word] = 1;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

乌龟棋

DP问题，每次枚举上一步 + 当前棋子个数就可以

#include <cstdio>
int step[351], card[5];
int DP[41][41][41][41]; //使用 i 张 1， j 张 2， k 张 3， q 张 4 最大值
int max(int a, int b) {
    if (a > b) return a;
    return b;
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &step[i]);
    for (int i = 1; i <= m; i++) {
        int tmp;
        scanf("%d", &tmp);
        card[tmp]++;
    }
    DP[0][0][0][0] = step[1];
    for (int i = 0; i <= card[1]; i++) {
        for (int j = 0; j <= card[2]; j++) {
            for (int k = 0; k <= card[3]; k++) {
                for (int q = 0; q <= card[4]; q++) {
                    int l = 1 + i + j * 2 + k * 3 + q * 4;
                    if (i != 0)
                        DP[i][j][k][q] = max(DP[i][j][k][q], DP[i - 1][j][k][q] + step[l]);
                    if (j != 0)
                        DP[i][j][k][q] = max(DP[i][j][k][q], DP[i][j - 1][k][q] + step[l]);
                    if (k != 0)
                        DP[i][j][k][q] = max(DP[i][j][k][q], DP[i][j][k - 1][q] + step[l]);
                    if (q != 0)
                        DP[i][j][k][q] = max(DP[i][j][k][q], DP[i][j][k][q - 1] + step[l]);
                }
            }
        }
    }
    printf("%d\n", DP[card[1]][card[2]][card[3]][card[4]]);
    return 0;
}

关押罪犯

并查集 + 贪心

#include <cstdio>
#include <algorithm>
int n, m; //罪犯的数目以及存在仇恨的罪犯对数
int father[100001], enemy[100001];
struct data {
    int a, b, c;
} f[100001];
bool cmp(data x, data y) { //从大到小排序
    return x.c > y .c;
}
int find_father(int x) {
    if (x == father[x])
        return x;
    father[x] = find_father(father[x]);
    return father[x];
}
bool check(int a, int b) {
    if (find_father(a) == find_father(b)) {
        return true;
    }
    return false;
}
void add(int x, int y) {
    x = find_father(x);
    father[x] = find_father(y);
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &f[i].a, &f[i].b, &f[i].c);
    }
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
    std::sort(f + 1, f + 1 + m, cmp);
    for (int i = 1; i <= m; i++) {
        if (check(f[i].a, f[i].b) == true) {
            printf("%d\n", f[i].c);
            return 0;
        }
        if (enemy[f[i].a] == 0) enemy[f[i].a] = f[i].b;
        else add(enemy[f[i].a], f[i].b); //f[i].a 已经有敌人了，因此把 f[i].b 同 f[i].a 的敌人关在一起更好
        if (enemy[f[i].b] == 0) enemy[f[i].b] = f[i].a;
        else add(enemy[f[i].b], f[i].a); //把他们两个关进同一所监狱中
    }
    printf("%d\n", 0);
    return 0;
}

引水入城

①当无解时，很好处理，把挨着湖泊的那一行城市每个都 DFS 一遍，看看最后一排点是否都被经过。

②当有解时，首先可以想到搜索挨着湖泊的那一行城市，然后看每个城市的影响区间是多少。

影响区间是连续的，证明可以见 [洛谷-天上一颗蛋的博客] 。

因此，可以 DFS 出每个蓄水厂的影响区间 left 与 right。然后就可以得到以下这张图：

其中，矩形代表挨着沙漠的城市，每根线段表示每个蓄水厂的影响范围。

接着，进行 DP。

DP[i] 代表第 i 个城市是否选择作为蓄水厂。因此就可以得到 DP[i] = min(DP[j] + 1) 的方程式，其中 j 是所有右节点 + 1大于等于 i 的左节点（也就是 i 和 j 能够拼成一条更长的线段）的线段。

DP的具体实现：

首先将所有的 DP 赋值为 MAX，然后，起点必须要从左端点为 的线段进行转移，因此把所有左端点为 的点的 DP 值都设为 ，然后进行 DP。当每根线段的右端点恰好为 时，更新答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
int high[501][501], vis[501][501], DP[501];
struct node {
    int left, right;
} a[501][501]; //每个点能够到达最左和最右的位置
bool cmp(node x, node y) {return x.left < y.left;}
int n, m;
int xx[4] = {0, 1, -1, 0};
int yy[4] = {1, 0, 0, -1};
int max(int a, int b) {return a > b ? a : b;}
int min(int a, int b) {return a < b ? a : b;}
void DFS(int x, int y) {
    vis[x][y] = 1;
    if (x <= 0 || x > n || y <= 0 || y > m) return;
    for (int i = 0; i < 4; i++) {
        int nx = x + xx[i], ny = y + yy[i];
        if (high[nx][ny] < high[x][y] && nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
            if (vis[nx][ny] == false)
                DFS(nx, ny);
            a[x][y].left = min(a[nx][ny].left, a[x][y].left);
            a[x][y].right = max(a[nx][ny].right, a[x][y].right);
        }
    }
}
int main() {
    //将 left 设置为最大值
    for (int i = 1; i <= 500; i++)
        for (int j = 1; j <= 500; j++)
            a[i][j].left = 214748364;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &high[i][j]);
    for (int i = 1; i <= m; i++)
        a[n][i].left = a[n][i].right = i;
    for (int i = 1; i <= m; i++)
        if (vis[1][i] == false)
            DFS(1, i);
    int cnt = 0;
    for (int i = 1; i <= m; i++)
        if (vis[n][i] == false)
            cnt++;
    if (cnt) {
        printf("0\n%d\n", cnt);
        return 0;
    }
    std::sort(a[1] + 1, a[1] + 1 + m, cmp);
    memset(DP, 0x3f, sizeof(DP));
    for (int i = 1; i <= m; i++) {
        if (a[1][i].left == 1) {
            DP[i] = 1;
        }
    }
    int ans = 2147483647;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            if (i != j) {
                if (a[1][j].right + 1 >= a[1][i].left)
                    DP[i] = min(DP[i], DP[j] + 1);
                if (a[1][i].right == m)
                    ans = min(ans, DP[i]);
            }
        }
    }
    printf("1\n%d\n", ans);
    return 0;
}