题解1545b cf
ARC166A的题解
略带一点思维吧。 个人认为比 B 难想。 先来考虑弱化版的题面: Case 1 如果 \(X\) 串和 \(Y\) 串都没有字母 C,如何判断是否有解? 观察操作,我们能发现这个操作的本质实际上是让一个位于前面的字母 A 挪到其后面的任意的位置,并且前后两个 A 的相对位置不会发生改变。 所以,如果 ......
[题解]CF1881G Anya and the Mysterious String
思路 发现如果一个字符串中有长度大于等于 \(2\) 回文子串,必定有长度为 \(2\) 的回文子串或长度为 \(3\) 的回文子串,并且形如:aa 和 aba。 所以考虑用线段树这两种情况。维护一段区间的最左、次左、最右、次右的元素,同时用两个标记变量 \(f_1,f_2\) 分别表示这个区间中是 ......
CF1542E2 Abnormal Permutation Pairs (hard version) 题解
Abnormal Permutation Pairs (hard version) 两个限制:字典序小、逆序对大,一个显然的想法就是确保一对关系,统计另一对关系。 确保哪一对呢?我们想了想,决定确保字典序小,因为字典序是可以贪心的。 具体而言,我们考虑两个排列自第 \(i\) 位开始出现了不同。这样 ......
[ABC207F] Tree Patrolling 题解
[ABC207F] Tree Patrolling 弱智 DP 题,设 \(f(i,j,0/1/2)\) 表示在点 \(i\),子树中有 \(j\) 个点被覆盖,且 \(i\) 点自身状态是未被覆盖/被自身覆盖/被某个儿子覆盖,然后树上背包更新就行了。 代码: #include<bits/stdc+ ......
AT_tdpc_tree 木 题解
木 弱智 DP 题,直接设 \(f_i\) 表示 \(i\) 子树内染色的方案数,然后每次合并一个点与它的儿子即可(具体而言,因为儿子间独立,所以方案数就是二项式系数)。 需要注意的是因为第一条边可以在任意位置,所以要以每个点为根各 DP 一次。但是这样每条边会被算两次,所以乘以 2 的逆元即可。 ......
洛谷 P4749 [CERC2017] Kitchen Knobs 题解
Kitchen Knobs 首先,一个 trivial 的想法是,因为每个旋钮如果上面的数字并非全部相同则其必有唯一最优位置,故直接扔掉那些全部相同的旋钮,对于剩余的求出其最优位置。明显此位置是一 \(0\sim6\) 的数。 因为是区间同时旋转,所以转成数之后就是区间加同一个数。 一个经典套路是差 ......
[AGC020F] Arcs on a Circle 题解
Arcs on a Circle 首先,一个非常自然的想法是尝试断环成链。怎么断呢?我们发现,选择最长线段的起点处截断是个非常好的选择,因为不可能有一个线段完全覆盖它。这之后,一个紧接着的想法就是 DP。 假如把描述中的全部“实点”改成“整点”的话,那么这题是比较 trivial 的,可以通过随便状 ......
[ARC072E] Alice in linear land 题解
[ARC072E] Alice in linear land 首先,一个 trivial 的想法是记 \(f_i\) 表示第 \(i\) 步前离终点的距离,于是 \(f_i=\min\Big(f_{j-1},|f_{j-1}-d_i|\Big)\)。 然后,我们设 \(f_i'\) 表示在修改第 \ ......
CF568E Longest Increasing Subsequence 题解
Longest Increasing Subsequence LIS 问题有两种主流 \(O(n\log n)\) 解法,最常见的树状数组法,以及不那么常见的二分法。然后考虑本题,发现一个神奇的思路就是求出 LIS 后倒序复原出数组。 进一步思考后发现,因为本题是 LIS(Longest Incre ......
[AGC046D] Secret Passage 题解
Secret Passage 稍微观察一下就能发现,任一时刻,我们剩下的东西必然是一段定死了的后缀,加上一些可以任意塞位置的 0 与 1。考虑任意一个由上述时刻生成的串,就会发现它与该后缀的最长公共子序列长度即为后缀长度,且还剩余一些 0 与 1。 于是考虑模拟最长公共子序列的过程。设 \(g_{i ......
CF1257E The Contest
用桶存,做一遍前缀和,令 \(b_{x,y}\) 表示序列 \(x\) 包含 \(1\sim y\) 的数字个数。考虑枚举第一个序列保留的前缀 \(1\sim i\),对于第三个序列,如果其保留了后缀 \(j\sim n(i<j)\),考虑哪些数需要被移掉,那么答案就是: \[b_{1,n}-b_{ ......
Atcoder Beginner Contest 324 G Generate Arrays 题解-Treap
为了更好的阅读体验,请点击这里 题目链接 套上平衡树板子就能做的很快的题,然后因为是指针存树,因此交换只需要把序列大小较小的挨个拿出来插到相应的地方即可。复杂度 \(O(N \log^2 N)\)。 但是一定要记住 不可以直接使用 std::swap 交换包含带有指针的类的实例(如代码中的 Trea ......
CF914B题解
一道简单的博弈论。 思路 我们可以先记录每张牌的个数,如果这个牌的个数为奇数,则 Conan 胜利,如果全部为偶数,Agase 胜利。 证明 如果说所有牌为偶数,那么无论 Conan 取哪张牌,Agasa 都可以和他取一样的,最终让 Conan 失败。 如果不满足,那么 Agasa 会无法操作。 A ......
P6346 题解
题目大意 如果 \(\texttt{Kevin}\) 想和第 \(i\) 个人交朋友,要么需要认识 \(a_i\) 个人,要么付出 \(b_i\) 的代价,他让你使 \(\texttt{Kevin}\) 与所有的人交朋友。 解题思路 如果想水到 \(15\) 分,也就是所有 \(b_i\) 都等于 ......
P2198 题解
解题思路 激光塔一定在最后。\(f_{i,j}\) 表示前 \(i\) 个位置放 \(j\)(\(j\le i\))个放射塔,那么 \(i-j\) 个干扰塔的伤害。 若第 \(i\) 个位置放放射塔:\(f_{i,j}=f_{i-1,j-1}+(j-1)\times g\times[t+b\time ......
P7974 题解
解题思路 首先可以确保每一次列的方向一定不会与 \(s\) 到 \(t\) 的方向相反。 不妨设 \(l=\min\{s,t\}\),\(r=\max\{s,t\}\)。 对于每次移动,所花体力值如下: 显然,从 \(l\) 到 \(r\),一定要翻过 \([l,r]\) 间最高的一个,区间最大我们 ......
P4814 题解
解题思路 对于每条边 \((u,v)\),权值为 \(w\),假设存在一条经过这一条边的路径,其最短距离为 \(a\) 到 \(u\) 的最短路加上 \(v\) 到 \(b\) 的最短距离加上 \(w\),若这个值都大于 \(d\),则不可能关闭这条边。 由于边权非负,所以可采用 dijkstra ......
P1124 题解
题目大意 一个长度为 \(n\) 的字符串 \(S\),进行以下操作。 假设 \(s\) 为 acbdef,每一次将首字母移至末尾,得到 \(6\) 个字符串: acbdef cbdefa bdefac defacb efacbd facbde 将每个字符串的首字母排序: acbdef bdefac ......
C++常见入门题题解
前言 因为本人目前比较菜,所以给出的题解都是按照自己的学习进度来的,所以难度是一个循序渐进的过程,由于本人水平有限,望读者能够指出谬误,共同进步。 回文数输出 #include <bits/stdc++.h>//万能头 using namespace std; int main(void) { ve ......
题解 CF1651F【Tower Defense】
一个塔防游戏。
一共有 $n$ 个塔按 $1 \sim n$ 的顺序排成一列,每座塔都有魔力容量 $c_i$ 和魔力恢复速率 $r_i$。对于一座塔 $i$,每过一秒它的魔力 $m_i$ 会变为 $\min(m_i+r_i, c_i)$。每座塔初始时满魔力。
一共有 $q$ 个怪物,每个怪物有两... ......
【题解 CF840C & P4448】 On the Bench & 球球的排列
On the Bench 题面翻译 给定一个序列 \(a(a_i\le 10^9)\),长度为 \(n(n\le 300)\)。 试求有多少 \(1\) 到 \(n\) 的排列 \(p_i\),满足对于任意的 \(2\le i\le n\) 有 \(a_{p_{i-1}}\times a_{p_i} ......
CF350E Wrong Floyd
什么一眼构造题 首先要卡Floyd的关键就是存在某两个点\(x,y\),满足这两个点之间的所有最短路经过的点中(除\(x,y\)本身)至少有一个非关键点 因此很容易想到如下构造法,先随便找一个关键点\(K\),然后把所有非关键点和\(K\)连边(当然如果所有点都是关键点就显然无解) 接下来先随便连边 ......
P9506 题解
blog。First solution /kx。 容易想到断环成链。打开标签发现是 DP,于是就可以 DP 了。 code,时间复杂度 \(O(\text{能过})\)。 ......
CF638D Three-dimensional Turtle Super Computer
什么大力爆搜题 不妨考虑枚举要拿掉的位置,考虑怎么检验它是某两个点之间必经之点 简单手玩一下会发现如果存在这么一条路径,那么我们一定可以把该路径的端点定为与要拿掉的点距离为\(1\)的点上(即与要拿掉的点上下左右前后\(6\)连通) 因此我们把这些点找出来后爆枚点对,判断路径是否唯一就直接爆搜即可 ......
CF73D FreeDiv
首先先把原图中的连通信息求一下,不妨设其中有\(tot\)个连通块,每个连通块的大小为\(sz_i\) 考虑第二步操作时我们需要连\(tot-1\)条边使得图连通,而每个连通块中只有\(\min(sz_i,k)\)个点可以参与连边 因此如果\(\sum_{i=1}^{tot} \min(sz_i,k ......
CF543B Destroying Roads
好经典的题,因为暑假前集训做过类似的思想的题所以知道怎么处理 这题由于要求最多的删去的边数,则等价于求最少保留几条边,很显然留下的边一定是最短路上的 但问题是如果两条路不相交的话很简单,可事实是两条路径可以重叠一些部分,这些边用了两次可能可以使答案变优 关于这种图上两条路径的题有一个经典结论,即两条 ......
NOIP2018PJ T3 摆渡车(2023.10第二版题解)
题目链接 题意: 时间轴上分布着$n$位乘客($1\le n\le 500$),$i$号乘客的位置为$t_i$(0\le t_i\le 4\times 10^6),用互相距离不小于$m$的车次将时间轴分为若干部分,并管辖以自己为右端点的这个区间(除了第一趟车包括$0$,其他车次左开右闭),求最小费用 ......
CF513G3 Inversions problem
CF513G3 Inversions problem 更好的阅读体验 推式子题。 task 1 直接爆搜,统计每种结果的答案,最后加在一起除以总方案数。 task 2 数据范围变大,显然不能记录整个数组的状态,考虑拆位算贡献。设 \(f_{i,j,k}\) 表示交换了 \(k\) 步,\((i,j) ......