糯米

思路：

這題的背景是亮點，描述如下：
Background 
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.
Problem 
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.

Hopper 在研究某種稀有蟲子的性行為。他假設(shè)蟲子們有兩種不同的性別，而且它們只跟異性發(fā)生關(guān)系。
在他的試驗里，每個蟲子和它的性行為都很容易辨認，因為它們的背后印著號碼。
給出一些蟲子的性行為，確定是否有同性戀的蟲子能推翻這個假設(shè)。

同性戀確實讓人無法接受，無論是人還是蟲子。。

這題的解法不是亮點，就是普通的并查集，數(shù)據(jù)量非常龐大，需要路徑壓縮。

#include <stdio.h>
#include <string.h>

int N, T, set[2048], val[2048];

inline int find(int idx)
{
    static int stk[2048], i;

    for (i = 0; set[idx]; i++) {
        stk[i] = idx;
        idx = set[idx];
    }
    for (i--; i >= 0; i--) {
        val[stk[i]] ^= val[set[stk[i]]];
        set[stk[i]] = idx;
    }

    return idx;
}

int main()
{
    int i, j, a, b, t, m, r;

    scanf("%d", &T);
    for (t = 1; t <= T; t++) {
        scanf("%d%d", &N, &m);
        memset(set, 0, (N + 1) * 4);
        memset(val, 0, (N + 1) * 4);
        r = 0;
        while (m--) {
            scanf("%d%d", &a, &b);
            i = find(a);
            j = find(b);
            if (i == j) 
                r |= val[a] == val[b];
            else {
                set[i] = b;
                val[i] = !val[a];
            }
        }
        printf("Scenario #%d:\n%s\n\n", 
                t,
                r ? "Suspicious bugs found!" : "No suspicious bugs found!"
                );
    }

    return 0;
}

     摘要: 思路：繼推箱子以后，又發(fā)現(xiàn)POJ上有這類題目，哈哈。這次是給出一條貪食蛇當前的狀態(tài)、墻的位置、食物的位置。求吃到食物需要走的最小的步數(shù)。這類題目是相當牛逼的！高手的速度可以做到很BT的。在 status 上面就看到有 0ms 的！相當震驚，如此龐大的數(shù)據(jù)量能做到 0ms，肯定是神牛！后來搜了一下，還找到了那位神牛的博客，看了一下，發(fā)現(xiàn)看不大懂，杯具。。哪一天有空，一定會再想一下這道題的。一開始想了...  閱讀全文

思路：

四個字：能放就放。。

     摘要: 思路：這題沒有啥好的方法了，看來。用組合C(K, D)枚舉所有可能的疾病集合。其實復雜度很高的，C(15, 7) 都不知道多大了。但是數(shù)據(jù)比較弱。用別人的代碼試了一下，用STL里面的全排列生成函數(shù)，都可以 60ms AC。下面的代碼，沒有用STL里面的函數(shù)，我以為會快一點，結(jié)果慢了不少，200+ms。。原理就是把16位分成2個8位來處理。#include <stdio.h>...  閱讀全文

     摘要: 思路：每個石頭可以分為兩個波，一個高峰波，一個低谷波。每個波可以分為很多個水平方向的波。每個水平方向的波有三種情況，起始點的位置：1. 位于 B1 左邊2. 位于 B1，B2 中間3. 位于 B2 右邊其中第2種情況有點麻煩，多次往返的話要一次算完。代碼：#include <stdio.h>#include <string.h>int P,&...  閱讀全文

思路：

有油的時候能走多遠就走多遠，看能否走到目的地。
如果走不到，就必須要加一次油，途中會遇到很多加油站，一定要選油最多的那個。
這很容易理解，因為如果你只加這一次，越多當然越好。如果要以后還要加，那能走遠一點選擇也多一點。

重復這樣的過程就可以求解了。可以用堆維護加油站中的油量。

杯具：稍稍修改了一下堆的寫法，結(jié)果WA兩次。。

代碼：

思路：

每次放錢的時候，遵循兩個原則來尋找最優(yōu)方案：
1. 不能用面額小的組成面額大的
2. 所有方案中取最接近 C 的那個
就這樣一次次的放，放到?jīng)]錢為止。

注意，由于貨幣的數(shù)量較大，如果最優(yōu)方案可以執(zhí)行多次，那就一次過執(zhí)行完。

     摘要: 屬于狀態(tài)型的動態(tài)規(guī)劃，特難搞的那一類，狀態(tài)一多，轉(zhuǎn)換的時候難免遺漏一兩個。這題還算，借助數(shù)據(jù)搞出來了，漏了兩個轉(zhuǎn)移，結(jié)果一組數(shù)據(jù)過不了。后來加上就AC了，時間還行，32MS。思路：從左往右開始放矩形，假設(shè)現(xiàn)在準備擺放第i列之后的矩形。實際上我們只關(guān)注第i-1列是怎么擺的，前面怎么擺都無所謂。所以，第i列牛的狀態(tài) + 第i-1列擺放的狀態(tài) -> 第i列擺放的狀態(tài)擺放的狀態(tài)有五種：1. 光上面有...  閱讀全文

看到這道題，忽然想到，這就是大一時候C++考試的最后一題啊！
叫寫一個程序，計算今天是星期幾。
那時候記得寫滿了半張卷子。。八成還沒寫對。
不過今天，只用了5行！
我感到很由衷的高興，面包會有的，牛奶會有的，腦殘只是暫時的！

這題看起來很屌。
但是實際上走到每個點之后，速度必然是當前點和左上角點的差值的倒數(shù)。
所以，每個點到其他點的所花費的時間都是這個點自己的值決定的。
而且沒可能經(jīng)過一個點兩次的，因為經(jīng)過兩次肯定是浪費時間的。
問題就變成了求最短路徑。

注意：
這題的精度很莫名其妙，用C++可以AC的，G++、GCC都是WA。
不能用整數(shù)來保存時間，雖然看上去位數(shù)是夠用的，但是遇到比較屌的數(shù)據(jù)就掛了。
就在這個問題上杯具了很久。