糯米

這題做得人特別少，但實(shí)際上就是很普通的動(dòng)態(tài)規(guī)劃。

思路：
由于飛到某個(gè)點(diǎn)的時(shí)候，后面的行程跟前面的行程沒有什么聯(lián)系，所以開一個(gè)二維數(shù)組 f[K][N]，
f[i][j] = { 從第 j 個(gè)點(diǎn)，第 i 個(gè)時(shí)刻開始飛行直到終點(diǎn)，所需要的最小花費(fèi) }

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

     摘要: 思路：這題就是平常玩的那種推箱子的游戲。不過簡化了一下，只是推一個(gè)箱子而已。用 bfs 來做，搜索樹里面的節(jié)點(diǎn)，也就是狀態(tài)，可以定義為：1. 箱子的坐標(biāo)2. 上一次推完之后，人要走多少步才能到達(dá)箱子的上、下、左、右側(cè)。如果到達(dá)不了，值則為無窮大。這樣，狀態(tài)轉(zhuǎn)移的時(shí)候。就首先看是否能向某個(gè)方向推。如果能的話，就推一下。然后對人進(jìn)行一次 bfs ，看下此時(shí)到達(dá)箱子的各個(gè)側(cè)要走多少步。就可以生成一個(gè)新的...  閱讀全文

思路：

一開始想到用線段樹來做，但是發(fā)現(xiàn)坐標(biāo)范圍異常的大，放一個(gè)都勉勉強(qiáng)強(qiáng)，更不用說幾個(gè)了！
想了一下，發(fā)現(xiàn)有一個(gè)至關(guān)重要的條件“不存在覆蓋的情況”。
那就沒必要用線段樹了，因?yàn)閴焊蜎]必要解決覆蓋問題。
可以用一種取巧的方法解決這題。



對于每個(gè)矩形，首先把它 y 方向的兩條邊抽取出來。
對于所有矩形的 y 方向的邊，先按照 x 排序，然后按照頂端的 y 坐標(biāo)排序。



然后對于位于同一 x 坐標(biāo)的邊，找出所有首尾相接或者有交集的邊。
那么這些邊對應(yīng)的矩形必定要排除。

對于 x 方向的邊，作同樣的處理。

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

代碼 500 多ms。。

     摘要: 此題只有130人solved！也算小牛題了，剛開始看到的時(shí)候，打算不做了的，但后來想了一下，發(fā)現(xiàn)有一點(diǎn)點(diǎn)思路。經(jīng)過好幾個(gè)小時(shí)的奮戰(zhàn)，居然做出來了！那感覺非常爽！思路：首先此題的變態(tài)之處是，要求比較的是排名，就不是單純的字符串匹配了。如果每次都重新求排名然后跟pattern比較，復(fù)雜度 O(NK)，八成會超時(shí)。關(guān)鍵是：一，不能每次都重新求排名二，不能逐個(gè)逐個(gè)的和pattern做比較看來也只有動(dòng)態(tài)規(guī)...  閱讀全文

思路：
看到這題，第一個(gè)想到的方法就是枚舉 sqrt(2), sqrt(3), sqrt(4) 。。，然后sprintf出來，再比較字符串。
顯然，這種方法比較低級啦。
仔細(xì)想了下，發(fā)現(xiàn)如果 x.123... 這個(gè)數(shù)字的平方是一個(gè)整數(shù)的話，那必然
 sqr(x.124) > ceil(sqr(x.123))  [sqr = 求平方, ceil = 向上取整]
所以，就可以從小到大枚舉它的整數(shù)部分 x ，遇到第一個(gè)滿足結(jié)果的 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;
}

     摘要: 這個(gè)題目立意很好，但是就是數(shù)據(jù)比較無語了。O(N^3)的算法都能跑得比 O(N^2LgN)的快。代碼寫很長，這份應(yīng)該算比較爛了，連自己都不知道代碼的時(shí)間復(fù)雜度是多少！最終170ms AC，速度不快，比幾百行的O(N^3)代碼要慢很多。。。注意：用分?jǐn)?shù)保存斜率，可以不觸及精度問題，而且還比較方便。提交了很多次都WA，不知道問題所在，于是還寫了一個(gè)腳本來測數(shù)據(jù)，然后發(fā)現(xiàn)了問題所在。附帶腳本和測試數(shù)據(jù)...  閱讀全文

有人說，宮崎駿只拍過一部片子，叫做《我們的純真與失落》。

思路：
開四個(gè)樹狀數(shù)組。。
arr_x，arr_y，arr_xy，arr_cnt
分別統(tǒng)計(jì)y軸下：x的和、y的和、x*y的和、點(diǎn)的個(gè)數(shù)。
把點(diǎn)按照x排序，x越大的點(diǎn)出現(xiàn)得越晚。
從前往后推，每出現(xiàn)一個(gè)新的點(diǎn)的時(shí)候：
Step1，將該點(diǎn)加入到四個(gè)數(shù)組中。
Step2，對于高于它的點(diǎn)，面積增量為 x*sum(y) - sum(x*y)。
Step3，對于低于它的點(diǎn)，面積增量為 sum(y) * (cnt * x - sum(x))
最終得出結(jié)果。復(fù)雜度O(NlgN)。代碼 63ms。

注意：
需要用int64保存數(shù)組元素

思路：
如果之前出現(xiàn)過長度為 len 的子序列。假設(shè)該子序列出現(xiàn)在 [a, b] 之間。
那如果存在 1, 2, ... K 任意一個(gè)數(shù)字出現(xiàn)在 [a, b] 之間，則必然存在一個(gè)長度為 len + 1 的非子序列。

代碼：
從后往前推。用的是鏈表。94ms AC。
速度一般，還是不知道那些 0ms 是怎么搞出來的。
有人說可以從前往后推，可能會快一點(diǎn)吧。

#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;
}

思路：
首先每條路徑的值都可以分解一下質(zhì)因數(shù)，就可以表示為多個(gè)質(zhì)數(shù)的冪相乘的形式，
 比如 2^6 * 3^8 * 17^22 * 23^1。

三個(gè)數(shù)字a, b, c求最大公約數(shù)，分解完質(zhì)因數(shù)后：
如果a擁有2^8，b擁有2^10，c擁有2^4。那最大公約數(shù)必然擁有2^4，取最小的一個(gè)。
對于每個(gè)質(zhì)數(shù) 2, 3, 5, 7。。都是這個(gè)道理。

如果是求最小公倍數(shù)，在剛剛的例子里，就是取最大的一個(gè)了。

在點(diǎn)之間行走的過程，可以這樣來看。在點(diǎn)1的時(shí)候GCF的值是所有質(zhì)數(shù)的最大次冪的乘積。
GCF的值必定是越走越小。
每經(jīng)過一條路徑，CGF各個(gè)質(zhì)因數(shù)的冪都必須小于等于路徑的對應(yīng)的值。
就好比路徑就只能容納這么大的流量。然后到達(dá)點(diǎn)2的時(shí)候，看看哪條路徑的流量最大。
看起來像最大流問題，但不是最大流問題。

我們沒辦法遍歷一次圖，就求出哪條路徑的流量最大。
但由于路徑的權(quán)值最大才2000，質(zhì)因數(shù)的冪最大也只有11（2^11 = 2048），大不了每個(gè)冪都試一次。
用二分法就可以了。

對于每一個(gè)質(zhì)數(shù)，求到達(dá)點(diǎn)2 的時(shí)候的最大的冪。
最后再乘起來，就是答案了。
可見這種方法還是很巧妙的，效率也很高，0ms AC。

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