About

地址：http://poj.grids.cn/summercamp2012a/

据说都是POJ原题……ABCDE都是一眼题吧，F非常巧妙，G这题第二次遇到还是不会，H完全看不懂。

A: 勇敢与鲁莽

询问Fib[i]是否整除Fib[j]。

可以证明（或者打表发现），问题等价于i是否整除j。需要特判Fib[2]这一项。

B: 一个有意义的校庆

给定若干对事件的先后顺序，求字典序最小的顺序。

拓扑……

C: 雷涛的小猫

有若干个柱子，柱子某些位置上有东西，可以从任意柱子的顶端出发，每次可以向下一格，或者跳到任意柱子上并且掉下delta个位置，问到达地上时最多拿到多少物品。

F[i, j] = max{ F[i-1, j], max(F[i-delta, k]) }

D: Edge Detection

给定一张很大的图像，让你产生一个输出，每个格子的值是原图它和上下左右差的最小值。图像用不多于1000组的数对(value, times)表示接下来有连续times个value。

觉得就是细节处理题吧……估计大家都不爱写，考场上只有3人写，1人AC。

E: Priest John’s Busiest Day

有n个人要结婚并且婚礼时间是[Si, Ti]，在婚礼的开始或者结束，需要Di分钟让神父为他们祝福，也就是[Si, Si+Di]或者[Ti-Di, Ti]，问能否安排使得全部人都能收到祝福。

应该是2-SAT吧，没写过，得补一下。

F: 边配对

给出一个有n个顶点、m条边的简单无向连通图，其中m为偶数。求一个边的一个配对，使得每一对边共用一个顶点。

非常巧妙的一个DFS构造。不得不膜拜Discuss里面的神犇。见另外一篇题解。

G: Color a Tree

给定一棵带点权的树，要求对树染色，第i次染色花费为i*v[node]，一个点仅当它的父亲被染色他才能被染色。求最小花费。

神贪心，上次考试的时候出过，不会，现在还是不会……一开始每个点自己为一个集合，然后按照sum[s]/size[s]贪心，一个集合一个集合地并到父亲节点上。

H: ATP

看不懂题目我会乱说？