糯米

这题做得人特别少，但实际上就是很普通的动态规划。

思路：
由于飞到某个点的时候，后面的行程跟前面的行程没有什么联系，所以开一个二维数组 f[K][N]，
f[i][j] = { 从第 j 个点，第 i 个时刻开始飞行直到终点，所需要的最小花费 }

然后就从后往前推就可以了。

     摘要: 思路：这题就是平常玩的那种推箱子的游戏。不过简化了一下，只是推一个箱子而已。用 bfs 来做，搜索树里面的节点，也就是状态，可以定义为：1. 箱子的坐标2. 上一次推完之后，人要走多少步才能到达箱子的上、下、左、右侧。如果到达不了，值则为无穷大。这样，状态转移的时候。就首先看是否能向某个方向推。如果能的话，就推一下。然后对人进行一次 bfs ，看下此时到达箱子的各个侧要走多少步。就可以生成一个新的...  阅读全文

思路：

一开始想到用线段树来做，但是发现坐标范围异常的大，放一个都勉勉强强，更不用说几个了！
想了一下，发现有一个至关重要的条件“不存在覆盖的情况”。
那就没必要用线段树了，因为压根就没必要解决覆盖问题。
可以用一种取巧的方法解决这题。



对于每个矩形，首先把它 y 方向的两条边抽取出来。
对于所有矩形的 y 方向的边，先按照 x 排序，然后按照顶端的 y 坐标排序。



然后对于位于同一 x 坐标的边，找出所有首尾相接或者有交集的边。
那么这些边对应的矩形必定要排除。

对于 x 方向的边，作同样的处理。

排除完之后，剩下的矩形就是可以答案了。

代码 500 多ms。。

     摘要: 此题只有130人solved！也算小牛题了，刚开始看到的时候，打算不做了的，但后来想了一下，发现有一点点思路。经过好几个小时的奋战，居然做出来了！那感觉非常爽！思路：首先此题的变态之处是，要求比较的是排名，就不是单纯的字符串匹配了。如果每次都重新求排名然后跟pattern比较，复杂度 O(NK)，八成会超时。关键是：一，不能每次都重新求排名二，不能逐个逐个的和pattern做比较看来也只有动态规...  阅读全文

思路：
看到这题，第一个想到的方法就是枚举 sqrt(2), sqrt(3), sqrt(4) 。。，然后sprintf出来，再比较字符串。
显然，这种方法比较低级啦。
仔细想了下，发现如果 x.123... 这个数字的平方是一个整数的话，那必然
 sqr(x.124) > ceil(sqr(x.123))  [sqr = 求平方, ceil = 向上取整]
所以，就可以从小到大枚举它的整数部分 x ，遇到第一个满足结果的 x，就是答案了。


代码 0ms AC

#include <stdio.h>
#include <math.h>

double A, P, B;
int L;

__inline double sqr(double i)
{
    return i * i;
}

double pow_1[] = {
    1, 1e-1, 1e-2, 1e-3, 1e-4, 1e-5, 1e-6, 1e-7, 1e-8, 1e-9, 1e-10, 
};

int main()
{
    double i, j;
    int d;

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

    scanf("%d%d", &L, &d);
    P = pow_1[L];
    B = P * d;
    for (A = 1; ; A++) {
        i = (__int64)sqr(A + B) + 1;
        j = sqr(A + B + P);
        if (j > i)
            break;
    }
    printf("%I64d\n", (__int64)i);

    return 0;
}

     摘要: 这个题目立意很好，但是就是数据比较无语了。O(N^3)的算法都能跑得比 O(N^2LgN)的快。代码写很长，这份应该算比较烂了，连自己都不知道代码的时间复杂度是多少！最终170ms AC，速度不快，比几百行的O(N^3)代码要慢很多。。。注意：用分数保存斜率，可以不触及精度问题，而且还比较方便。提交了很多次都WA，不知道问题所在，于是还写了一个脚本来测数据，然后发现了问题所在。附带脚本和测试数据...  阅读全文

有人说，宫崎骏只拍过一部片子，叫做《我们的纯真与失落》。

思路：
开四个树状数组。。
arr_x，arr_y，arr_xy，arr_cnt
分别统计y轴下：x的和、y的和、x*y的和、点的个数。
把点按照x排序，x越大的点出现得越晚。
从前往后推，每出现一个新的点的时候：
Step1，将该点加入到四个数组中。
Step2，对于高于它的点，面积增量为 x*sum(y) - sum(x*y)。
Step3，对于低于它的点，面积增量为 sum(y) * (cnt * x - sum(x))
最终得出结果。复杂度O(NlgN)。代码 63ms。

注意：
需要用int64保存数组元素

思路：
如果之前出现过长度为 len 的子序列。假设该子序列出现在 [a, b] 之间。
那如果存在 1, 2, ... K 任意一个数字出现在 [a, b] 之间，则必然存在一个长度为 len + 1 的非子序列。

代码：
从后往前推。用的是链表。94ms AC。
速度一般，还是不知道那些 0ms 是怎么搞出来的。
有人说可以从前往后推，可能会快一点吧。

#include <stdio.h>

#define MAX_N 100032
#define MAX_K 10032

struct node {
    int idx;
    struct node *next;
};
struct node nodes[MAX_N], *pos[MAX_K];
int N, K, left;

int main()
{
    int i, j, len;

    freopen("e:\\test\\in.txt", "r", stdin);
    
    scanf("%d%d", &N, &K);
    for (i = 0; i < N; i++) {
        scanf("%d", &j);
        nodes[i].idx = i;
        nodes[i].next = pos[j];
        pos[j] = &nodes[i];
    }

    left = N + 1;
    for (len = 1; len <= N; len++) {
        j = left;
        for (i = 1; i <= K; i++) {
            while (pos[i] && pos[i]->idx >= left)
                pos[i] = pos[i]->next;
            if (!pos[i])
                break;
            if (pos[i]->idx < j)
                j = pos[i]->idx;
        }
        if (i <= K)
            break;
        left = j;
    }
    printf("%d\n", len);

    return 0;
}

思路：
首先每条路径的值都可以分解一下质因数，就可以表示为多个质数的幂相乘的形式，
 比如 2^6 * 3^8 * 17^22 * 23^1。

三个数字a, b, c求最大公约数，分解完质因数后：
如果a拥有2^8，b拥有2^10，c拥有2^4。那最大公约数必然拥有2^4，取最小的一个。
对于每个质数 2, 3, 5, 7。。都是这个道理。

如果是求最小公倍数，在刚刚的例子里，就是取最大的一个了。

在点之间行走的过程，可以这样来看。在点1的时候GCF的值是所有质数的最大次幂的乘积。
GCF的值必定是越走越小。
每经过一条路径，CGF各个质因数的幂都必须小于等于路径的对应的值。
就好比路径就只能容纳这么大的流量。然后到达点2的时候，看看哪条路径的流量最大。
看起来像最大流问题，但不是最大流问题。

我们没办法遍历一次图，就求出哪条路径的流量最大。
但由于路径的权值最大才2000，质因数的幂最大也只有11（2^11 = 2048），大不了每个幂都试一次。
用二分法就可以了。

对于每一个质数，求到达点2 的时候的最大的幂。
最后再乘起来，就是答案了。
可见这种方法还是很巧妙的，效率也很高，0ms AC。

注意：
不需要高精度。但需要用__int64来保存答案。