Main » 2014 January 4 » 【批量题解】【14.1.4—14.1.10 】
12:45 PM 【批量题解】【14.1.4—14.1.10 】 |
[HNOI2002]营业额统计：set水过 Code:b1588UPD:这批题总算撸完了 囧，其实主要是因为维修数列太坑人了。。。[SHOI2008]汉诺塔:对于任意的优先级，一定存在n>3 f[n]=a*f[n-1]+b 于是我们可以算出f[3],f[4],f[5]然后推出a和b然后算。 Code:b1019[NOI2005]维修数列:这道就是让我抽风的题 Splay维护两个标记加上LMax,RMax,Max_Sum和Sum,注意在 update里面最好先pushdown一下它和两个孩子 还有旋转完 不要忘记update(goal) 这里为了空间，我们得牺牲delete的效率，一个个删除，把废结点扔进栈里，之后再循环使用。 Code:b1500[HNOI2004]宠物收养所:set水过。。。 Code:b1208Zju2112 Dynamic Rankings:这题其实是平衡树套线段树，我用主席树水过了。Code:b1901[Noi2008]志愿者招募:线性规划转费用流，可以看by void的题解 Code:b1061[JSOI2008]最小生成树计数:生成树定理：所有最小生成树的边值集合相同，集合中同边值的边构成的联通分量相同。然后就可以DFS+斌茶几搞了 Code:b1016[HNOI2008]Cards:学了一下群论。。这题给你的洗牌法是满足群性质的，解法是burnside定理+DP。Code:b1004[SHOI2008]堵塞的交通traffic:线段树维护矩形左上/下 和 右上/下的联通性，同时顺便维护同一侧两个点的连通性，查询的时候为了防止路线绕圈，除了查询[L,R]外还要查询[1,L]和[L,R] 。这题细节很多 ，比较恶心，不好写。建议update时做传递闭包。Code:b1018 [ZJOI2010]network 网络扩容:第二问对残余网络加上附属边，并限流为K，注意：不用清除退边，因为可能还需要退流。Code:b1834[JSOI2007]字符加密Cipher:裸的后缀数组. Code:b1031 |
|
|
| Total comments: 0 | |