期末考期间作死囤题的我12月乱做——囤题计划4
- [Upd 2016.12.29] 话说统一下格式会死吗……写了4份囤题用了4种格式……还好我不是处女……
- [Upd 2016 1.6]今天CF研究了shift-and算法，居然超时我&^(^*&)
- [Upd 2016.1.9] 居然丢失了一部分文档……已经补在后面了……
- [Upd 2016.1.10] 过了facebookHackCup的资格赛……因为网络延时只交了1题好气啊……投诉主席！不过还好总算是过了.今天栗子考完电磁场了大家会不会轻松一点？
【BZOJ 1209:[HNOI2004]最佳包裹】3d凸包
【BZOJ 4247: 挂饰】 背包
int n;
struct arr{
ll a[10000];
ll &operator[](int i) {
if (i<-n) i=-n; if (i>n) i=n;
return a[5000+i];
}
}f;
//这个数组写法好评【BZOJ 1071: [SCOI2007]组队】将题意化简为平面上有一堆点，你需要用某个直角三角形（保证直角边平行坐标轴不能旋转斜边方向为\），问最多能框住几个点。
O(n^2)暴力双指针，这里注意斜边顺序入队，丨边顺序出队。
【BZOJ 4373: 算术天才⑨与等差数列】hash+线段树
【BZOJ 4589: Hard Nim】裸的FFT，见正文
【BZOJ 3670: [Noi2014]动物园】kmp
【BZOJ 2561: 最小生成树】只要看出是最小割就行了。
【BZOJ 2761: [JLOI2011]不重复数字】暴力
【BZOJ 1189: [HNOI2007]紧急疏散evacuate】BFS计算出每个人离每个出口的距离，网络流，二分+拆点，注意一个人不能路过一个出口到达另一个出口（因为出口格子有人数限制）d。
【BZOJ 4551: [Tjoi2016&Heoi2016]树】倒序，并查集
【BZOJ 4195: [Noi2015]程序自动分析】 并查集
【BZOJ 4196: [Noi2015]软件包管理器】 树链剖分
BZOJ 4197: [Noi2015]寿司晚宴】小素数状压dp，每次处理一个大素数
【BZOJ 4198: [Noi2015]荷马史诗】 哈夫曼树，如果k>2时，要通过填0使$n\mod(k-1)=1$
【BZOJ 4199: [Noi2015]品酒大会】
【BZOJ 4128: Matrix】？？？ BSGS 矩阵
【BZOJ 4180: 字符串计数】矩阵乘法+SAM// 不想写
【BZOJ 4747: [Usaco2016 Dec]Counting Haybales】set
【BZOJ 4748: [Usaco2016 Dec]Cities and States】哈希
【BZOJ 4749: [Usaco2016 Dec]Moocast】暴力建图
【BZOJ 4746: [Usaco2016 Dec]Lasers and Mirrors】直接bfs（变为权限题无法提交）
【BZOJ 2302: [HAOI2011]Problem c】组合数学
【BZOJ 4036: [HAOI2015]按位或】论文题
http://ydc.blog.uoj.ac/blog/336
【BZOJ 4766: 文艺计算姬】矩阵树定理
【BZOJ 4519: [Cqoi2016]不同的最小割】Gusfield算法
【BZOJ 4320: ShangHai2006 Homework】分段讨论
【BZOJ 2671: Calc】mobius反演
大爷题解：http://blog.csdn.net/popoqqq/article/details/45095601
【BZOJ 2661: [BeiJing wc2012]连连看】费用流
【BZOJ 2751: [HAOI2012]容易题(easy)】没修改的数用快速幂求解，修改的暴力
【BZOJ 2731: [HNOI2012]三角形覆盖问题】
【BZOJ 3224: Tyvj 1728 普通平衡树】Treap
【BZOJ 3196: Tyvj 1730 二逼平衡树】Treap
【BZOJ 2733: [HNOI2012]永无乡】Treap+启发式合并
【BZOJ 3287: Mato的刷屏计划】打表找规律
【BZOJ 1797: [Ahoi2009]Mincut 最小割】如何判断一条边在不在最小割上（残余网络跑强连通分量）
【BZOJ 1951: [Sdoi2010]古代猪文】lucas+费马小定理
【BZOJ 4776: [Usaco2017 Open]Modern Art】想法题，2维前缀和
【BZOJ 4804: 欧拉心算】mobius反演
【BZOJ 4805: 欧拉函数求和】杜教筛
【BZOJ 4809: 皇后】就是n皇后
【BZOJ 4800: [Ceoi2015]Ice Hockey World Championship】meet in the middle 搜素，数据范围提示了
【BZOJ 4807: 車】 $ans=C(max(n,m),min(n,m))$
【BZOJ 4808: 马】二分图最大独立集
【BZOJ 1801: [Ahoi2009]chess 中国象棋】dp,$f[i][j][k]$为前i行有j列有一个炮 k列有两个炮
【BZOJ 4801:[Lydsy2017年4月月赛]打牌】分类讨论
【BZOJ 4810: [Ynoi2017]由乃的玉米田】bitset+莫队
【BZOJ 4811: [Ynoi2017]由乃的OJ】树链剖分
【BZOJ 4542: [Hnoi2016]大数】如果$gcd(p,10)=1$,显然一个子串是k的倍数当且仅当它的2个后缀mod p余数相同。
当p是2，5的时候可以根据最后一位判断。
这2种情况都可以用莫队。
【BZOJ 4813: [Cqoi2017]小Q的棋盘】由于起点必须是0号点，不难发现最优决策是走最远点，此时最长链上的边代价为1，其余为2，注意考虑能访问的点不能超过点数
【BZOJ 1078: [SCOI2008]斜堆】模拟斜堆的操作，发现最后一个节点是从根往左一直走直到第一个没有右节点的节点（如果有左节点再向左走一步，那么倒推即可
【BZOJ 4806: 炮】同BZOJ 1801
【BZOJ 3242: [Noi2013]快餐店】树形dp，要么最远点在同一颗树上（dp），要么在不同树上，此时答案=去掉任何一条边后形成的树的答案的最小值，我们枚举去掉的那条边。
由于答案=s[i]-s[j]+dis[i]+dis[j]，i，j可以分开考虑，也可以用线段树解决。
【BZOJ 4878: [Lydsy2017年5月月赛]挑战NP-Hard】染色问题，每次沿边染max，注意最后如果颜色数超过k，则可以按(k+1)-k-...-1的简单路径