=====比赛信息===== * **日期：2020.8.1** * **比赛地址：** [[https://ac.nowcoder.com/acm/contest/5672?&headNav=www#rank|传送门]] * **做题情况：lxh(C)，tyx(J)，gyp(BDH)** =====题解===== ====A - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====B - Mask Allocation==== ===solved by gyp=== ===题意=== 给定n,m。将$n\times m$拆成若干个数，使得可以凑成n个m或m个n。输出字典序最大的一种方案 ===数据范围=== $n,m\le 10^4$ ===题解=== 设$n\ge m$。先输出n/m*m个m，然后将问题转化为求$m\times (n%m)$ ====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 - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====E - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====F - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====G - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====H - Dividing==== ===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 - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====J - Pointer Analysis==== ===solved by tyx=== ===题意=== 给出26个Pointer用大写字母表示，26个object用小写字母表示，每个object还有26个field，然后给出四种指向关系的赋值方式，问最后每个Pointer指向了哪些object ===数据范围=== 略 ===题解=== 模拟题，要注意给出的赋值语句是可以调换顺序的，所以不能只做一遍，我们按照最坏情况，处理一遍以后第一个赋值语句被增加了一个，所以只需要重复处理26遍即可 =====Replay===== 第一小时：gyp和tyx发现D题是签到题于是直接开写，但是发现用cin超时了，改成scanf后通过。gyp开始想H并通过，tyx和lxh开始想B 第二小时：tyx写的B一直WA，随后gyp和lxh发现方法有问题，修正后通过。tyx开始想J，gyp和lxh开始想C 第三小时：tyx写出J并通过，随后加入gyp和lxh开始想C 第四小时：三个人想出了C，但是写起来非常复杂，由于lxh临时有事所以tyx开始写 第五小时：tyx写完了C但是WA了两次，后来发现是因为多组数据有一小部分没有初始化，更改后通过 =====总结===== * 为了以防万一尽量不使用cin和cout进行输入输出