糯米

这题不懂做，一开始想了一个动态规划的方法，复杂度很高。估计得几百ms。
看status，觉得肯定有很低复杂度的方法。
然后看了 Discuss ，看到某位大牛说的贪心方法，顿时恍然大悟，吗的实在太牛逼了。
这位大牛的解法如下：
想象自己是一个黑一日游的司机：
1.如果有乘客要上车，那么就让他上，收钱！
2.如果超载了，把距目的地最远的几个乘客踢下去，退钱。
3.行驶到下一站

照着这个方法编码，一开始速度很慢，后来改成用一个队列来维护车上的乘客，速度就很快了，还飚上榜了。

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 10032
#define MAX_K 50032

struct slot_node {
    int end, cap;
    struct slot_node *next;
};
struct stat_node {
    int idx[MAX_N], cnt[MAX_N], head, tail, tot;
};
struct slot_node *start[2][MAX_N], slots[MAX_K*2];
struct stat_node stat[2];
int K, N, C, left, right, slots_cnt, ans;

inline int min(int a, int b)
{
    return a < b ? a : b;
}

inline void ins(int a, int b, int c, int d)
{
    struct slot_node *t;

    if (b > right)
        right = b;
    if (a < left)
        left = a;
    t = &slots[slots_cnt++];
    t->next = start[d][a];
    t->end = b;
    t->cap = c;
    start[d][a] = t;
}

inline void off(int d, int i)
{
    struct stat_node *t = &stat[d];

    if (t->head == t->tail || t->idx[t->head] != i) 
        return ;
    ans += t->cnt[t->head];
    t->tot -= t->cnt[t->head];
    t->head++;
}

inline void del(struct stat_node *t)
{
    int c;

    while (t->tot > C) {
        c = min(t->tot - C, t->cnt[t->tail - 1]);
        t->cnt[t->tail - 1] -= c;
        t->tot -= c;
        if (!t->cnt[t->tail - 1])
            t->tail--;
    }
}

inline void add(struct stat_node *t, int cap, int end)
{
    int i, j;

    t->tot += cap;

    for (i = t->tail - 1; i >= t->head; i--) {
        if (t->idx[i] == end) {
            t->cnt[i] += cap;
            return ;
        } else if (t->idx[i] < end)
            break;
    }
    i++;
    t->tail++;
    for (j = t->tail - 1; j > i; j--) {
        t->idx[j] = t->idx[j - 1];
        t->cnt[j] = t->cnt[j - 1];
    }
    t->idx[i] = end;
    t->cnt[i] = cap;
}

inline void on(int d, int i)
{
    struct slot_node *s;
    struct stat_node *t = &stat[d];

    for (s = start[d][i]; s; s = s->next) 
        add(t, s->cap, s->end);
    del(t);
}

int main()
{
    int i, a, b, c;

    freopen("e:\\test\\in.txt", "r", stdin);

    scanf("%d%d%d", &K, &N, &C);
    left = N;
    for (i = 0; i < K; i++) {
        scanf("%d%d%d", &a, &b, &c);
        if (a > b) 
            ins(N - a, N - b, c, 1);
        else
            ins(a, b, c, 0);
    }

    for (i = left; i <= right; i++) {
        off(0, i);
        off(1, i);
        on(0, i);
        on(1, i);
    }
    printf("%d\n", ans);

    return 0;
}

思路：

f[a][b] = { 种类数目为 a，蚂蚁数目为 b 时候的方案总数 }
转移：
f[a][b] = f[a - 1][0] + f[a - 1][1] + ... + f[a - 1][b]

时间 O(AT) 如果求 f[a][*] 只用一次循环的话
可以用循环数组

杯具：
把i看成j了，足足调了3个小时，注意，是不吃不喝，也没有上厕所，没有听歌，没有看优酷。。
是精神高度集中地浪费了3个小时！
与非主流之脑残相比，有过之而无不及也。

#include <stdio.h>

#define P 1000000

int T, A, S, B, fam[1024], dp[2][1024*128], *cur, *pre;

inline int min(int a, int b)
{
    return a < b ? a : b;
}

int main()
{
    int i, j, cnt, end, sum;

    freopen("e:\\test\\in.txt", "r", stdin);

    scanf("%d%d%d%d", &T, &A, &S, &B);
    for (i = 0; i < A; i++) {
        scanf("%d", &j);
        fam[j]++;
    }
    
    for (i = 0; i <= fam[1]; i++)
        dp[1][i] = 1;
    end = fam[1];

    for (i = 2; i <= T; i++) {
        cur = dp[i & 1];
        pre = dp[(i+1) & 1];
        cur[0] = pre[0];
        end += fam[i];
        for (j = 1; j <= end; j++) {
            cur[j] = cur[j - 1] + pre[j];
            if (j > fam[i])
                cur[j] -= pre[j - fam[i] - 1];
            cur[j] += P;
            cur[j] %= P;
        }
    }

    sum = 0;
    for (i = S; i <= B; i++) {
        sum += cur[i];
        sum %= P;
    }

    printf("%d\n", sum);

    return 0;
}

首先考虑这个子问题：
从地图上的某一点开始一直向右上方发展，一共能组成多少个以这个点的字母为开头的单词。
那么要把以这个点为左下角的矩形中的点全部都考察一遍。
假设这个点的字母为'N'，那就要看所有单词组成的单词树里面，所有'N'节点孩子的字母，是否出现在这个矩形中。
如果有出现的话，则又是一个子问题了。
把所有这样的子问题的和求出来，就是答案了。

再考虑一个细节：
'N'节点在单词树中可以出现很多次，因此每个'N'节点都是一个子问题。表示：
所有组成的单词，第一个字母节点是'N'，余下的字母节点出现的'N'的子树里。
动态规划的时候，对于每个节点要处理一次，因为每个节点的孩子都不一样。
在矩形中统计所有孩子对应的子问题的和。

关键是怎么存放子问题的答案：
我们需要找出矩形中跟指定孩子对应的点。如果把答案存放在地图W*H的数组里面，那就比较麻烦，需要枚举。
但是如果存放在单词树里面，就好很多。
如果我们从上往下扫描每一行，每一行从右到左扫描。那就只需要存放长度为W的一维数组了。

考虑一个细节：
对于地图上的点'N'，要以什么样的顺序处理单词树的每个'N'。
按照单词树的位置，应该从上到下处理。

代码写出来，跑了100ms+，居然排到第9，然后换了gcc编译，又排前了一点！
发现前面的人，除了第二名，估计算法都是一样的。

思路：

就是一个最短路径的问题。但是题目数据规模跟描述不符合。
数组要开大一些才能过。官方数据是描述是符合的，可能是管理员加了一些进去。

     摘要: 第一次写这玩意，还真有点麻烦，出了点问题。然后看了一下别人的代码，发现双向边，要分成两个单向边来插入。长见识了。而且费用的值有正有负，最好用SPFA来找最短路径。思路：建立一个超级源点，跟点1连起来，容量为2。建立一个超级汇点，跟点N连起来，容量为2。其他的边容量均为1。#include <stdio.h>#include <stdlib.h>#inc...  阅读全文

思路：

留意到题目里面有一句话“All farms are connected one way or another to Farm 1.”。
这貌似说明图一开始就是连通的。

二分答案，判断依据是：
如果将大于某个长度的边都去掉以后，图就不连通了。
那这个长度相对答案来说，一定是大了。

思路：

每天要么以今天的价格买入，要么前面某天买了存在仓库里。不存在一半是今天买的，一半是从仓库拿的，这种情况。
因为如果这样，肯定有一半具有更高的性价比，那就全部都改成更高性价比的方式就好了。。
所以，这题只需要保存一个当前的最大值，扫描一遍就能出结果了。瞬间就沦为一道水题了。还以为要大动作的呢。

思路：

深搜的时候，可以生成一棵树。
深搜也就是深度遍历这棵树，把遍历的路径打印出来，就解决了一部分边了，这部分边都是经过两次的，来一次去一次。
剩下的边，就是遍历的时候正在访问的节点与已经访问的节点之间的边，很容易的判断的。同样把这部分路径也打印出来。
后来看了 Discuss 才发现，这个东西叫做“欧拉回路”，又长见识了。

代码