https://ac.nowcoder.com/acm/problem/51180 Description 给你一颗有 个节点的树，每一条边连接 和 ，流量为 ，你需要找出一个点作为 ，并最大化从该点出发到所有叶子节点的流量最大值。多组数据。（PS：题意读不懂的可以结合题目中的图理解，类似网络流的流法）数据范围 ，并且 时间限制  Solution 我们先默认这棵树以 为根，跑一次 。定义 表示以 为根的子树中流量最大值。那么， 节点从儿子 得到的流量为：1.若为叶子节点，那么（可以直接流过来）；2.若为非叶子节点，那么（和相连的边有流量限制）。这样，我们得到了以 为根时的答案，记为 ，它的值...

T3 Solution 我们先判断答案是否存在，即这几个物品能否凑成，如果不能，答案则为。否则的话，我们易知：不同体积的物品不超过个。我们可以用分治的思想来解决该题。令表示保留到区间的物品，其余的物品已经塞入背包时的状态，我们用一个bitset来维护。那么，考虑如何分治转移。令，则当我们要进行时，就先将的物品依次插入； 同理。复杂度，可以通过 Code 下面是我考场写的丑陋代码 // Author: wlzhouzhuan #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using n...

Solution 我们来考虑什么情况下才有解。首先一个数分解成个数，那么我们可以默认，一共有个。我每次如果要拆分，则要将个数拆分成个数，所以增加了个数。所以，有解的充要条件是，即。接下来，直接按上述方式构造即可。 Code // Author: wlzhouzhuan #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define rint ...

题意: 给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。  题解 最先想到的是枚举[L,R]区间内的每一个数,然后求和。考虑如何优化。我们发现只用写出最高位出现的次数所以下来就是来计算每个 对应的区间比如 那么最后决定答案的是什么?不就是 在范围的倍数的个数如然后呢就是如果每一个都要计算的话,那么时间复杂度为 ,这样接着超时(弥天大雾)举个例子 ,在 的符合的倍数的个数都为 个,所以就可以相当于111*9,然后就可以跳过一部分枚举区间时间复杂度:  ...

Shortest Path 题目链接：Shortest Path Description 给定一颗个节点的树，保证为偶数。你需要将这个节点分成个点对，并最小化这个点对的距离之和。多组数据。数据范围  Solution 这其实是一道CF原题，原题既需要最小化值，也需要最大化值。下面来谈谈最小化值。既然是想要最小化，那么我们希望每一条边被访问的次数越少越好。如果有一条以为父亲，为儿子的边，它的权值为，我们想尽可能少次数得经过它。我们先跑一次，记录每一个节点的子树大小，如果为奇数，说明我在这个子树内无论如何匹配，总有一个点会被孤立的，那么这个点一定要经过到的这条边，所以这条边的贡献是；否则我一定可以...

Running Median 题目链接：Running Median Description 给定一个数列 ，你需要输出前个数中的中位数分别是多少。多组数据。数据范围  Solution 我们先考虑暴力。对于前个数，我们可以用一个桶来记录一下所有数的出现情况，然后取第个数即可。考虑如何优化暴力。我们发现，从前个数到前个数，其实只是新加了两个数和，所以我们可以用数据结构来维护。我们考虑用两个优先队列来模拟这一过程。第一个优先队列（大根堆），我们用来维护这个数中从小到大，排名小的数集合；第二个优先队列（小根堆），我们用来维护这个数中从小到大，排名小的数集合。显然中位数就是第二个优先队列的头。每次新...

昨日直播中奖的50元，在兑换处哪个地方提现呢？   感激不尽。