|
|
思路： 这题目非常牛逼！是道月赛的题目！看完题目我就放弃了。。直接看解题报告。 解法果然牛逼！ 解题报告链接在此： http://acm.pku.edu.cn/JudgeOnline/images/contestreport/200606/G.htm代码是照着解题报告写的，不过还是很烂，好像3000+ms，实在佩服那些1000ms内的神牛们！
 #include <stdio.h>
#define MAX_N 1024
  struct queue_node  {
 int y, x;
 };
int set[MAX_N][MAX_N], cut[MAX_N][MAX_N];
int N, M;
int left, top, right, bottom;
struct queue_node queue[MAX_N * MAX_N];
int head, tail;
inline int find(int *arr, int idx)
{
static int stk[MAX_N * MAX_N], sp;
for (sp = 0; arr[idx]; idx = arr[idx])
stk[sp++] = idx;
for (sp--; sp >= 0; sp--)
arr[stk[sp]] = idx;
return idx;
}
inline void push(int y, int x)
{
if (x < left || x > right || y < top || y > bottom)
return ;
if (cut[y][x])
return ;
cut[y][x] = 1;
  if (cut[y][x - 1] && cut[y][x + 1]) {
set[y][x] = x + 1;
set[y][x - 1] = x + 1;
 } else if (cut[y][x - 1])
set[y][x - 1] = x;
else if (cut[y][x + 1])
set[y][x] = x + 1;
queue[tail].y = y;
queue[tail].x = x;
tail++;
}
inline int bfs(int y, int x)
{
x = find(set[y], x);
if (cut[y][x])
x++;
if (x > right)
return 0;
head = tail = 0;
push(y, x);
while (head != tail) {
y = queue[head].y;
x = queue[head].x;
head++;
push(y - 1, x);
push(y + 1, x);
push(y, x - 1);
push(y, x + 1);
}
return 1;
}
int main()
{
int i, j, ans;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &M);
while (M--) {
scanf("%d%d%d%d", &left, &top, &right, &bottom);
ans = 0;
for (i = top; i <= bottom; i++)
while (bfs(i, left))
ans++;
printf("%d\n", ans);
}
return 0;
}
思路：
状态数组 f[N][B][2]：
f[i][j][0] = { 现在处于第 i 个小时，之前一共休息了 j 个小时，第 i 个小时休息了。到现在为止获得的最大点数 }
f[i][j][1] = { 现在处于第 i 个小时，之前一共休息了 j 个小时，第 i 个小时没休息。到现在为止获得的最大点数 }
由于是循环数组。所以就分开两种情况：
1. 第 1 个小时没休息
2. 第 1 个小时休息了
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_N 4096
int in[MAX_N], N, B;
int dp[2][MAX_N][2], (*cur)[2], (*pre)[2];
__inline int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
int i, j, val;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &B);
for (i = 0; i < N; i++)
scanf("%d", &in[i]);
// not using period #1
for (i = 2; i < N; i++) {
pre = dp[i & 1];
cur = dp[(i + 1) & 1];
for (j = B - 2; j >= 0; j--) {
cur[j][1] = max(pre[j + 1][1] + in[i], pre[j + 1][0]);
cur[j][0] = max(pre[j][1], pre[j][0]);
}
}
val = max(cur[0][1], cur[0][0]);
// using period #1
memset(dp, 0, sizeof(dp));
pre = dp[0];
pre[B - 2][1] = in[1];
for (i = 2; i < N; i++) {
pre = dp[i & 1];
cur = dp[(i + 1) & 1];
for (j = B - 2; j >= 0; j--) {
cur[j][1] = j == B - 2 ? 0 : max(pre[j + 1][1] + in[i], pre[j + 1][0]);
if (i == N - 1)
cur[j][1] += in[0];
cur[j][0] = max(pre[j][1], pre[j][0]);
}
}
val = max(val, cur[0][1]);
val = max(val, cur[0][0]);
printf("%d\n", val);
return 0;
}
摘要: 这题看了以后，想了一个很脑残的做法，也过了，不过用了1.2s，哈哈。后来看了一个高中生大牛写的 Pascal 程序。根据函数名字来看，它用的是 floodfill 算法，提交了发现居然才用了188ms。现在高中生真太牛逼了！佩服！同时，作为一个即将毕业的大学生，哥表示压力很大。。以前没见过这个算法，看了一下，发现看不大懂，但是这样做确实很有道理！在网上面搜了一下关于floodfill算法的资料，发... 阅读全文
用邻接表存边，需要记录路径。
#include <stdio.h>
#define MAX_N 50032
#define MAX_K 1024
struct queue_node {
int step, idx;
struct queue_node *prev;
};
struct queue_node queue[MAX_K];
struct edge_node {
int idx;
struct edge_node *next;
};
struct edge_node edges[MAX_N], *map[MAX_K];
int qh, qt, N, K, visited[MAX_K], path[MAX_K];
__inline int push(int idx, int step, struct queue_node *prev)
{
if (visited[idx])
return 0;
visited[idx]++;
queue[qt].idx = idx;
queue[qt].step = step;
queue[qt].prev = prev;
qt++;
return idx == K;
}
int main()
{
int i, a, b;
struct queue_node *t;
struct edge_node *e;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &K);
for (i = 0; i < N; i++) {
scanf("%d%d", &a, &b);
edges[i].idx = b;
edges[i].next = map[a];
map[a] = &edges[i];
}
push(1, 1, NULL);
while (qh != qt) {
t = &queue[qh++];
for (e = map[t->idx]; e; e = e->next)
if (push(e->idx, t->step + 1, t))
break;
if (e)
break;
}
if (qh == qt) {
printf("-1\n");
return 0;
}
t = &queue[--qt];
printf("%d\n", t->step);
for (i = 0; t; t = t->prev)
path[i++] = t->idx;
for (i--; i >= 0; i--)
printf("%d\n", path[i]);
return 0;
}
思路：
首先对所有位置排序一下。
可能的最大的 distance 为 (range_right - range_left) / (C - 1)。
所以二分答案的时候区间的右边就是这个了。
判断某个 distance 是否能够成立的过程很简单：
只需要从左往右放牛，如果放到最后一个点都放不完，就不成立了。
代码 140ms：
#include <stdio.h>
#include <stdlib.h>
int N, C, in[100032];
int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
__inline int can(int val)
{
int i, pos, sum;
pos = 1;
for (i = 1; i < C; i++) {
sum = 0;
while (pos < N && sum < val) {
sum += in[pos] - in[pos - 1];
pos++;
}
if (sum < val)
return 0;
}
return 1;
}
int main()
{
int i, l, r, m;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &C);
for (i = 0; i < N; i++)
scanf("%d", &in[i]);
qsort(in, N, sizeof(in[0]), cmp);
l = 0;
r = (in[N - 1] - in[0]) / (C - 1);
while (l <= r) {
m = (l + r) / 2;
if (can(m))
l = m + 1;
else
r = m - 1;
}
printf("%d\n", r);
return 0;
}
思路：
首先按照 J牛 的数量排序，最小的前 K 个肯定是一个组了。反正这组都是输的，多烂都行。
剩下的 2K 个元素，和肯定是超过 2K*500 的。问题就是要划分一下，让每个组的和都大于 K*500。
这里没有说一定要平均分，也没说要满足什么其他特殊条件，而且数据又特别小。
所以就可以随机的分别挑选两个元素交换，然后看是否满足条件了。
代码居然 0MS AC了，随机的威力很大啊，只是不可能题题都用罢了。。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int K, in[256], *ptr[256];
int cmp(const void *a, const void *b)
{
return *(*(int **)a) - *(*(int **)b);
}
__inline void swap(int **a, int **b)
{
int *t = *a;
*a = *b;
*b = t;
}
int main()
{
int i, sa, sb, a, b;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &K);
for (i = 0; i < 3*K; i++) {
scanf("%d", &in[i]);
ptr[i] = &in[i];
}
qsort(ptr, 3*K, sizeof(ptr[0]), cmp);
sa = 0;
for (i = K; i < 2*K; i++)
sa += *ptr[i];
sb = 0;
for (i = 2*K; i < 3*K; i++)
sb += *ptr[i];
while (1) {
a = (rand() % K) + K;
b = (rand() % K) + 2*K;
sa = sa - *ptr[a] + *ptr[b];
sb = sb - *ptr[b] + *ptr[a];
swap(&ptr[a], &ptr[b]);
if (sa > 500*K && sb > 500*K)
break;
}
for (i = 0; i < 3*K; i++)
printf("%d\n", ptr[i] - in + 1);
return 0;
}
思路： 一次宽搜就可以解决了。 每个搜索节点需要保存一个 stat 值：如果携带了 shrubbery 则 stat = 1。否则为 0。
地图上的每个点也保存一个 stat 值：如果没经过则stat = 0；如果空着手经过则stat = 1；如果带着 shrubbery经过则stat = 2。判重的时候，如果地图的 stat 值大于搜索节点的 stat 值就可以忽略了。 代码 266ms：
#include <stdio.h>
#define SIZE 1024
struct map_node {
int type, stat;
};
struct map_node map[SIZE][SIZE];
struct queue_node {
int step, x, y, stat;
};
struct queue_node queue[SIZE * SIZE * 2];
int W, H, qh, qt;
__inline int push(int y, int x, int stat, int step)
{
if (y < 0 || y >= H || x < 0 || x >= W)
return 0;
if (map[y][x].type == 1)
return 0;
if (map[y][x].type == 3)
return stat;
if (map[y][x].type == 4)
stat = 1;
if (map[y][x].stat > stat)
return 0;
map[y][x].stat++;
queue[qt].stat = stat;
queue[qt].y = y;
queue[qt].x = x;
queue[qt].step = step;
qt++;
return 0;
}
int main()
{
int i, j;
struct queue_node *t;
freopen("e:\\test\\in.txt", "r", stdin);
t = &queue[qt++];
scanf("%d%d", &W, &H);
for (i = 0; i < H; i++) {
for (j = 0; j < W; j++) {
scanf("%d", &map[i][j].type);
if (map[i][j].type == 2) {
t->y = i;
t->x = j;
}
}
}
while (qh != qt) {
t = &queue[qh++];
if (push(t->y - 1, t->x, t->stat, t->step + 1) ||
push(t->y + 1, t->x, t->stat, t->step + 1) ||
push(t->y, t->x - 1, t->stat, t->step + 1) ||
push(t->y, t->x + 1, t->stat, t->step + 1)
)
break;
}
printf("%d\n", t->step + 1);
return 0;
}
这题目真的把人雷了！
题目看上去是最简单的那种01背包，但范围是 2^30 特别大，所以必然就不能用背包来做，只能搜索。
题目说 N <= 1000，还说输入的数据中，一个数大于它前面两个数的和。
所以就一直在想，是不是能利用这种特性来做些什么，但是思考了很久，无果。
看到题目 1400 / 300 的通过率，就认定这是一道难题了，基本做不出来了。
于是就直接看了下数据，发现 N 最大才 40 ！
写了一个很简单的搜索，0ms 就过了。被瞬间雷倒了！
为什么这道题要这样整蛊人呢？
看到 Discuss 里面有人提到“斐波那契数列”。忽然发现，题目的数据不就是跟“斐波那契”差不多吗！
只不过增长的还要快一点。
写了个程序测了下，发现第 46 项的和就已经超过 2^30 了。瞬间又无语了。
所以这题目确实是一道牛题！
#include <stdio.h>
#include <math.h>
int detect_range()
{
double f, n;
for (n = 1; n < 100; n++) {
f = pow(((sqrt(5.0) + 1) / 2), n);
printf("%d -> %lf\n", (int)n, f);
if ((int)f > (1 << 30))
break;
}
return 0;
}
#define MAX_N 64
__int64 sum[MAX_N], data[MAX_N], min_val, C;
int N;
void dfs(int idx)
{
while (idx > 0 && data[idx] > C)
idx--;
while (idx > 0 && sum[idx] >= C) {
C -= data[idx];
dfs(idx - 1);
C += data[idx];
dfs(idx - 1);
idx--;
}
if (C - sum[idx] < min_val)
min_val = C - sum[idx];
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%I64d", &N, &C);
for (i = 1; i <= N; i++) {
scanf("%I64d", &data[i]);
sum[i] = sum[i - 1] + data[i];
}
min_val = C;
while (data[N] > C)
N--;
dfs(N);
printf("%I64d\n", C - min_val);
return 0;
}
这题看似挺有实际用途的，呵呵。
大意就是用最小的花费覆盖一段区间。
思路：
动态规划，就是说，将线段的左端点从左到右排序。依次处理：
 1. 假设已经知道，所有的短线拼接起来之后，能组成哪几条长线（M为左端点）。 2. 当我们放入一条短线的时候，它能够和旧长线继续拼接。这时候，我们需要选取花费最小的那条。 3. 拼接之后，生成一条新的长线。 在（2）中，“选取花费最小的那条”可以用线段树来实现。也就是求区间内的最小值，RMQ问题，由于只插入不删除，线段树是可以维护的。 就这样一直处理，最终答案就是花费最小的以E为右端点的长线。 代码 94MS：
#include <stdio.h>
#include <stdlib.h>
#ifndef INT_MAX
#define INT_MAX 0x7fffffff
#endif
struct tree_node {
int cnt, min;
};
struct seg_node {
int a, b, s;
};
int N, M, E;
struct tree_node tree[86432 * 4];
struct seg_node in[10032];
int cmp(const void *a, const void *b)
{
return ((struct seg_node *)a)->a - ((struct seg_node *)b)->a;
}
__inline int max(int a, int b)
{
return a > b ? a : b;
}
__inline int min(int a, int b)
{
return a < b ? a : b;
}
void tree_op(const int ins,
int idx,
int left, int right,
int start, int end,
int *val
)
{
int mid;
if (ins) {
if (!tree[idx].cnt || *val < tree[idx].min)
tree[idx].min = *val;
tree[idx].cnt++;
}
if (left == start && right == end) {
if (!ins && tree[idx].cnt && tree[idx].min < *val)
*val = tree[idx].min;
return ;
}
mid = (left + right) / 2;
if (end <= mid)
tree_op(ins, idx*2, left, mid, start, end, val);
else if (start > mid)
tree_op(ins, idx*2 + 1, mid + 1, right, start, end, val);
else {
tree_op(ins, idx*2, left, mid, start, mid, val);
tree_op(ins, idx*2 + 1, mid + 1, right, mid + 1, end, val);
}
}
int main()
{
int i, val, start, end;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &N, &M, &E);
for (i = 0; i < N; i++)
scanf("%d%d%d", &in[i].a, &in[i].b, &in[i].s);
qsort(in, N, sizeof(in[0]), cmp);
for (i = 0; i < N; i++) {
if (in[i].b < M)
continue;
if (in[i].a > E)
break;
start = max(M, in[i].a - 1);
end = min(E, in[i].b);
if (in[i].a == M) {
tree_op(1, 1, M, E, end, end, &in[i].s);
continue;
}
val = INT_MAX;
tree_op(0, 1, M, E, start, end, &val);
if (val == INT_MAX)
continue;
val += in[i].s;
tree_op(1, 1, M, E, end, end, &val);
}
val = INT_MAX;
tree_op(0, 1, M, E, E, E, &val);
printf("%d\n", val == INT_MAX ? -1 : val);
return 0;
}
摘要: 思路：由于数据量比较小，可以枚举ABCDE的所有身份和时间（白天或者晚上），不会超时。判断deducible、impossible的部分很难写，基本上是照着数据改的。。1. 如果没有任何状态是符合要求的，输出 impossible。2. 在符合要求的状态中，如果对于某个人的身份或者时间，存在分歧，那该条就不能输出。3. 在（2）的情况下，如果没有任何输出，就输出 deducible。快被这玩意整疯... 阅读全文
|