#
一點說明:寒假期間的計劃是重寫USACO Chapter3然后寫完Chapter4.現在看來完成有難度.總而言之,寒假的計劃注重熟練程度,速度是其次,“傷其十指，不如斷其一指”.
2011.1.22
agrinet 3WA 90min.[Krusal+Bsort]
2011.1.23
agrinet 1PE 20min.[Krusal+Bsort]
(1)坐標編號中應從0開始.
(2)研究最小生成樹相關問題.
NOIp 2010 第三題,瓶頸生成樹,Wrong. 1.5h
inflate 1Y 15min
完全背包問題
humble 2TLE 90min
45min 讀題錯誤
10min TLE,卡4
2011.1.24
contect 1h 編寫錯誤.
stamp 未寫 20min
[方程] f[i][k] |= f[i-s[t]][k-1]
i表示可拼郵資,k表示已用郵票數,s[t]表示郵資大小.
滾動,24MB.
fact4 8min 1PE [同余分析]
prime3 80min TLE [爆搜]
構造10^4-10^5質數表,五重循環(huán)枚舉.1000*8000^4.
2011.1.25
agrinet 1WA 30min
(1)坐標編號從0開始,減少思維復雜度
(2)直接交換struct指針地址的寫法
2011.1.26
humble 90min 不明.
stamps 40min [DP]
[方程]f[i] = min{f[i], f[i-s[i]]+1} (f[i]<>0)
k,n打反,邊界條件弄反.
stamps 80min [BFS]
失敗.
2011.1.27
stamps 12min 1WA [DP]
Max應為Max+1
UVa 11425 40min 暴力 未完成
{樹狀數組}
UVa 11600 20min 讀題
(數學期望)
rect1 30min 直接灌水模擬
讀題:x為閉區(qū)間，y為開區(qū)間
rect1 100min 矩形切割,討論14種情況,約200行
未完成,參看標程發(fā)現應討論坐標.
[勘誤] 薛矛論文 17種情況.
2011.1.28
rect1 3h 矩形切割
坐標變換,討論5種情況
2011.1.29
agrinet 23min [Kruskal]
(1)指針用法;
(2)注意,的使用.
stamps 27min DP 3WA
f[]數組數據類型
rect1 90min
參考 NOI‘04 薛矛論文, 取公共部分.
USACO放出的最終分數是350,升級線370,差距開始減小了.
題目很簡單，近一個月沒寫題，還是在2h內寫完.最后發(fā)現了最后一題的bug，調試成功后突然發(fā)現超時3min，然后又悲劇了. = =
引gXX神牛:long long 類型使用cout輸出，避免平臺差異.
============================== SUMMARY =============================
-- case number --
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
cropcir * * * * * * * * * *
dishes * * * * * * * * * *
space * * * * * s * * * * * * * * * * s * s
sym * * x * x x x x * *
. = no entry t = time exceeded * = correct answer
x = wrong s = signal e = bad exit status
=======================================================================
Complete results for cropcir --------------------
1: OK [0.01 sec]
2: OK [0.01 sec]
3: OK [0.01 sec]
4: OK [0.00 sec]
5: OK [0.00 sec]
6: OK [0.00 sec]
7: OK [0.00 sec]
8: OK [0.02 sec]
9: OK [0.01 sec]
10: OK [0.01 sec]
Complete results for dishes --------------------
1: OK [0.00 sec]
2: OK [0.01 sec]
3: OK [0.01 sec]
4: OK [0.01 sec]
5: OK [0.00 sec]
6: OK [0.00 sec]
7: OK [0.03 sec]
8: OK [0.03 sec]
9: OK [0.01 sec]
10: OK [0.01 sec]
Complete results for space --------------------
1: OK [0.00 sec]
2: OK [0.01 sec]
3: OK [0.01 sec]
4: OK [0.01 sec]
5: OK [0.00 sec]
6: Wrong: Signal 11 -- segmentation violation [maybe caused by
accessing memory out of bounds, array indexing out of bounds, using a
bad pointer (failed open(), failed malloc), or going over the maximum
specified memory limit]
7: OK [0.16 sec]
8: OK [0.20 sec]
9: OK [0.15 sec]
10: OK [0.01 sec]
11: OK [0.01 sec]
12: OK [0.01 sec]
13: OK [0.01 sec]
14: OK [0.02 sec]
15: OK [0.02 sec]
16: OK [0.03 sec]
17: Wrong: Signal 11 -- segmentation violation [maybe caused by
accessing memory out of bounds, array indexing out of bounds, using a
bad pointer (failed open(), failed malloc), or going over the maximum
specified memory limit]
18: OK [0.12 sec]
19: Wrong: Signal 11 -- segmentation violation [maybe caused by
accessing memory out of bounds, array indexing out of bounds, using a
bad pointer (failed open(), failed malloc), or going over the maximum
specified memory limit]
Complete results for sym --------------------
1: OK [0.01 sec]
2: OK [0.02 sec]
3: Wrong: L1: Wanted 0 got 4
4: OK [0.01 sec]
5: Wrong: L1: Wanted 87381 got 1135957
6: Wrong: L1: Wanted 21845 got 89412949
7: Wrong: L1: Wanted 1398101 got 68506965
8: Wrong: L1: Wanted 1398101 got 68506965
9: OK [0.02 sec]
10: OK [0.00 sec]
1.[3/10,數組開小]
模擬統計.
特別需要注意表中列和行的關系，利用一個q[10][50000]記錄，如果q[1..10][i](1<=i<=50000=N),那么ans++.
【特別注意】測試數據即使行列打反亦可通過.可利用N>50的數據測試，打反會報錯.
2.[AC]
讀入一個整數n(0<n<1e4)，取百位和十位，平方作為隨機數.
當生成兩個相同隨機數時終止.
【testdata】5345
3.[AC]
讀入一個數，每隔三位輸出一個逗號，利用字符串實現
輸出逗號的情況:strlen(n)-i-1|3 && strlen(n)-i-1≠0
用了1.5h，坐等3AC.
果斷23/30,silver線27/30.
坐等2011 Jan 7-10 USACO Monthly Bronze.
上次7/30,這次23/30..為什么實力和發(fā)揮總是差這么大 = =
果斷去做Silver...聽取gXX神牛建議果斷contest.
Summary of USACO Monthly Bronze of Nov1.daisy(20)
題目給出一個無向圖，和若干組邊，輸出從1出發(fā)不能到達的邊.
[邊界]沒有結果則輸出0
【Fllodfill(DFS)】
1.c1 c2關系不一定
2.無向圖，遍歷從1開始
3.邊界條件
4.vis數組記錄
2.marathon(20)
裸的三值排序，O(n^2)即可
【標準算法使用hash】
0.少打一個等號
3.數據類型錯誤
USACO Monthly Nov2005Flood fill的某特性，
計算過的點可以去掉NOIp 2009【潛伏者】
注意“一一映射”
【Hankson的趣味題】
注意
內存NOIp 2007【字符串的展開】
注意讀題，考慮特殊情況，不要被題目迷惑
【矩陣取數】
dp，
高精度調試不能NOIp 1999 攔截導彈多次計算最長連續(xù)不上升子序列，可以將計算過的值變?yōu)?1，循環(huán)時排除.
[原文鏈接]http://www.coderspace.net/bbs/viewthread.php?tid=119&extra=page%3D1
看了這份非官方的NOIp大綱，還是弱不禁風.不過分治、貪心似乎被無視了.
目前指熟練掌握了1/3，還有近1/2的部分不熟練，聯想起"不要總想著AC"，需要大量做題了.
排序：
(1,5)冒泡/選排(這個很常用，一定要保證正確性)
(2,5)快排(Pascal選手可以去FPC文件夾里找代碼,C/C++選手注意sort的正確性)
(3,4)歸并排序(最好要會，因為有可能有題要卡快排)
數據結構：
(2,2)循環(huán)隊列(節(jié)省空間用)
(2,4)單調隊列(DP里經常用)
(1,3)完全二叉樹的數組存儲
(2,5)并查集(一定要會路徑壓縮)
(3,4)圖的前向星存法
(4,2)Trie樹，后綴數組(這些學過的就再復習一下，沒學過就不用看了，估計考的概率不大)
(3,2)森林轉二叉樹(樹狀DP常用)
動態(tài)規(guī)劃：
(1,5)基本的背包問題(一定要熟練寫出方程，尤其注意邊界的取值)
(3,4)多線程DP(二取方格數)
(3,2)LIS的二分優(yōu)化
(2,4)DP的隊列優(yōu)化(LCIS，單調隊列很常用的)
(3,4)樹狀DP(其實就是記憶化搜索，很好理解)
圖論：
(1,5)最短路(dijkstra,floyd,spfa)
(2,5)最小生成樹(prim,kruskal)
(2,5)拓撲排序
(2,3)floyd求最小環(huán)
(3,4)求(有向/無向)圖的強連通分量
(1,3)判斷圖中是否有環(huán)
(3,2)圖的關鍵路徑
(4,1)差分約束系統(就是求最長路，用spfa)
其他：
(2,4)RMQ問題的ST算法(LCA問題也可以轉化為RMQ問題)
(4,5)高精度的加減乘除開方(開方一般情況下直接二分比較方便)
(3,4)表達式求值(棧或并查集皆可，一般來說并查集比較容易實現)
(2,2)擴展歐幾里得算法(解同余方程用)
(1,5)乘法轉加法神器：log
(1,4)求最大子序列和的備忘錄算法
(2,3)位運算優(yōu)化搜索(N皇后問題，建議去USACO做一下)
(4,2)搜索剪枝(推薦做USACO的fence rail那題)
第一講 時空分析
(1)時間復雜度
(2)空間復雜度
第二講 排序算法
n較大 【快速排序】
n較小 【冒泡排序】
n較大 n值較小 【計數排序】
取n的最值 【堆排序】
n較大 要求穩(wěn)定性 【歸并排序】
第三講 線性數據結構
1.棧
(1)DFS的顯式寫法 => 類似BFS
(2)回溯 => DFS+狀態(tài)還原
【求總方案數或者最優(yōu)方案問題】
2.隊列
BFS
【求最少操作次數】
第四講 樹形結構的應用
1.二叉排序樹 O(nlogn)
遞歸構造
2.哈夫曼樹 => 堆實現
3.樹狀數組 => 鄰接表
【貌似NOIp超綱】
1.參考書籍
【全國青少年信息學競賽培訓教材:復賽】
http://www.amazon.cn/gp/product/B003VD3RXA/ref=oss_product剛買的新書，感覺比較貼近復賽實際，涉及了大部分算法，尤其是dp的分類非常贊，唯一的缺陷是搜索比較少.書中的內容基本上都學過，權當系統復習，務必搞透.
【算法競賽入門經典】
大部分章節(jié)都看過，重點研究后面的部分，這本書搜索和數學方面內容更多一些.
【程序設計中常用的計算思維方式】
整體比較難，但是例題還可以看懂，看一部分吧.
2.題目
A.USACO Monthly 銅組&銀組，從后往前做吧 - -
http://oj.jzxx.net/searchproblemB.USACO Training 的搜索&dp&圖論
C.歷年試題
D.各種模擬題(NOI導刊etc) => 不一定要做，訓練對于題目的選擇能力
3.別的貌似沒了...
題目風格什么年年換,歷年試題權當參考，僅此而已.
在眾多神牛的推薦下，開始寫USACO Monthly銀銅組，發(fā)現一個不錯的網站，收錄的歷年USACO月賽的所有題目：
重啟usaco.
抽象出模型,可以發(fā)現是一個簡單的完全背包問題,復雜度O(N^2+VN).需要考慮幾種特殊情況:
(1)無解
當且僅當n個數中有一個數為1.
(2)惟一解
需要確定的是體積v的最大值.題解中是最大的兩個數的最小公倍數,程序中使用最大數的平方,證明方法不知.
(3)無限解
n個數不互質
1
/**//*
2
ID: liuyupa1
3PROG: nuggets
4LANG: C++
5
*/
6
#include<stdio.h>
7int w[15] = 
{0}, f[66000] = {0};
8int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251};
9void swap(int *x, int *y){
10 int k = *x; *x = *y; *y = k;
11}
12int max(int x, int y){
13 return x>y ? x : y;
14}
15int main(){
16 FILE *fin, *fout;
17 fin = fopen("nuggets.in", "r");
18 fout = fopen("nuggets.out", "w");
19 int n, i, j;
20 fscanf(fin, "%d", &n);
21 for (i = 1; i <= n; i++) fscanf(fin, "%d", &w[i]);
22
for (j = 0; j < 54; j++){
23 int t = 0;
24 for (i = 1; i <= n; i++)
25 if (w[i] % p[j] == 0) t++;
26 if (t == n) {
27 fprintf(fout, "0\n", p[j]);
28 return 0;
29
}
30 }
31 for (i = 1; i < n; i++)
32 for (j = i+1; j <= n; j++)
33 if (w[i] > w[j]) swap(&w[i], &w[j]);
34 if (w[1] == 1){
35 fprintf(fout, "0\n", p[j]);
36 return 0;
37 }
38 for (i = 1; i <= n; i++)
39 for (j = 0; j <= w[n]*w[n]; j++)
40 if (j-w[i] >= 0)
41 f[j] = max(f[j], f[j-w[i]]+w[i]);
42 i = w[n-1]*w[n];
43 while (i > -1 && f[i] == i) i--;
44 fprintf(fout, "%d\n", i);
45 return 0;
46}
47