AFO后做题记录1

[ABC240Ex] Sequence of Substrings

考题T3，菜飞，显然把所有串搞出来之后DP， \(dp[i]\) 表示 \(1-i\) 的字符的答案，能推出： \(dp[r[i]]=max(dp[r[i]],max(dp[1-l[i]])+1)\) ，显然能用数据结构优化到 \(nlogn\) ，那么现在如何去把子串搞出来，对于每一个后缀建trie，考虑最优情况下一个串最大是多少，可以卡住上界进而优化时间，那么 \(1+2+...+m<=n\) ，所以 \(m<= \sqrt{2n}\) ，那么就是 \(O(n\sqrt{n}logn)\) 了

P4303 [AHOI2006] 基因匹配

考虑到LCS转移方程只可能 \(a[i]==b[j]\) 的时候答案增加，所以处理出每一个数出现的5个位置，就是转移的位置，然后构成一个 \(5n\) 长度的序列，然后就是经典 \(LIS\) 问题了

P5785 [SDOI2012] 任务安排

\(O(n^2)\) 感觉很好推，\(dp[i]\) 表示答案，显然 \(dp[i]=min(dp[i],dp[j]+S*(sumF[n]-sumF[j])+sum[i]*(sumF[i]-sumF[j])))\) ，然后拆开，斜率优化掉，但发现斜率 \(sumt[i]\) 不一定单调，所以要二分找第一个满足前一个小于等于它后一个大于等于它的东西作为转移点，即这条直线第一次切到的凸包上的点。然而也能李超线段树，避免出错没有选择ds

P5495 Dirichlet 前缀和

发现贡献只有 \(i|k\) 的时候 \(i\) 才会产生贡献，由唯一分解定理有， \(i\) 分解质因数后的次幂一定小于对应 \(k\) 的次幂，然后就相当于是选子集，想到高维前缀和DP，那么把质数次幂当作维度，做个高维前缀和就行了，实际上通过暴力算贡献去优化去理解同样也能得到相同的式子

[ARC100E] Or Plus Max

SOSDP板子，DP最大值次大值，最后取前缀max即为答案

CF499D Jzzhu and Numbers

二进制下恰好为 \(i\) 个 \(1\) ，通过子集反演能够去想到 至少为 \(0\) 的个数-至少为 \(1\) 的个数+至少为 \(2\) 个 \(1\) - \(...\) 的个数定义 \(f[i]\) 表示状态为 \(i\) 二进制下 \(i\) 超集的个数，显然对于所有的超集任意选除了空集，都能保证二进制下 \(1\) 的个数大于 \(i\) ，统计超集显然SOSDP，算出贡献容斥计算即可

P4503 [CTSC2014] 企鹅 QQ

哈希正反做，卡模数，用的是周可质数2009021220090529和铁铮质数99824435320081103就过了 /tyt