2020-2021:teams:hotpot:nordiccollegiateprogrammingcontest2015
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:nordiccollegiateprogrammingcontest2015 [2020/05/29 17:03] lotk |
2020-2021:teams:hotpot:nordiccollegiateprogrammingcontest2015 [2020/05/29 18:03] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 25: | 行 25: | ||
| ===题解=== | ===题解=== | ||
| - | 将两棵树连在一起之后，考虑最小化直径，采取和按秩合并并查集类似的思想，我们就将直径的中点作为根来链接，并对新的直径的大小进行分析，我们不妨记两棵树的直径长度分别为 $a,b$ 且 $a /le b$ ,则： | + | 将两棵树连在一起之后，考虑最小化直径，采取和按秩合并并查集类似的思想，我们就将直径的中点作为根来链接，并对新的直径的大小进行分析，我们不妨记两棵树的直径长度分别为 $a,b$ 且 $a \le b$ ,则： |
| - | 若$ b /ge a+3 $,则新树的直径长度仍为 $ b $, | + | 若$ b \ge a+3 $,则新树的直径长度仍为 $ b $, |
| 若$ b == a+2 $,当 $b$ 为奇数时，新树直径为 $b+1$, 当 $b$ 为偶数时，直径长度不改变。 | 若$ b == a+2 $,当 $b$ 为奇数时，新树直径为 $b+1$, 当 $b$ 为偶数时，直径长度不改变。 | ||
| 行 36: | 行 36: | ||
| - | ====B==== | + | ====B - Bell Ringing==== |
| - | ===solved by lxh=== | + | ===solved by tyx=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给出$n$，给出一个$n$全排列的排列，满足相邻两个排列只有两个位置不相同。第一个必须是从1到$n$排列。 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $1 \le n \le 8$ | ||
| ===题解=== | ===题解=== | ||
| - | 表面上给出的数字范围很大，但我们关心的只有它包含哪些位，用状压的方式压含有哪些位进行hash即可 | + | 先算出$n$的排列，然后让$n+1$在这些排列里面反复移动即可，例如 |
| - | ====D - Rotating Display==== | + | 2的答案是 |
| + | <code> | ||
| + | 1 2 | ||
| + | 2 1 | ||
| + | </code> | ||
| - | ===upsolved by lxh=== | + | 3的答案是 |
| + | <code> | ||
| + | 1 2 3 | ||
| + | 1 3 2 | ||
| + | 3 1 2 | ||
| + | 3 2 1 | ||
| + | 2 3 1 | ||
| + | 2 1 3 | ||
| + | </code> | ||
| - | ===题意=== | + | ====C - Cryptographer’s Conundrum==== |
| - | 给定由以下符号$“<”, “>”, “^”, “v”, “o”, “x”, “|”, “-”, “/”, “\backslash”$组成的$n×n$矩阵,给定操作如$“<”, “>”$代表顺/逆时针翻转矩阵，$ “|”, “-”, “/”, “\backslash”$代表沿该方向中轴翻转矩阵，要求输出结果矩阵。 | + | ===solved by tyx=== |
| + | |||
| + | ===题意=== | ||
| - | 注：$"<"顺时针翻转后为“v”$. | + | 给出一个字符串$s$，问把它改成PERPERPER...这样的循环需要更改几次。 |
| ===数据范围=== | ===数据范围=== | ||
| - | $n≤100$ ，操作串$≤1000000$ | + | $|s| \le 300$ |
| ===题解=== | ===题解=== | ||
| - | 显然这题类似大模拟，耐心的话我们可以完成翻转等操作的实现，但是由于操作串过长而超时，细心观察后我们可以发现，它这样操作所能得到的矩阵形态时有限的，所以我们可以通过操作串直接计算得到最后的形态并进行变换。 | + | 直接$O(n)$扫一遍即可。 |
| - | ====F - Tree Stands==== | + | ====D - Disastrous Downtime==== |
| - | ===solved by gyp=== | + | ===solved by tyx,gyp=== |
| + | |||
| + | ===written by gyp=== | ||
| ===题意=== | ===题意=== | ||
| - | 一棵树，n个点中选m个，要求不能有孤立点（即每个被选的点旁边还有选中的点）。求方案数。 | + | 现在有$n$个进程要处理，每个进程的长度都是1s，开始时间会给出，一个服务器最多同时处理$k$个进程，问最少需要多少个服务器。 |
| ===数据范围=== | ===数据范围=== | ||
| - | $2\le m\le n\le 200$ | + | $n,k \le 10^5$ |
| ===题解=== | ===题解=== | ||
| - | dp0[i][j]表示i的子树中选j个，且根节点不选的合法方案数；dp1[i][j]表示i的子树中选j个，根节点选中且子树中有与根连接的点被选中的合法方案数；dp2[i][j]表示i的子树中选j个，根节点选中且子树中无与根连接的点被选中的合法方案数。 | + | 找到所有单个毫秒中同时有要处理的进程的最大值即可，由于只需要查询一次，可以直接差分，时间复杂度$O(n)$。 |
| - | 递推的时候，对根节点的每个子节点，类似01背包（取max改为加）。最终答案为dp0[1][m]+dp1[1][m]。 | + | |
| - | 时间复杂度：$O(nm^2)$ | + | ====E - Entertainment Box==== |
| - | ====G - Orchard Division==== | + | ===solved by tyx,gyp=== |
| - | ===solved by tyx=== | + | ===written by lxh=== |
| ===题意=== | ===题意=== | ||
| - | 有一块$M \times M$的田地，其中有$N$棵树，主人现在想卖掉尽可能多的地，但是保留所有树总数的**恰好一半**。不仅如此，主人想要保留的地必须是一块矩形且包含了整个$M \times M$矩形的至少一个角，问留下的地最小是多少。 | + | 有n个区间，选择区间，使得在保证任意时刻不会有超过k个区间重合的情况下区间最多。 |
| ===数据范围=== | ===数据范围=== | ||
| - | $M \le 10^9,N \le 10^6$ | + | $1 \le k < n \le 100000$ |
| ===题解=== | ===题解=== | ||
| - | 按照一行的树为单位扫描线即可，少于一半加一行，多于一半减一列，等于一半统计答案。因为要分别判断四个角所以需要做四次。每次先按某一个坐标排序，从小到大或从大到小加，多了就从大往小或者从小往大删，每次维护一个大根堆或小根堆即可。复杂度$O(N \log N)$ | + | 这题我们采取贪心的思想，我们按照区间左端点排序加入区间，在已经有 $k$ 个重叠的情况下，如果新加入第 $k+1$ 个区间，显然我们要弹出区间右端点最大的区间，同时在读入新的区间时，将右端点小于当前区间左端点的区间弹出，用平衡树来维护这种关系即可。 |
| - | ====I - Suspicious Samples==== | + | ====F - Floppy Music==== |
| - | ===solved by gyp=== | + | ===solved by tyx,gyp=== |
| + | |||
| + | ===written by tyx=== | ||
| ===题意=== | ===题意=== | ||
| - | 给长度为n的序列，每个元素两个参数t（时间）,v。保证t严格递增。m次询问，每次问大于/小于，在k以内之前的时间里所有v的最大/最小/平均的元素个数。 | + | 现在有$T + 1$个位置，要找一个位置使得这个位置满足以下规则：在某几个给定的时间区间里可以以一个位置一秒的速度**不停地**移动，在时间区间内**不能转向**，区间之间可以转向，保证区间不会相连，问是否可以找到一个位置。 |
| ===数据范围=== | ===数据范围=== | ||
| - | $n\le 10^5，m\le 10$ | + | $T \le 10^4$，区间个数$n \le 100$，数据组数$f \le 10$。 |
| ===题解=== | ===题解=== | ||
| - | 因为数据不大，直接线段树+二分即可。如果数据再大一些，比如n是$10^6$，可以用前缀和+单调队列。 | + | 一开始把每个位置置成1，然后每次找到一个位置后根据区间长度$L$检查这个位置往左和往右$L$的位置在不在$T + 1$个位置之中，如果在就把那个位置置成1（在另一个数组），一共有区间个数个数组，时间复杂度为$O(Tnf)$。 |
| - | 时间复杂度：$O(n\log n m)$或$O(nm)$ | + | ====G - Goblin Garden Guards==== |
| - | ====J - Colorful Tribune==== | + | ===solved by tyx,gyp=== |
| - | ===solved by tyx== | + | ===written by lxh=== |
| ===题意=== | ===题意=== | ||
| - | 有一个$N \times N$的方阵，每一行和每一列都由$N$个不同的字母组成，现在有**一个**字母放错了位置，问是哪一个。例如： | + | 在一个平面给出一些点，再给出一些圆，问有多少点没有被覆盖。（一个坐标上可以有多个点） |
| - | + | ||
| - | <code> | + | |
| - | ABC | + | |
| - | BCA | + | |
| - | BAB | + | |
| - | </code> | + | |
| - | + | ||
| - | 中第三行第一个字母应该是C。 | + | |
| ===数据范围=== | ===数据范围=== | ||
| - | $3 \le N \le 26$ | + | 点数 $\le 10^5$, 圆数 $\le 2\times 10^4$, 坐标 $0 \le xi,yi \le 10^4$ ,圆的半径 $ r \le 100 $. |
| ===题解=== | ===题解=== | ||
| - | 先从前三行找到两行的字母集合相同，可以用多种方式，我这里用的是一个26位的2进制数，然后开始找不合法的地方。如果一个字母在一行或一列出现两次就不合法，或者一个字母没有出现在我们刚刚找到的字母集合里就不合法。找到后输出即可。 | + | 本题坐标的范围较大，我们不妨考虑从圆的半径这较小的一维来切入，采取对点每行用一个 $vector$ 来保存，之后对于每个圆，由于只涉及到最多 $200$ 行，对每一行取 $lower\_bound$ 和 $upper\_bound$ 来得到圆覆盖的位置，并采取在开始位置 $+1$， 在结束位置 $-1$ 的方式来标记覆盖的点（因此 $vector$ 里的变量应当是 $pair$）,最后遍历所有 $vector$ 来统计标记前缀和为 $0$ 的点的数量. |
| =====Replay===== | =====Replay===== | ||
| - | 第一小时：gyp,lxh面对一堆题看中了F。发现F可做，于是gyp开始写F。lxh,tyx开始看B，并想出来了。gyp写F不过样例，让lxh先写B并1a。 | + | 第一小时：tyx,lxh先想A，想出后lxh开始写A，gyp想I。tyx发现C题很多人过，于是A掉了C题，gyp没有想出I转而想E。tyx想出D后gyp优化了其算法并A掉了D题。lxhA错了几次后发现算法有瑕疵，更改后通过A。 |
| - | + | ||
| - | 第二小时：gyp继续调F，继续不过样例。让lxh先写，写完却发现计蒜客上没有这道题。tyx发现J过的人很多，尝试并迅速通过。 | + | |
| - | 第三小时：gyp继续调F，lxh和tyx想H。gyp终于过了F，lxh和tyx也想出了H。lxh开始写H，tyx看G并想出，tyx与gyp交流G。 | + | 第二小时：gyp想出E但是不会实现，给lxh讲解后lxh开始写E并通过。tyx和gyp想出了G，给lxh讲解后lxh开始写G。tyx,gyp开始看F但没有看懂。 |
| - | 第四小时：lxh写H未果。tyx写G但wa。gyp想出I，gyp开始写I。gyp的I一直wa。lxh开始看D并产生思路。 | + | 第三小时：lxhA了G，tyx看懂了F并A掉了F。gyp继续想I但没有想出。 |
| - | 第五小时：lxh开始写D。tyx发现gyp未加多组数据。I通过。tyx的G一直wa。lxh写完D却tle。 | + | 第四小时：三个人先看了H、I、J，其中H没有看懂，I和J看懂了但没有想出，之后三个人一起看B发现是构造题，gyp先写但没有写出，tyx想到了构造方法，但花了半个小时左右才写出A掉。 |
| - | 赛后，tyx的G交到cf上ac，cf上的标程交到计蒜客上wa。 | + | 第五小时：tyx看懂了H但不会做，三个人开始想J，隐约想到了做法但并不知道细节怎么写。最后没有人A题。 |
| =====总结===== | =====总结===== | ||
| - | * 一定要注意有没有多组数据！ | + | * 要仔细看清楚题目要求。 |
| + | * DP方面的知识点还需要加强。 | ||
2020-2021/teams/hotpot/nordiccollegiateprogrammingcontest2015.1590743015.txt.gz · 最后更改: 2020/05/29 17:03 由 lotk
