NOIP2010 提高组
机器翻译
队列。
#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;
}