「BZOJ3757」苹果树

神犇家门口种了一棵苹果树。苹果树作为一棵树,当然是呈树状结构,每根树枝连接两个苹果,每个苹果都可以沿着一条由树枝构成的路径连到树根,而且这样的路径只存在一条。由于这棵苹果树是神犇种的,所以苹果都发生了变异,变成了各种各样的颜色。我们用一个到n之间的正整数来表示一种颜色。树上一共有n个苹果。每个苹果都被编了号码,号码为一个1到n之间的正整数。我们用0代表树根。只会有一个苹果直接根。

继续阅读「BZOJ3757」苹果树

简短说明

以后这个网站上的项目会咕掉一阵子,博客会继续写。

[BZOJ3697] 采药人的路径

采药人的药田是一个树状结构,每条路径上都种植着同种药材。采药人以自己对药材独到的见解,对每种药材进行了分类。大致分为两类,一种是阴性的,一种是阳性的。采药人每天都要进行采药活动。他选择的路径是很有讲究的,他认为阴阳平衡是很重要的,所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的,所以他希望他选出的路径中有一个可以作为休息站的节点(不包括起点和终点),满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。

如XHT大佬所说,这是点分治裸题一个。

继续阅读[BZOJ3697] 采药人的路径

CF1009G Allowed Letters 题解

题目链接

这一道题题面大概是有一个包含a,b,c,d,e,f六种字符的字符串(长度为n),要求它的一个重新排列的字符串,其中有m位可能有对填写的字母的限制。其中保证

$$n,m\leq10^5$$

要求输出字典序最小的可能解,如果无解输出”Impossible”。

继续阅读CF1009G Allowed Letters 题解