糯米

     摘要: 这题很牛逼，是楼教主的《男人七题》的其中一道。求：一棵树内最短距离小于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，这题哥的代码是第一！

思路：

这题数据很水，所以二维背包都能过的。

思路：

由于上下都可以加空格，这个有点崩溃。
但后来发现还是可以用动态规划做的。
假设输入的字符串分别为 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;
}