|
|
摘要: 這題很牛逼，是樓教主的《男人七題》的其中一道。求：一棵樹內最短距離小于K的點對數量后來看了解題報告，原來樹也是可以分治的。分：選取一條邊，將一棵樹分成兩半，這兩半的節點數要盡量相等。首先，統計個每個節點的下面有多少個節點然后，就知道每個邊切斷之后的情況了。選擇最優的即可。治：分成兩半之后，統計經過該條邊的點對線段中，長度小于K的數目。Amber 大牛論文的精辟描述如下： Divide... 閱讀全文
思路：
f[ch][len] = { 有多少個以 ch 開頭，長度為 len 的字符串 }
 #include <stdio.h>
__int64 dp[16][32], sum[16], ans;
int main()
   {
 int i, j, len;
char str[16];
freopen("e:\\test\\in.txt", "r", stdin);
for (i = 0; i < 26; i++)
dp[0][i] = 1;
  for (i = 1; i < 10; i++) {
for (j = 25 - i; j >= 0; j--) {
dp[i][j] += dp[i][j + 1];
dp[i][j] += dp[i - 1][j + 1];
 }
}
for (i = 0; i < 10; i++)
for (j = 0; j < 26; j++)
sum[i] += dp[i][j];
scanf("%s", str);
for (len = 0; str[len]; len++)
ans += sum[len];
ans -= sum[len - 1];
j = 0;
for (i = len - 1; i >= 0; i--) {
while (j < str[len - 1 - i] - 'a') {
ans += dp[i][j];
j++;
}
j++;
}
for (i = 0; i < len - 1; i++)
if (str[i] >= str[i + 1])
ans = -1;
printf("%I64d\n", ans + 1);
return 0;
 }
思路：
力矩 = 力臂*重量。這個高中物理學過啦，呵呵。
所以如果現在有一個 3 放在 -5 的位置上，一個 4 放在 3 的位置上，那當前天平的總力矩就是 3*-5 + 4*3 = -3 了
動態規劃：
從小到大依次放 weight。
f[i][j] = { 已經放了 i 個 weight，天平的總力矩為 j 時候的方案個數 }
初始化 f[0][0] = 1
狀態轉移：
對每個位置 x
f[i + 1][j + W[i + 1]*x] += f[i][j]
#include <stdio.h>
#include <stdlib.h>
int C, G, X[24], W[24];
struct {
int val, tm;
} _dp[2][1 << 15], *dp[2] = {
&_dp[0][_countof(_dp[0]) / 2],
&_dp[1][_countof(_dp[1]) / 2],
}, *cur, *pre;
int up, down;
int main()
{
int i, j, k, y;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &C, &G);
for (i = 1; i <= C; i++)
scanf("%d", &X[i]);
for (i = 1; i <= G; i++)
scanf("%d", &W[i]);
dp[1][0].tm = 1;
dp[1][0].val = 1;
for (i = 1; i <= G; i++) {
pre = dp[i & 1];
cur = dp[(i + 1) & 1];
for (j = down; j <= up; j++) {
if (pre[j].tm != i)
continue;
for (k = 1; k <= C; k++) {
y = j + W[i]*X[k];
if (cur[y].tm != i + 1) {
cur[y].tm = i + 1;
cur[y].val = 0;
}
cur[y].val += pre[j].val;
if (y < down)
down = y;
if (y > up)
up = y;
}
}
}
printf("%d\n", cur[0].val);
return 0;
}
思路：
這題是道好題！
假比確定了 [2, 4]、[5, 6]、[7, 8] 的奇偶性
[4, 5] 的奇偶性無法得知
[2, 6] 的奇偶性是知道的
所以只有詢問的區間符合以下要求：
1. 頭部和某個已知區間的頭部重合
2. 尾部和某個已知區間的尾部重合
3. 區間內每一段都是已知的
才能得出結論
我只想到這一步，然后用鏈表寫了一遍，TLE 了。上網搜解題報告，看到“并查集”三字，恍然大悟。嗎的太牛逼了。
我們把首尾相接的多個已知區間歸為一類。
將這多個區間的尾部的點歸在同一個集合中。
它們的父親就是最左邊區間頭部。
它們的權值就是從左邊區間頭部的到自己的這段區間的奇偶性。
插入區間 [i, j] 的時候，首先查找 i, j 對應的父親。就是 find 操作。
如果它們的父親相同，則表明它們處在同一個段的多個已知區間中。
那么 i, j 的權值相減，就很容易得出 [i, j] 的奇偶性了。
如果它們的父親不同，則需要將 i, j 分別對應的區間段關聯起來。也就是 union 操作。
這時候要注意判斷 i, j 父親的位置先后。因為這個 WA 了一次。
由于節點的位置分得很散，用 hash 存放。
#include <stdio.h>
#define HASH_SIZE (1 << 18)
#define NODES_NR 65536
struct node {
struct node *root, *next;
int idx, val;
};
struct node *hash[HASH_SIZE], nodes[NODES_NR];
int nodes_cnt;
inline void find(struct node *t)
{
static struct node *stk[NODES_NR];
int i;
for (i = 0; t->root != t; t = t->root)
stk[i++] = t;
for (i--; i >= 0; i--) {
stk[i]->val += stk[i]->root->val;
stk[i]->root = t;
}
}
inline struct node *insert(int idx)
{
int h;
struct node *t;
h = idx & (HASH_SIZE - 1);
for (t = hash[h]; t; t = t->next) {
if (t->idx == idx)
break;
}
if (!t) {
t = &nodes[nodes_cnt++];
t->root = t;
t->idx = idx;
t->next = hash[h];
hash[h] = t;
}
return t;
}
inline int solve(int start, int end, int val)
{
struct node *a, *b;
a = insert(start);
b = insert(end);
find(a);
find(b);
if (a->root == b->root)
return ((b->val - a->val) & 1) == val;
val -= b->val;
val += a->val;
a = a->root;
b = b->root;
if (a->idx < b->idx) {
b->root = a;
b->val = val;
} else {
a->root = b;
a->val = -val;
}
return 1;
}
int main()
{
int n, i, x, a, b;
char str[16];
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &n, &x);
for (i = 0; i < x; i++) {
scanf("%d%d%s", &a, &b, str);
if (!solve(a, b + 1, str[0] == 'o'))
break;
}
printf("%d\n", i);
return 0;
}
思路：
方程：
f[i][j] = { 還剩 i 次投 dice 的機會，此時位于第 j 個格子。這種情況下贏的概率 }
狀態轉移：
現在投 dice。分別考慮投到 1~6 的情況，假設最后停在 k 點。
如果 k 點是 L 點。則概率 g = f[i - 2][j]
如果 k 點是 B 點。則概率 g = f[i - 1][0]
如果 k 點是一個普通的點，則概率 g = f[i - 1][j]
f[i][j] = g[1]/6 + g[2]/6 + ... + g[6]/6
代碼：
#include <stdio.h>
#include <string.h>
double prob[3][128], *p[3];
int N, T, L, B;
char map[128];
inline double calc(int x)
{
switch (map[x]) {
case 'B': return p[1][0];
case 'L': return p[0][x];
default : return p[1][x];
}
}
int main()
{
int i, j, c, x;
freopen("e:\\test\\in.txt", "r", stdin);
while (scanf("%d%d%d%d", &N, &T, &L, &B), N) {
memset(map, ' ', sizeof(map));
memset(prob, 0, sizeof(prob));
while (L--) {
scanf("%d", &i);
map[i] = 'L';
}
while (B--) {
scanf("%d", &i);
map[i] = 'B';
}
//prob[1][N] = 1;
for (i = 0; i < T; i++) {
p[2] = prob[(i+2)%3];
p[1] = prob[(i+1)%3];
p[0] = prob[i%3];
p[1][N] = 1;
for (j = 0; j < N; j++) {
p[2][j] = 0;
for (c = 6, x = j + 1; c && x < N; c--, x++)
p[2][j] += calc(x) / 6;
for ( ; c; c--, x--)
p[2][j] += calc(x) / 6;
}
}
printf("%.6lf\n", p[2][0]);
}
return 0;
}
思路： 這題剛開始看上去，很屌，真的。 如果用很圖論的做法，就很牛逼了。 首先要把環合并為一點，然后就變成了有向無環圖，然后可能用拓撲排序之類的手段解決它。 這個很難很難，反正以哥的智商是沒可能想出來的。 考慮了一下，只要每頭牛為起始點遍歷一下圖，然后統計每個點上有多少頭牛能過經過就行了。 復雜度 O(NK) 還是能過的。所以就瞬間淪為一道水題了。 后來代碼寫出來，太爽啦 0MS，這題哥的代碼是第一！
#include <stdio.h>
#define MAX_N 1024
#define MAX_E 10032
struct edge_node {
struct edge_node *next;
int b;
};
struct vetx_node {
struct edge_node *e;
int cows, degs;
};
struct edge_node edges[MAX_E];
struct vetx_node vetxs[MAX_N];
int K, N, M;
int vis[MAX_N], tm;
int queue[MAX_N], head, tail;
inline void push(int i, int d)
{
if (vis[i] == tm)
return ;
vis[i] = tm;
vetxs[i].degs += d;
queue[tail++] = i;
}
inline void pop(int *i)
{
*i = queue[head++];
}
inline void bfs(int i)
{
int d;
struct edge_node *e;
d = vetxs[i].cows;
tm++;
head = tail = 0;
push(i, d);
while (head != tail) {
pop(&i);
for (e = vetxs[i].e; e; e = e->next)
push(e->b, d);
}
}
int main()
{
int i, a;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &K, &N, &M);
for (i = 0; i < K; i++) {
scanf("%d", &a);
vetxs[a].cows++;
}
for (i = 0; i < M; i++) {
scanf("%d%d", &a, &edges[i].b);
edges[i].next = vetxs[a].e;
vetxs[a].e = &edges[i];
}
for (i = 1; i <= N; i++)
if (vetxs[i].cows)
bfs(i);
a = 0;
for (i = 1; i <= N; i++)
if (vetxs[i].degs == K)
a++;
printf("%d\n", a);
return 0;
}
思路： 這題數據很水，所以二維背包都能過的。
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 10032
#define MAX_B 1024
#define MAX_L 1024
struct node {
int x, w, f, c;
};
struct node in[MAX_N];
int dp[MAX_L][MAX_B], right[MAX_L];
int L, N, B;
int cmp(const void *a, const void *b)
{
return ((struct node *)a)->x - ((struct node *)b)->x;
}
inline void update_max(int *a, int b)
{
if (b > *a)
*a = b;
}
int main()
{
int i, c;
struct node *t;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &L, &N, &B);
for (i = 0; i < N; i++)
scanf("%d%d%d%d", &in[i].x, &in[i].w, &in[i].f, &in[i].c);
qsort(in, N, sizeof(in[0]), cmp);
right[0] = 1;
dp[0][0] = 1;
for (i = 0; i < N; i++) {
t = &in[i];
for (c = 0; c < right[t->x] && c + t->c <= B; c++) {
if (!dp[t->x][c])
continue;
update_max(&dp[t->x + t->w][c + t->c], dp[t->x][c] + t->f);
update_max(&right[t->x + t->w], c + t->c + 1);
}
}
for (i = c = 0; c <= B; c++)
update_max(&i, dp[L][c]);
printf("%d\n", i - 1);
return 0;
}
思路：
由于上下都可以加空格，這個有點崩潰。
但后來發現還是可以用動態規劃做的。
假設輸入的字符串分別為 A，B
f[i][j] = { 從 A[i] 和 B[j] 開始匹配，所能達到的最大值 }
假設 A[i] = G，B[j] = C
那么現在的情況就是
Gxxxxx
Cxxxxx
狀態轉移為
=> f[i + 1][j] + table(A[i], '-')
G...
-C..
=> f[i][j + 1] + table(B[j], '-')
-G..
C...
=> f[i + 1][j + 1] + table(A[i], B[j])
G...
C...
可以用滾動數組。
所以這樣就解決了，覺得很神奇。
#include <stdio.h>
int N, M, f[2][256], *pre, *cur;
char A[256], B[256], map[256];
int tbl[5][5] = {
{ 5, -1, -2, -1, -3},
{-1, 5, -3, -2, -4},
{-2, -3, 5, -2, -2},
{-1, -2, -2, 5, -1},
{-3, -4, -2, -1, 0},
};
inline void swap(int **a, int **b)
{
int *t = *a;
*a = *b;
*b = 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 int dif(char a, char b)
{
return tbl[map[a]][map[b]];
}
int main()
{
int t, i, j;
freopen("e:\\test\\in.txt", "r", stdin);
map['A'] = 0;
map['C'] = 1;
map['G'] = 2;
map['T'] = 3;
map['-'] = 4;
scanf("%d", &t);
while (t--) {
scanf("%d%s%d%s", &N, &A[1], &M, &B[1]);
pre = &f[0][0];
cur = &f[1][0];
cur[0] = 0;
for (i = 1; i <= M; i++)
cur[i] = dif(B[i], '-') + cur[i - 1];
for (i = 1; i <= N; i++) {
swap(&pre, &cur);
cur[0] = dif(A[i], '-') + pre[0];
for (j = 1; j <= M; j++) {
cur[j] = dif(A[i], B[j]) + pre[j - 1];
cur[j] = max(cur[j], dif(A[i], '-') + pre[j]);
cur[j] = max(cur[j], dif(B[j], '-') + cur[j - 1]);
}
}
printf("%d\n", cur[M]);
}
}
思路：
由于一共有5種物品，每種物品最多只能有5個，所以物品的擁有情況，可以表示為 6*6*6*6*6 中狀態。
這個數好像是 7k 多，不大。
狀態轉移發生在有折扣的時候，如果當前的狀態可以打折，那么就看打折之后是否會比現在劃算就可以了。
一開始用的是取模，后來改成位操作了，快了一點，但還是很慢，不明白那些0ms怎么來的，⊙﹏⊙b汗
代碼很爛，僅供參考
#include <stdio.h>
int S, B;
int price[1024], code[1024];
int offer[128], cut[128];
int ans[1 << 15];
inline int min(int a, int b)
{
return a < b ? a : b;
}
int main()
{
int c, k, i, j, n, t, m[5], a, b;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &B);
t = 0;
for (i = 0; i < B; i++) {
scanf("%d%d%d", &c, &k, &price[i]);
t |= k << (i*3);
code[c] = i;
}
scanf("%d", &S);
for (i = 0; i < S; i++) {
scanf("%d", &n);
offer[i] = 0;
while (n--) {
scanf("%d%d", &c, &k);
offer[i] |= k << (code[c]*3);
}
scanf("%d", &cut[i]);
}
for (i = 0; i <= t; i++) {
ans[i] = 0;
a = i;
for (j = 0; j < B; j++) {
ans[i] += price[j] * (a & 7);
a >>= 3;
}
for (j = 0; j < S; j++) {
a = i;
b = offer[j];
for (k = 0; k < B; k++) {
if ((a & 7) < (b & 7))
break;
a >>= 3;
b >>= 3;
}
if (k < B)
continue;
ans[i] = min(ans[i], ans[i - offer[j]] + cut[j]);
}
}
printf("%d\n", ans[t]);
return 0;
}
思路：
一個 O(N^3) 的動態規劃，由于 N 比較小，所以沒啥問題。
f[i][j][k] = { 從一開始到三輛車分別位于 i, j, k 的時候，所有車走過的距離之和的最小值 }
其中 i <= j <= k
狀態轉移：
1. 第一輛車走到 k + 1
2. 第二輛車走到 k + 1
3. 第三輛車走到 k + 1
注意：
兩點之間的距離跟輸入一致。
不可以計算兩點間的最短距離，這樣會 WA。
這是題目沒有描述清楚！
#include <stdio.h>
#define MAX_N 32
#define MAX_DIS 0x70000000
int M, N;
int D[MAX_N][MAX_N];
int dp[MAX_N][MAX_N][MAX_N];
inline void update(int *a, int b)
{
if (b < *a)
*a = b;
}
int main()
{
int i, j, k, v;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &M);
while (M--) {
scanf("%d", &N);
for (i = 1; i <= N - 1; i++) {
for (j = i + 1; j <= N; j++) {
scanf("%d", &v);
D[i][j] = D[j][i] = v;
}
}
/**//*
兩點之間的距離跟輸入一致。
不可以計算兩點間的最短距離，這樣會 WA。
這是題目沒有描述清楚！
for (k = 1; k <= N; k++)
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
if (D[i][k] + D[k][j] < D[i][j])
D[i][j] = D[i][k] + D[k][j];
*/
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
for (k = 1; k <= N; k++)
dp[i][j][k] = MAX_DIS;
dp[1][1][1] = 0;
for (i = 1; i <= N - 1; i++) {
for (j = 1; j <= i; j++) {
for (k = j; k <= i; k++) {
update(&dp[k][i][i + 1], dp[j][k][i] + D[j][i + 1]);
update(&dp[j][i][i + 1], dp[j][k][i] + D[k][i + 1]);
update(&dp[j][k][i + 1], dp[j][k][i] + D[i][i + 1]);
}
}
}
v = MAX_DIS;
for (i = 1; i <= N; i++)
for (j = i; j <= N; j++)
update(&v, dp[i][j][N]);
printf("%d\n", v);
}
return 0;
}
|