首页 > 其他分享 >Z AT 板刷记录

Z AT 板刷记录

时间:2023-07-05 12:12:11浏览次数:29  
标签:mathbb ABC 记录 板刷 sum mid times dp

从 2022-08-25 开始更新。

\(\mathbb{ARC \ 146 \ C}\)

观察

一眼递推,问题在于 \(\Theta(2^n)\) 的复杂度显然不对。
考虑怎么从上一层转移,可以从现在新增的元素里选出一些往上一层合法的集合中加,如果在添加后不合法则情况是上一层的集合存在一个大小为奇数的子集异或值和当前选出的元素相等,继续想,这个子集只可能有一个,因为如果存在两个,则上一层的该集合不合法,即会存在一个大小为偶数且异或和为 \(0\) 的子集。
其实还可以发现一个性质,即是说因为上一层的集合每一个大小为奇数的集合都对应着一个唯一一个不能加进去的元素,那么每一新元素都有 \(2^i - 2^{i - 1}\) 种选法。
具体推一下,定义 \(dp_i\) 为第 \(i\) 层的答案,那么可以拿到 \(dp_{i - 1}\) 。
得到的转移方程为

\[dp_i = \frac{dp_{i - 1} \times (2^i - 2^{i - 1})}{i} \]

边界是 \(dp_1 = 1\) 。
回到最开始的问题,复杂度不对,其实打表可以看到在 \(i \ge n + 2\) 时,答案不会再次变化。

\(\mathbb{ABC \ 256 \ F}\)

/kk 因为这道题没看到弱智题 G

可以考虑一个最蠢的 \(dp_{t,i,j}\) 表示,前确定了 \(t\) 个维度后,距离 \(p\) 为 \(i\) ,距离 \(q\) 为 \(j\) 的多维体的总数,可以写出一个 \(\Theta(nD^3)\) 的转移方程。
然后比赛时就卡在这里了,,,

如果把代码写出来,估计优化就容易了。

for (int t = 1; t <= n; t++) {
    memset(dp[t & 1], 0, sizeof(dp));
    for (int pos = -2 * 1000; pos <= 2 * 1000; pos++) {

      int dis1 = Abs(pos - p[t]);
      int dis2 = Abs(pos - q[t]);
      if (Max(dis1, dis2) > d) continue;

      for (int i = 0; i <= d - dis1; i++) {
        for (int j = 0; j <= d - dis2; j++) {
          dp[t & 1][i + dis1][j + dis2] += dp[t & 1 ^ 1][i][j];
        }
      }

    }
  }

然后要搞一个奇妙的转化,定义 \(s_i = \mid p_i - q_i \mid\) ,把合法的 \((dis1,dis2)\) 分成三类。如下

\((s, 0), (s - 1, 1), (s - 2, 2), (s - 3, 3) \dots (0, s)\)

\((s + 1, 1), (s + 2, 2), (s + 3, 3) \dots\)

\((1, s + 1), (2, s + 2), (3, s + 3) \dots\)

那么这个就可以做了,因为这些合法的点均在一条直线上,最终可以优化到 \(\Theta(nd^2)\)。

\(\mathbb{ABC \ 264 \ G}\)

居然不会写了

标签:mathbb,ABC,记录,板刷,sum,mid,times,dp
From: https://www.cnblogs.com/Iridescent41/p/17528186.html

相关文章

  • Z CF 板刷记录
    七点半的灯火,人潮将我吞没,连同我小小的歌。CF1783E难点在读题,一句话题意是对于两个元素大小在\(n\)以内的序列\(a,b\),找到所有的\(k\)能够满足\(\foralli\in[1,n],\lfloor\frac{a_i}{k}\rfloor\leq\lfloor\frac{b_i}{k}\rfloor\)。假设我们已经对于每一对......
  • 济南市第六人民医院门诊就诊记录
    济南市第六人民医院门诊就诊记录背景因为最近换工作.忘记提前进行体检,有几天的空档期.自己父亲的身体也不是很好,想着趁这个空档期陪父亲检查一下身体.结果发现自己对医院的运作其实一直不是很清晰.想着这里总结一下,为自己,也为他人遇到所需之时提供帮助.晚上时陪......
  • navicat添加触发器实现禁止删除指定表的记录(mysql)
     选中指定表,右键选择设计表 在定义那儿填写语句 BEGINdeclaremsgvarchar(255);setmsg="禁止删除操作";SIGNALSQLSTATE'HY000'SETMESSAGE_TEXT=msg;END......
  • android 基于ListView和CheckBox实现多选和全选记录的功能(转)
    [原]基于ListView和CheckBox实现多选和全选记录的功能应用开发中经常会有从数据库中读取数据显示,然后选中多条、全部记录并且删除的需求。在做定制系统联系人的时候也遇到这样的需求,下面写个简单的通过ListView和CheckBox实现多选、全选的例子。下面是具体的代码,有问题请留言。代......
  • windows 远程桌面连接(mstsc) 删除历史记录
    删除下拉框的记录进入注册表编辑:win+R>regedit按HKEY_CURRENT_USER\Software\Microsoft\TerminalServerClient\Default的路径,删除除了“默认外的”,所有“MRU+数字”的项。删除输入框的默认填充打开当前用户的主文件夹>我的文档(MyDocuments),点选工具栏组织>查看找到隐藏文件和......
  • 实习记录(2)
    torch中的squeeze和unsqueezesqueeze是压缩,对维度进行降维。不写的话,默认将所有维度为1的去掉(我理解就是去掉对应层的"[]"中括号)举例: unsqueeze是和squeeze相反的操作 ......
  • 记录--组件库的 Table 组件表头表体是如何实现同步滚动?
    这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助前言在使用Vue3组件库NaiveUI的数据表格组件DataTable时碰到的问题,NaiveUI的数据表格组件DataTable在固定头部和列的示例中,在键盘操作下表格横向滚动会有问题,本文是记录下解决问题的过程,并最后向Naiv......
  • 中国卫星的3买成功记录
      买入逻辑:1下跌趋势走完后,25.31的低价已出2底部的对称三角形走势非常饱满(重点)3缺口突破底部后,形成一个头肩顶式中继形态,形成3买位置  ......
  • Anolis 8.x (8.6, 8.8, CentOS )安装记录
    硬件:一台DellPowerEdgeT130服务器,2*2T Harddisk软件:Anolis8.6 2023.7.3,发现系统自动下载了很多updates等待安装,选择安装更新,并重新启动系统。启动系统后,在屏幕左上角出现闪烁光标,系统长达10分钟以上无反应。按Ctrl+Alt+del, 系统的Anolis图形标志闪现后,系统重......
  • 记录XPO查询 日志
    记录由XPO产生和执行的sql语句//z2013-02-2714:01:[email protected][T215,L2906,R88,V3140]1.在App.Config中添加如下行:[XML]<?xmlversion="1.0"encoding="utf-8"?><configuration><system.diagnostics><switches&......