20190817笨笨的套题

A \(DHOJ 1503\) 笨笨与电影票

B \(DHOJ 1506\) 笨笨玩糖果

C \(DHOJ 1506\) 笨笨玩糖果

正解

  1. 求出哪些是必胜态还是必败态
  2. 胜利要尽量快,失败要尽量慢
  3. 显而易见这道题是有一个博弈的背景的,那么根据博弈的那两个经典结论,只要能转移到一个必败态的就是必胜态,如果一个必败态都转移不到的就是比败态。
    那么我们首先将0与1初始化为必败态,对于每一个数i,减去所有比i小的所有质数,如果有必败态即为必胜态,如果都转移不到就是必败态了。
    接着再留心一下题目,题目要求至多x步,那么就是取得胜利的最多次数了。这样的话因为已经求出了哪个点是必胜态与必败态,我们也便可以推出转移方程:
    如果这个状态i是必胜态,那么能转移到它的一定是比它小的j的必败态,因为知道自己会胜利,那么一定会选择其中的最小步数。
    如果这个状态i是必败态,那么能转移到它的就是比它小的任意一个数了,因为知道自己会失败,那么一定会选择其中的最大步数。
    这道题目最恶心的就是卡常数了。于此我使用了o(n)的素数筛来筛出质数,并同时处理出比i小的最大素数是第几个素数,这样能够尽量减少后期的枚举量,以便不被卡常

思路

  1. 没想到第二步

D \(DHOJ 1507\) 笨笨的宇宙蘑菇 题解

正解1

  1. 杨辉三角
  2. 卡特兰数,重点就是无效序列失效后面的序列反转
  3. 高精度
  4. 分享图片

ans就是C(n,[n/2])
首先,把那个三角形当做一个图来看,每一个点的数字表示的含义就是从顶点走到该点的路径的数目。
路径数目可以转换为序列数目,从定点0开始 向左为-1 向右为+1
所以路径的数目也就等价于由-1和+1组成的,长度为n-1的,任意前k项和都大于等于-1的个数。

解释:

  1. 因为到第n天,一共经历了n-1次转换的过程。
  2. 如果任何时刻出现了序列前k项的和为-2,则表示该路径经过比-1(也就是第一个位置)还要左的地方,这是不允许的。

接下来进行分析一个无效序列的特点:
假设这个序列含有m个-1(有C(n-1,m)种摆放方法)
如果这n-1个数组成的序列是无效的,说明有一个最小的k使得前k项和为-2,也就是有 [k/2]-1 个1 和 [k/2]+1个-1
如果我们把这k个数反向 也就是1变为-1 -1变为1 则得到了一个含有m-2个-1的序列
这种变换是一对一的(因为反向的特性) 所以换一种说法就是
在一个含有m个-1的序列的集合里,失效的序列的个数正好等于 由m-2个-1的序列组成的集合的大小
数学语言就是
C(n-1,m) - C(n-1,m-2)
而遍历m从0到[(n-1)/2]+1 = [n/2],求和。可以得到
Ans = C(n-1,0) + C(n-1,1) + [C(n-1,2)-C(n-1,0)]+[C(n-1,3)-C(n-1,1)] + [C(n-1,4)-C(n-1,2)] + ....+[C(n-1,[n/2])-C(n-1,[n/2]-2)]
化简得到
Ans = C(n-1,[n/2]-1) + C(n-1,[n/2])= C(n,[n/2])

正解2

  1. 打表,输出1的个数
  2. 找规律
  3. 高精度

正解3

  1. 打表,输出1的个数
  2. 看出为卡特兰数
  3. 高精度

思路

  1. 模拟,看出符合杨辉三角变化 或 应该打表输出1的个数

E \(DHOJ 1508\) 笨笨的电路

正解

  1. 题目的限制条件很多,但是有很明显的阶段性,及BC类点之间AB类点之间应该是分做两个不同的子问题的。
  2. (本题的第一个难点):对于一个B类点,如果它到N+M+T点(方便起见,后面称其为终点,点1为起点)有奇数条路径,那么改变它的信号就会改变终点的信号,如果有偶数条就不会改变.因为如果改变了一个点的信号,从它开始往后走能到达的点都会被改变一次.显然只有被到达奇数次的点才会改变信号。这样就可以把B类点分成3类,一类是到终点有奇数条路径的,称为”有效点“,一类是偶数条路径的,称为"无效点",剩下的是没法到达终点的,是”废点“,直接忽略掉就可以了。
  3. 如果终点的信号是1,那么根据贪心的原则把一个有效点和起点连起来就好了。如果信号是0,那么有2种情况:一种是取一个无效点,一种是取2个有效点。
  4. 本题的第二个难点就是取2个有效点的情况。 也就是有一个起点,2个终点,把起点和2个终点都连起来的最小费用. 设2个终点分别为x,y,显然起点到x的最短路+起点到y的最短路是错误的,因为2条最短路可能会有重叠的路段,那么这些路段费用就算了2次. 题解里没给出做法,我的做法是先跑一遍floyd,然后枚举到x,y的路径在哪个点第一次分岔.(预处理f[i][i]=0,否则无法处理在一号店分岔的情况)容易证明最优解只可能有一个分岔点。假设有多个分岔点,那么对于任意两个分岔点之间的2条路,如果费用一样不影响结果,如果费用不一样,显然不如合并到费用小的那一条.
  5. 所以算法就出来了:先dp出终点到所有B类点的路径数,给B类点分类。根据k是0和1分别计算。如果k=0,还需要枚举选哪2个有效点,并枚举分岔点。 总的复杂度为O(N^3+T).

思路

  1. 第3步没有分类讨论
相关文章
相关标签/搜索