糯米

思路：

这题的背景是亮点，描述如下：
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 在研究某种稀有虫子的性行为。他假设虫子们有两种不同的性别，而且它们只跟异性发生关系。
在他的试验里，每个虫子和它的性行为都很容易辨认，因为它们的背后印着号码。
给出一些虫子的性行为，确定是否有同性恋的虫子能推翻这个假设。

同性恋确实让人无法接受，无论是人还是虫子。。

这题的解法不是亮点，就是普通的并查集，数据量非常庞大，需要路径压缩。

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

     摘要: 思路：继推箱子以后，又发现POJ上有这类题目，哈哈。这次是给出一条贪食蛇当前的状态、墙的位置、食物的位置。求吃到食物需要走的最小的步数。这类题目是相当牛逼的！高手的速度可以做到很BT的。在 status 上面就看到有 0ms 的！相当震惊，如此庞大的数据量能做到 0ms，肯定是神牛！后来搜了一下，还找到了那位神牛的博客，看了一下，发现看不大懂，杯具。。哪一天有空，一定会再想一下这道题的。一开始想了...  阅读全文

思路：

四个字：能放就放。。

     摘要: 思路：这题没有啥好的方法了，看来。用组合C(K, D)枚举所有可能的疾病集合。其实复杂度很高的，C(15, 7) 都不知道多大了。但是数据比较弱。用别人的代码试了一下，用STL里面的全排列生成函数，都可以 60ms AC。下面的代码，没有用STL里面的函数，我以为会快一点，结果慢了不少，200+ms。。原理就是把16位分成2个8位来处理。#include <stdio.h>...  阅读全文

     摘要: 思路：每个石头可以分为两个波，一个高峰波，一个低谷波。每个波可以分为很多个水平方向的波。每个水平方向的波有三种情况，起始点的位置：1. 位于 B1 左边2. 位于 B1，B2 中间3. 位于 B2 右边其中第2种情况有点麻烦，多次往返的话要一次算完。代码：#include <stdio.h>#include <string.h>int P,&...  阅读全文

思路：

有油的时候能走多远就走多远，看能否走到目的地。
如果走不到，就必须要加一次油，途中会遇到很多加油站，一定要选油最多的那个。
这很容易理解，因为如果你只加这一次，越多当然越好。如果要以后还要加，那能走远一点选择也多一点。

重复这样的过程就可以求解了。可以用堆维护加油站中的油量。

杯具：稍稍修改了一下堆的写法，结果WA两次。。

代码：

思路：

每次放钱的时候，遵循两个原则来寻找最优方案：
1. 不能用面额小的组成面额大的
2. 所有方案中取最接近 C 的那个
就这样一次次的放，放到没钱为止。

注意，由于货币的数量较大，如果最优方案可以执行多次，那就一次过执行完。

     摘要: 属于状态型的动态规划，特难搞的那一类，状态一多，转换的时候难免遗漏一两个。这题还算，借助数据搞出来了，漏了两个转移，结果一组数据过不了。后来加上就AC了，时间还行，32MS。思路：从左往右开始放矩形，假设现在准备摆放第i列之后的矩形。实际上我们只关注第i-1列是怎么摆的，前面怎么摆都无所谓。所以，第i列牛的状态 + 第i-1列摆放的状态 -> 第i列摆放的状态摆放的状态有五种：1. 光上面有...  阅读全文

看到这道题，忽然想到，这就是大一时候C++考试的最后一题啊！
叫写一个程序，计算今天是星期几。
那时候记得写满了半张卷子。。八成还没写对。
不过今天，只用了5行！
我感到很由衷的高兴，面包会有的，牛奶会有的，脑残只是暂时的！

这题看起来很屌。
但是实际上走到每个点之后，速度必然是当前点和左上角点的差值的倒数。
所以，每个点到其他点的所花费的时间都是这个点自己的值决定的。
而且没可能经过一个点两次的，因为经过两次肯定是浪费时间的。
问题就变成了求最短路径。

注意：
这题的精度很莫名其妙，用C++可以AC的，G++、GCC都是WA。
不能用整数来保存时间，虽然看上去位数是够用的，但是遇到比较屌的数据就挂了。
就在这个问题上杯具了很久。