先把題目貼出來(lái)，總結(jié)再說(shuō)：
POJ 2234 Matches Game
HOJ 2533 Stone II
POJ 2975 Nim
HOJ 1367 A Stone Game
POJ 2505 A multiplication game
ZJU 3057 beans game
POJ 1067 取石子游戲
POJ 2484 A Funny Game
POJ 2425 A Chess Game
POJ 2960 S-Nim
POJ 1704 Georgia and Bob
POJ 1740 A New Stone Game
POJ 2068 Nim
POJ 3480 John
POJ 2348 Euclid's Game
HOJ 2645 WNim
POJ 3710 Christmas Game
POJ 3533 Light Switching Game
高斯消元法用于求解線性方程組，采用選主元的方法，算法復(fù)雜度O(N ^ 3)。相應(yīng)的題型一種是在實(shí)數(shù)域進(jìn)行求解，一種是在整數(shù)域求解，一般涉及到取模。實(shí)數(shù)域的求解比較簡(jiǎn)單，整數(shù)域需要注意幾個(gè)問(wèn)題。模p一定是素?cái)?shù)，因?yàn)椴皇撬財(cái)?shù)的話求解的時(shí)候可能會(huì)出現(xiàn)多個(gè)解，處理起來(lái)比較麻煩。一個(gè)特殊的情況是模2域下的求解，可以采用位運(yùn)算優(yōu)化。還有一點(diǎn)要注意的是在最開(kāi)始構(gòu)造系數(shù)矩陣和增廣矩陣的時(shí)候，一定要先模p，否則選主元的時(shí)候一些模p為0的系數(shù)會(huì)被誤選。
高斯消元法另一個(gè)需要討論的地方就是解的情況。分為無(wú)解、唯一解和無(wú)窮解。這三種情況根據(jù)線性代數(shù)的知識(shí)很容易判斷，主要就是看系數(shù)陣的秩和增廣陣的秩。如果某一次選主元發(fā)現(xiàn)當(dāng)前列的系數(shù)都為0，那么對(duì)應(yīng)的變量是一個(gè)自由變?cè)?，解不確定。這個(gè)時(shí)候要跳過(guò)這一列，保持行不變，繼續(xù)進(jìn)行消元。在消元之后查看增廣陣的秩確定是否無(wú)解，若有解再根據(jù)自由變?cè)欠翊嬖趤?lái)判斷是否是唯一解。
如果解是無(wú)窮多個(gè)的時(shí)候，需要枚舉變?cè)娜≈?。一般用于處理解空間很小的情況，比如在模2域上的求解。枚舉變?cè)鬅o(wú)需重新列方程，只需進(jìn)行一次回帶找解即可。
題目不難，就是給定一個(gè)w * h的紙，中間切一刀，切出來(lái)的兩個(gè)矩形，從一個(gè)中剪下一個(gè)圓做圓柱的底，然后讓另一個(gè)彎起來(lái)套住底，做柱面，最后求能形成的最大體積。
練習(xí)的時(shí)候做了一下，總是WA。后來(lái)仔細(xì)想了一想，發(fā)現(xiàn)要討論幾種情況。首先要確保圓的直徑要不大于w，之后因?yàn)閺澢匦慰梢杂袃煞N方式，要分別討論。一種是高為w，這樣只需底面直徑越大越好。一種是高不定，這時(shí)候需要列一個(gè)方程，求出極值點(diǎn)?？梢宰C明極值就是極大值。但是要注意的是底面圓直徑是有范圍的，要注意極值點(diǎn)是否落在范圍內(nèi)。如果不在，由于極值點(diǎn)左側(cè)單調(diào)遞增，那么取直徑為w就是這種情況的最優(yōu)解。
這種題目比賽的時(shí)候很容易出錯(cuò)，需要靜下心來(lái)仔細(xì)想好才行，這方面能力以后還要多多鍛煉。
題目代碼：
#include <iostream>
#include <cmath>
using namespace std;
const double pi = acos(-1.0), eps = 1e-6;
int main()
{
double w, h, s, d;
while (scanf("%lf %lf", &w, &h) == 2)
{
if (fabs(w) < eps && fabs(h) < eps)
break;
if (h < w)
swap(w, h);
d = h / (pi + 1);
d = min(d, w);
s = pi * d * d * 0.25 * w;
d = 2.0 * h / 3.0;
if (pi * d <= w)
{
d = min(d, w);
s = max(s, pi * h * h * h / 27.0);
}
s = max(s, w * w * (pi * h - w) / (4 * pi * pi));
printf("%.3lf\n", s);
}
return 0;
}
龍貝格積分的基本思想就是先利用復(fù)化梯形公式把曲線劃分若干小區(qū)間，把每個(gè)小區(qū)間當(dāng)成梯形來(lái)求和；然后每次將區(qū)間數(shù)加倍，直到收斂到一定精度范圍內(nèi)為止。
程序基本參照計(jì)算方法的書(shū)寫(xiě)的，但是開(kāi)始寫(xiě)完之后發(fā)現(xiàn)巨慢。找了網(wǎng)上一個(gè)版本和我的比較下，發(fā)現(xiàn)我們倆只是二維數(shù)組的兩個(gè)維代表的含義互換了，但是時(shí)間復(fù)雜度完全相同。后來(lái)改了一下發(fā)現(xiàn)居然快很多，囧。之后可以過(guò)JOJ 2457。但是仍然過(guò)不了HOJ 2539。一旦把精度調(diào)高就TLE，郁悶。
后來(lái)找到了liuyu大牛曾經(jīng)寫(xiě)過(guò)的romberg積分模板，發(fā)現(xiàn)巨快，研究了一下發(fā)現(xiàn)他把那個(gè)T數(shù)組巧妙的壓縮成了一維，但是總時(shí)間復(fù)雜度不變，不知道為什么那么快，也許是因?yàn)槎S數(shù)組遍歷的時(shí)候?qū)ぶ繁容^耗時(shí)間吧。按照他的方法改了下，仍然過(guò)不了，但是這回是WA。找了很久發(fā)現(xiàn)在更新的時(shí)候每次乘以定值就會(huì)WA，用pow才可以過(guò)，估計(jì)是數(shù)據(jù)的精度有問(wèn)題。改了之后終于過(guò)了，速度很快:-)
對(duì)于兩個(gè)n階多項(xiàng)式的乘法，如果模擬做的話復(fù)雜度為O(n^2)，利用快速傅里葉變換可以把復(fù)雜度降到O(nlogn)。
多項(xiàng)式有兩種表示：系數(shù)形式和點(diǎn)值表示。如果把兩個(gè)多項(xiàng)式寫(xiě)成點(diǎn)值形式，那么相乘的復(fù)雜度就是O(n)的。FFT的基本思想就是通過(guò)把系數(shù)形式化成點(diǎn)值形式，相乘之后再化回來(lái)，使得復(fù)雜度降到O(nlogn)。具體就是先通過(guò)巧妙地選取n個(gè)復(fù)數(shù)單位根，利用復(fù)數(shù)的一些非常好的性質(zhì)求得DFT，把這一步的復(fù)雜度降到O(nlogn)，然后將得到的點(diǎn)值相乘后，利用插值再變換成系數(shù)形式。插值的過(guò)程居然和求DFT的過(guò)程驚人的相似，復(fù)雜度依然為O(nlogn)。
在實(shí)現(xiàn)的時(shí)候基本參照算法導(dǎo)論，感覺(jué)遞歸不太好寫(xiě)，就寫(xiě)了個(gè)迭代的。N久不用復(fù)數(shù)了，連基本運(yùn)算都忘了，導(dǎo)致實(shí)現(xiàn)的時(shí)候出了一堆錯(cuò)，后來(lái)好不容易寫(xiě)好了，結(jié)果卻一點(diǎn)都不靠譜。查了好久才發(fā)現(xiàn)，初始w是1的時(shí)候，我把實(shí)部和虛部都設(shè)成1了，囧。實(shí)際上虛部應(yīng)該是0。改完后發(fā)現(xiàn)多項(xiàng)式的表示又出了問(wèn)題，后來(lái)發(fā)現(xiàn)我把系數(shù)的順序?qū)懛戳?。然后利用這個(gè)做了HDU 1402，就是高精度乘法。WA了幾次，很抓狂。后來(lái)寫(xiě)了一個(gè)程序跑了一組極限數(shù)據(jù)，居然掛了。仔細(xì)觀察后發(fā)現(xiàn)是精度的問(wèn)題。因?yàn)镕FT中間運(yùn)算過(guò)程都是浮點(diǎn)數(shù)，但是最后要輸出整數(shù)，取整的時(shí)候舍入精度出了問(wèn)題，加了1e-3之后過(guò)了。
還有一道比較巧妙的FFT的題目，SRM 436 DIV 1 1000pt，做的時(shí)候開(kāi)始Z0忘記取模了，結(jié)果還以為是模板的問(wèn)題，找了很長(zhǎng)時(shí)間才發(fā)現(xiàn)。做題還是要細(xì)心啊。