upd 5.7

终于完结了。

提交的过程中胆战心惊可是还是有wa有T，没完成50题太遗憾。

截图为证：

（再也不想屯题了）

听说日AC50题十分炫酷，我决定也来干一发，不知道能不能在二试前屯完？

现在屯了几道了？                                                   50

//list

（可能漏了一些没写上了来）

upd 5.6

(3502: PA2012 Tanie linie & 2288: 【POJ Challenge】生日礼物) 把符号相同的可以合并在一起。先把正数取完。如果序列个数大了，那么考虑每次只能删掉一个正数或者拿进来一个负数。用堆维护。感觉要手写堆所以就写multiset了。各种细节很麻烦。写了一上午。

upd 4.30

1887: Spoj 3974. Another Tree Problem f[i]表示经过i的路径积之和。dfs过程中枚举孩子计算即可。

3555: [Ctsc2014]企鹅QQ  呵呵卡死我的哈希。以后再也不写模10^9+7的可怕的哈希了。要写自然溢出的双哈希！三哈希也好！改成自然溢出都能A，而且又短又快233。

upd 4.29

2012: [Ceoi2010]Pin 跟day1T1一样0 0  就是要注意“仅”。 所以……就容斥呗，搞清楚每种被多算了几次即可。

3207: 花神的嘲讽计划Ⅰ 哈希。直接暴力的map套set不能跟愉悦。

2301: [HAOI2011]Problem b 就是POI的ZAP 0 0算四部分就好了

2423: [HAOI2010]最长公共子序列 就是普通的dp。算LCS的同时记录方案数即可。

upd 4.28

煞笔哈希被卡感觉不会再爱了还是太naive

3550: [ONTAK2010]Vacation 设[tex]x_i[/tex]表示第[tex]i[/tex]个数取不取，那我们只要满足对于所有[tex]i(1 \leq i \leq 2n+1)[/tex]，都有[tex]\sum_{j=i}^{i+n-1} x_j \leq k[/tex]，然后要最大化[tex]\sum_{i=1}^{3n} x_i W_i[/tex]。裸的线性规划。转成对偶。以为要T结果A了 0 0。

3543: [ONTAK2010]Garden hehehe

upd 4.27 

最近的一些题具体日期忘了。另明天ctsc day1求rp++。

2986: Non-Squarefree Numbers  二分之后容斥。或者算miu也行。

3549: [ONTAK2010]Tower  USACO2009 原题 单调队列搞一搞

3124: [Sdoi2013]直径 答案一定是一条简单路径，随意找出一条直径然后一直缩小范围即可

2441: [中山市选2011]小W的问题  扫描线从下往上移动，一开始记录每个点左上角的点个数。后面维护每个点左上角且在扫描线上方的点的个数。这样只涉及到区间减。线段树即可。

3545: [ONTAK2010]Peaks  比较弱所以一开始写的就是离线。启发式合并。

3542: DZY Loves March 煞笔题攒人品。线段树。没了。

upd 4.22

3544: [ONTAK2010]Creative Accounting 搞出mod m的前缀和，然后set维护一下不就好了？

upd 4.19

3527: [Zjoi2014]力 裸FFT。考场上没看出卷积桑心的不能多说。

3528: [Zjoi2014]星系调查  用kb表示直线似乎比用abc表示直线舒服许多。设[tex]y=kx+b[/tex]，那我们要最小化的就是[tex]\sum \frac{(kx_i+b-y_i)^2}{k^2+1}[/tex]。显然[tex]b=-k \overline{x}+\overline{y}[/tex]会最优。我们暴力的拆开它，

[tex]\sum \frac{k^2(x^2_i+\overline{x}^2-2x_{i} \overline{x}) + 2k(x_{i}\overline{y}-\overline{x}\overline{y}-x_{i}y_{i}+\overline{x}y_{i})+(\overline{y}^2+y^2_{i}-2\overline{y}y_{i})}{k^2+1}[/tex]

这么一来，显然我们需要维护[tex]\sum x[/tex],[tex]\sum y[/tex],[tex]\sum xy[/tex],[tex]\sum x^2[/tex],[tex]\sum y^2[/tex]，还有点的个数即可。

把以上三个庞大的系数用[tex]A,B,C[/tex]代替，则我们只要求[tex]\frac{Ak^2+Bk+C}{k^2+1}[/tex]的极值，令其值为[tex]t[/tex]，则[tex](A-t)k^2+Bk+C-t=0[/tex]，显然极值会取在[tex]\Delta = 0[/tex]时，解一下即可。

（练习一下tex仅此而已）

upd 4.18

3519: [Zjoi2014]消棋子  昨天闲得DT打算艹一发这道题。结果后来没A。今天又多写了个3k然后还是wa然后对拍然后手画大样例然后就发现漏写了一句很重要的话！然后就A了！方法当然是set乱搞。

upd 4.15

3531: [Sdoi2014]旅行  对于每一种宗教建主席树，维护树链剖分，复杂度[tex]\text{O}(n \text{log}^2 n)[/tex]。

upd 4.14

2223: [Coci 2009]PATULJCI 原题 同3524

3538: [Usaco2014 Open]Dueling GPS

3539: [Usaco2014 Open]Odometer

3540: [Usaco2014 Open]Fair Photography

三道usaco silver的题 见前一篇（第一题看错题目了= =

upd 4.13

3530: [Sdoi2014]数数 AC自动机+数位dp 233333

upd 4.11

3523 : [Poi2014] Bricks 奇葩的贪心多的能拿就拿然后根据颜色是不是第一个或最后一个乱搞 OK99 只好羞耻的特判0 求正常向的做法

3337 : ORZJRY I 哈哈哈深藏功与名，突然发现这题我还没交过。裸的块链当时出的用来积(bao)攒(fu)人(she)品(hui)的。

upd 4.10

3524 : [Poi2014] Couriers  单个询问的版本见bzoj2456。沿用这个思想，倍增（怕线段树慢）记录每个点往右延伸2^k的cnt和ans。合并时ans相等则cnt相加，否则ans是cnt大的那个，cnt减去小的cnt。最后二分判断一下这个数是否合法。（正确性怎么证明？TAT）

upd 4.9

3521 : [Poi2014] Salad Bar （再多做一点然后就可以把题目扔到bzoj上了？233反正迟早是bzoj上的题）O(n)预处理出每个点向左向右最远到达的距离，然后就是类似二维数点的东西，用树状数组O(nlogn)。一开始用了快速排序，结果一直98分。（卡你*的常数！）然后改成基数排序就OK了。= =

3522 : [Poi2014] Hotels 枚举这三个点的lca，然后对于每种深度dp即可。O(n^2)

upd 4.8

2792: [Poi2012]Well 二分答案显然，之后就是用单调队列维护贪心。详见hza爷爷的题解。

3505: [Cqoi2014]数三角形 随意选3个的方案数减去共线的方案数。枚举向量即可。

3504: [Cqoi2014]危桥 网络流。直接建图。把源汇都交换一次再跑一遍。两次都满足就行了。

upd 4.5

2788: [Poi2012]Festival 考虑差分约束系统，建图之后tarjan求scc。一个scc内的用floyd求出最长路即可，最后加起来就行。

3481: DZY Loves Math III 一阵推导然后剖了肉分解算各个质因子的答案相乘即可。计算答案时可以推出一个公式的（一开始先写了个暴力枚举结果6s AC？）然后就是注意Q=0太坑，long long乘爆太坑，快速乘一定要选用O(1)的不然慢出翔。

upd 4.4

3509: [CodeChef] COUNTARI 枚举中间点，然后两边FFT这样复杂度是n^2logn的。那么就可以分块，块内暴力，块两边FFT。块的个数取在45的时候似乎跑的最快，在cc上rank3（前两个代码一样，似乎不是FFT，看起来很神），可是在bzoj上就特慢，玩了好久的常数才过。

upd 4.2

2791: [Poi2012]Rendezvous  基环加外向树。在一棵树内就LCA，否则讨论一下经过环的两种情况即可。

upd 4.1

2796: [Poi2012]Fibonacci Representation 一个数最少能通过几个fibonacci数表达出来。例如19=21-2，最少只要两个。10组询问，n≤4×10^17。直接搜？肯定要选离当前最近的fib数，然后继续搜下去。用map记忆化一下感觉更靠谱。

3060: [Poi2012]Tour de Byteotia    先把两端都大于K的边取走，之后尽量取，用并查集维护即可。

upd 3.31

2802: [Poi2012]Warehouse Store  依次枚举，如果能拿就拿，不然和之前拿过的最大值（用堆维护即可）比较一下，比当前的大就替换掉。

2803: [Poi2012]Prefixuffix  由于这个循环同构的串一定能表示成AB....BA，枚举A，然后就是快速计算B了。令F[i]表示S[i..|S|-i+1]最长相同的前后缀。可以发现F[i]≤F[i+1]+2。这样复杂度就是O(|S|)了。使用hash判字串相等。

upd 3.30

2790: [Poi2012]Distance  把dist(a,b)转化成a的质因子个数+b的质因子个数-2*[gcd(a,b)的质因子个数]，预处理枚举gcd()保留最小值，由于i≠j，需要保留次小值。

2793: [Poi2012]Vouchers  暴力统计2333，记录每种数下一次拿的位置，这么一来复杂度还是靠谱的。n=100w需要适当常数优化。

• 相关文章