【暑假Aug】Problems

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

给2n个字符串，两两配对使得lcp最大。

贪心，在一棵子树上若有两种子串的结尾节点的话就配对，剩余的就扔到父亲集中。

【然而一开始想的是Trie上跑费用流，可怎么求方案？并不会。。。】【这种思想比贪心不知神到哪里去了】

给一有向图，问某条边有没有可能是最短路网的桥（就是走最短路必须经过这条边），若不是则需要减少多少边值才能满足要求？

两边跑个最短路，然后求最短路网内的桥边，再判断需要减少多少边值。【求桥边的正确姿势并不会】【自己都是乱搞】

有两棵树，加一条边连接起来形成树S，求S的最短直径和期望直径

预处理出每个点与树中所有点的最远距离，和每棵树的直径长度，然后O(n)扫一遍求最短直径，期望直径就排序后O(n)扫一遍

求\(\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\)

维护向量集，支持插入和删除向量，以及询问某个向量的点积最大值。

对于每次询问可以知道答案一定在凸壳上。以时间为轴建线段树，离线处理所有点存在的时间区间，插入线段树，树上每个点维护凸壳。\(O(nlog^2n)\)的复杂度。

[回复]

ORZkpm

NanoApe's Blog