首页 > 其他分享 >A2OJ Ladder 21 简要题解

A2OJ Ladder 21 简要题解

时间:2023-11-09 19:12:48浏览次数:37  
标签:submission contest 题解 Ladder codeforces https A2OJ com 考虑

https://earthshakira.github.io/a2oj-clientside/server/Ladder21.html

只记录 Difficulty level >= 8 的。有很多题是口胡的。写了的会标注提交记录。还有些很久以前写过的题就懒得搬提交记录了。

71. CF444E DZY loves planting

我们二分答案,然后可以这样转化:把权 \(\ge d\) 的边全部切掉,需要然后需要使得 \(i,p_i\) 不在同一连通块。如果所有连通块大小都 \(\le n/2\) 那么显然可行;否则考虑最大连通块,如果其余连通块的 \(\sum x\) 要比这个连通块的 size 小那么肯定不行,否则一定可行。

https://codeforces.com/contest/444/submission/232029798

72. CF536D Tavas in Kansas

首先注意到和图的关系不大,我们分别求出每个点到 \(s,t\) 的最短路,排序后就可以直接 DP 了。\(f(i,j)\) 表示 S 已经选了距离它前 \(i\) 近的,T 已经选了距离它前 \(j\) 近的,S 先手。\(g\) 同理。考虑转移。\(f(i,j)=\max -g(k,j)+p(k+1,i)\),其中 \(p(l,r)\) 表示 \([l,r]\) 中距离 T \(> j\) 的点权和。于是我们在固定 \(j\) 时,可以轻松借助单调栈求出所有 \(f(i,j)\),求 \(g\) 同理。复杂度 \(O(n^2)\)。

73. CF605E Intergalaxy Trip

考虑对于 \(i\),设其临边的点按 \(f\) 排序为 \(a_1,\dots,a_m\),则有 \(f_i=\sum_j (1+f_{a_j})e_{i,a_j}\prod_{k<j}(1-e_{i,a_k})\),其中 \(a_m=i\)。把 \(f_i\) 项的系数移到左边,就是一个式子了。考虑如果我们每次能保证用 \(f_i\) 最小的点去更新其它点,那么 \(f_i\) 这个式子只会往后面填上一项,并且更改 \(f_i\) 项的系数。于是我们每次找到 \(f_i\) 最小的点,显然它不会再被更新了,用来更新别的点即可。

https://codeforces.com/contest/605/submission/232024752

74. CF407D Largest Submatrix 3

考虑先钦定上边界,然后下边界往下扫,维护每列的 \(l_i,r_i\) 表示若要包含这列,那么必须满足 \(L\ge l_i\),\(R\le r_i\),然后就可以对右边界扫的时候维护一个单调队列。暴力更新 \(l_i,r_i\) 逃不掉求前驱后继的 \(\log\)。考虑上边界从下往上扫,然后每次考虑上边界往上挪后对每行的所有列的 \(l_i,r_i\) 的贡献,发现可以做到 \(O(n^3)\)。

https://codeforces.com/contest/407/submission/232016115

75. CF455D Serega and Fun

可以考虑分块。每个块用一个双端队列维护块内的值,然后每个块再维护一个桶。

但是这题可以 polylog。考虑维护一个维护原序列的 treap,和一个对于每个值都维护这个值的这些点的 treap,构成一个平衡树森林。然后我们每次问询,需要在 \(k\) 代表的平衡树上分裂出一段区间,满足这段区间在原序列上位于 \([l,r]\)。查在原序列的位置可以直接在第一个 treap 上查。

76. CF484E Sign on Fence

一种整体二分的方法:考虑离散化后整体二分,然后每一个分治层相当于维护一个 01 序列,从左往右不断把一些位置的 0 变成 1,求区间最长连续段。这是双 log 的。

EI 的单 log 做法:考虑把 \([ l,r]\) 的最大值 \(f_{l,r}\) 形成的表格画在坐标系上。于是这个表格应该是一个由若干个矩形拼成的45°的直角三角形,然后每次查询一个斜线段上的最大值。考虑把坐标轴变换,让问询变成水平的线段,那么现在修改就变成了一堆左右边平行于y轴的平行四边形。考虑把平行四边形切成两个三角形+一个矩形,或两个三角形+一个上下边平行于x轴的平行四边形。矩形直接做,平行四边形再把它变换成矩形后直接做,三角形考虑分别统计问询线段经过直角边,经过斜边和被包含的情况。单 log。

77. CF321E Ciel and Gondolas

首先考虑暴力 DP。\(f(i,j)\) 表示前 \(i\) 个分成 \(j\) 段。首先我们可以仔细分析拥有决策单调性,所以通过整体二分复杂度降为 \(O(nk\log n)\)。但是实际上由于这是二维 DP,决策关于 \(i,j\) 都是递增的,所以可以 \(O(n^2)\) 做。

还有,答案关于 \(k\) 是凸的,所以也可以 wqs 二分,结合决策单调性的整体二分可以做到 \(O(n\log^2 n)\)。

78. CF568D Sign Posts

考虑一些性质:对于一个点,如果它被 \(k+1\) 条直线经过,那么它必选;任意 \(k+1\) 条直线形成的交点中,必有一个点被选。利用这个性质,进行转移。并且在转移的时候,对于选出的 \(k+1\) 条直线的形成的交点中,选出被经过次数最多的优先去转移。并且进行一个微小的记忆化,对目前剩余的直线以及目前的 \(k\) 进行哈希然后记忆化。在有解的时候跑的飞快。

ps. 这题 CF 上数据十分水… 把其中的一些数据的前 \(30\) 条直线拉出来,能卡掉洛谷题解区的所有解。

https://codeforces.com/contest/568/submission/232054523

79. CF285E Positions in Permutation

考虑二项式反演,然后把排列变成二分图匹配的形式。现在我们需要钦定一些点满足第 \(i\) 层的点匹配第 \(i-1\) 层的点。可以直接 DP:\(f(i,j,0/1,0/1)\) 表示前 \(i\) 层配了 \(j\) 个且第 \(i\) 层的左右部分别有没有配。然后再二项式反演即可。

https://codeforces.com/contest/285/submission/231948437

80. CF547E Mike and Friends

一个不好的方法是建出广义后缀树后直接线段树合并。更好的做法:建 AC 自动机,离线后把问询拆成对于 \(s_1,\dots,s_r\),\(s_x\) 出现了多少次。考虑对 \(r\) 扫描线,每次把 trie 路径上的点 +1,然后问询就是 fail 树上子树和。

81. CF461D Appleman and Complicated Task

首先我们可以发现这个现实很严。更进一步地,只要确定了第一行,那么剩下的都能全部确定。考虑用第一行来表示剩下的格子上的数。设第一行的格子的值为 \(x_1,\dots,x_n\),那么我们可以发现某一个格子一定是一段同奇偶的连续 \(x_i\) 的异或和。于是我们设 \(x\) 的前缀异或为 \(s\),那么限制就可以描述成 \(s_i\oplus s_j=0\) 或 \(s_i\oplus s_j=1\)。用并查集即可。

https://codeforces.com/contest/461/submission/231912114

82. Stairs and Lines

怎么看都可以直接轮廓线吧…复杂度看上去是 \(O(2^nn w)\),但是感觉常数挺小的啊。

如果 \(w\) 更大一些呢?处理出上一列轮廓线为 \(s\) 到下一列轮廓线为 \(t\) 的转移系数,然后矩阵快速幂。

83. CF494C Helping People

首先离散化后,相当于长 \(O(q)\) 的序列,然后有 \(q\) 次操作。由于操作区间不交,所以可以搞出 \(O(q)\) 个区间使得每个区间都包含或者等于一个操作区间。\(f(x,y)\) 表示对于区间 \(x\),最大值恰好为原先区间最大值 \(+y\) 的概率。转移是容易的。

84. CF494D Birthday

把平方拆开后暴力各种分类讨论。/tuu

85. CF477D Dreamoon and Binary

考虑 DP:\(f(r,l)\) 表示截至到 \(r\),最后一个分割的串为 \(S[l,r]\),最小分段数。然后我们在 \(r\) 处尝试更新所有以 \(r+1\) 为起点的 \(f(x,r+1)\)。具体而言,\(f(x,r+1)\) 可以由 \(S[l,r]\le S[r+1,x]\) 进行转移,于是我们可以用单调栈加速转移。比较两个数可以用 trie 进行预处理。求答案暴力比较所有的 \(S[i,n]+f(n,i)\) 即可。

86. CF487D Conveyor Belts

考虑对于线段树上每个区间 \([l,r]\),处理出数组 \(v\),其中 \(v_j\) 表示如果从 \((l,j)\) 出发,那么最终会跑到什么地方。容易发现这是可以简单合并与修改的。复杂度 \(O((n+q)m+(Cm+q)\log n)\)。

https://codeforces.com/contest/487/submission/231889491

87. CF505E Mr. Kitayuta vs. Bamboos

二分答案 \(d\),然后倒过来做。倒过来相当于一开始每个都是 \(x_i=d\),然后第 \(t\) 轮需要保证 \(x_i\ge t\times a_i\),然后选 \(k\) 次加 \(p\),并希望最终能 \(x_i\ge h_i+m\times a_i\)。于是我们贪心,维护每个元素存储 \(x_i\) 最紧急的要求是,在往后的 \(r_i\) 轮之内需要加 \(w_i\) 次 \(p\)。这些条件最终都会被满足,于是我们肯定是优先选择 \(r_i\) 最小的进行加。

88. CF601E A Museum Robbery

动态背包。看上去没有什么更好的解法,只能硬线段树分治。复杂度 \(O(nk\log n)\)。

89. CF512D Fox and Travelling

这题的操作方式相当于剥一度点,于是能剥的点一定形成一个森林。于是我们对森林做树形 DP,\(f(i,j)\) 表示 \(i\) 子树剥掉 \(j\) 个点的方案数,合并类似于 EGF 卷积。环上挂着的相当于有根树,非环上的相当于无根树。无根树要钦定一个最后一个选的点作为根。最后要除掉选根的贡献。所以总复杂度 \(O(n^3)\)。

90. CF258D Little Elephant and Broken String

考虑这样的 DP:\(f(i,x,y)\) 表示对于两个数 \(p<q\),它们一开始位置在 \(x,y\),那么在经过了 \([i,m]\) 的这些操作后,最后 \(p,q\) 形成逆序对的概率。那么转移就很方便,从 \(i+1\) 到 \(i\) 只会更改 \(O(n)\) 个位置的值。所以总复杂度 \(O(n(n+m))\)。由于和 AGC30F 是几乎一样的,就放 AGC30F 的代码了,因为 AGC30F 有取模,我喜欢取模不喜欢小数。

https://atcoder.jp/contests/agc030/submissions/47373650

91. CF547D Mike and Fish

考虑转化为图论模型。把每行每列看作点,每一个整点看作一条边,把染色看作定向。由于是二分图,所以可以对于每行,入边为蓝;对于每列,出边为蓝。由于最多差一,于是意味着偶数时必须相等,可以想到欧拉回路。允许差一的限制表示每个奇点可以再连一条人为加的边出去。由于奇点数一定为偶数,所以一定可以连成一个欧拉图。然后跑欧拉回路,给边定向,即可。

92. CF484C Strange Sorting

这个 d-sorting 没有什么性质,考虑直接做。考虑令对区间 \([1,k]\) 的置换为 \(P_1\),那么我们现在希望求得对 \([2,k+1]\) 的置换 \(P_2\)。即原本 \(x\to y\) 要变成 \(x+1\to y+1\)。可以理解为 \(x\to x-1\to y-1\to y\),于是 \(P_2=(2,\dots,n,1)\circ P_1 \circ (n,1\dots,n-1)\)。令 \(Q=P_1\circ (n,1,\dots,n-1)\),则全部结合起来可以得到最终总的置换 \(P\) 为 \(Q^{n-k+1}\circ (n,1\dots,n-1)^{n-k+1}\)。然后就做完了。

https://codeforces.com/contest/484/submission/231938693

93. CF555E Case of Computer Network

考虑边双联通分量一定可以定向为一个强连通分量。于是我们边双缩点后,就转化为了一棵树,然后需要进行定向使得 \(s_i\) 可以到达 \(t_i\)。这个是 Trivial 的,树上差分即可。

94. CF521D Shop

首先对于每个数,一定是先赋值,再加。赋值一定只需要保留最大的,于是就可以转化为加。加一定是优先加最大的,所以对于每个数的加,把它从大到小排序后,一定是从前往后去选,于是就可以转化为乘法。然后就全是乘法了,就做完了。输出方案的时候需要注意一下细节。

95. CF559E Gerald and Path

考虑一个性质:我们把所有没有实际贡献的线段删掉后,每个区间最多被两个线段覆盖,否则一定可以进行调整。然后考虑离散化后进行一种 DP:\(f_{i}(j,k)\) 表示第 \(i\) 段被 \(j,k\) 覆盖(\(j<k\),若只被覆盖一次那么 \(k=0\),没有被覆盖则 \(j=k=0\)),前 \(i\) 段中被覆盖的最大长度和。我们发现每次转移实际上从 \(f_{i-1}\) 转移过来只会修改 \(O(n)\) 个位置的值,并且除 \((0,0)\) 外全局加 \(x\)。后面那个我们稍微修改一下状态,变为没被覆盖的最短长度和,就只需要在 \((0,0)\) 处加 \(x\) 了。总复杂度 \(O(n^2)\)。

https://codeforces.com/contest/559/submission/231741031

96. CF536E Tavas on the Path

树剖板板题。考虑离线,按 \(l\) 排序。然后我们就是单点修改,然后树剖维护题目中说的这个东西即可。可能代码会比较复杂一些。

97. CF288E Polo the penguin and lucky numbers

考虑把每个数的贡献拆在其 LCP 处算。按高位往低位 DP。对于 LCP 的贡献,DP 时记录平方和即可;LCP 后面一定是 7444... 和 4777...,统计个数以及 LCP 之和即可。

https://codeforces.com/contest/288/submission/230933609

98. CF364D Ghd

考虑每次选一个数,有 \(1/2\) 的概率这个数在答案集合中。然后假设已经钦定了包含数 \(x\),我们令 \(b_i=\gcd(a_i,x)\),那么我们就需要对于每个 \(d\mid x\) 求 \(d\mid b_i\) 的个数。写一个 dfs 做迪利克雷前缀和即可。复杂度 \(O(T(n\log n+d_nw_n\log n))\),其中 \(T\) 取 \(10\) 即可。但是感觉后面那个用暴力求不会差太多。

https://codeforces.com/contest/364/submission/231584365

100. CF590E Birthday

本质上题目是让我们在子串偏序关系中选出一个最长反链。于是我们建 AC 自动机,然后对于每个 trie 上节点找到 fail 树上第一个有串的祖先,连边后再 floyd 求传递闭包即可得到偏序关系。然后就是最长反链了。

https://codeforces.com/contest/590/submission/227682207

标签:submission,contest,题解,Ladder,codeforces,https,A2OJ,com,考虑
From: https://www.cnblogs.com/TetrisCandy/p/17822576.html

相关文章

  • 题解:疯狂lcm
    %你赛打到一半来写个题解link:疯狂lcm题意,求:\[\sum_{i=1}^{n}lcm(i,n)\]不多说废话,直接开推:\[\begin{aligned}&=n\sum_{i=1}^{n}\frac{i}{gcd(i,n)}\\&=n\sum_{d\midn}\sum_{i=1}^{n}\frac{i}{d}[gcd(i,n)=d]\\&=n\sum_{d\midn}\sum_{i=1}^{n}......
  • KubeEdge部署 完美运行 附问题解决方法
    云端部署环境准备一、部署前工作(k8s、docker安装及配置、初始化集群、golang安装、keadm安装)配置网络参数cat>>/etc/hosts<<EOF#GitHubStart52.74.223.119github.com192.30.253.119gist.github.com54.169.195.247api.github.com185.199.111.153assets-cdn.gith......
  • linux/docker 版 Sql Server新建的数据库插入中文乱码问题解决方案
    SqlServer插入遇到乱码原因:在英文系统中,SqlServer默认排序规则为英文字典顺序解决方案一:容器版SqlServer,在创建容器时,可以加上环境变量-eMSSQL_COLLATION=Chinese_PRC_CI_AS-eTZ=Asia/Shanghai 把排序规则设为中文字典顺序并忽略大小写区分重音,时区设置为上海,不然......
  • CSP-S 2023 T1 题解
    CSP-S2023T1题解很简单,我们只需要暴力枚举五位密码,每次判断拨一个齿轮和两个齿轮能达到的状态数,如果等于\(n\),答案\(+1\)。时间复杂度\(O(10^5\times5n)\)。code#include<iostream>#include<algorithm>#include<cmath>#include<cstring>usingnamespacestd;......
  • P4069 题解
    简要题意给定一棵\(n\)个点的树,树有边权。对每个点维护一个集合\(S_u\),一开始集合均包含整数\(123456789123456789\)。设\({\rmdis}_{a,b}\)为树上两点\(a\),\(b\)的距离。共\(m\)次操作,分为如下两种:stab:设\(f\)为\(s\),\(t\)路径上的点集,对与\(\forall......
  • 上序问题解决补充(1)
    我发现好像只在idea里面整插件是不可以的你还需要下一个wampSERVER然后吧!他这个东西需要在法国官网下载,很他娘的慢,显示下载时间需要一天想不到吧我找到了中文站Wampserver3.3.064位官方版下载-WampServer中文站噔噔噔噔,闪亮登场......
  • cf908(div2)题解(补题)
    纪念这次div2让我上绿名,但还是有点遗憾,差一点就可以过三题超神了比赛链接cf908div2A这题是个骗人题,整个比赛会停下来就是一个人赢够了回合数,那么在谁这停下来就是谁赢了整个比赛,不用管每回合赢得规则。#include<iostream>usingnamespacestd;#include<string>intmain(){......
  • Qt - QWidget::setGeometry()不生效问题解决方案
    开发过程中经常碰到setGeometry()不生效的问题,发现只要在setGeometry()之前调用一下show()或者setVisible(true)就可以了!问题就出在setVisible(true)!!!setVisible()会判断当前控件的WA_WState_Created属性,意思就是看看控件是否已经创建了window,如果为没有创建,就调用create()方......
  • 第三方组件及计算属性传参的问题解决方式
    1.前言唉,好想玩滋嘣。2.计算属性直接传参接收不到表格数据某一列需要用的计算属性时,模板中使用计算属性fullName就会直接调用fullName函数,而在模板中fullName(item)相当于fullName()(item),此处为函数柯里化。<el-table-columnlabel="名称"align="center"min-width=......
  • Balance Addicts 题解
    BalanceAddicts题目大意给定序列\(a\),求有多少种合法的划分方案。定义一种划分方案是合法的当且仅当划分出的各段序列的和构成回文序列。思路分析一种不太一样的做法。我们先对\(a\)做一遍前缀和,得到\(s\)。观察各段序列的和形式:\[s_{p_1},s_{p_2}-s_{p_1},s_{p_3}......