Main » 2013 December 21 » 【13.12.21—27】批量题解
10:39 AM 【13.12.21—27】批量题解 |
[Zjoi2013]K大数查询：主席树。注意外面是权值，里面是区间。这样树套树才可以。由于这道题学到了标记永久化。 Code:b3110UPD：[SCOI2005]扫雷Mine:水DP Code:b1088UPD：[JSOI2008]火星人prefix:用splay维护子串的hash值，一直被卡常数啊，后来发现玩long long作死了。Code:b1014UPD：[ZJOI2013]蚂蚁寻路:ZJOI史上难有的DP水题。 Code:b3111UPD：[ZJOI2006]物流运输trans:刚开始没想到。囧。由于数据范围极小，因此有了非常暴力的做法，求出任意两天间不改变航线的代价，用区间DP合并答案。Code:b1003UPD：[HNOI2008]水平可见直线:先将这些直线按斜率排序，然后用栈维护下凸线即可 Code:b1007UPD：[JSOI2008]Blue Mary的战役地图:二维的RKHash，看了CLJ的博客才知道要换seed 看来数据有专门卡不换seed的,不过很暴力好像，我只写到了O(n^3log(n^2)) Code:b1567UPD：[HAOI2008]圆上的整点:x^2+y^2=r^2 --> y=sqrt((r+x)(r-x)) 令 d=gcd(r+x,r-x) ,a=(r+x)/d,b=(r-x)/d; 则a,b一定是完全平方数 (因为a*b是完全平方数，且gcd(a,b)=1),然后设u^2=a,v^2=b,先枚举d，再枚举u,v即可 Code:b1041UPD：[HNOI2006]鬼谷子的钱袋:大水题啊，可是我竟然想不到二进制。Code:b1192UPD：屯题... 1017 1010 1009 2038 3240 1560 1036 1067 1005 in BZOJ |
|
|
| Total comments: 0 | |