Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"AtCoder-abc312_f\":[\"Cans and Openers\",1135,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/abc312\\\"\\u003eUNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312)\\u003c/a\\u003e\"],\"AtCoder-abc312_e\":[\"Tangency of Cuboids \",399,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/abc312\\\"\\u003eUNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312)\\u003c/a\\u003e\"],\"AtCoder-past201912_j\":[\"Leveling\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past201912-open\\\"\\u003e第一回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past201912_g\":[\"Division\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past201912-open\\\"\\u003e第一回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past201912_h\":[\"Bulk Selling\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past201912-open\\\"\\u003e第一回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202005_m\":[\"Real Traveling Salesman\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202005-open\\\"\\u003e第三回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202004_n\":[\"Building Construction\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202004-open\\\"\\u003e第二回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202212_k\":[\"Buy an Integer\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202212-open\\\"\\u003e第13回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202005_n\":[\"Swap and Sort\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202005-open\\\"\\u003e第三回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202004_o\":[\"Variable Spanning Trees\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202004-open\\\"\\u003e第二回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202212_l\":[\"Segments\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202212-open\\\"\\u003e第13回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202005_o\":[\"Quoits\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202005-open\\\"\\u003e第三回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202212_m\":[\"Tree and Intervals\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202212-open\\\"\\u003e第13回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202212_n\":[\"Sequence and Function\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202212-open\\\"\\u003e第13回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202212_o\":[\"Shift and Shift\",0,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202212-open\\\"\\u003e第13回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202004_k\":[\"Parentheses\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202004-open\\\"\\u003e第二回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202005_k\":[\"Moving Containers\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202005-open\\\"\\u003e第三回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202004_l\":[\"Lexicographically Minimum\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202004-open\\\"\\u003e第二回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202005_l\":[\"Supamarket\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202005-open\\\"\\u003e第三回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202004_m\":[\"Cafeteria\",0,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202004-open\\\"\\u003e第二回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"CodeForces-863F\":[\"Almost Permutation\",1307,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/863\\\"\\u003eEducational Codeforces Round 29\\u003c/a\\u003e\"],\"AtCoder-past202004_h\":[\"1-9 Grid\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202004-open\\\"\\u003e第二回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202212_j\":[\"Crossing\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202212-open\\\"\\u003e第13回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202303_n\":[\"Garbage\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202303-open\\\"\\u003e第14回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202303_o\":[\"Range Sort Range Sum\",0,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202303-open\\\"\\u003e第14回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202303_l\":[\"Ranking\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202303-open\\\"\\u003e第14回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202303_m\":[\"Put Away\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202303-open\\\"\\u003e第14回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"HDU-7318\":[\"Guess\",218,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2023%A1%B0%B6%A4%B0%D2%B1%E0%B3%CC%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A84%A3%A9\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2023“钉耙编程”中国大学生算法设计超级联赛(4) \\u003c/a\\u003e \\u003c/div\\u003e\"],\"AtCoder-past202303_j\":[\"Shift the Pattern\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202303-open\\\"\\u003e第14回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202303_k\":[\"Game with Coins and Bag\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202303-open\\\"\\u003e第14回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past201912_o\":[\"Endurance\",0,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past201912-open\\\"\\u003e第一回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past201912_m\":[\"Auto Choice\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past201912-open\\\"\\u003e第一回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past201912_n\":[\"Land Clearing\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past201912-open\\\"\\u003e第一回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past201912_k\":[\"Conglomerate\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past201912-open\\\"\\u003e第一回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past201912_l\":[\"Gradation\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past201912-open\\\"\\u003e第一回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202010_k\":[\"転倒数\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202010-open\\\"\\u003e第四回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202010_l\":[\"マンションの改築\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202010-open\\\"\\u003e第四回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202010_m\":[\"筆塗り\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202010-open\\\"\\u003e第四回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202010_i\":[\"ピザ\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202010-open\\\"\\u003e第四回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"AtCoder-past202010_j\":[\"ワープ\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202010-open\\\"\\u003e第四回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"]}","joined":false,"groups":{}},"managingGroups":{},"author":"hh2048","updateTime":1692866223000,"title":"【W的A题计划】比赛刷题小记","dislikeCnt":0,"content":"$\\huge \\pmb {\\mathfrak{I\\ took\\ the\\ one\\ less\\ traveled\\ by,}}$ \n\n$\\huge \\pmb {\\mathfrak{and\\ that\\ has\\ made\\ all\\ the\\ difference.}}$\n\n\u003c/br\u003e\n\n此前的刷题小记:[2022.12.13-2023.04.14备战省赛时期](https://www.cnblogs.com/WIDA/p/17004563.html)、[2023.04.23-2023.07.16过渡时期](https://www.cnblogs.com/WIDA/p/17346245.html) 。\n\n\u003c/br\u003e\n***\n***\n\u003c/br\u003e\n\n## 第三回 アルゴリズム実技検定 過去問\n\n[problem:AtCoder-past202005_k] 数据结构-链表、模拟\n\n链表模板题。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202005_l] 数据结构-STL、模拟、暴力\n\n很棒的一道练习STL的题目,方法很好想,但是实现很困难。我中途换了好几个思路,最终还是采用了 `set` 维护最大值、`vector\u003cvector\u003cint\u003e\u003e` 维护某个商品是否被买走、`map` 维护被买走的商品的行列编号。我自认为这样的思路写起来不算太难,但是要注意各种边界情况(否则 `set` 很容易会返回RE)。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202005_m] 图论-最短路、暴力、动态规划、位运算\n\n由于途径的点至多为 $16$ 个,分别跑 $16$ 次最短路是显然的。随后我们考虑如何利用这 $16$ 个距离数组获得答案——位运算DP是容易被想到的,由于我动态规划做的比较少,转移方程写的比较磕绊,但总体难度应该是不高的。\n\n`dp[i][j]`: 经过的地点位运算压缩后的值为 $i$ 、且刚刚经过的地点为 `p[j]` 的最小代价。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202005_n] 思维、暴力、二分查找、数据结构-STL、模拟\n\n好题,这道题的主要困难在于复杂度很不容易算清楚。题目很像维护一个手写数据结构,但其实并没有。\n\n考虑初学排序操作的时候,冒泡排序的做法和操作一是一致的,所以我们可以将操作二借由冒泡排序变为操作一。随后,我们分析复杂度,注意到将被排序的区间初始是有序的,只有被操作一执行过之后才会需要进行冒泡排序,这代表着冒泡排序执行的次数是与操作一的次数相关的,即 $\\mathcal O(Q)$ ,至此,我们可以模拟执行完成本题。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202005_o] 网络流-最小费用流\n\n强技巧题,但是这些技巧在网络流中都很常用。首先我们假设能考虑到网络流这一思路,随后:\n\n- 由于游戏一共分三轮进行,故建立三个虚拟点代表每一轮的开始,显然,从起点到这三个虚拟点的流量为 $M$ ;\n- 由于题目要求求出最大值,所以我们在建图时权值取反;\n- 减去的权值与轮次相关,故我们对其进行差分处理(这一操作与 [problem:CodeForces-863F] 一致)。\n\n\u003c/br\u003e\n***\n***\n\u003c/br\u003e\n\n## 第四回 アルゴリズム実技検定 過去問\n\n[problem:AtCoder-past202010_i] 前缀和、三分算法\n\n这是一道极其考验技巧的题。首先,对于这种左右边界都不固定的题目,应当能想到固定其中一个端点后计算另一端点这样的思路,这里的计算包含二分、两点法、尺取、以及本题会用到的三分,可能还需要前缀和、差分等等常见优化。\n\n由于要求解的函数式为 $|X-Y|$、且 $X+Y$ 的值固定,显然,随着 $X$ 上升,$Y$ 不停下降,为凸函数,满足三分性质,所以我们可以跑一个整数域三分来确定每一个左端点的最佳右端点。\n\n三分的 `check` 函数需要计算区间和,使用前缀和+差分处理;同时,对于环状数组,使用二倍长数组法避免取模,简化步骤。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202010_j] 图论-最短路\n\n~~又是我没见过的神仙建图法,不愧是我最爱的PSAT。~~\n\n显然,根据题意为传送器两两建边必然会超时,所以本题使用了**虚空建点**法(这个名字是我自己取的,类比于网络流中的超级源点),即虚空建立三个额外点,随后按照题意描述建立**单向边**,之后便正常跑Djikstra即可。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202010_k] 数据结构-树状数组、逆序对\n\n简单题,但是题意很多坑,我先后在范围和取模上翻了车。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202010_l] 贪心、模拟、思维、差分与前缀和\n\n非常巧妙的一题,并没有使用到数据结构。将所询问的“相邻高度相等的楼房数量”转换为“相邻高度差为 $X$ 的楼房数量”,随后依次模拟各个操作会对这个 $X$ 和高度差数组造成的影响。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202010_m] 树论-LCA、数据结构-并查集、贪心\n\n好题。\n\n如果维护的是点的信息而不是边的信息,那么就是树链剖分后维护区间问题的模板。但是本题并不是这样的,我们需要先执行一个贪心的思路——逆序考虑,被涂过颜色的边不会再修改第二次。这提示我们寻求一个链表一样的数据结构,确保已经被检查过的点不会再被检查第二次,暴力涂色即可,显然,不带启发式合并的并查集(因为我们需要将点与其父节点连接)可以很方便的做到这一点。\n\n随后便是涂色细节的讨论,由于是树上涂色,绕不开的便是LCA问题,使用树链剖分比倍增略快一些,但是都能够轻松通过。\n\n\u003c/br\u003e\n***\n***\n\u003c/br\u003e\n\n## 杭电多校:2023“钉耙编程”中国大学生算法设计超级联赛(4)\n\n[problem:HDU-7318] 数论、暴力\n\n\u003c/br\u003e\n***\n***\n\u003c/br\u003e\n\n## AtCoder Beginner Contest 312\n\n[problem:AtCoder-abc312_e] 几何、暴力、贪心\n\n好题,让人想起2023湘潭邀请赛的最后一题,同样是精妙的控制点的坐标来获取答案的题目。赛时没有意识到点的范围代表着什么,于是感觉不可做、直接跳过了,看了题解才意识到点的范围的意义。\n\n解题的关键点其一在于 $N$ 的范围,显然提醒我们可以 $\\mathcal O(N^3)$ 暴力枚举全部的点;其二在于图形互不重叠,且均是三维的图形(即不会出现二维的形状)这提示我们每一个长方体内部都存在一些点是仅被这个立方体包含的。\n\n我们很容易有这样一个朴素的想法,即判断每一个长方体外围一圈是否存在其他长方体。这个想法在理论上显然是正确的,但是长方体外围一圈的整数点可能同时被多个长方体包含(即没有用到上方说的第二个解题关键点),这会导致难以直接判断,那么我们不妨转变思路——既然难以准确的求出这样的点,那干脆直接把长方体内部的全部点都判断一遍就好了,符合要求的点一定在这些点之中。\n\n于是,我们可以使用 $\\mathcal O(6\\cdot N^3)$ 的复杂度暴力枚举点并进行判断(六个方向,其实三个方向就足以了,但是这个优化与否差别不大)。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-abc312_f] 贪心、模拟、数据结构-STL、排序\n\n赛时其实知道这是个经典的贪心+模拟配置的题,但是由于我贪的策略比较劣,导致写了很久写不出来,赛后十多分钟终于过样例了然后 ~~喜提~~ WA了,应该是赛时思路的贪心策略有问题。\n\n其实看了题解之后就感觉很简单了,使用一个数组维护 $T_0$ 操作的答案、另一个数组维护 $T_1,T_2$ 操作的答案。之后使用一个类双指针的很典的贪心思路计算一些答案即可。~~异常的通过人数证明了这题的难度~~。\n\n模拟过程中有一些小优化可以学习,例如不使用指针记录当前位置,而是善用STL自带的函数完成,在本题中,将 `vector` 从小到大排序可以使用 `back()` 和 `pop_back()` 方便的取出最大值、判断是否为空。\n\n\u003c/br\u003e\n***\n***\n\u003c/br\u003e\n\n## Atcoder:第二回 アルゴリズム実技検定 過去問\n\n[problem:AtCoder-past202004_h] 搜索、dp、暴力\n\n这个 $n,m$ 的范围很显然就是爆搜,关键在于如何建立 `vis` 数组使得不重复搜索,这里我们用一个三维的 `dp` 数组,第一、二维为横纵坐标,第三维为题中所要求的当前已经遇到的序列的最后一个数字,这样可以在 $\\mathcal O(NM\\cdot 10)$ 的复杂度内完成搜索。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202004_k] 动态规划\n\n简单动态规划,适合复习动规知识点。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202004_l] 贪心、数据结构-线段树\n\n贪心策略比较好想到:在保证剩余元素能被选到的前提下,在当前元素中选择最小的那个。由于要求答案字典序最小,故这样的局部最优即为答案。现在问题便在于查找最小值,在一开始我直接使用了遍历的方式,然而 ~~喜提一发~~ 超时,随后考虑使用线段树优化这一时间复杂度,得以通过。\n\n[problem:AtCoder-past202004_m] 动态规划\n\n~~不会动规。~~\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202004_n] 离散化、贪心、数据结构-KDTree/二维线段树/树状数组\n\n解法一:离散化+离线+贪心+树状数组\n\n本题做法较多,但是我不会其他高级的数据结构,所以采用贪心的方式降维。\n\n具体的做法很典。首先将坐标离散化,随后,我们假设固定的是横轴,将涂色的左右端点、查询的端点分别标记入队,按照横轴从小到大排序,随后按照左端点、查询的端点、右端点的顺序取出,对于左端点,我们将其对应的纵轴部分差分赋值;对于查询的端点,我们可以直接获取其答案,由于是离线查找,所以暂存到答案数组;随后对于右端点,再使用一次差分复原刚刚的赋值操作。\n\n解法二:离散化+二维线段树(线段树套线段树)\n\n这一做法的典型可以参考 [SSRS的这发提交](https://atcoder.jp/contests/past202004-open/submissions/29907005) 。其基本思路是,使用二维前缀和在线段树外部维护区块的值,随后赋值到线段树上,查询时直接查找 $(0,0)$ 到 $(A_i,B_i)$ 的答案(但是其实我个人很疑惑的是,为什么不直接使用区块赋值、单点查询的方式,应当是能做到的,但是我并不熟悉这一数据结构,就不做过多评价了)。\n\n[二维树状数组可以参考这一发提交](https://atcoder.jp/contests/past202004-open/submissions/12693965);[二维线段树参考2](https://atcoder.jp/contests/past202004-open/submissions/12901572);[二维线段树参考3](https://atcoder.jp/contests/past202004-open/submissions/14470114)。\n\n解法三:KD-Tree\n\n这一数据结构可以直接处理原数据,不需要离散化,典型可以参考 [这一发提交](https://atcoder.jp/contests/past202004-open/submissions/29401260) 。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202004_o] 树论-最近公共祖先、图论-最小生成树\n\n由于做过[类似的题目](https://codeforces.com/contest/1184/problem/E3),所以对于我来说就跟板题差不多,花了不到半小时就过题了。主体思路是生成最小生成树后检查每一条不在这棵树内的边,使用最近公共祖先维护路径上的边权最大值,随后将这条边的边权替换为给定边的边权即可。\n\n综合性较强,如果没有现成的LCA模板,你需要先学习树上倍增、树链剖分,可能还需要使用线段树等数据结构维护路径最大值;如果没有现成的MST模板,你需要先学习并查集。\n\n\u003c/br\u003e\n***\n***\n\u003c/br\u003e\n\n## Atcoder:第14回 アルゴリズム実技検定 過去問\n\n[problem:AtCoder-past202303_j] 字符串-KMP/扩展KMP、暴力\n\n创新题。我此前不经常写字符串算法题,赛时在做完后面某题之后脑子一热想到了这个做法,于是花了十分钟就A了,感觉非常不错。\n\n题目非常巧妙,将原图的每一行都复制两遍形成新的串 $T$ ,随后将待匹配图的每一行作为模式串 $S$ 跑 $\\tt KMP$ 算法得到每一次出现位置的起始下标,塞入容器中,待每一行都操作完后检查即可。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202303_k] 期望与概率、动态规划\n\n简单期望dp,注意在转移时,上轮期望与本轮新增数量都要乘上本轮概率:`dp[i] \u003d p * (dp[i - 1] + add);` 。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202303_l] 图论-拓扑排序、数据结构-二叉树\n\n模板题略微变形。注意到,只有某一个数字的全部前置限制都解除后才会被输出,这就是一个典型的拓扑排序模型(解除限制即为减少入度);随后注意到输出需要字典序最小,那么即输出最小的拓扑序,将队列改成二叉树即可(STL中的 `priority_queue` 可以简便的做到这一点)。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202303_m] 数据结构-线段树、二分查找\n\n建立线段树处理是很容易想到的,本题的难点在于如何快速的获取修改的位置,这里我们可以借助二分查找完成(典,但是我此前没有遇到过,记录一下),我的代码最终复杂度为 $\\mathcal O(N\\log ^2M)$ ,好像更优秀的封装(AT Library)可以做到单 $\\log$ ,但是一般卡不掉,所以未深入研究。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202303_n] 贪心、数据结构-二叉树\n\n贪心思维题,很难。我们可以注意到题目有两个难点,其一是初始的 $X$ 不确定,其二是 $D$ 的范围过大导致难以枚举。于是引入本题的贪心思想:逆向解题,第 $1$ 天的废料为 $C$,每天减少 $1$,某些日子可以增加废料,询问最少花费使得到达第 $D$ 天、途中剩余废料不为负数。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202303_o] 数据结构-?????\n\n~~写不了,逃了。~~\n\n\u003c/br\u003e\n***\n***\n\u003c/br\u003e\n\n## Atcoder:第13回 アルゴリズム実技検定 過去問\n\n[problem:AtCoder-past202212_j] 几何、暴力\n\n~~最喜欢的几何题~~。题目定义的过于数学,简单的描述即:给定一条线段以及若干条直线方程,询问有几条直线与这一线段有交点。\n\n解法一:叉乘求解两点式直线方程交点+判定交点是否位于线段上(赛时思路)\n\n著名的快速排斥+跨立实验能够解决的是“判断两条线段是否相交”这一问题,然而不幸的是将直线取成线段可能会导致精度问题(本题给出的二维平面范围是 $\\[-10^9,10^9\\]$ ,如果取到极限的话,剩余能够利用的位数只有 $9$ 位,这是比较危险的;而不取到极限的话,由于线段长度不足,很有可能出现遗漏交点的问题),于是我们只能考虑其他解法。\n\n随后想到叉乘,其能解决“判断两条直线是否相交”这一问题,我们可以将线段扩展成直线后计算出交点、随后判定交点是否在线段上这一方式解决原问题,可行。于是考虑如何将题目给出的**一般式方程转换为两点式**,这里其实也会遇到与上面相同的精度问题,于是我们需要尽可能的使整数部分的数位少一些,多分些精度给小数部分,于是一个显然的思路是枚举两个特殊点——与 $x$ 和 $y$ 轴的交点。\n\n注意讨论垂直、平行于 $x,y$ 轴的情况,套用函数即可得解。\n\n解法二:暴力(官方思路)\n\n~~极其简单,简直是降维碾压我赛时的。~~我们知道,对于点线关系,将点的坐标直接代入直线方程即可得到点位于直线上方还是下方。所以对于给定的每一条直线,将线段的两个端点代入判断是否位于其两侧,若是,则相交。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202212_k] 暴力、贪心、搜索、数位dp\n\n刚拿到手的时候就感觉很像数位dp,于是从高位向低位(这是一个贪心)依次枚举判断能否加入答案:从 $10^{18}$ 开始向 $10^{0}$ 枚举倍数位,对于每一个倍数位,再从 $9$ 开始向 $0$ 枚举个数位。复杂度约为 $\\mathcal O(18\\times 9)$,且整体代码非常简短,属于重思维的题目。\n\n注意答案最大不超过 $10^9$ (所以其实可以从 $10^9$ 开始向 $10^{0}$ 枚举倍数位),被这个细节卡了很久。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202212_l] 贪心、二分搜索、数据结构-线段树\n\n创新题。我们将线段先按照右边界从大到小、左边界从小到大排序(这是一个贪心),这样做的后果是——覆盖的区间越广的线段会在越前面。\n\n随后便是即为精彩但是很典的固定一段操作另一端的做法:无视右边界,仅考虑左边界,计算左边界序列的最长非严格递增子序列($\\tt LIS$)。由于排序的存在,这样做的正确性可以被保证。\n\n同时也有线段树的做法,由于我没有这样写,所以略过。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202212_m] 组合数学、图论-搜索\n\n创新题。题面的简单版本为:对于全部的区间 $(l,r)\\ (1\\le l \\le r\\le n-1)$ ,选取编号在这个区间内的所有边连接成新图,统计 $1$ 节点能直接联通的点的数量。\n\n这其实是能够转换为一个传统的计数问题(乘法原理):已知我们知道一个区间 $\\[l, r]\\ (1\\le l\\le r\\le n)$,包含这个区间的全部区间数量即为 $l\\cdot (n-r+1)$ 。\n\n将原问题转化为:只通过编号在 $\\[l,r]$ 之间的边就能从 $1$ 节点到当前节点的 $(l,r)$ 的数量。\n\n首先,全部 $\\dfrac{n(n-1)}{2}$ 个区间都可以直接从 $1$ 到达 $1$ 。对于其他点,使用搜索得到 $1$ 节点到当前点最短路径上需要经过的边的编号的最小、最大值 $C_{Min}$ 和 $C_{Max}$,这说明只通过编号在 $\\[C_{Min},C_{Max}]$ 之间的边就能从 $1$ 节点到当前节点,那么联系刚刚的计数问题,推广得到——有 $C_{Min}\\cdot(n-C_{Max})$ 个区间可以使得 $1$ 节点直接连通当前点。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202212_n] 数据结构-莫队、数据结构-二叉树、暴力\n\n容易发现,题目给出的操作是可以被复原的,这样的性质显然可以使用莫队解决;随后我们考虑如何维护区间,使得区间有序、且可以进行查询与修改,这样的性质显然可以使用二叉树解决,而STL中的 `multiset` 可以满足全部要求。\n\n本题对于技巧性要求较高。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past202212_o] 数据结构-线段树、位运算\n\n线段树高难题,我自认为暂时没能力写,故暂时放一放。\n\n其中操作 $1$ 的解决方法很妙,属于一眼就会但是自己想极难想到的类型——使用一个偏移量 `shift` 记录,于是对于此后所有的区间修改、查询,均先计算出偏移后的区间边界、再做计算。\n\n\u003c/br\u003e\n***\n***\n\u003c/br\u003e\n\n## Atcoder:past201912 - 第一回 アルゴリズム実技検定\n\n[problem:AtCoder-past201912_g] 搜索、暴力、位运算\n\n解法一:位运算+状压枚举(赛时思路)\n\n范围显然,可以跑 $2^n$ 的算法,考虑位运算状态压缩。以 $\\mathcal O(2^n \\cdot 2^n)$ 的复杂度分别枚举位于第一组、第二组中的人,随后计算每一种分组的快乐值,代码较长,赛时敲了半个小时,不过好在一发过了。\n\n\u003e 总结:其实代码里面的剪枝完全可以不要的,先一口气枚举,随后再计算快乐值会比较容易写一些。随后,下方代码中补全了给定数组的另一半(刚开始没补打算用特判的,这里花费了一些不必要的时间),这样做也能方便后续计算快乐值。\n\n解法二:搜索枚举(官方思路)\n\n这个思路就简便很多了,主体和“八皇后问题”很像,先操作后回溯。平时写这种搜索比较少,赛时确实没想到。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past201912_h] 数据结构-线段树、模拟\n\n解法一:线段树(赛时思路)\n\n显然,这是一道线段树能够解决的题目,问题在于有一个操作是对奇数位置进行的,显然,传统的线段树难以区分叶子节点的奇偶性——所以,我在这题中建立了两棵线段树,分别负责奇数、偶数位置。\n\n实现难度并不高,只需要修改使得其能够实现“修改、查询区间最小值”即可,但是要注意细节。赛时敲了四十分钟,然后调BUG调了二十分钟,略显逊色……\n\n\u003e 总结:需要留心的地方在于,如果不存在偶数位置,我们需要特判建一棵只含有一个极大值节点的偶数线段树。\n\u003e\n\u003e 如果不为一个节点,有可能在 `build` 函数中出现 `build(1, 0);` 这样的越界情况(导致RE);\n\u003e\n\u003e 如果不包含一个极大值节点,在计算操作三的最小值时可能出现 $0$ 的情况。\n\n解法二:模拟(官方思路)\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past201912_j] 图论-最短路、暴力\n\n图论,由于存在右下角这个中转点,所以显然不能用传统的 $\\tt dp$ 解题,进而想到枚举路径交点,然后使用最短路暴力求出最小值。\n\n代码实现的难点在于如何将矩阵转化为传统的边、或者可以直接用邻接矩阵写最短路。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past201912_k] 树论-lca\n\n树论模板题,很一眼的 $\\tt lca$ 求最近公共祖先。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past201912_l] 图论-最小生成树、暴力\n\n如果说没有 $m$ ,那么就是很经典的最小生成树模板;加上了 $m$ 之后我们发现这个范围很小,所以其实只是多了一步暴力枚举,本质依旧是 $\\tt MST$ 模板。\n\n然而,本题的难点在于代码的书写上,由于需要暴力枚举、点的编号不定、边权也需要计算,需要较为缜密的代码书写能力。这里提一下我的优化思路,即使用位运算(类似于状压)辅助枚举、$\\tt dsu$ 直接开 $n+m$ 、使用封装减少思考量。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past201912_m] 数学、二分搜索\n\n创新题。所求的式子为 $ans\u003d\\dfrac{a_1+a_2+a_3+a_4+a_5}{b_1+b_2+b_3+b_4+b_5}$ ,假设答案已知,那么移项后式子变为 $(b_1\\cdot ans-a_1)+\\dots+(b_5\\cdot ans-a_5)$ ,容易发现,随着答案单调变化,式子跟随单调变化,那么,只需要二分答案即可。注意实数域二分与传统二分的区别。\n\n至于 $\\it{helper\\ monsters}$ ,由于至多取一只,故并没有什么影响,特判下即可。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past201912_n] 离散化-坐标压缩、前缀和、贪心\n\n难题、创新题,这个前缀和的做法我以前没有遇到过。需要注意题目中有石头的区间是开区间,而这一点正是我个人觉得本题最难的地方所在。\n\n首先离散化坐标是很容易想到的,之后,需要想到一个贪心——答案一定在区间 $(l_i-c,l_i\\]$ 和 $\\[r_i,r_i+c)$ 中取到(这个贪心我不会证明,只能暂时留白)。于是,我们可以暴力枚举全部的端点寻找答案,那么,对于某个区间 $\\[x,y\\]$ 我们该如何计算移走某一个区间中全部石头需要花费的代价呢,这里我们使用到前缀和的思想——移走全部石头的代价**减去**移走区间终点在 $x$ 之前的石头的代价**再减去**移走区间终点在 $y$ 之后的石头的代价。\n\n想到这里,代码就比较好写了。在写题的过程中我还尝试使用线段树来维护代价,然而没能成功,可能需要用到区间合并、动态开点等思想,于是作罢。\n\n\u003c/br\u003e\u003c/br\u003e\n\n[problem:AtCoder-past201912_o] 动态规划\n\n队友补了就没看了。","threadId":152134,"likeCnt":0,"createTime":1690010724000,"isWorkbook":true,"viewCnt":278,"openness":2,"fav":false,"id":3864,"trustable":false}