2020-2021:teams:famerwzyyuki:2020_05_05
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:famerwzyyuki:2020_05_05 [2020/05/10 23:09] yuki 创建 |
2020-2021:teams:famerwzyyuki:2020_05_05 [2020/05/29 20:28] (当前版本) famerthy |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | 2020.5.5：\\ | + | 2020/05/05：\\ |
| 第一场团队赛：[[https://www.jisuanke.com/contest/9569|Nordic Collegiate Programming Contest 2019]]\\ | 第一场团队赛：[[https://www.jisuanke.com/contest/9569|Nordic Collegiate Programming Contest 2019]]\\ | ||
| 比赛过程:\\ | 比赛过程:\\ | ||
| 当场过题情况：\\ | 当场过题情况：\\ | ||
| - | A：思路&代码：Wzy\\ | + | A：未通过\\ |
| - | B：思路：Wzy 代码：Yuki\\ | + | B：未通过\\ |
| - | C：思路&代码：Wzy\\ | + | C：未通过\\ |
| - | D：思路&代码：Yuki\\ | + | D：未通过\\ |
| E：思路&代码：Yuki\\ | E：思路&代码：Yuki\\ | ||
| - | F：思路：Wzy&Yuki 代码：Wzy\\ | + | F：思路：Wzy&Yuki 代码：Yuki\\ |
| - | G：思路&代码：Famerthy\\ | + | G：未通过\\ |
| H：未通过\\ | H：未通过\\ | ||
| - | I：思路：Famerthy 代码：Famerthy&Yuki\\ | + | I：思路：Famerthy&Wzy 代码：Wzy\\ |
| + | J：未通过\\ | ||
| + | K：思路：Yuki 代码：Yuki\\ | ||
| + | L：未通过\\ | ||
| + | M：思路：FarmerThy 代码：FarmerThy\\ | ||
| 题解：\\ | 题解：\\ | ||
| - | **A:** | + | **A：** |
| - | 签到题 | + | 不会m(\\ |
| - | 题意：你在说动物的名字，每次说的名字的首字母需要和上一次的末字母字样。给定上一次的动物名字和所有的动物名字，问你能不能说出这一次的动物名字，如果能，能不能让下一个人说不出名字。 | + | **B：** |
| - | 解法：挨个判断就可以了 | + | 题意：在坐标平面上给出许多点，求一个以原点为中心的正方形，满足正方形边长最大且不包含空间中的所有点\\ |
| - | + | 题解：二分答案，每个点都会将正方形约束在一个角度区间，若所有区间交集不为空，则该正方形可以满足不包含空间中所有点。\\ | |
| - | **B:**\\ | + | 思路其实很早就想出来了，但是那个角度区间的推导遇到了很多问题，数学菜鸡哭了\\ |
| - | 题意：给出三个小矩形的长宽，求拼成的大矩形的最小面积。\\ | + | |
| - | 题解：暴力枚举所有情况：矩形只能是1 1 1 或 2 1 排列（每个矩形两个方向）\\ | + | |
| **C：** | **C：** | ||
| - | 签到题 | + | 不会m(\\ |
| - | 题意：有一块n*m巧克力，每次可以取出一块掰成两块，问你最少几次可以搞出若干个巧克力一共有a块。（n,m<10^6） | + | **D：** |
| - | 解法：设b=n*m-a 如果a或b是n或m的倍数 答案是1. 如果a或b能分成两个小于n,m的数的乘积，答案是2. 否则，答案是3. | + | 题意：平面上有许多点，求能否将坐标轴旋转某个角度使得：每个点，若y不同，则y从小到大，若y相同，则x从小到大\\ |
| + | 题解：\\ | ||
| + | **E：**\\ | ||
| - | **D：**模拟签到题 | ||
| - | |||
| - | **E：**\\ | ||
| - | 题意：一棵树，每个点的权值是它子树所有点权值之和，给出部分点的权值，另一些未知，判断是否优解且解是否唯一(权值必须为正)\\ | ||
| - | 题解：从下往上递归判断讨论不同情况，再从上到下进行检查和填数。\\ | ||
| - | 因为权值必为正Min[x]表示x权值的最小值（权值确定时Min[x]=a[x]），显然Min[x]=ΣMin[u](u是x儿子)\\ | ||
| - | 从下往上判断时： | ||
| - | * 当前节点权值确定： | ||
| - | * Min[x]>a[x]：无解 | ||
| - | * Min[x]==a[x]：x的儿子的权值可以全部确定，显然a[u]=Min[u] | ||
| - | * Min[x]<a[x]： | ||
| - | * 儿子的值全部确定：无解 | ||
| - | * 儿子的值只有一个不确定：继续向上递归，这个儿子的权值确定 | ||
| - | * 儿子的值有超过两个不确定：多解 | ||
| - | * 当前节点权值不确定： | ||
| - | * 所有儿子权值确定：当前节点数值确定 | ||
| - | * 否则继续向上递归，最终判断不确定 | ||
| - | 从上往下检查和填数： | ||
| - | * 由于从上往下填数，若访问到当前节点，该节点权值仍不确定：无解 | ||
| - | * 当前节点权值确定： | ||
| - | * sMin==a[x]：x的儿子的权值可以全部确定，显然a[u]=Min[u]（sMin=ΣMin[u]）\\ 再判断一次是因为从下往上时a[x]可能暂时还不确定 | ||
| - | *sMin!=a[x]且超过1个儿子节点不确定：多解 | ||
| - | *只有一个儿子不确定：这个儿子的值确定 | ||
| - | **超级大坑：**输出量过大300000！！不然会TLE....呜呜呜检查了好久 | ||
| **F：** | **F：** | ||
| - | 题意：题的大致意思为有n个地精，最多分成m个组，然后每次攻击每个地精造成一点伤害，造成伤害以后会有一道闪电劈一组地精，造成K点伤害，也就是这个组里减少k个地精，闪电一定会挑地精最多的组劈。(1 ≤ n ≤ 10⁹, 1 ≤ m, k ≤ 10⁷) | + | 题意：堆箱子，上层的箱子不能多于下层的箱子，最底层的箱子数目固定，求方案数\\ |
| - | 题解：本题的思路是首先选出一部分地精，组成a组，每组k个地精，然后将剩下的地精平均分到min(m,n)组里，选取每一个可行的a值，求出最大值即可。枚举a（根据数据范围推导出最多枚举m次） | + | 题解：dp[i][j]表示用了i个箱子，最上层有j个箱子，按层转移即可，预处理后缀和优化\\ |
| **G：** | **G：** | ||
| - | 签到水题 | + | |
| **H：** | **H：** | ||
| - | 暂时还没过qaq | ||
| - | **I：** | + | **I：**\\ |
| - | 贪心水题 | + | 题意：有向无环图从1号点到所有终止点的方案数（吐槽：英文看起来真的太难理解题意了...）\\ |
| + | 题解：签到题\\ | ||
| + | **J：** | ||
| + | |||
| + | **K：** | ||
| + | **L：** | ||
| + | 题意：一个01矩阵，可以将每一行的0变成1，1变成0，求长度最大的全为1的方阵（题意依旧很难理解到...）\\ | ||
| + | 题解：单调栈，但是比赛时莫名wa了...\\ | ||
| + | **M：**\\ | ||
| + | 题意：签到题，略了。\\ | ||
| **一些反思：** | **一些反思：** | ||
2020-2021/teams/famerwzyyuki/2020_05_05.1589123344.txt.gz · 最后更改: 2020/05/10 23:09 由 yuki
