Luogu3576 POI2014 MRO-Ant colonyThe ants are scavenging an abandoned ant hill in search of food. The ant hill has nn chambers and n-1n−1 corridors con...

设i点的度数为d[i]则如果有x只蚂蚁在从i走到别处，会分裂成每群$\lfloor\frac{x}{d[i]-1}\rfloor$只蚂蚁对于x出发的m只蚂蚁，到y处还剩$\lfloor\frac{m}{x到y路径上所有点度数-1的乘积}\rfloor$于是我们一遍DFS求出到每个叶子节点时一路上点度...

传送门ber~怎么又在刷水/糗大了 预处理每个点到问题中的边剩k个的上下界。。。 然后二分。。。。 我是卡常大师啦啦啦 把函数改成define就过了/呲牙代码如下：#include<algorithm>#include<ctype.h>#include<cstdio&g...

因为下取整可以合并，即a/b/c=a/bc，且我们只关心经过某一条边< s,t>的蚂蚁，将树以< s,t>为界砍成两棵树，分别以s，t为根，那么我们只关心这两棵树的叶子到根上方时，有多少个k 对于子树中的叶子i，他走到根上方的分母f[i]已经确定，可以做个简单的dp求，这个叶...

啊我把分子分母混了WA了好几次……就是从食蚁兽在的边段成两棵树，然后dp下去可取的蚂蚁数量区间，也就是每次转移是l[e[i].to]=l[u](d[u]-1),r[e[i].to]=(r[u]+1)(d[u]-1)-1，这里注意当l>maxm的时候就return，不然之后的没有贡献而且会爆lo...

Ant colony bzoj-3872 Poi-2014题目大意：说不明白.....题目链接注释：略。想法：两个思路都行。反正我们就是要求出每个叶子节点到根节点的每个路径权值积。可以将边做为代理根。或者将边断掉。最后，附上丑陋的代码... ...#include <cstdio>#in...

 Luogu3576 POI2014 MRO-Ant colonyThe ants are scavenging an abandoned ant hill in search of food. The ant hill has nn chambers and n-1n−1 corridors co...

DescriptionThere is an entrance to the ant hill in every chamber with only one corridor leading into (or out of) it. At each entry, there are \(g\) gr...

传送门一群蚂蚁能被吃,也就是走到指定边的两端点之一要走到另一端点时有\(k\)只,我们可以从这两端点逆推,记两个值为走到某个点时最后会被吃掉\(k\)只蚂蚁的蚂蚁数量范围,式子下面有,很好理解(雾).最后在每个叶子节点二分查找有多少个数在区间内即可// luogu-judger-enable-o2#...

题目地址：http://codeforces.com/contest/474/problem/F 由题意可知，最后可以留下来的一定是区间最小gcd。那就转化成了该区间内与区间最小gcd数相等的个数。区间最小gcd一定小于等于区间最小值，所以只要求最小值的个数。然后用r-l+1-个数即可。 对于以...

题目地址：http://codeforces.com/contest/474/problem/F 由题意可知，最后可以留下来的一定是区间最小gcd。那就转化成了该区间内与区间最小gcd数相等的个数。区间最小gcd一定小于等于区间最小值，所以只要求最小值的个数。然后用r-l+1-个数即可。 对于以...