2021 牛客多校第一场 I.Increasing Subsequence @ Wings            分类 ACM
发布于 星期六, 七月 24 日, 2021 年
更新于 星期一, 八月 16 日, 2021 年

笑死比赛时读错题了.

题目

题意

给一个大小为n的排列P, 两个人在上面选数, 要求如下:

  • 某个人选的数的下标要比之前这个人选的大
  • 每次选的数值要比之前两个人选的数都大

每次选都是等概率从可以选的数中选一个, 第一个人随便选(选择每个数的概率都是$\frac{1}{n}$). 最后不能选了结束. 问结束时期望两人一共选多少个数.

$n \le 5000$

题解

!注意下标是比自己之前选的大, 不和对方比较.

补一下基础知识: 期望dp

期望dp一般这样设:

$dp(i)$ 为当前在 $i$, 还需要期望 $dp(i)$ 的代价到终点(不是从起点开始到dp[i]期望步数)

方程一般长这样:

$dp(i) = v_i + \sum p_j dp(j)$

其中 $v_i$ 是这一步的代价, $j$ 是后继状态, $p_j$ 是这个从状态 $i$ 走到状态 $j$ 的概率. 答案是起点的dp值, 比如 $dp(0)$.

在这个题中, 走一步对应的代价是1, 而等概率选取, 则某个 $i$ 在方程中对应的 $p_j$ 都是相等的, 且是 $\frac{1}{out_i}$, $out_i$ 表示 $i$ 的后继个数.

upd: 写你个🔨写半天错得一塌糊涂. 期望DP

这个题是两个人在走, 所以状态要两维, 设 $dp(i, j)$ 表示第一个人在$i$, 第二个人在$j$, 期望还需要走多少步结束. 还需要考虑是哪一个人走, 由于是排列, 并且满足每次选的数比所有人上次的大, 所以比对手大, 这样直接判断 $a_i, a_j$ 的大小关系就可以知道是谁在走了.

方程分两部分转移

  • $a_i > a_j$, 第二个人走: $dp(i, j) = 1 + \frac{1}{c_1} \sum dp(i, k_1)$, 其中, $k_1$ 满足 $k_1 > j, a_{k_1} > a_i$, $c_1$ 是满足该条件的 $k$ 的个数
  • $a_i < a_j$, 第一个人走: $dp(i, j) = 1 + \frac{1}{c_2} \sum dp(k_2, j)$, 其中, $k_2$ 满足 $k_2 > i, a_{k_2} > a_j$, $c_2$ 是满足该条件的 $k$ 的个数

朴素转移复杂度 $O(n^3)$, 需要优化. 显而易见, $k_1$ 要满足比 $j$ 大, 且 $k_1, j$ 都是第二维, $k_2$ 和 $i$ 同理. 那么可以逆序枚举, 用前缀和(后缀和)的思想来加速转移, 同时可知, $1/c_1 \sum dp(i, k_1)$ 和 $j$ 无关(关系已经通过转移顺序搞掉了).

设 $f(i) = \sum dp(i, k_1), c_1(i)$ 为第一个方程中的$c_1$. 对称地, 再设 $g(j) = \sum dp(k_2, j), c_2(j)$. 以第一个方程为例, 现在还需要考虑的是 $dp(i, k_1)$ 的另一个条件 $a_{k_1} > a_i$. 只有这样的状态, 才能够对 $f(i)$ 产生贡献. 然后会发现, 满足这个条件的状态, 不就是第二个方程吗? 所以做完第二个方程, 即 $a_i < a_j$ 的 $dp(i, j)$ 后, 把它加到 $f(i)$ 中, 同时 $c_1(i)+1$. 另一边同理.

这样就把复杂度降到了 $O(n^2)$.

答案需要枚举一下第一个人选的位置, 第二个人在0, 即 $dp(i, 0)$, 第一个人等概率选, 所以最后是 $\frac{1}{n} \sum_{i=1}^n dp(i, 0)$

代码
int mult(LL a, LL b) {
  return a * b >= P ? a * b % P : a * b;
}
int pls(LL a, LL b) {
  return a + b >= P ? a + b - P : a + b;
}

int power(int a, int b = P-2) {
  int res = 1;
  while (b) {
    if (b&1)
      res = mult(res, a);
    a = mult(a, a);
    b >>= 1;
  }
  return res;
}

int T, n, inv[MAXN], c1[MAXN], c2[MAXN], a[MAXN], dp[MAXN][MAXN], f[MAXN], g[MAXN];

int main() {
  scanf("%d", &n);
  inv[0] = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    inv[i] = power(i);
  }

  for (int i = n; ~i; i--) {
    for (int j = n; ~j; j--) {
      if (a[i] > a[j]) {
        dp[i][j] = pls(1, mult(inv[c1[i]], f[i]));
        g[j] = pls(g[j], dp[i][j]);
        c2[j]++;
      }
      else if (a[i] < a[j]) {
        dp[i][j] = pls(1, mult(inv[c2[j]], g[j]));
        f[i] = pls(f[i], dp[i][j]);
        c1[i]++;
      }
    }
  }

  int ans = 0;
  for (int i = 1; i <= n; i++)
    ans = pls(ans, dp[i][0]);
  ans = mult(inv[n], ans);
  printf("%d\n", ans);

  return 0;
}

留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch