这里的题目前来说都是 Atcoder 中比较简单的题。但我还是没几道是自己想出来的。

AGC018C : Coins : 贪心

  • $x+y+z$个人,每个人有 $a,b,c$三个参数,将这些人分为 $X,Y,Z$三类,求 $\sum_{i\in X}a_i+\sum_{i\in Y}b_i+\sum_{i\in Z}c_i$的最大值
  • NOI2019 有类似的一道题。假设只有 $a,b$两个参数,我们可以先将所有人放入集合 $Y$,然后选择 $a$个人放入集合 $X$。选择的那 $a$个人一定是 $a-b$最小的几个。
  • 同理,如果分为了三类,假设我们已经确定了哪些人放入 $Z$,我们用上面的方法就可以了。如何利用上面的方法呢?我们还是将所有人按照 $a-b$排序,那么剩下的人中放入 $X$的一定都在放入 $Y$的人的左边。根据这一性质,我们可以枚举这两种人的分界线,然后进行贪心。
  • 我只想到了第一步,第二步没有想到。我曾试验过这样一种做法:先将任意的 $x+y$个人用方法 1 分配进 $X,Y$两个集合,然后不停添加新的人,进行替换。这样的做法存在的问题是:无法保证权值单调,因此不能用单调队列维护贪心。

AGC080F : Prime Flip : 匹配

  • 给定一排无穷多的硬币,只有有限个位置反面朝上。每次选择一段长度为奇质数的区间,将它们区间翻转。求最少多少次使得所有硬币正面朝上。
  • 先将序列转化为前缀异或序列,则每次我们可以同时翻转两个距离为奇质数的位。
  • 根据素数分布,两个距离为偶数的位我们可以 $2$步完成同时翻转,距离为奇数但是不是质数的位,我们可以 $3$步完成翻转。
  • 因此我们需要将所有的位两两匹配(显然有偶数个位),且匹配权值为:
    $$
    \begin{cases}
    1 & (|x-y|\in \mathcal P\text{\ } {2})\\
    2 & (|x-y|\in {2n })\\
    3 & (|x-y|\in {2n+1}\text{\ }P)
    \end{cases}
    $$
  • 实际上,我们只需要最大化权值为 $1$的匹配即可。设有 $E$个位的下标为偶数,$O$个位的下标为奇数,$x$为权值为 $1$的匹配数,则 $ans=x+\lfloor (O-x)/2\rfloor\times 2 + \lfloor (E-x)/2\rfloor\times 2 + ((O-x)\bmod 2)\times 3$,这个函数有关 $x$是单调的。最大化 $x$直接使用二分图最大匹配即可。
  • 我只想到了第三点,没有意识到第四点。

AGC009D : Uninity : 贪心

  • 给定一棵树,求点分治的最浅层数
  • 需要将模型转化为:给树的每个节点编号,使得最大编号最小,且任意两个相同编号的节点之间的路径上必须有一个节点的编号大于这两个节点的编号。
  • 然后进行贪心即可,在 Dfs 的同时给树的每个节点一个尽量小的标号。
  • 我没有想到这个转化。我以为答案只与直径的长度有关,实际上存在反例。

ARC072E : Alice in linear land : 贪心

  • 给定 $y$,$x$一开始等于 $0$,给定一个数列 $d_i$,依次对于 $i=1\cdots n$,如果 $|x\pm d_i-y|<|x-y|$,则将 $x$更新。对于每一个 $i$,求能否将 $d_i$更改后使得最终 $x\not=y$
  • 我们可以从后往前动态维护,对于剩余的序列,如果起始位置为每个地方,能否到达终点。
  • 但是维护这个东西的复杂度较高,我们可以想一想能否少维护一点东西。
  • 实际上,我们只需要维护最小的距离 $f[i]$使得如果 $x,y$的距离为 $f[i]$,时,$x$经过序列 $d[i\cdots n]$没法到达 $y$
  • 我花了很久 (分两次思考,两次间隔 9 个月,每次大概都花了半个小时以上) 才想到了第 3 点。

ARC083F : Collecting Balls : 基环树模型

  • 给定 $n\times n$的矩阵上的 $2n$个点,矩阵的左侧有每行有一辆向右开的车,下方每列有一辆向上开的车。车出发后会捡起遇到的第一个点。有多少种让车出发的顺序可以使所有的点被捡到?
  • 假如一个点只能被一个车捡,或者一辆车的路径上只有一个点,那么这两者一定需要匹配。将可以匹配的车和点删除后,运用鸽巢原理可以知道,每辆车的路径上都有两个点,每个点都可以被两个车捡,它们的关系大致形成几个环。
  • 这就启发我们,我们刚才删掉的是基环树的树边,剩下的是环。
  • 实际上,如果 $(x,y)$处有一个点,那么在图 $G$上的点 $x,y$之间连一条边即可。一种合法的车和点的配对方式对应着一种合法的将每条边分配到它的端点的方案。当然,并不是每一种安排方式都可以任意安排车启动 d 的顺序。我们需要保证在启动车 $i$之前,所有挡住它的点已经都被捡起了。这种关系对应的是图 $H$上的一种拓扑序,且图 $H$是个森林。
  • 这道题难度很大,我花了很久只能想到第一步。实际上类似的模型我曾经见过,只能没有突发奇想将这个问题和基环树模型联系起来。

ARC06E : Addition and Subtraction Hard : 贪心

  • 给定一个数字和加减号组成的算式,加括号使得结果最大。
  • 首先,在符号后面加左括号才有用。
  • 然后我以为只需要加一层括号即可,因为两层括号会相互抵消,但是存在反例:
  • 1 – (20 – (13 + 14) – 5)
  • 但是三层括号就没有必要了,因为第二层括号已经可以把第一层括号内部的第一个负号以后的所有数字都变成正的,而第一个负号前的数字就算再添括号也不能变成正的。
  • 因此 Dp 一下,状态设两维,分别表示当前位置和括号层数就可以了。
  • 我想到了这 5 点。
分类: 文章

2 条评论

quhengyi11 · 2019年8月24日 9:43 下午

讲个故事,今天 nju 学科营比赛第一题就是 agc018C,awsl

    boshi · 2019年8月28日 9:46 上午

    奇迹奇迹

发表评论

电子邮件地址不会被公开。 必填项已用*标注