• 「CF543X」Codeforces Round #302 (Div. 1)

    「CF543X」Codeforces Round #302 (Div. 1)

    本场血崩A.WritingCode显然的n^3dp,滚动数组[crayon-5b519c7a8cb14296816318/]B.DestroyingRoadsn个结点,m条边的无向图(边权全为1),问最多能删掉多少条边使得s1到t1距离不超过l1,s2到t2距离不超过l2。\(1\leqn\leq500,1\leqm\leqn(n-1)/2\)题解其实就是问,至少需要多少条边,才能使得s1到t1距离不超过l1,s2到t2距离不超过l2。如果这两条路径不相交,那么答案为dis(s1,t1)+dis(s2,t2)。如果相交部分为(p1,p2),答案为p1,p2的...

  • 「BZOJ4027」[HEOI2015] 兔子与樱花

    「BZOJ4027」[HEOI2015] 兔子与樱花

    Description很久很久之前,森林里住着一群兔子。有一天,兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由n个树枝分叉点组成,编号从0到n-1,这n个分叉点由n-1个树枝连接,我们可以把它看成一个有根树结构,其中0号节点是根节点。这个树的每个节点上都会有一些樱花,其中第i个节点有c_i朵樱花。樱花树的每一个节点都有最大的载重m,对于每一个节点i,它的儿子节点的个数和i节点上樱花个数之和不能超过m,即so...

    02015年4月27日4,160贪心,树形动规
  • 「BZOJ3572」[HNOI2014] 世界树

    「BZOJ3572」[HNOI2014] 世界树

    Description 世界树是一棵无比巨大的树,它伸出的枝干构成了整个世界。在这里,生存着各种各样的种族和生灵,他们共同信奉着绝对公正公平的女神艾莉森,在他们的信条里,公平是使世界树能够生生不息、持续运转的根本基石。世界树的形态可以用一个数学模型来描述:世界树中有n个种族,种族的编号分别从1到n,分别生活在编号为1到n的聚居地上,种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连,道路的长度为1。保...

    22015年4月21日7,439虚树,树形动规
  • 「BZOJ3573」[HNOI2014] 米特运输

    「BZOJ3573」[HNOI2014] 米特运输

    Description米特是D星球上一种非常神秘的物质,蕴含着巨大的能量。在以米特为主要能源的D星上,这种米特能源的运输和储存一直是一个大问题。D星上有N个城市,我们将其顺序编号为1到N,1号城市为首都。这N个城市由N-1条单向高速通道连接起来,构成一棵以1号城市(首部)为根的树,高速通道的方向由树中的儿子指向父亲。树按深度分层:根结点深度为0,属于第1层;根结点的子节点深度为1,属于第2层;依此类推,深度为i的结点...

    02015年4月21日2,495树形动规
  • 「BZOJ1912」[Apio2010] patrol 巡逻

    「BZOJ1912」[Apio2010] patrol 巡逻

    DescriptionInput第一行包含两个整数n,K(1≤K≤2)。接下来n–1行,每行两个整数a,b,表示村庄a与b之间有一条道路(1≤a,b≤n)。Output输出一个整数,表示新建了K条道路后能达到的最小巡逻距离。SampleInput8112313453758556SampleOutput11HINT10%的数据中,n≤1000,K=1;30%的数据中,K=1;80%的数据中,每个村庄相邻的村庄数不超过25;90%的数据中,每个村庄相邻的村庄数不超过150;100%的数据中,3≤n≤100,000,1...

    02015年4月9日2,916树形动规
  • 「BZOJ3522」[POI2014] Hotel

    「BZOJ3522」[POI2014] Hotel

    Description有一个树形结构的宾馆,n个房间,n-1条无向边,每条边的长度相同,任意两个房间可以相互到达。吉丽要给他的三个妹子各开(一个)房(间)。三个妹子住的房间要互不相同(否则要打起来了),为了让吉丽满意,你需要让三个房间两两距离相同。有多少种方案能让吉丽满意?Input第一行一个数n。接下来n-1行,每行两个数x,y,表示x和y之间有一条边相连。Output让吉丽满意的方案数。SampleInput7125725235645SampleOutp...

    02015年4月2日2,058树形动规
  • 「NOIP模拟赛」小奇的仓库

    「NOIP模拟赛」小奇的仓库

    原题:「East!_XI」第一个问题2015年10月4日hzwer改写了题面「题目背景」小奇采的矿实在太多了,它准备在喵星系建个矿石仓库。令它无语的是,喵星系的货运飞船引擎还停留在上元时代!「问题描述」喵星系有n个星球,星球以及星球间的航线形成一棵树。从星球a到星球b要花费[dis(a,b)XorM]秒。(dis(a,b)表示ab间的航线长度,Xor为位运算中的异或)为了给仓库选址,小奇想知道,星球i(1<=i<=n)到其它所有星球花费的时...

    32015年3月30日1,925树形动规
  • 「CF519X」Codeforces Round #294 (Div. 2)

    「CF519X」Codeforces Round #294 (Div. 2)

    「cf519A」AandBandChess模拟[crayon-5b519c7a8eefb227249425/]「cf519B」AandBandCompilationErrors排序,双指针对比用个hash/map统计下元素出现次数[crayon-5b519c7a8ef05130824343/]「cf519C」AandBandTeamTraining实际上答案是min(n,m,(m+n)/3)我分类讨论了TAT还是很好yy的[crayon-5b519c7a8ef0a167025717/]「cf519D」AandBandInterestingSubstringsa[i][j]表示前缀和为i,字母j为末尾的前缀数量每次查询...

  • 「BZOJ1369」[Baltic2003] Gem

    「BZOJ1369」[Baltic2003] Gem

    Description给出一棵树,要求你为树上的结点标上权值,权值可以是任意的正整数唯一的限制条件是相临的两个结点不能标上相同的权值,要求一种方案,使得整棵树的总价值最小。Input先给出一个数字N,代表树上有N个点,N<=10000下面N-1行,代表两个点相连Output最小的总权值SampleInput107512178941975610293SampleOutput14题解WJMZBMR:这题首先是不能用奇偶层染色的办法来做的,我构造出了至少需要1-3的反例,同时...

    02015年2月27日1,886树形动规
  • 「codechef」February Lunchtime 2015

    「codechef」February Lunchtime 2015

    懒得开多篇了LuckyFour 这题在逗我么[crayon-5b519c7aa5b1c200117741/]TheWarehouse发现实际上把一个东西移动到一个位置相当于不断做代价为1的交换所以只要枚举给3种字母赋权,求逆序对最小值即可[crayon-5b519c7aa5b24583664169/]Heavy-lightDecompositions设f[i][j]表示i为根的子树,后代到i经过轻边数量不超过j树形dp,要用到前缀后缀积/逆元。。。[crayon-5b519c7aa5b2b494413536/]  TheFirstCube 一眼分...

  • 「BZOJ2815」[ZJOI2012] 灾难

    「BZOJ2815」[ZJOI2012] 灾难

    小强和阿米巴0.0fhq神犇的题==http://fanhq666.blog.163.com/blog/static/8194342620124274154996/[crayon-5b519c7aa606e562599628/] 

  • 「BZOJ3162」独钓寒江雪

    「BZOJ3162」独钓寒江雪

    Description题解参照2007杨弋论文vfk的博客http://vfleaking.blog.163.com/blog/static/17480763420134452440444/太神了orzorzorz[crayon-5b519c7aa6776049379160/]  

    72015年1月28日2,842树形动规,哈希表