先把題目貼出來，總結再說：
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
posted @
2009-05-31 21:53 sdfond 閱讀(859) |
評論 (0) |
編輯 收藏
高斯消元法用于求解線性方程組，采用選主元的方法，算法復雜度O(N ^ 3)。相應的題型一種是在實數域進行求解，一種是在整數域求解，一般涉及到取模。實數域的求解比較簡單，整數域需要注意幾個問題。模p一定是素數，因為不是素數的話求解的時候可能會出現多個解，處理起來比較麻煩。一個特殊的情況是模2域下的求解，可以采用位運算優化。還有一點要注意的是在最開始構造系數矩陣和增廣矩陣的時候，一定要先模p，否則選主元的時候一些模p為0的系數會被誤選。
高斯消元法另一個需要討論的地方就是解的情況。分為無解、唯一解和無窮解。這三種情況根據線性代數的知識很容易判斷，主要就是看系數陣的秩和增廣陣的秩。如果某一次選主元發現當前列的系數都為0，那么對應的變量是一個自由變元，解不確定。這個時候要跳過這一列，保持行不變，繼續進行消元。在消元之后查看增廣陣的秩確定是否無解，若有解再根據自由變元是否存在來判斷是否是唯一解。
如果解是無窮多個的時候，需要枚舉變元的取值。一般用于處理解空間很小的情況，比如在模2域上的求解。枚舉變元后無需重新列方程，只需進行一次回帶找解即可。
posted @
2009-05-26 17:13 sdfond 閱讀(528) |
評論 (0) |
編輯 收藏
題目不難，就是給定一個w * h的紙，中間切一刀，切出來的兩個矩形，從一個中剪下一個圓做圓柱的底，然后讓另一個彎起來套住底，做柱面，最后求能形成的最大體積。
練習的時候做了一下，總是WA。后來仔細想了一想，發現要討論幾種情況。首先要確保圓的直徑要不大于w，之后因為彎曲矩形可以有兩種方式，要分別討論。一種是高為w，這樣只需底面直徑越大越好。一種是高不定，這時候需要列一個方程，求出極值點。可以證明極值就是極大值。但是要注意的是底面圓直徑是有范圍的，要注意極值點是否落在范圍內。如果不在，由于極值點左側單調遞增，那么取直徑為w就是這種情況的最優解。
這種題目比賽的時候很容易出錯，需要靜下心來仔細想好才行，這方面能力以后還要多多鍛煉。
題目代碼：
#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;
}
posted @
2009-05-25 16:10 sdfond 閱讀(324) |
評論 (0) |
編輯 收藏 龍貝格積分的基本思想就是先利用復化梯形公式把曲線劃分若干小區間，把每個小區間當成梯形來求和；然后每次將區間數加倍，直到收斂到一定精度范圍內為止。
程序基本參照計算方法的書寫的，但是開始寫完之后發現巨慢。找了網上一個版本和我的比較下，發現我們倆只是二維數組的兩個維代表的含義互換了，但是時間復雜度完全相同。后來改了一下發現居然快很多，囧。之后可以過JOJ 2457。但是仍然過不了HOJ 2539。一旦把精度調高就TLE，郁悶。
后來找到了liuyu大牛曾經寫過的romberg積分模板，發現巨快，研究了一下發現他把那個T數組巧妙的壓縮成了一維，但是總時間復雜度不變，不知道為什么那么快，也許是因為二維數組遍歷的時候尋址比較耗時間吧。按照他的方法改了下，仍然過不了，但是這回是WA。找了很久發現在更新的時候每次乘以定值就會WA，用pow才可以過，估計是數據的精度有問題。改了之后終于過了，速度很快:-)
posted @
2009-05-20 19:56 sdfond 閱讀(989) |
評論 (0) |
編輯 收藏
對于兩個n階多項式的乘法，如果模擬做的話復雜度為O(n^2)，利用快速傅里葉變換可以把復雜度降到O(nlogn)。
多項式有兩種表示：系數形式和點值表示。如果把兩個多項式寫成點值形式，那么相乘的復雜度就是O(n)的。FFT的基本思想就是通過把系數形式化成點值形式，相乘之后再化回來，使得復雜度降到O(nlogn)。具體就是先通過巧妙地選取n個復數單位根，利用復數的一些非常好的性質求得DFT，把這一步的復雜度降到O(nlogn)，然后將得到的點值相乘后，利用插值再變換成系數形式。插值的過程居然和求DFT的過程驚人的相似，復雜度依然為O(nlogn)。
在實現的時候基本參照算法導論，感覺遞歸不太好寫，就寫了個迭代的。N久不用復數了，連基本運算都忘了，導致實現的時候出了一堆錯，后來好不容易寫好了，結果卻一點都不靠譜。查了好久才發現，初始w是1的時候，我把實部和虛部都設成1了，囧。實際上虛部應該是0。改完后發現多項式的表示又出了問題，后來發現我把系數的順序寫反了。然后利用這個做了HDU 1402，就是高精度乘法。WA了幾次，很抓狂。后來寫了一個程序跑了一組極限數據，居然掛了。仔細觀察后發現是精度的問題。因為FFT中間運算過程都是浮點數，但是最后要輸出整數，取整的時候舍入精度出了問題，加了1e-3之后過了。
還有一道比較巧妙的FFT的題目，SRM 436 DIV 1 1000pt，做的時候開始Z0忘記取模了，結果還以為是模板的問題，找了很長時間才發現。做題還是要細心啊。
posted @
2009-05-18 16:01 sdfond 閱讀(558) |
評論 (0) |
編輯 收藏