NanoApe's Blog

既是咸鱼又是辣鸡

【暑假Aug】Problems

NanoApe posted @ 2015年8月05日 16:37 in 蒟蒻不比赛何来学费 , 571 阅读

[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)\)的复杂度。

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter