XXI Open Cup, Grand Prix of Belarus D.Bank Security Unification @ Wings            分类 ACM
发布于 星期一, 十一月 1 日, 2021 年
更新于 星期一, 十一月 1 日, 2021 年

题目

题面

长度为 $n$ 的序列 $f_n$, 从中选出若干个数, 不改变其相对顺序, 使得 $\sum\limits_{j=1}^{k-1} f_{i_j}\&f_{i_{j+1}}$ 最大. $2 \ne n \le 10^6, 0 \le f_i \le 10^{12}$.

题解

首先很容易想到一个 $O(n^2)$ 的 dp: 设 $dp(i)$ 为前 $i$ 个中, 选的最后一个为 $i$, 能得到的最大值. 方程为 $dp(i) = \max\limits_{1 \le j < i} \{dp(j) + (f_i \& f_j)\}$. 但很显然 $O(n^2)$ 是过不了的. 并且这范围好像用个数据结构维护起来都可能 T. 这里有个位运算. 所以一个方向是按位考虑.

我们看这个方程实际上是在干什么, 他就是一个很简单的枚举. 然后我们看一般的动态规划优化是在干什么, 他是将一些一定不是可能的最优解排除掉, 不去枚举他, 而是枚举一定可能是最优解的决策点. 那么我们需要做的就是从这个方向去考虑. 结合位运算, 那么一个方向就是, 考虑每一个位, 能不能排除一些一定不是最优的解.

由于 $f_i$ 对 $dp(i)$ 多出来的贡献是每一位是 $1$ 的个数, 那么我们可以枚举第几位, 考虑"这一位是1"的所有决策. 把这些决策单独拎出来, 一定会从离 $i$ 最近的点 $k$ ($k < i$) 转移过来, 否则假设从 $l$ ($l < k$) 转移过来, 那么如果把 $k$ 加进去, 答案会更优, 因为这一位的贡献是一样的, 但是由于 dp 值是递增的, 所以从 $k$ 转移会更好. 然后考虑"这一位是0"的所有决策, 也是同理. 那么我们把每一位都这样考虑掉, 实际上就是减少了很多不必要的枚举量, 从而使复杂度降下来.

通过这题, 可以发现 dp 优化的本质, 这也是我一直以来没有掌握的东西. 如果我们从另一个角度, 另一个方面去做"枚举", 注意依然是枚举, 只不过是换一个分类, 换一个顺序. 从这个角度去考虑"不优"的决策点, 就可以做到优化. 或者可以从题目本身的性质去想, 比如发掘单调性. 但是我太菜了, 即使能够发现性质, 也不知道怎么放在 dp 中去优化(jyz的思维就是这个, 所以jyz很强我很菜). 所以还是先从思考方向去入手叭.

然后注意 & 运算优先级问题, 和左移右移的数字, 超过 int 的要用 LL 的数字, 如 1ll << 1.

代码
int T, n, last[MAXN][2];
LL f[MAXN], dp[MAXN];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%lld", f + i);
  LL ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 40; j++)
      for (int k = 0; k < 2; k++)
        dp[i] = max(dp[i], dp[last[j][k]] + (f[i] & f[last[j][k]]));
    for (int j = 0; j < 40; j++)
      last[j][(f[i] & (1ll << j)) > 0] = i;
    ans = max(ans, dp[i]);
  }
  printf("%lld\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