|
|
樸素的Prim！
 #include <stdio.h>
int map[128][128], set[128], N, tm;
__inline int prim()
   {
 int sum, i, j, k, min_val, min_idx;
tm++;
set[0] = tm;
sum = 0;
  for (i = 0; i < N - 1; i++) {
min_val = 0x7fffffff;
for (j = 0; j < N; j++) {
if (set[j] != tm)
continue;
for (k = 0; k < N; k++) {
if (set[k] != tm && map[j][k] < min_val) {
min_val = map[j][k];
min_idx = k;
 }
}
}
sum += min_val;
set[min_idx] = tm;
}
return sum;
 }
int main()
{
int i, j;
freopen("e:\\test\\in.txt", "r", stdin);
while (scanf("%d", &N) != EOF) {
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
scanf("%d", &map[i][j]);
printf("%d\n", prim());
}
return 0;
}
用的SPFA算法。
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1024
#define MAX_T 2048
struct edge_node {
int idx, len;
struct edge_node *next;
};
struct edge_node edges[MAX_T * 2], *map[MAX_N];
int N, T, D[MAX_N], queue[MAX_N], qh, qt, visited[MAX_N];
__inline void add_edge(struct edge_node *e, int from, int to, int len)
{
e->idx = to;
e->len = len;
e->next = map[from];
map[from] = e;
}
int main()
{
int i, from, to, len;
struct edge_node *e;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &T, &N);
for (i = 0; i < T * 2; i += 2) {
scanf("%d%d%d", &from, &to, &len);
add_edge(&edges[i], from, to, len);
add_edge(&edges[i + 1], to, from, len);
}
for (i = 1; i <= N; i++)
D[i] = 0x00ffffff;
queue[0] = N;
visited[N] = 1;
D[N] = 0;
qh = 0;
qt = 1;
while (qh != qt) {
i = queue[qh++];
qh &= _countof(queue) - 1;
visited[i] = 0;
for (e = map[i]; e; e = e->next) {
if (D[i] + e->len < D[e->idx]) {
D[e->idx] = D[i] + e->len;
if (!visited[e->idx]) {
visited[e->idx] = 1;
queue[qt++] = e->idx;
qt &= _countof(queue) - 1;
}
}
}
}
printf("%d\n", D[1]);
return 0;
}
注意：
要去掉前面的0再輸出。
#include <stdio.h>
#include <string.h>
struct node {
char arr[128];
int len;
};
__inline int max(int a, int b)
{
return a > b ? a : b;
}
__inline void add(struct node *a, struct node *b)
{
int i, val;
for (val = i = 0; i < max(a->len, b->len); i++) {
if (i < a->len)
val += a->arr[i];
if (i < b->len)
val += b->arr[i];
a->arr[i] = val % 10;
val /= 10;
}
if (val)
a->arr[i++] = val;
a->len = i;
}
__inline void mul_single(struct node *a, int val, int pad, struct node *c)
{
int i, r;
for (i = 0; i < pad; i++)
c->arr[i] = 0;
c->len = pad;
for (r = i = 0; i < a->len; i++) {
r += a->arr[i] * val;
c->arr[c->len++] = r % 10;
r /= 10;
}
if (r)
c->arr[c->len++] = r;
}
__inline void mul(struct node *a, struct node *b, struct node *c)
{
struct node t;
int i;
c->len = 0;
for (i = 0; i < a->len; i++) {
mul_single(b, a->arr[i], i, &t);
add(c, &t);
}
}
__inline void input(struct node *t)
{
char str[sizeof(t->arr)];
int i, len;
scanf("%s", str);
len = strlen(str);
t->len = 0;
for (i = len - 1; i >= 0; i--)
t->arr[t->len++] = str[i] - '0';
}
__inline void output(struct node *t)
{
int i;
for (i = t->len - 1; i >= 0 && !t->arr[i]; i--);
if (i < 0) {
printf("0\n");
return ;
}
for ( ; i >= 0; i--)
putc(t->arr[i] + '0', stdout);
putc('\n', stdout);
}
int main()
{
struct node a, b, c;
freopen("e:\\test\\in.txt", "r", stdin);
input(&a);
input(&b);
mul(&a, &b, &c);
output(&c);
return 0;
}
紀念一下，跟我生日一樣的題目。 思路： 這題可以用并查集來做，也是挺取巧的。 每個棧看做是一個集合，用一個數組記錄棧中元素離棧底的距離，一個數組記錄每個棧底元素對應的棧頂的元素。 對于移動操作，只需要合并集合，然后更改棧頂元素數組就行了。 用了棧寫的路徑壓縮，代碼跑到230ms。不知道那些100ms是怎么搞出來的。。真的有什么神奇技巧嗎。
#include <stdio.h>
#define MAX_N 30032
int top[MAX_N];
struct set_node {
int parent, dis;
};
struct set_node set[MAX_N];
__inline int find(int idx)
{
static int stk[MAX_N], sp, i;
for (sp = 0; set[idx].parent; sp++) {
stk[sp] = idx;
idx = set[idx].parent;
}
for (sp--; sp >= 0; sp--) {
i = stk[sp];
set[i].dis += set[set[i].parent].dis;
set[i].parent = idx;
}
return idx;
}
int main()
{
int p, a, b;
char op[16];
freopen("e:\\test\\in.txt", "r", stdin);
for (a = 0; a < MAX_N; a++)
top[a] = a;
scanf("%d", &p);
while (p--) {
scanf("%s%d", op, &a);
if (op[0] == 'M') {
scanf("%d", &b);
a = find(a);
b = find(b);
set[a].parent = top[b];
set[a].dis = 1;
top[b] = top[a];
} else {
find(a);
printf("%d\n", set[a].dis);
}
}
return 0;
}
思路：
由于W的值 <= 30，比較小，所以這題可以用動態規劃來做。
首先要把連續同一個數字一次處理。
dp[i] = {走了 i 次以后，得到的最大的蘋果數目}。這個數組的大小為 W。
走了奇數次以后，一定位于樹2下面。
走了偶數次以后，一定位于樹1下面。
假設當前是在第 t 時刻掉了 cnt 個蘋果下來。val 表示哪棵樹掉的蘋果，則執行下面的操作更新數組就可以了。
if (val == 1) {
for (i = 0; i <= min(t, W); i += 2)
dp[i] += cnt;
for (i = 1; i <= min(t, W); i += 2)
dp[i + 1] = max(dp[i + 1], dp[i] + cnt);
} else {
for (i = 1; i <= min(t, W); i += 2)
dp[i] += cnt;
for (i = 0; i <= min(t, W); i += 2)
dp[i + 1] = max(dp[i + 1], dp[i] + cnt);
}
轉移方程就是這個，還是挺簡單的。
因為數據弱，代碼 0ms ac了。
完整代碼：
#include <stdio.h>
int T, W, dp[35], t;
__inline int max(int a, int b)
{
return a > b ? a : b;
}
__inline int min(int a, int b)
{
return a < b ? a : b;
}
__inline void calc(int val, int cnt)
{
int i;
if (val == 1) {
for (i = 0; i <= min(t, W); i += 2)
dp[i] += cnt;
for (i = 1; i <= min(t, W); i += 2)
dp[i + 1] = max(dp[i + 1], dp[i] + cnt);
} else {
for (i = 1; i <= min(t, W); i += 2)
dp[i] += cnt;
for (i = 0; i <= min(t, W); i += 2)
dp[i + 1] = max(dp[i + 1], dp[i] + cnt);
}
t++;
}
int main()
{
int i, pre, cnt;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &T, &W, &pre);
cnt = 1;
while (--T) {
scanf("%d", &i);
if (i == pre) {
cnt++;
continue;
}
calc(pre, cnt);
cnt = 1;
pre = i;
}
calc(pre, cnt);
cnt = 0;
for (i = 0; i <= W; i++)
cnt = max(cnt, dp[i]);
printf("%d\n", cnt);
return 0;
}
昨天做了2008，今天準備做2009。但是看了下題目，發現爆難，才100個人過。
覺得這種題還是別碰了，等以后牛逼了再做。
于是跳過2008年，直接到2010年了！呵呵。
這題還是算容易的，比較適合自己水平發揮，用堆來做，速度尚可 188ms 。
思路： 先把牛按照score排序一下，然后從后往前找，把每一頭牛當做是位于中間的那頭牛。 那現在就是求： 該頭牛前面的所有牛中，哪 (N - 1) / 2 頭牛aid值的和最小。 該頭牛后面的所有牛中，哪 (N - 1) / 2 頭牛aid值的和最小。 這就是典型的用堆可以解決的問題了。
#include <stdio.h>
#include <stdlib.h>
#define MAX_C 100032
#define MAX_N 20032
struct node {
int score, aid;
};
struct node in[MAX_C];
int N, C, F;
int after[MAX_C], before[MAX_C];
int heap_size, heap_sum, heap[MAX_N];
int cmp(const void *a, const void *b)
{
return ((struct node *)a)->score - ((struct node *)b)->score;
}
__inline void shift_down(int idx)
{
int val = heap[idx];
while (1) {
idx *= 2;
if (idx > heap_size)
break ;
if (idx + 1 <= heap_size && heap[idx + 1] > heap[idx])
idx++;
if (heap[idx] <= val)
break;
heap[idx / 2] = heap[idx];
}
heap[idx / 2] = val;
}
__inline int heap_init(int start, int len)
{
int i;
heap_sum = 0;
for (i = start; i < start + len; i++) {
heap[i - start + 1] = in[i].aid;
heap_sum += in[i].aid;
}
for (i = heap_size / 2; i >= 1; i--)
shift_down(i);
return heap_sum;
}
__inline int heap_update(int aid)
{
if (aid < heap[1]) {
heap_sum -= heap[1] - aid;
heap[1] = aid;
shift_down(1);
}
return heap_sum;
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &N, &C, &F);
for (i = 0; i < C; i++)
scanf("%d%d", &in[i].score, &in[i].aid);
qsort(in, C, sizeof(in[0]), cmp);
heap_size = (N - 1) / 2;
before[heap_size - 1] = heap_init(0, heap_size);
for (i = heap_size; i < C; i++)
before[i] = heap_update(in[i].aid);
after[C - heap_size] = heap_init(C - heap_size, heap_size);
for (i = C - heap_size - 1; i >= 0; i--)
after[i] = heap_update(in[i].aid);
for (i = C - heap_size - 1; i - heap_size >= 0; i--) {
if (in[i].aid + before[i - 1] + after[i + 1] <= F)
break;
}
printf("%d\n", i - heap_size < 0 ? -1 : in[i].score);
return 0;
}
思路：
這道題目的解法非常牛逼。剛一看題就知道做不出來了，所以就在這個博客
http://hi.baidu.com/findthegateopen/
找到了一份解題報告。下面的內容都是基于原作者的代碼參考出來的。感謝原作者的代碼！
樸素的做法是O(N^3)的復雜度。usaco官方的算法是O(N^2)的復雜度。原作者的代碼跑了不到100ms，應該說是相當不錯了！
首先，要把所有牛放到坐標系上來表示。目的，就是求出包含最多點的直角三角形。
直角三角形的兩條直角邊上都必須有點，也就是一組牛中的具有最小height的點和具有最小width的點。
直角三角形的邊長也是固定的，cw = C/B，ch = C/A。這個還好說，從那個限制條件可以推出來的。初中都學過，呵呵。
Step1：求出經過一個點的所有可能存在的三角形。
其實也就是在該點下方的灰色區域中選擇點來確定一個三角形。
  Step2：求出經過一個點的所有可能存在的三角形中，最多包含的點數。 解法相當精妙。 求一個三角形內的點數，可以分解為一個矩形內的點數減去一個梯形內的點數。  用這個方法，求出最上面那個三角形的點數之后。可以繼續遞推得到下面其他三角形的點數。  也就是加上一個矩形，再減去一個梯形。 如果點按照高度排序以后，那么后面矩形里的點一定是后出現的。這樣就可以做到隨時增加矩形。 但是減去梯形這個操作，就難理解一點，把點按照A*H + B*W來排序，就能保證后面梯形里的點一定是后出現的。  可見，A*H + B*W 值的大小決定了他們的位置分布。完全可以保證這個順序。 這種數形結合的方法實在是相當精妙！ 那我們就可以首先求出第一個三角形的點數，然后接下來的三角形就根據減去梯形，和增加矩形的操作，來做小的調整就可以了。 在代碼里面的表現形式就是維護兩個指針，不斷向后移，中間剔除橫坐標不在范圍之內的點。 這個操作的復雜度是O(N)。 對所有點執行一次，故算法的復雜度是O(N^2)。 代碼：
/**//*
* 本代碼參考自 http://hi.baidu.com/findthegateopen/
* 中的代碼，感謝原作者的代碼！
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1024
struct node {
int w, h, k;
};
struct node in[MAX_N], *sort_h[MAX_N], *sort_k[MAX_N];
int A, B, C, N, ch, cw, ans, box, slash, cnt;
int cmp_h(const void *a, const void *b)
{
return (*(struct node **)b)->h - (*(struct node **)a)->h;
}
int cmp_k(const void *a, const void *b)
{
return (*(struct node **)b)->k - (*(struct node **)a)->k;
}
__inline void update(int h, int w)
{
int k;
for ( ; box < N && sort_h[box]->h >= h; box++)
if (sort_h[box]->w >= w && sort_h[box]->w <= w + cw)
cnt++;
k = A * h + B * w + C;
for ( ; slash < N && sort_k[slash]->k > k; slash++)
if (sort_k[slash]->w >= w && sort_k[slash]->w <= w + cw)
cnt--;
if (cnt > ans)
ans = cnt;
}
__inline void calc(int i)
{
int h, w;
box = 0;
slash = 0;
cnt = 0;
h = sort_h[i]->h;
w = sort_h[i]->w;
for ( ; i < N && sort_h[i]->h >= h - ch; i++)
if (sort_h[i]->w >= w && sort_h[i]->w <= w + cw)
update(sort_h[i]->h, w);
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d%d", &N, &A, &B, &C);
cw = C/B;
ch = C/A;
for (i = 0; i < N; i++) {
scanf("%d%d", &in[i].h, &in[i].w);
in[i].k = A * in[i].h + B * in[i].w;
sort_h[i] = &in[i];
sort_k[i] = &in[i];
}
qsort(sort_h, N, sizeof(sort_h[0]), cmp_h);
qsort(sort_k, N, sizeof(sort_k[0]), cmp_k);
for (i = 0; i < N; i++)
calc(i);
printf("%d\n", ans);
return 0;
}
思路： 1985也可以用1986的程序改改就行了。 但是覺得不用什么算法也是可以做出1985的。 想了一下，發現： 路徑的最大值一定存在于兩個葉子節點中。 如果只有一個葉子，那整個樹就是一條直線了。 由于我們只是考慮葉子節點。那么對于每一個非葉子節點，我們只需要找出它下面的所有節點中，離它最遠的兩個葉子就行了。 這兩個葉子節點的距離也就有可能成為答案。 對于每個點，我們只需要保存一個值，就是該點下面的所有節點中，距離它最遠的一個葉子節點，和它的距離。 對于每個點，遍歷完它的孩子之后，就知道“離它最遠的兩個葉子的距離”了。 注意： 代碼里需要處理“一條直線連著幾個點”這種情況，將這樣的幾個點縮成一個點比較好。不做這個處理一定會爆棧。最后一個數據是一條直線。（陰險） 這份代碼跑了141MS，還算可以，呵呵。應該比直接用lca要快。
#include <stdio.h>
#define MAX_N 40032
struct edge_node {
struct edge_node *next;
int idx, len;
};
struct edge_node edges[MAX_N*2];
struct tree_node {
struct edge_node *edge;
int visited;
};
struct tree_node tree[MAX_N];
int max_val;
__inline void add_edge(int idx, int a, int b, int len)
{
struct edge_node *e = &edges[idx];
e->idx = b;
e->len = len;
e->next = tree[a].edge;
tree[a].edge = e;
}
int dfs(int idx)
{
struct edge_node *e;
int sum, cnt, arr[2], r;
sum = 0;
while (1) {
tree[idx].visited = 1;
cnt = 0;
for (e = tree[idx].edge; e; e = e->next)
cnt += !tree[e->idx].visited;
if (!cnt)
return sum;
if (cnt > 1)
break;
for (e = tree[idx].edge; tree[e->idx].visited; e = e->next);
sum += e->len;
idx = e->idx;
}
arr[0] = arr[1] = 0;
for (e = tree[idx].edge; e; e = e->next) {
if (tree[e->idx].visited)
continue;
r = dfs(e->idx) + e->len;
if (r >= arr[1]) {
arr[0] = arr[1];
arr[1] = r;
} else if (r >= arr[0])
arr[0] = r;
}
r = arr[0] + arr[1];
if (r > max_val)
max_val = r;
return arr[1] + sum;
}
int main()
{
int m, n, a, b, len, i;
char str[16];
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (i = 0; i < m*2; i += 2) {
scanf("%d%d%d%s", &a, &b, &len, str);
add_edge(i, a, b, len);
add_edge(i + 1, b, a, len);
}
for (i = 1; i <= n; i++) {
if (tree[i].visited)
continue;
a = dfs(i);
if (a > max_val)
max_val = a;
}
printf("%d\n", max_val);
return 0;
}
摘要: 以前沒見過“最近公共祖先”這一類的題啊。長見識了，呵呵。解法基本上就是http://m.shnenglu.com/varg-vikernes/archive/2010/03/10/109355.html這篇文章里面提到的兩種方法。兩種方法的解法都非常精妙！最后程序寫出來：Tarjan 3372K 219MSDFS+RMQ 7992K 329MS代碼Tarjan：... 閱讀全文
|