AGC049

• A - Erasing Vertices
  • 题意：给出n(n<100)个点的有向图，重复如下动作直到图为空：每次从当前剩余的点里random一个点，然后删除这个点和所有这个点可以到达的点。问期望的步数是多少。
  • 题解：期望的步数等价于每个点被删除的概率和。那么怎么计算每个点被删除的概率呢。考虑s(u)表示删除这些点之后u就会被删除，那么删除u点的概率就是1/count(s(u))，因为每个点都是等概率的。
  • 代码：https://atcoder.jp/contests/agc049/submissions/18204401
• B - Flip Digits
  • 题意：给两个字符串s，t，和一种操作，对于任意s[i] == '1'的，可以把s[i]变成0，s[i-1] = ~s[i - 1]，问经过多少步可以将s变成t。
  • 题解：注意到操作的本质是将字符串s中的1左移，并且遇到1会都变成0。那么对于s[i] != t[i]的情况，都可以通过从后面最近的1移动过来，完成s[i] == t[i]，注意一下操作可能超过int。
  • 代码：https://atcoder.jp/contests/agc049/submissions/18205268
• C - Robots
  • 题意：给一个无限大的x轴，每个点上有一个robot，现在给n个编号，编号a[i]的球，在a[i]机器人手上，然后球一共有b[i]个，现在有如下操作，编号i个球的机器人可以向左移动一格，然后球个数损失一个，直到球个数变成0，机器人路过的机器人都会被这个机器人吃掉。现在每个机器都要被吃掉或者把手上的球数字变成0，你可以对任意一个球上的编号进行修改，问最少需要修改多少球使得坐标为0的robot不会被吃掉。
  • 题解：对于第i个robot，两种情况，要么走完全程，要么被后面的机器人吃掉。那么对于一个不会被后面机器人吃掉的机器人，这时候有两种选择，一种将自己的一个球变成a[i]+1,把自己吃掉，或者把多余的b[i]-a[i]+1个球编号改成其他的（最优的是改成前面需要自己吃自己的那些球的编号+1），操作2的好处是后面的球都被吃了，不需要自己吃自己了，而且前面的球吃自己的操作，可以被这个操作低消一部分。我们注意到，我们一定最多只有一个第二种情况，所以遍历的时候枚举当前执行第二种情况所需要的操作数，最终和完全不用第二种情况的对比取最小值。
  • 代码：https://atcoder.jp/contests/agc049/submissions/18224296
• D - Convex Sequence GOOD
  • 题意：给定n，m(n,m<=1e5)，长度为n的非负数组，问有多少种满足以下条件的构造方法，使得a[1]+a[2]+...+a[n]=m && 2 * a[i] <= a[i-1] + a[i+1]
  • 题解：首先这个数列可以看成3部分，第一部分斜率是负且斜率只能增不能减少，第二部分斜率位0，第三部分斜率为正，而且也是只能增，不能减少，所以斜率整体是个递增的数列。对于第一部分，我们设dp[i][j]表示一共i个数，且和为j的个数。那么如果当前的斜率发生了变化t，那么i之前的数都要都加上t，设A = t * i * (i - 1) / 2，那么dp[i][j] = dp[i - 1][j - A] + dp[i][j - A]，然后注意到第三部分和第一部分长度和最多只能sqrt(n)，且统计应该一样，对于第二部分，相当于整体数列都+n，所以整体dp非常类似背包！
  • 代码：https://atcoder.jp/contests/agc049/submissions/18219695