BZOJ_3872_[Poi2014]Ant colony_dfs

时间:2022-11-02 19:20:09

BZOJ_3872_[Poi2014]Ant colony_dfs

Description

There 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 groups of m1,m2,...,mg ants respectively. These groups will enter the ant hill one after another, each successive group entering once there are no ants inside. Inside the hill, the ants explore it in the following way:
Upon entering a chamber with d outgoing corridors yet unexplored by the group, the group divides into d groups of equal size. Each newly created group follows one of the d corridors. If d=0, then the group exits the ant hill.
If the ants cannot divide into equal groups, then the stronger ants eat the weaker until a perfect division is possible. Note that such a division is always possible since eventually the number of ants drops down to zero. Nothing can stop the ants from allowing divisibility - in particular, an ant can eat itself, and the last one remaining will do so if the group is smaller than d.
The following figure depicts m ants upon entering a chamber with three outgoing unexplored corridors, dividing themselves into three (equal) groups of floor(m/3) ants each.
A hungry anteater dug into one of the corridors and can now eat all the ants passing through it. However, just like the ants, the anteater is very picky when it comes to numbers. It will devour a passing group if and only if it consists of exactly k ants. We want to know how many ants the anteater will eat.
给定一棵有n个节点的树。在每个叶子节点,有g群蚂蚁要从外面进来,其中第i群有m[i]只蚂蚁。这些蚂蚁会相继进入树中,而且要保证每一时刻每个节点最多只有一群蚂蚁。这些蚂蚁会按以下方式前进:
·在即将离开某个度数为d+1的点时,该群蚂蚁有d个方向还没有走过,这群蚂蚁就会分裂成d群,每群数量都相等。如果d=0,那么蚂蚁会离开这棵树。
·如果蚂蚁不能等分,那么蚂蚁之间会互相吞噬,直到可以等分为止,即一群蚂蚁有m只,要分成d组,每组将会有floor(m/d)只,如下图。
BZOJ_3872_[Poi2014]Ant colony_dfs
一只饥饿的食蚁兽埋伏在一条边上,如果有一群蚂蚁通过这条边,并且数量恰为k只,它就会吞掉这群蚂蚁。请计算一共有多少只蚂蚁会被吞掉。

Input

The first line of the standard input contains three integers n, g, k (2<=n,g<=1000000, 1<=k<=10^9), separated by single spaces. These specify the number of chambers, the number of ant groups and the number of ants the anteater devours at once. The chambers are numbered from 1 to n.
The second line contains g integers m[1],m[2],...,m[g](1<=m[i]<=10^9), separated by single spaces, where m[i] gives the number of ants in the i-th group at every entrance to the ant hill. The n-1 lines that follow describe the corridors within the ant hill; the i-th such line contains two integers a[i],b[i] (1<=a[i],b[i]<=n), separated by a single space, that indicate that the chambers no.a[i] and b[i] are linked by a corridor. The anteater has dug into the corridor that appears first on input.
第一行包含三个整数n,g,k,表示点数、蚂蚁群数以及k。
第二行包含g个整数m[1],m[2],...,m[g],表示每群蚂蚁中蚂蚁的数量。
接下来n-1行每行两个整数,表示一条边,食蚁兽埋伏在输入的第一条边上。

Output

Your program should print to the standard output a single line containing a single integer: the number of ants eaten by the anteater.
一个整数,即食蚁兽能吃掉的蚂蚁的数量。

Sample Input

7 5 3
3 4 1 9 11
1 2
1 4
4 3
4 5
4 6
6 7

Sample Output

21

 倒过来做,以最后输入的两端为根dfs整棵树。
求出每个点的蚂蚁数目范围,满足最后走到根时恰好剩下k个蚂蚁。
对于最大值upper[to[i]]=upper[x]*(out[x]-1)+out[x]-2.out[x]表示x的度数。
对于最小值lower[to[i]]=lower[x]*(out[x]-1)。
可能中间过程爆longlong,当最小值比总数大的时候就不必继续dfs下去。
然后对于每个初始的叶子结点二分查找一下合法蚂蚁的个数。
 
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd() {
register int x=0;
register char s=nc();
while(s<'0'||s>'9')s=nc();
while(s>='0'&&s<='9')x=(x<<3)+(x<<1)+s-'0',s=nc();
return x;
}
#define N 1000050
typedef long long ll;
int head[N],to[N<<1],nxt[N<<1],out[N],cnt;
int m[N],n,g,k,root1,root2;
ll upper[N],lower[N];
inline void add(int u,int v) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; out[u]++;
}
void dfs(int x,int y) {
int i;
for(i=head[x];i;i=nxt[i]) {
if(to[i]!=y) {
upper[to[i]]=upper[x]*(out[x]-1)+out[x]-2;
if(upper[to[i]]<0) upper[to[i]]=m[g];
upper[to[i]]=min(upper[to[i]],1ll*m[g]);
lower[to[i]]=lower[x]*(out[x]-1);
if(lower[to[i]]<=m[g]&&lower[to[i]]>=0)
dfs(to[i],x);
}
}
}
int search(ll x) {
int l=1,r=g+1;
while(l<r) {
int mid=(l+r)>>1;
if(m[mid]<=x) l=mid+1;
else r=mid;
}
return l-1;
}
int main() {
n=rd(); g=rd(); k=rd();
int i,x,y;
for(i=1;i<=g;i++) m[i]=rd();
sort(m+1,m+g+1);
root1=rd(); root2=rd();
add(root1,root2); add(root2,root1);
for(i=2;i<n;i++) {
x=rd(); y=rd();
add(x,y); add(y,x);
}
upper[root1]=upper[root2]=lower[root1]=lower[root2]=k;
dfs(root1,root2);
dfs(root2,root1);
ll ans=0;
for(i=1;i<=n;i++) if(out[i]==1) ans+=search(upper[i])-search(lower[i]-1);
printf("%lld\n",ans*k);
}

BZOJ_3872_[Poi2014]Ant colony_dfs的更多相关文章

  1. &lbrack;BZOJ3872&rsqb;&lbrack;Poi2014&rsqb;Ant colony

    [BZOJ3872][Poi2014]Ant colony 试题描述 There is an entrance to the ant hill in every chamber with only o ...

  2. bzoj 3872&colon; &lbrack;Poi2014&rsqb;Ant colony -- 树形dp&plus;二分

    3872: [Poi2014]Ant colony Time Limit: 30 Sec  Memory Limit: 128 MB Description   There is an entranc ...

  3. 【BZOJ3872】&lbrack;Poi2014&rsqb;Ant colony 树形DP&plus;二分

    [BZOJ3872][Poi2014]Ant colony Description 给定一棵有n个节点的树.在每个叶子节点,有g群蚂蚁要从外面进来,其中第i群有m[i]只蚂蚁.这些蚂蚁会相继进入树中, ...

  4. &lbrack;bzoj3872&rsqb;&lbrack;Poi2014&rsqb;Ant colony&lowbar;树形dp

    Ant colony bzoj-3872 Poi-2014 题目大意:说不明白.....题目链接 注释:略. 想法:两个思路都行. 反正我们就是要求出每个叶子节点到根节点的每个路径权值积. 可以将边做 ...

  5. &lbrack;POI2014&rsqb;Ant colony

    题目大意: 给定一棵$n(n\le10^6)$个结点的树.在每个叶子结点,有$g$群蚂蚁要从外面进来,其中第$i$群有$m_i$只蚂蚁.这些蚂蚁依次爬树(一群蚂蚁爬完后才会爬另一群),若当前经过结点度 ...

  6. bzoj 3872 &lbrack;Poi2014&rsqb;Ant colony——二分答案

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3872 可以倒推出每个叶子节点可以接受的值域.然后每个叶子二分有多少个区间符合即可. 注意一开 ...

  7. bzoj 3872&colon; &lbrack;Poi2014&rsqb;Ant colony【树形dp&plus;二分】

    啊我把分子分母混了WA了好几次-- 就是从食蚁兽在的边段成两棵树,然后dp下去可取的蚂蚁数量区间,也就是每次转移是l[e[i].to]=l[u](d[u]-1),r[e[i].to]=(r[u]+1) ...

  8. &dollar;bzoj3872&bsol; &lbrack;Poi2014&rsqb;&bsol; Ant&bsol; colony&dollar; 二分&plus;&dollar;dp&dollar;

    正解:二分+$dp$ 解题报告: 传送门$QwQ$ 一年过去了依然没有头绪,,,$gql$的$NOIp$必将惨败了$kk$. 考虑倒推,因为知道知道除数和答案,所以可以推出被除数的范围,然后一路推到叶 ...

  9. POI2014题解

    POI2014题解 [BZOJ3521][Poi2014]Salad Bar 把p当作\(1\),把j当作\(-1\),然后做一遍前缀和. 一个合法区间\([l,r]\)要满足条件就需要满足所有前缀和 ...

随机推荐

  1. &lbrack;原&rsqb; Cgroup CPU&comma; Blkio 测试

    关于Cgroup的简单测试 [toc] 简单介绍Cgroup (如果对cgroup熟悉可以忽略) 一般情况下,cgroup挂载到一个虚拟文件目录,然后可以通过文件系统的API对其操作. ># m ...

  2. (原创)android Sqlite多线程访问异常解决方案

    在开发Android的程序的时候sqlite数据库是经常用到的:在多线程访问数据库的时候会出现这样的异常:java.lang.IllegalStateException: Cannot perform ...

  3. 造成win2008 500内部错误不能显示详细错误的原因和解决方法

    造成500错误常见原因有:ASP语法出错.ACCESS数据库连接语句出错.文件引用与包含路径出错.使用了服务器不支持的组件如FSO等. 另外,对于win2008的IIS默认不显示详细出错信息的问题以下 ...

  4. 用手机或外部设备在同一局域网下访问虚拟主机wampsever的方法版本号是2&period;4&period;9

    1,首先在虚拟服务器电脑上可以打开http://localhost/ 2,在外部设备访问时报错为:You don't have permission to access / in on this se ...

  5. &lt&semi;自动化测试方案&lowbar;5&gt&semi;第五章、代码单元自动化测试

    第五章.代码单元自动化测试 代码单元测试需要根据编程语言,选择单元测试框架,然后访问类方法,函数.代码单元测试做自动化,相比API.UI自动化做起来更加麻烦,建议放到待API自动化测试.UI自动化测试 ...

  6. OGG-01028 Incompatible Record解决办法

    How to recover from an OGG-01028 Incompatible Record if the trail is not corrupt (Doc ID 1507462.1) ...

  7. Java网络通信方面,BIO、NIO、AIO、Netty

    码云项目源码地址:https://gitee.com/ZhangShunHai/echo 教学视频地址:链接: https://pan.baidu.com/s/1knVlW7O8hZc8XgXm1dC ...

  8. 4&period; Median of Two Sorted Arrays &lpar;二分法;递归的结束条件)

    There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two ...

  9. QQ开发技术资料集锦

    1.GG2013:可在广域网部署运行的QQ高仿版 http://www.cnblogs.com/justnow/category/503400.html 2. 苏飞博客: C#仿QQ皮肤-皮肤控件窗体 ...

  10. spm教程

    1.spm初学者教程:http://www.ernohermans.com/wp-content/uploads/2011/11/spm8_startersguide.pdf 2.spm官方mannu ...