Codeforces Round 597

發表於 更新於 分類於 ， Disqus： 文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘
E (模拟,DP,概率论),F(bitDP,容斥原理)

E

原题链接

2300评分

大意

很难直接说 ，看原题目图片

大概就是10x10网格，从左下 横走到头，向上一层，再横走到头，再向上一层，这样走到左上角

每次步长 整数[1->6]等概率

其中有一些纵向梯子，梯子出度为0/1

只能停在 梯子下方时(立刻?)使用梯子，重叠的梯子不能切换,不能从上到下使用梯子, 不能在没有横着走的情况下连续使用梯子

如果 走的步数会导致超过终点那么他不会走

他会尽快走

求期望步数

数据范围

梯子数量<=100

题解

显然虽然我赛内 没有做出来，也知道基本知识点是 dp和概率论，然而我的概率论弱到爆炸

然后也是显然把二维降到一维

官方题解

先定义f函数 如果

i点没有梯子， f(i) = i;

i有梯子， f(i) = 梯子的目标;

i点到终点，的最小期望步数为$dp_i$

显然dp_100 = 0

$$dp_i = 1 + \sum_{r = 1}^{6} \frac{1}{6} \cdot \min(dp_{g(i, r)}, dp_{f(g(i, r))})$$ // 这里min是必要的 因为可能因为一些小梯子错过一些大梯子，不一定爬梯子更优

从i走 r=1->6步,到 i->i+r 或者

其中 当 $i+r<=100$时 $g(i, r) = i + r$ 否则 $g(i,r)=i$

作为一个 概率论弱菜，想说这里的期望步数竟然可以直接取min的咯????

以及为什么明明是 1/6 的前进概率，却可以反过来 还是按照1/6来算???

对于上面会超过终点，也就是$95 \leq i \leq 99$时

$dp_i = \frac{6}{100 - i} \cdot \left( 1 + \sum_{r = 1}^{100 - i} \frac{1}{6} \cdot \min(dp_{i + r}, dp_{f(i + r)}) \right)$

其实也是上面的式子，把其中 走 改为停在原地 $dp_i$再移项得到的

这里我卡了很久很久很久

大概最后能理解 的是

dp表示的是剩余期望步数,是一个最终结果值

如果考虑过程的话，每一次 i 会向 i+1~6 发送 (期望步数-1)*1/6

而计算 当计算到i时，小于i的所有都已经和最终结果相同了，所以对于dp[i]来说

dp[i][最终结果] = sum{dp[i-1~6][最终结果]-1}/6也是满足的

也就是 每次从i走1/6的概率 和反过来 看最终期望值，可以用一样的概率

然后对于尾部的思考 感觉还是没有直接思考出，但是用无穷级数得到一样的答案了XD

感觉自己概率论还是没有入门啊

当然题解的另外一个方法就是 直接模拟个1000次

每次至少前进一步，那么100步以后，就只剩下 最后几个，然后就没了，每轮的量也就100*6 随便搞啊 精度应该不会爆吧

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

// 10x10
// 左下->左上

// 蛇形路线
//
// 有纵向梯子
// 不能用连续的后一个梯子

int main() {
  int grid[10][10]; // 输入
  int arr[110]; // 可以用梯子到达的目标
  int flat[10][10]; // 映射为一维数组
  rep(i,0,10){
    rep(j,0,10){
      scanf("%d",grid[i]+j);
      flat[i][j] = (9 - i) * 10 + ((i & 1) ? j : 9 - j);
      arr[flat[i][j]] = flat[i-grid[i][j]][j];
    }
  }

  double dp[100];
  dp[99] = 0;
  per(i,0,99){
    double dpi = 0;
    int c = 6;
    rep(r,1,7){
      if (i + r >= 100) continue;
      dpi += min(dp[i + r], dp[arr[i + r]]) / 6;
      c--;
    }
    dp[i] = 6 * (1+dpi) / (6 - c);
  }
  printf("%.10lf\n",dp[0]);
  return 0;
}

参考

https://www.cnblogs.com/LLTYYC/p/11782276.html

问题难点分析

为什么可以反过来使用概率,反过来用不等于反着走，而且期望的事情，可以把dp[i]改成dp[i][过程中/最终值]来加深理解

然后就是自己能到自己的理解了，依照各个题解过程意思是等价代换 推新公式即可？

然后就是题目这里的梯子，其实是一个可选择的不消耗次数的传送门，当你停在门前时才可选择，不能路过时使用。

F

原题链接

2300评分

大意

t组测试数据

求 l<=x,y<=r中 满足 x+y==x^y的有序对(x,y)的个数

数据范围

0<=l<=r<=10^9

题解

如果一道题看上去像bitdp，长得像容斥原理，那么它就是 bitdp+容斥原理

假设 F(n,m)表示 a属于[0,n], b属于[0,m]

那么ans = F(r,r) - 2F(l-1,r) + F(l-1,l-1)

所以如果能计算F(n,m)即可

G[前i位][x 是否贴着上限][y 是否贴着上限]的方案数

贡献

G[i][false][false]:

x3 -> G[i+1][false][false]

(因为都没有贴着上限，所以x,y值无论填0/1都 依然没有贴着上限,由因为两个只能最多有一个1,所以只有(0,0),(1,0),(0,1)三种))

对于

G[i][false][true] / G[i][true][false] / G[i][true][true]

其中至少有 一个是贴着上限的，那么，贡献时注意是否上限，填写的时候不要超过上限

也注意x&y == 0 也就是x+y<=1

1
2
3
4
5
rep(x,0,2){
  rep(y,0,2-x){
    G[i][ln & ( x == ((n>>(30-i))&1) )][lm & ( y == ((m>>(30-i))&1) )] += G[i-1][ln][lm];`
  }
}

当然可以用滚动数组进行优化

代码

官方题解

https://codeforces.com/blog/entry/71080

直接设f(l,r)是l<=x,y<r的答案，也就是真的答案是f(l,r+1)

有f(0,r)=2r-1+f(1,r), 因为 (0,0),(0,1~r-1),(1~r-1,0)都合法 一共(2r-1)

如果l,r都大于0那么 f(2l,2r) = 3 f(l,r)

其实和上面的数位dp 推理很像， 这里是考虑最后一位， 只有3种可选的，且都合法，因为有2倍保证

然后再 把 l,r 不是2的倍数的 和2的倍数之间找出关联，最终可归约到 f(0,?) 即可

问题难点分析

第一个是 我有往数位dp想，但是没想到具体

一个是没有拆解成F(x,y)变成类似前缀和 或者说计算子矩阵和的样式

另外就是数位dp做的题太少，还是不够熟悉

问题还有就是 两种方法，只要在草稿纸上多画一画会变得简单很多。

虽然以前对两个的维度来做前缀，或者向下归约的题型做过，但实际操作 还是体现出了不熟练

容斥是没怎么用还是矩阵和数位dp