2020-2021:teams:hotpot:2020nowcoder7
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:2020nowcoder7 [2020/08/07 11:23] 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 - ==== | ||
| 行 98: | 行 123: | ||
| ===题解=== | ===题解=== | ||
| - | ====J - ==== | + | ====J - Pointer Analysis==== |
| - | ===solved by === | + | ===solved by tyx=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给出26个Pointer用大写字母表示，26个object用小写字母表示，每个object还有26个field，然后给出四种指向关系的赋值方式，问最后每个Pointer指向了哪些object | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | 略 | ||
| ===题解=== | ===题解=== | ||
| - | ====K - ==== | + | 模拟题，要注意给出的赋值语句是可以调换顺序的，所以不能只做一遍，我们按照最坏情况，处理一遍以后第一个赋值语句被增加了一个，所以只需要重复处理26遍即可 |
| - | ===solved by === | ||
| - | |||
| - | ===题意=== | ||
| - | |||
| - | ===数据范围=== | ||
| - | |||
| - | ===题解=== | ||
| =====Replay===== | =====Replay===== | ||
2020-2021/teams/hotpot/2020nowcoder7.1596770631.txt.gz · 最后更改: 2020/08/07 11:23 由 misakatao
