2020-2021:teams:hotpot:2020nowcoder5
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:2020nowcoder5 [2020/07/31 11:15] misakatao 创建 |
2020-2021:teams:hotpot:2020nowcoder5 [2020/07/31 16:29] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| ===题解=== | ===题解=== | ||
| - | ====B - ==== | + | ====B - Graph==== |
| - | ===solved by === | + | ===solved by gyp,tyx=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给定一棵树。每次可以添加一条边或删去一条边。保证任何时候一定是连通图，每个环上的边异或和为0。求所有边的和最小是多少 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $2\le n \le 10^5$,$0 \le w < 2^30$ | ||
| ===题解=== | ===题解=== | ||
| - | ====C - ==== | + | 可以证明，每条边的长度是确定的。任取一点为根，可以计算出每一点到根的所有边的异或和，记为$a_i$。本题等价于求一个最小生成树，第i和第j个点的边权为$a_i \bigoplus a_j$。先按升序排序。从最高位开始，从所有最高位是1和最高位是0的里各选一个数，使得其异或结果最小，这条边被计入。然后再分别从两个部分再进行类似的操作。 |
| - | ===solved by === | + | ====C - Easy==== |
| + | |||
| + | ===upsolved by gyp=== | ||
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给定n,m,k。对长度为k的正整数序列$\sum_{i=1}^k a_i=n$,$\sum_{i=1}^k b_i=m$，$P=\prod_{i=1}^kmin(a_i,b_i)$。求所有满足要求的a,b对应的P的和 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $T\le 100$,$1\le n,m\le 10^6,1\le k\le min(n,m)$ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 对于给定的a,b，P为满足$c_i\le min(a_i,b_i)$，长度为k的正整数序列c的个数。对于任意c，设$S=\sum_{i=1}^kc_i$，一共有$C_{n-S+k-1}^{k-1}\cdot C_{m-S+k-1}^{k-1}$个a,b包含c。枚举S即可。 | ||
| ====D - ==== | ====D - ==== | ||
| 行 49: | 行 61: | ||
| ===题解=== | ===题解=== | ||
| - | ====F - ==== | + | ====E - Bogo Sort==== |
| - | ===solved by === | + | ===solved by tyx=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给出一个长度为$n$的排列$P$，对于任意一个长度为$n$的排列$A$，不断执行$A_i = A_{P_i}$，问有多少排列最终可以变成有序的 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $1 \le n \le 10^5$ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 由于$P$给定，这个置换一定会成若干个环，我们只需要考虑$1,2,3 ... n$这个排列经过这个变换能组成多少种不同的排列，很容易发现只需要求出所有环的大小的最小公倍数即可，由于题目要求需要高精度或者python | ||
| + | |||
| + | ====F - DPS==== | ||
| + | |||
| + | ===solved by tyx=== | ||
| + | |||
| + | ===题意=== | ||
| + | |||
| + | 给出若干个人在一局游戏里的输出，输出一个柱状图 | ||
| + | |||
| + | ===数据范围=== | ||
| + | |||
| + | 略 | ||
| + | |||
| + | ===题解=== | ||
| + | |||
| + | 签到题，直接模拟 | ||
| ====G - ==== | ====G - ==== | ||
| 行 79: | 行 113: | ||
| ===题解=== | ===题解=== | ||
| - | ====I - ==== | + | ====I - Hard Math Problem==== |
| - | ===solved by === | + | ===solved by gyp=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 很奇怪的一道数学题，没有输入，只输出一个结果 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | 无 | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 反正答案是2/3。试也能试出来，并不会证。 | ||
| ====J - ==== | ====J - ==== | ||
| 行 101: | 行 141: | ||
| =====Replay===== | =====Replay===== | ||
| - | 第一小时： | + | 第一小时：gyp发现I题是数学题，求解并通过，tyx和lxh发现F是签到题，但是写出来却WA，后来发现需要开longlong，修改后通过 |
| - | 第二小时： | + | 第二小时：lxh开始想H，gyp开始想B，tyx开始想E，tyx想出了E并写出，但是因为某个循环边界问题WA了两次 |
| - | 第三小时： | + | 第三小时：gyp开始写B但是超时，lxh开始写H但是因为方法很麻烦所以花费了很长时间 |
| - | 第四小时： | + | 第四小时：gyp想出了B的另一个方法并由tyx写出并通过，lxh继续写H，写出但是WA，三个人开始想D，猜了一个结论并实现发现是正确的 |
| - | 第五小时： | + | 第五小时：lxh继续调试H题，但是最后TLE无法通过 |
| =====总结===== | =====总结===== | ||
| - | * | + | * 应该在比赛开始的时候尽量先把所有的题都看了再想题 |
2020-2021/teams/hotpot/2020nowcoder5.1596165326.txt.gz · 最后更改: 2020/07/31 11:15 由 misakatao
