2020-2021:teams:hotpot:2020nowcoder7
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:2020nowcoder7 [2020/08/07 11:47] misakatao 更新 |
2020-2021:teams:hotpot:2020nowcoder7 [2020/08/07 16:26] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| ===题解=== | ===题解=== | ||
| - | ====B - ==== | + | ====B - Mask Allocation==== |
| - | ===solved by === | + | ===solved by gyp=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给定n,m。将$n\times m$拆成若干个数，使得可以凑成n个m或m个n。输出字典序最大的一种方案 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $n,m\le 10^4$ | ||
| ===题解=== | ===题解=== | ||
| - | ====C - ==== | + | 设$n\ge m$。先输出n/m*m个m，然后将问题转化为求$m\times (n%m)$ |
| - | ===solved by === | + | ====C - A National Pandemic==== |
| + | |||
| + | ===solved by lxh,tyx, written by tyx=== | ||
| ===题意=== | ===题意=== | ||
| + | |||
| + | 在树上，支持以下三种操作： | ||
| + | |||
| + | 1、选定一个点 $i$，别的点 $j$ 的价值都加上 $w[i]-dis(i,j)$。 | ||
| + | |||
| + | 2、选定一个点，它的价值值为 $min(价值，0)$。 | ||
| + | |||
| + | 3、询问某点的价值。 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $1 \le n(点数)、m(询问数) \le 5e4$ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 经过分析后我们可以发现，一次$1$操作，对于任何一个点来说，权值的变化都是 $w-dep[x]-dep[p]+2*dep[k]$ (k是对于任何一个点来说从选定点 $x$ 到根的路径上最近的祖先).对于 $w-dep[x]$ 来说，所有点都是一样的，用一个全局的 $sum$ 来记录就可以。对于 $dep[p]$ 这部分同理记录次数，$2*dep[k]$ 这部分则需要利用树链剖分每次从 $x$ 到根每个点都$+1$，最后查询点时查询到根路径上的和来得到，对于二操作，我们单开一个新数组来记录操作对原值的影响就可以了。 | ||
| ====D - ==== | ====D - ==== | ||
| 行 79: | 行 97: | ||
| ===题解=== | ===题解=== | ||
| - | ====H - Harmony Pairs==== | + | ====H - Dividing==== |
| - | ===solved by === | + | ===solved by gyp=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 定义传奇二元组。(1,k)是传奇二元组，若(n,k)是传奇二元组，则(n+k,k)，(nk,k)是传奇二元组。给定n,k，求$1\le a\le n,1\le b\le k$的传奇二元组(a,b)个数。 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $1\le n,k\le 10^{12}$ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 所有第一个数模第二个数为0或1的均满足要求。数论分块计算个数即可。 | ||
| + | |||
| ====I - ==== | ====I - ==== | ||
2020-2021/teams/hotpot/2020nowcoder7.1596772057.txt.gz · 最后更改: 2020/08/07 11:47 由 misakatao
