#
一点说明:寒假期间的计划是重写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质数表,五重循环枚举.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为闭区间，y为开区间
rect1 100min 矩形切割,讨论14种情况,约200行
未完成,参看标程发现应讨论坐标.
[勘误] 薛矛论文 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内写完.最后发现了最后一题的bug，调试成功后突然发现超时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..为什么实力和发挥总是差这么大 = =
果断去做Silver...听取gXX神牛建议果断contest.
Summary of USACO Monthly Bronze of Nov1.daisy(20)
题目给出一个无向图，和若干组边，输出从1出发不能到达的边.
[边界]没有结果则输出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 拦截导弹多次计算最长连续不上升子序列，可以将计算过的值变为-1，循环时排除.
[原文链接]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)循环队列(节省空间用)
(2,4)单调队列(DP里经常用)
(1,3)完全二叉树的数组存储
(2,5)并查集(一定要会路径压缩)
(3,4)图的前向星存法
(4,2)Trie树，后缀数组(这些学过的就再复习一下，没学过就不用看了，估计考的概率不大)
(3,2)森林转二叉树(树状DP常用)
动态规划：
(1,5)基本的背包问题(一定要熟练写出方程，尤其注意边界的取值)
(3,4)多线程DP(二取方格数)
(3,2)LIS的二分优化
(2,4)DP的队列优化(LCIS，单调队列很常用的)
(3,4)树状DP(其实就是记忆化搜索，很好理解)
图论：
(1,5)最短路(dijkstra,floyd,spfa)
(2,5)最小生成树(prim,kruskal)
(2,5)拓扑排序
(2,3)floyd求最小环
(3,4)求(有向/无向)图的强连通分量
(1,3)判断图中是否有环
(3,2)图的关键路径
(4,1)差分约束系统(就是求最长路，用spfa)
其他：
(2,4)RMQ问题的ST算法(LCA问题也可以转化为RMQ问题)
(4,5)高精度的加减乘除开方(开方一般情况下直接二分比较方便)
(3,4)表达式求值(栈或并查集皆可，一般来说并查集比较容易实现)
(2,2)扩展欧几里得算法(解同余方程用)
(1,5)乘法转加法神器：log
(1,4)求最大子序列和的备忘录算法
(2,3)位运算优化搜索(N皇后问题，建议去USACO做一下)
(4,2)搜索剪枝(推荐做USACO的fence rail那题)
第一讲 时空分析
(1)时间复杂度
(2)空间复杂度
第二讲 排序算法
n较大 【快速排序】
n较小 【冒泡排序】
n较大 n值较小 【计数排序】
取n的最值 【堆排序】
n较大 要求稳定性 【归并排序】
第三讲 线性数据结构
1.栈
(1)DFS的显式写法 => 类似BFS
(2)回溯 => DFS+状态还原
【求总方案数或者最优方案问题】
2.队列
BFS
【求最少操作次数】
第四讲 树形结构的应用
1.二叉排序树 O(nlogn)
递归构造
2.哈夫曼树 => 堆实现
3.树状数组 => 邻接表
【貌似NOIp超纲】
1.参考书籍
【全国青少年信息学竞赛培训教材:复赛】
http://www.amazon.cn/gp/product/B003VD3RXA/ref=oss_product刚买的新书，感觉比较贴近复赛实际，涉及了大部分算法，尤其是dp的分类非常赞，唯一的缺陷是搜索比较少.书中的内容基本上都学过，权当系统复习，务必搞透.
【算法竞赛入门经典】
大部分章节都看过，重点研究后面的部分，这本书搜索和数学方面内容更多一些.
【程序设计中常用的计算思维方式】
整体比较难，但是例题还可以看懂，看一部分吧.
2.题目
A.USACO Monthly 铜组&银组，从后往前做吧 - -
http://oj.jzxx.net/searchproblemB.USACO Training 的搜索&dp&图论
C.历年试题
D.各种模拟题(NOI导刊etc) => 不一定要做，训练对于题目的选择能力
3.别的貌似没了...
题目风格什么年年换,历年试题权当参考，仅此而已.
在众多神牛的推荐下，开始写USACO Monthly银铜组，发现一个不错的网站，收录的历年USACO月赛的所有题目：
重启usaco.
抽象出模型,可以发现是一个简单的完全背包问题,复杂度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