Asusetic
0%

杂题记录

发表于 分类于 Valine：
本文字数： 5.8k 阅读时长 ≈ 5 分钟

Every page of tragedy is thrown away Burned out in the flame

随便做

Edu111 D. Excellent Arrays

如果在 ii 位置上放了一个 i+ai+a 另一个位置是 j−aj-a 和就能满足条件

显然最大值是一半选 +a+a 一半选 −a-a 是个组合数

然后讨论下边界，有些地方不能任选

Submission

Edu112 E. Boring Segments

极差的话考虑排序之后双指针，维护全覆盖用线段树即可

Submission

Edu112 D. Say No to Palindromes

只有三个字符的无回文子串只能是 abcabc 这样的排列，一共 3!3! 种，每种都试一下做个前缀和即可

Submission

Edu112 F. Good Graph

考虑如果现在是一个好图，加入一个新边的影响，如果他连接了两个连通块肯定可以加

否则需要考虑生成树，首先需要保证异或和为 11 ，然后需要保证树上 u→vu \to v 的路径都不是其他环

因为如果有环相交构成的大环就是 00 了，这个可以给边打标记，因为每个边仅被访问一次，所以直接树状数组大力加

Submission

CF721 Div2 D. MEX Tree

挺好想的，不太好写，mex⁡=k\operatorname{mex}=k 的肯定是选择了 [0,k−1][0,k-1] 的一条链加上不包含 kk 的某些点

找链可以直接跳上去拼接，但是去掉包含 kk 的点需要巨大多分类讨论，为了避免讨论可以差分一下，只用找包含 [0,k][0,k] 的路径

Submission

CF708 Div2 E2. Square-free division

暴力 dpi,jdp_{i,j} 表示前 ii 个修改了 jj 次的最小段，每次枚举前面的位置是 O(n2k)O(n^2k) 的

可以发现，能取的话肯定是取最靠前的最优，所以预处理 (r,i)(r,i) 表示点 rr 修改 ii 次最左边的位置即可 O(nk2)O(nk^2)

Submission

Edu109 E. Assimilation IV

大降智少推式子多动脑子

考虑每个点的概率，共 n!n! 种可能，被选到的是排列中至少有一个 ii 使得 i+ai≥ni+a_i \ge n 发现没啥好办法统计…

补集转化，一个都没有就需要第 nn 位至少是 22 第 n−1n-1 位至少是 33

直接乘起来统计即可

Submission

Edu109 C. Robot Collisions

只能在整数值相交意味着可以奇偶分开处理，每次相撞必然是里的最近的 LR 相撞

形如 LLRRLRLRLLLRL 的序列可以转换成括号序列，每次匹配的括号相撞，剩余的括号到了边界后反转后匹配

Submission

Edu113 D. Inconvenient Pairs

距离不等于曼哈顿距离的必然不在十字交叉口

考虑在横线方向上的答案 两个点不等于曼哈顿距离的一定处于两个不同的横线上，并且中间没有竖线，开个 map 统计即可

Submission

ABC224 F. Problem where +s Separate Digits

考虑每一位 xx 的贡献，如果他在从后往前数第 kk 个，它可以成为第 [1,k−1][1,k-1] 位数，贡献分别为 x×10ix\times10^i

他成为第 ii 位的方案数是自己后面 ii 位都没有 ++ 的方案，总方案为 (12)n−1(\frac{1}{2})^{n-1} 这种方案占比为 (12)i(\frac{1}{2})^{i} 需要注意因为最后不能放加号，所以他贡献为 x×10k−1x\times 10^{k-1} 的方案应该是是 (12)k−1(\frac{1}{2})^{k-1}

Submission

AGC035D Add and Remove

发现 a1a_1 和 ana_n 没意义，一定只贡献一次

剩下的考虑计算每个元素对答案的贡献次数

反着进行这个过程，在 ai,ai+1a_i,a_{i+1} 种插入一个数，若 aia_i 被算了 kik_i 次这个数会被算 ki+ki+1k_i+k_{i+1} 次

反着推，设 dpl,r,m,ndp_{l,r,m,n} 表示第 ll 个算了 mm 次 第 rr 个算了 nn 次的最小贡献

有转移 dpl,r,m,n=min⁡(dpl,k−1,m,m+n+dpk+1,r,m+n,n+(m+n)ai)dp_{l,r,m,n} = \min(dp_{l,k-1,m,m+n}+dp_{k+1,r,m+n,n} +(m+n)a_i)

状态上界是 2n2^n

DFS 做就行

SPOJ PERIODNI

分成多个矩形后每个矩形块可以独立DP然后合并

分成矩形这个过程就是在笛卡尔树上做DP，设 dpi,jdp_{i,j} 是第 ii 个子树里放了 jj 个数的方案数，然后合并子树的方案后计算当前矩形的方案即可

CF501 Div3 F. Bracket Substring

设 dpi,j,kdp_{i,j,k} 表示当前是第 ii 位，栈高 jj ，匹配到了子串的第 kk 位，用 KMP 预处理一下匹配即可 O(n3)O(n^3)

CF Edu 114

VP了一场，卡在E的分类讨论了

A~C

略

D. The Strongest Build

爆搜题，不知道为啥看错题以为最后的构造要升序卡了一会儿

发现 nn 才 1010 最有答案肯定是全选最大的，如果不能选最大的，就找一个位置选小一点的，然后堆优化BFS，第一个取出来的没被 ban 的就是答案

判断是不是被 ban 直接把 vector 塞进 map 里就行

因为没记录是否访问 MLE * 2 ，因为未知错误 WA * 2

Submission

E. Coloring

先考虑空的状态

发现如果有两个相邻的格子同色，那就可以直接递推出所有的状态了

即 2m−22^m-2 减去了没有相邻同色的方案

而没有相邻同色的话每一行都可以决策是否与上一行相同或相反，即 2×2n−12\times 2^{n-1}

如果加上限制，对于没有相邻同色的情况，意味着这一行被确定了，方案数要除 22 ，即 2空行2^{空行}

同理，对于有相邻同色的就是 2空列2^{空列}

还需要考虑有可能不能填成要求的状态，需要分类讨论

Submission

F. Occurrences

一个串出现的次数肯定不能比它的一个元素多，所以只要他的元素出现过，他就得出现过

如果把每个数按照序列顺序连边，每选定一个点就得把整个链放进去，如果这个链有分支或成环肯定是没办法选的

所以并查集维护能放进去的链，dp 方案即可

把连通块大小一样的一起做，最多只有 k\sqrt{k} 个，复杂度 O(mk)O(m\sqrt{k})

CF Edu106 D. The Number of Pairs

怎么又开始数学题了

设 g=gcd⁡(a,b)g = \gcd(a,b) a′=ag,b′=bga'=\dfrac{a}{g},b'=\dfrac{b}{g}

则 $cga’b’-dg=x \Rightarrow ca’b’-d=\dfrac{x}{g} $

即 g∣xg|x 设 k=xgk = \dfrac{x}{g}

则 a′b′=k+dca'b' = \dfrac{k+d}{c}

所以 c∣k+dc|k+d , 要求 gcd⁡(a′,b′)=1\gcd(a',b')=1 那么 a′,b′a',b' 就是 k+dc\dfrac{k+d}{c} 的质因子集合划分，即 2c2^c 种方案

枚举 gg 即可

Submission

CF Edu 105 D. Dogeforces

因为权值互异，所以按 LCA 的权值排序合并恰好形成了树形结构

每次合并当前的两个节点到一颗子树里，用并查集维护

Submission

CF749 Div1+2 E. Moment of Bloom

图上奇偶性 -> 生成树 ？

首先如果存在被访问奇数次的节点肯定无解，大概挺好理解的，而如果有解直接在生成树上找路径即可

原因是如果叶子结点成为端点次数是偶数，那么他与父节点边权是偶数，如此归纳即可

Submission

CF Harbour.Space Scholarship Contest 2021-2022 H

一个很妙的做法

强制每个 xx 只能使用那些，与 xx 相比只有最低的 dd 位可能不同的元素。

考虑一位一位更新答案，设 f(x,d)f(x,d) 为数字 xx 在 dd 位上的答案，维护 mmax(x,d)\mathrm{mmax}(x,d) 和 mmin(x,d)\mathrm{mmin}(x,d) 为数字 xx 在 dd 位的异或最大/最小值

mmax(x,d)=max⁡(mmax(x,d−1),mmax(x⊕2d,d−1)+2d=1)\mathrm{mmax}(x,d)=\max({\mathrm{mmax}(x,d-1),\mathrm{mmax}(x\oplus2^{d},d-1)+2^{d=1}})

mmin(x,d)=max⁡(mmin(x,d−1),mmin(x⊕2d,d−1)+2d=1)\mathrm{mmin}(x,d)=\max({\mathrm{mmin}(x,d-1),\mathrm{mmin}(x\oplus2^{d},d-1)+2^{d=1}})

对于 f(x,d)f(x,d) 仅需要决策 f(x,d),f(x⊕2d,d),mmin(x,d)−mmax(x,d)+2df(x,d),f(x\oplus2^d,d),\mathrm{mmin}(x,d)-\mathrm{mmax}(x,d)+2^{d} 即可

ARC114C Sequence Scores

考虑加入一个新数字 xx 在长度为 ii 的序列的贡献

如果 xx 不在其中，需要额外一次操作

如果 xx 插入的位置是一个低点，不需要操作

否则需要一次额外操作

即 F(i,x)F(i,x) 为这时的贡献，有 F(i,x)=mi−1−∑k=1i−1(m−x)i−1−k×mk−1F(i,x)=m^{i-1}-\sum\limits_{k=1}^{i-1}(m-x)^{i-1-k}\times m^{k-1}

即枚举 xx 出现的位置，减去情况 22

O(nm)O(nm) 求和即可

2021江西ICPC省赛 C. 水晶洞窟

曼哈顿距离 x,yx,y 独立

要求的就是 n(n−1)(n+1)6+max⁡(∑i=1n∑j=i+1n∣ai−aj∣)(at∈[lt,ryt])\dfrac{n(n-1)(n+1)}{6}+\max(\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}|a_i-a_j|) (a_t \in [l_t,r_yt])

显然后边的最大值在 aia_i 都是端点处取到，设 f(a1,a1,…,an)=max⁡(∑i=1n∑j=i+1n∣ai−aj∣)(at∈[lt,ryt]f(a_1,a_1,\dots,a_n)=\max(\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}|a_i-a_j|) (a_t \in [l_t,r_yt] 则对 aia_i 差分得到

Δfi=∑j=1n[aj<ai]−[aj>ai]\Delta f_i=\sum\limits_{j=1}^{n}[a_j<a_i]-[a_j>a_i] 容易发现他单调不降，所以肯定是在端点取到最大值

继续贪心的想，aia_i 的分布应该尽可能"均匀"

证明咕

设 dpi,jdp_{i,j} 表示到了第 ii 层选了 jj 个放在左边的最大值

转移可以递推，假设一开始所有层的点都处在 l1,r1l_1,r_1 的位置上，左右各有 n2\dfrac{n}{2} 个，每次决策一个点把其他点放下去

Submission

CF750 Div2 E. Pchelyonok and Segments

显然最长区间不能超过 n\sqrt{n}

从前到后不好考虑，需要从后向前考虑，记 dpi,jdp_{i,j} 为第 ii 位后缀，存在一个区间 [l,r][l,r] 和为 r−l+1=jr-l+1=j 的最大区间和

先转移 dpi,j←dpi+1,jdp_{i,j} \gets dp_{i+1,j} 若 [i,i+j−1][i,i+j-1] 的区间和 <dpi+j,j−1< dp_{i+j,j-1} 则可以选择这个区间

复杂度 O(nn)O(n\sqrt{n})

Submission

CF Edu 116 D. Red-Blue Matrix

考虑枚举 k∈[1,m−1]k \in [1,m-1] ，转换下条件就是前 kk 列的蓝色区域最大值小于红色区域最小值

为了满足这个条件直接按照第一列的顺序排列，即选择染色至少是染前 ii 行蓝色，剩下的条件可以 O(1)O(1) 二维最大值检查

O(nm)O(nm)