2020-2021:teams:hotpot:2020nowcoder7
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:2020nowcoder7 [2020/08/07 11:05] misakatao 创建 |
2020-2021:teams:hotpot:2020nowcoder7 [2020/08/07 16:26] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| =====比赛信息===== | =====比赛信息===== | ||
| - | * **日期：2020.7.27** | + | * **日期：2020.8.1** |
| - | * **比赛地址：** [[https://ac.nowcoder.com/acm/contest/5671#rank|传送门]] | + | * **比赛地址：** [[https://ac.nowcoder.com/acm/contest/5672?&headNav=www#rank|传送门]] |
| - | * **做题情况：lxh(-)，tyx(EJK)，gyp(BC)** | + | * **做题情况：lxh(C)，tyx(J)，gyp(BDH)** |
| =====题解===== | =====题解===== | ||
| 行 19: | 行 19: | ||
| ===题解=== | ===题解=== | ||
| - | ====B - Binary Vector==== | + | ====B - Mask Allocation==== |
| ===solved by gyp=== | ===solved by gyp=== | ||
| 行 25: | 行 25: | ||
| ===题意=== | ===题意=== | ||
| - | 从0和1构成n维向量里随机选n个，求这n个线性无关的概率 | + | 给定n,m。将$n\times m$拆成若干个数，使得可以凑成n个m或m个n。输出字典序最大的一种方案 |
| ===数据范围=== | ===数据范围=== | ||
| - | $1\le n\le 2\cdot 10^7$ | + | $n,m\le 10^4$ |
| ===题解=== | ===题解=== | ||
| - | 只需算有多少组线性无关的向量。已经选出m个线性无关的向量。这m个向量可以张成m维空间，因此下一个有$2^n-2^m$种选择。最终答案是$2^n\cdot \prod{i=1}^{n-1} (2^n-2^i)$ | + | 设$n\ge m$。先输出n/m*m个m，然后将问题转化为求$m\times (n%m)$ |
| - | ====C - Combination of Physics and Maths==== | + | ====C - A National Pandemic==== |
| - | ===solved by gyp=== | + | ===solved by lxh,tyx, written by tyx=== |
| ===题意=== | ===题意=== | ||
| - | 给定一个由正整数构成的矩阵。取它的一个子矩阵，使得这个子矩阵的元素之和除以最后一行的元素之和最大。求这个最大值 | + | 在树上，支持以下三种操作： |
| + | |||
| + | 1、选定一个点 $i$，别的点 $j$ 的价值都加上 $w[i]-dis(i,j)$。 | ||
| + | |||
| + | 2、选定一个点，它的价值值为 $min(价值，0)$。 | ||
| + | |||
| + | 3、询问某点的价值。 | ||
| ===数据范围=== | ===数据范围=== | ||
| - | $1\le m,n \le 200$ | + | $1 \le n(点数)、m(询问数) \le 5e4$ |
| ===题解=== | ===题解=== | ||
| - | 最终一定是选一列中靠上的所有。O(mn)枚举即可。 | + | 经过分析后我们可以发现，一次$1$操作，对于任何一个点来说，权值的变化都是 $w-dep[x]-dep[p]+2*dep[k]$ (k是对于任何一个点来说从选定点 $x$ 到根的路径上最近的祖先).对于 $w-dep[x]$ 来说，所有点都是一样的，用一个全局的 $sum$ 来记录就可以。对于 $dep[p]$ 这部分同理记录次数，$2*dep[k]$ 这部分则需要利用树链剖分每次从 $x$ 到根每个点都$+1$，最后查询点时查询到根路径上的和来得到，对于二操作，我们单开一个新数组来记录操作对原值的影响就可以了。 |
| ====D - ==== | ====D - ==== | ||
| 行 61: | 行 67: | ||
| ===题解=== | ===题解=== | ||
| - | ====E - Easy Construction==== | + | ====E - ==== |
| - | ===solved by tyx=== | + | ===solved by === |
| ===题意=== | ===题意=== | ||
| - | |||
| - | 构造一个$1$到$n$的排列，使对于任意$1 \le i \le n$，可以从这个排列中取出一个连续的长度为$i$的部分，它们的和$\mod \ n = k$，若没有解输出-1 | ||
| ===数据范围=== | ===数据范围=== | ||
| - | |||
| - | $1 \le n \le 5000$，$0 \le k < n$ | ||
| ===题解=== | ===题解=== | ||
| - | |||
| - | 首先我们发现$n$是奇数的时候必须有$k=0$，$n$是偶数的时候必须有$k=\frac{n}{2}$，其余情况均无解。$n$是奇数的时候，构造$n,1,n-1,2,n-2 ...$，$n$是偶数时构造$n,\frac{n}{2},1,n-1,2,n-2 ...$即可 | ||
| ====F - ==== | ====F - ==== | ||
| 行 97: | 行 97: | ||
| ===题解=== | ===题解=== | ||
| - | ====H - Harmony Pairs==== | + | ====H - Dividing==== |
| ===solved by gyp=== | ===solved by gyp=== | ||
| 行 103: | 行 103: | ||
| ===题意=== | ===题意=== | ||
| - | S(x)表示十进制数x每一位数字之和。给定n，求$0\le a\le b\le n$,$S(a)>S(b)$的数对(a,b)的个数。 | + | 定义传奇二元组。(1,k)是传奇二元组，若(n,k)是传奇二元组，则(n+k,k)，(nk,k)是传奇二元组。给定n,k，求$1\le a\le n,1\le b\le k$的传奇二元组(a,b)个数。 |
| ===数据范围=== | ===数据范围=== | ||
| - | $n\le 10^100$ | + | |
| + | $1\le n,k\le 10^{12}$ | ||
| ===题解=== | ===题解=== | ||
| - | dp1[i][j]表示前i位a<b<n，S(a)-S(b)+1000=j的方案数 | + | 所有第一个数模第二个数为0或1的均满足要求。数论分块计算个数即可。 |
| - | dp2[i][j]表示前i位a<b=n，S(a)-S(b)+1000=j的方案数 | ||
| - | |||
| - | dp3[i]表示前i位，a=b<n的方案数。这里S(a)-S(b)+1000一定等于1000 | ||
| - | |||
| - | 前i位a=b=n的方案数为1，S(a)-S(b)+1000一定等于1000。 | ||
| - | |||
| - | 对每一位，枚举a,b这一位的值，然后暴力分类转移即可。时间复杂度$O(100000\cdot l)$，其中l为n的长度。 | ||
| ====I - ==== | ====I - ==== | ||
| 行 129: | 行 123: | ||
| ===题解=== | ===题解=== | ||
| - | ====J - Josephus Transform==== | + | ====J - Pointer Analysis==== |
| ===solved by tyx=== | ===solved by tyx=== | ||
| 行 135: | 行 129: | ||
| ===题意=== | ===题意=== | ||
| - | 有一个排列$1,2 ... n$，$m$次操作，每次操作对其做$x$次$K$-约瑟夫变换，问最后这个排列是什么，$K$-约瑟夫变换的意思是，每次进行约瑟夫游戏，并依次将出局的人放到下一个排列 | + | 给出26个Pointer用大写字母表示，26个object用小写字母表示，每个object还有26个field，然后给出四种指向关系的赋值方式，问最后每个Pointer指向了哪些object |
| ===数据范围=== | ===数据范围=== | ||
| - | $1 \le n,m \le 10^5$，$n \times m \le 10^6$，$1 \le k \le n$，$1 \le x \le 10^9$ | + | 略 |
| ===题解=== | ===题解=== | ||
| - | $K$-约瑟夫变换本质也是一个置换，这个置换是固定的，所以我们对于每个环可以将其长度$\mod \ K$，这样我们可以在$O(len)$时间处理每个环变成了什么样，至于约瑟夫变换，可以每次通过在平衡树里query相应位置的数在$O(n \log n)$的时间内解决，因此总复杂度为$O(nm \log n)$ | + | 模拟题，要注意给出的赋值语句是可以调换顺序的，所以不能只做一遍，我们按照最坏情况，处理一遍以后第一个赋值语句被增加了一个，所以只需要重复处理26遍即可 |
| - | + | ||
| - | ====K - K-Bag==== | + | |
| - | + | ||
| - | ===solved by tyx=== | + | |
| - | + | ||
| - | ===题意=== | + | |
| - | + | ||
| - | 定义一个序列是$K-Bag$的，当且仅当它是由若干个$1$到$K$的排列组成的，例如$1\ 2\ 3\ 3\ 1\ 2\ 3\ 2\ 1\ 1\ 2\ 3$，现在给出一个长度为$n$序列，问它有没有可能是一个$K-Bag$序列的子序列 | + | |
| - | + | ||
| - | ===数据范围=== | + | |
| - | + | ||
| - | $1 \le n \le 10^5$，$1 \le K \le 10^9$ | + | |
| - | + | ||
| - | ===题解=== | + | |
| - | 当$K > n$的时候，这个序列最多被分成前一半后一半分别是两个排列的一部分，单独判断一下即可，当$K \le n$时，我们考虑在$O(n)$的时间内求出某个位置以及它之前的$K-1$个位置能否组成一个完整的排列，然后从头和尾分别找到一个最长的部分可以作为一个排列的一部分，然后我们从头上开始$K$个一步跳，如果能跳到尾部的部分就说明可以，如果都不行就不行 | ||
| =====Replay===== | =====Replay===== | ||
| - | 第一小时：tyx和gyp开始想E，lxh开始想D，tyx先猜了一个结论但是WA，后来发现有问题并找到正解通过，lxh写出了一个版本D但是超时 | + | 第一小时：gyp和tyx发现D题是签到题于是直接开写，但是发现用cin超时了，改成scanf后通过。gyp开始想H并通过，tyx和lxh开始想B |
| - | 第二小时：lxh开始想G，tyx开始想K，gyp连续通过了B和C题 | + | 第二小时：tyx写的B一直WA，随后gyp和lxh发现方法有问题，修正后通过。tyx开始想J，gyp和lxh开始想C |
| - | 第三小时：tyx写出了K但是WA，在找问题的时候lxh开始构造G但是一直WA，tyx找到了K的问题并通过 | + | 第三小时：tyx写出J并通过，随后加入gyp和lxh开始想C |
| - | 第四小时：tyx开始想J，gyp开始想H，tyx想出了J并开始写但是一直超时，后来发现因为多组数据有一个部分没有初始化，修改后通过 | + | 第四小时：三个人想出了C，但是写起来非常复杂，由于lxh临时有事所以tyx开始写 |
| - | 第五小时：gyp开始写H，lxh继续构造G但是没有通过，gyp最后没能写完H | + | 第五小时：tyx写完了C但是WA了两次，后来发现是因为多组数据有一小部分没有初始化，更改后通过 |
| =====总结===== | =====总结===== | ||
| - | * 要注意各种细节从而尽量避免罚时 | + | * 为了以防万一尽量不使用cin和cout进行输入输出 |
| - | * 多组数据一定要注意初始化 | + | |
2020-2021/teams/hotpot/2020nowcoder7.1596769545.txt.gz · 最后更改: 2020/08/07 11:05 由 misakatao
