sdoi2014专题

P3313 [SDOI2014] 旅行(分块做法)

~~~~~      P3313 [SDOI2014] 旅行 ~~~~~      总题单链接 思路 ~~~~~      遇到这种树上路径问题,就考虑用重链剖分转为区间问题。 ~~~~~      问题转换为了:给定一个区间和 k k k,求这个区间内信仰为 k k k 的城市的 权值和 或 最大权值。 ~~~~~      这个问题也可以用动态开点线段树解决(现在不会,以后

【bzoj3529】【SDOI2014】【数表】【莫比乌斯反演+树状数组】

Description 有一张N×m的数表,其第i行第j列(1 < =i < =礼,1 < =j < =m)的数值为 能同时整除i和j的所有自然数之和。给定a,计算数表中不大于a的数之和。 Input 输入包含多组数据。 输入的第一行一个整数Q表示测试点内的数据组数,接下来Q行,每行三个整数n,m,a(|a| < =10^9)描述一组数据。 Output 对每组数据,输出一行一个整数

BZOJ3529 : [Sdoi2014]数表(反演+BIT)

SDOI真的是什么毒瘤题都有qwq 这个题首先推式子的步骤我就不说了 最后长这个样子:(N<=M) (f(d)代表约数和函数) ∑T=1N⌊NT⌋⌊MT⌋∑d|Tf(d)∗μ(Td) ∑ T = 1 N ⌊ N T ⌋ ⌊ M T ⌋ ∑ d | T f ( d ) ∗ μ ( T d ) \sum_{T=1}^N \lfloor\frac N T\rfloor \lfloor

BZOJ3531 [Sdoi2014]旅行——树剖+动态开点线段树

Description S国有N个城市,编号从1到N。城市间用N-1条双向道路连接,满足 从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教,如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便,我们用不同的正整数代表各种宗教, S国的居民常常旅行。旅行时他们总会走最短路,并且为了避免麻烦,只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标

BZOJ 3531 [Sdoi2014]旅行

Description S国有N个城市,编号从1到N。城市间用N-1条双向道路连接,满足 从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教,如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便,我们用不同的正整数代表各种宗教, S国的居民常常旅行。旅行时他们总会走最短路,并且为了避免麻烦,只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标

bzoj3531 [Sdoi2014]旅行

传送门 Description S国有N个城市,编号从1到N。城市间用N-1条双向道路连接,满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教,如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便,我们用不同的正整数代表各种宗教, S国的居民常常旅行。旅行时他们总会走最短路,并且为了避免麻烦,只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个