期末考期间作死囤题的我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的简单路径