Alan233

未归档

题解(7)

/ 注册

全部文章 / 未归档（共7篇）

【每日一题4.13】Xorto

Description 给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。 Solution 我们假设选定的两个区间，靠左的为左区间，靠右的为右区间。注意到异或的性质：，于是我们只需要左区间异或值等于右区间异或值即可。我们固定右区间的左端点，记为，那么我们要...

2020-04-13

0 733

CF513E2 Subarray Cuts

Subarray Cuts 题目链接：CF513E2 Subarray Cuts Description 给定一个长度为的数组，你需要从中按顺序选出个不重复、不相交的子串，定义为第个子串的和，你需要最大化。数据范围 Solution 我们考虑拆开绝对值，对于一段单调递增/递减的子串，结...

2020-04-10

1 863

旗鼓相当的对手

旗鼓相当的对手题目链接：牛客旗鼓相当的对手 Description 给定一个个点的树，每个节点有点权。如果为和的，并且和不等于且树上距离为，那么点的答案就会加上。求所有点的答案。数据范围。 Solution 长链剖分板子。表示子树深度为的节点数表示...

2020-04-10

2 776

【好题推荐】Steps to One

Steps to One 题目链接：CF1139D Steps to One Description 给定一个数列，每次随机选一个到之间的数加到数列的末尾，数列中的所有数的时停止，求期望长度。答案对取模。数据范围。 Solution 考虑概率dp我们定义表示当前所有的数时，还需要加...

2020-04-08

4 907

【好题推荐】Accumulation Degree

https://ac.nowcoder.com/acm/problem/51180 Description 给你一颗有个节点的树，每一条边连接和，流量为，你需要找出一个点作为，并最大化从该点出发到所有叶子节点的流量最大值。多组数据。（PS：题意读不懂的可以结合题目中的图理解，类似网络...

2020-04-08

4 971

【牛客OI周赛15-提高组】T3

T3 Solution 我们先判断答案是否存在，即这几个物品能否凑成，如果不能，答案则为。否则的话，我们易知：不同体积的物品不超过个。我们可以用分治的思想来解决该题。令表示保留到区间的物品，其余的物品已经塞入背包时的状态，我们用一个bitset来维护。那么，考虑如何分治转移。令，则当我们要进行时，就...

2020-04-08

0 696

【牛客OI周赛15-提高组】T2

Solution 我们来考虑什么情况下才有解。首先一个数分解成个数，那么我们可以默认，一共有个。我每次如果要拆分，则要将个数拆分成个数，所以增加了个数。所以，有解的充要条件是，即。接下来，直接按上述方式构造即可。 Code // Author: wlzhouzhuan #pragma GCC opt...

2020-04-08

0 546