【暑假Aug】Problems
NanoApe
posted @ 2015年8月05日 16:37
in 蒟蒻不比赛何来学费
, 568 阅读
[CF 566A]
给2n个字符串,两两配对使得lcp最大。
贪心,在一棵子树上若有两种子串的结尾节点的话就配对,剩余的就扔到父亲集中。
【然而一开始想的是Trie上跑费用流,可怎么求方案?并不会。。。】【这种思想比贪心不知神到哪里去了】
[CF 567E]
给一有向图,问某条边有没有可能是最短路网的桥(就是走最短路必须经过这条边),若不是则需要减少多少边值才能满足要求?
两边跑个最短路,然后求最短路网内的桥边,再判断需要减少多少边值。【求桥边的正确姿势并不会】【自己都是乱搞】
[CodeVS #1 C]
有两棵树,加一条边连接起来形成树S,求S的最短直径和期望直径
预处理出每个点与树中所有点的最远距离,和每棵树的直径长度,然后O(n)扫一遍求最短直径,期望直径就排序后O(n)扫一遍
[STSR #2 B]
求\(\sum_{x=1}^n\sum_{y=1}^n gcd(x,y)(n\le10^9)\)
记忆化搜索\(f_k(n)=\sum_{x=1}^n\sum_{y=1}^n [gcd(x,y)=k]\)其中有两种性质:\(f_k(n)=f_1(n/k)\)和\(\sum_{i=1}^nf_i(n)=n*n\)
[STSR #2 C]
维护向量集,支持插入和删除向量,以及询问某个向量的点积最大值。
对于每次询问可以知道答案一定在凸壳上。以时间为轴建线段树,离线处理所有点存在的时间区间,插入线段树,树上每个点维护凸壳。\(O(nlog^2n)\)的复杂度。
Aug 07, 2015 06:54:15 AM
ORZkpm