题解914b cf
CF1707 题解
CF1707 题解 A 考场上 1h 才出思路...弱智了。 我们将参加大于当前智商的行为叫做 “摆烂”。我们考虑如果现在摆一次,将来某一次不摆,那么现在不摆,将来那次开摆,中间过程的智商会加1。更优。所以一定一摆就摆到底。而且一定会摆到最后一个。 所以我们二分从什么时候开摆,看是否能摆到最后,中间 ......
题解:洛谷P3745 期末考试(整数三分)
题解:洛谷P3745 期末考试(整数三分) 题目传送门 题目大意:给出 \(n\) 个同学期望出成绩的时间限制 \(a_i\) 和 \(m\) 个学科公布成绩的初始时间 \(t_i\) ,1个同学每多等一天就产生 A 的不愉快度。问通过一番操作后最小的不愉快度之和是多少? 操作有两种: 1.让学科 ......
[题解][ARC167C]一道申必的数数题
这道题目千岩万转,需要用到多次转化,其中有一些转化较为常见,有一些则需要思考。 首先观察原问题:给定数列 \(a\),对于所有 \(1\sim n\) 的排列 \(p\),构建一张只有 \(j-i\le k\) 的 \((i,j)\) 之间有权值为 \(\max\{a_{p_i}, a_{p_j}\ ......
题解 ABC326E【Revenge of "The Salary of AtCoder Inc."】
根据期望的线性性,总工资的期望等于在每一个 \(i\) 处获得的工资的期望之和,而在 \(i\) 处获得的工资的期望 \(E(i)=A_i\times p(i)\),其中 \(p(i)\) 表示掷骰子掷到 \(i\) 且有效的概率。 初始 \(p(0)=1\),则只有从 \(0\sim i-1\) ......
P5404 [CTS2019] 重复 题解
题目链接 观察题目,我们发现直接计算是困难的,先构造单个合法的 \(T\) 分析其性质。 为了构造出 \(T\),先考虑构造时 \(T\) 时什么时候会出现不合法的情况,此时 \(T\) 会有一段和 \(S\) 相同的前缀,且这段前缀后面跟着的字符比 \(S\) 所跟的小。 为了避免这种情况出现,我 ......
CSPRO 历届题目与题解
官方题目链接:http://118.190.20.162/ \(\Huge目录\) 201609 201612 201709 202104 202109 202112 202203 202206 202209 202303 202305 202309 \(\Huge\text{CSP201609}\ ......
CF1879C Make it Alternating
传送门 设\(f_{i,0}\)表示将\([1,i]\)位变成以\(0\)结尾的字符串的最小步数。 \(f_{i,1}\)表示将\([1,i]\)位变成以\(1\)结尾的字符串的最小步数。 \(f_{i,2}\)表示将\([1,i]\)位变成空字符串的最小步数。 转移的时候分类讨论一下第\(i\)位 ......
CF1884B Haunted House 题解
CF1884B Haunted House 题解 借鉴了当前 另一篇题解,加了更多的说明。 简化题意 给定一个长度为 \(n\) 的二进制串 \(S\),求 \(f(1),f(2),\cdots,f(n)\)。 其中,\(f(i)\) 定义为,每次交换相邻的两个二进制位,将 \(S\) 的后 \(i ......
AT_abc325_g offence 题解
AT_abc325_g offence 题解 一道不难但是需要想一想的区间 DP。 有一个比较复杂的例子:ooofofxxx,简单的分析可知,一个 of 后面删除多少,与其前、后都有关,于是考虑区间 DP。 想到这里,其实问题已经解决一半了。 状态设计 设 \(f(l,r)\) 为闭区间 \([l, ......
AT_abc326_d ABC Puzzle 题解
AT_abc326_d ABC Puzzle 题解 看题 事实上,即使在 \(N=5\) 的情况下,也只有 \(66240\) 个网格满足「每行/每列恰好包含一个 A、B 和 C」。——官方题解 其实看到这道题,就感觉是搜索,这很显然。 但是我们会发现,最最最 native 的搜索,是 \(4^{5 ......
AT_abc326_f Robot Rotation 题解
AT_abc326_f Robot Rotation 题解 经典问题,以前遇到过一个类似的问题:[ABC082D] FT Robot。 建议对比着看一看这两道题,是两种不同的思路。 (那一道题不用输出方案,因此可以用 bitset 优化;而此题需要输出方案,因此需要双向搜索。 思路 注意到每次只能「 ......
AT_abc325_f Sensor Optimization Dilemma 题解
AT_abc325_f Sensor Optimization Dilemma 题解 Date 20231025:修复手滑公式 \(\min\)、\(\max\) 写反了。 动态规划。类似背包问题。 朴素算法 记 \((x,y)\) 表示使用 \(x\) 个 (1) 传感器、\(y\) 个 (2) ......
AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解
AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解 一道简单的概率论+动态规划题目(然而我赛时没看这道题 题意 有一个长度为 \(n\) 的序列 \(A\)、一个 \(n\) 面骰子,掷若干次骰子,如果这一次掷骰子的点数小于等于上一次的点数, ......
CF1889B
题面 给一个 \(n\) 个点的图,每个点 \(i\) 有点权 \(a_i\),初始图上没有边,你可以进行如下操作若干次: 若 \(S_i+S_j\ge i\times j\times c\),添加一条边 \((i, j)\)。其中 \(S_i\) 表示 \(i\) 所在连通块的点权和,\(c\) ......
CF1891F A Growing Tree
给定一棵以 \(1\) 为根的有根树,支持以下两种操作共 \(q\) 次: 加入一个点; 子树内点权加。 \(q \le 5 \times 10^5\)。 最傻逼的一集,怎么会有这么简单的 d2f。 不难发现每个点存在的时间区间构成时间轴上的一段后缀,于是我们可以将所有操作离线下来,先把完整的树建出 ......
CF1891F A Growing Tree
CF1891F A Growing Tree 更好的阅读体验 有点诈骗。好多人都写的 LCT,但是这题其实连树剖都不需要。提供一个简单的单 \(\log\) 小常数做法。 动态加点是假的,可以离线下来得到最后树的结构,记一下 dfn 序。 一个操作对一个点有可能贡献当且仅当操作在加点之后进行。 所以 ......
CSP-S2023题解
lock 直接模拟题意,过程略。 #include<bits/stdc++.h> using namespace std; int st[15][15]; int dis(int x,int y){ if(x < y)return y - x; return y + 10 - x; } bool m ......
[CF551E] GukiZ and GukiZiana
CF551E 卧槽,lzh最爱的分块!卧槽,lzh最爱的分块!卧槽,lzh最爱的分块!卧槽,lzh最爱的分块! 维护懒标,散块重构。 unordered_map<long long,int> 会 TLE unordered_map<long long,bool> 会 AC #include<cstd ......
[CF566E] Restoring Map
Restoring Map 星空蚁来了秒了。 人与人的智力是有差距的。 刷再多的CF智力不行就是不行。 OI这种需要智力的游戏不适合我。 我还是更适合对智力要求低一点的。 比如和妹子贴贴。 但是也没有妹子。 life is hard. 这类树的构造似乎可以从边缘情况想起,比如 CF1844G 但是这 ......
[CSP-S2020] 儒略日 题解
[CSP-S2020] 儒略日 今儿终于做掉困扰多年的题目了,其实想好细节也不难。 容易发现儒略历和格里高利历的润年判断方式不一样,并且中间有消失的十天,计算起来相当不方便。所以我们可以首先计算出 \(-4713.1.1\) ~ \(1582.10.4\) 会经过多少天,可以通过一天一天暴力跳的方法 ......
[CF566E]Restoring Map
题目描述 Archaeologists found some information about an ancient land of Treeland. We know for sure that the Treeland consisted of $ n $ cities connected b ......
P8256字符串 题解
传送门 考虑\(DP\): 记状态 \(f_{i,j,st,en}\) 表示现在枚举到第 \(i\) 个字符,匹配了 \(j\) 个字符,要在前面删 \(st\) 个字符,在后面删 \(en\) 个字符的方案数 不难发现 \(f_{n+1,m,0,0}=1\) 状态转移有 当 \(s_i='-'\) ......
[eJOI2020 Day1] Fountain 题解
题目链接 原题做法:用单调栈求出每个圆盘中的水溢出后会 直接 流到哪个圆盘,因为每个圆盘中的水向下流有且仅有一个圆盘会 直接 接住它(将水池视作直径和容量都是正无穷的一个圆盘),因此构成了一棵树,根节点即为水池,每个点有点权,即该点代表的圆盘的容量。记 \(dis_{i,j}\) 表示节点 \(i\ ......
[CF403E]Two Rooted Trees
Two Rooted Trees 题面翻译 题目描述 你有两棵有根树,每棵树都有 \(n\) 个结点。不妨将这两棵树上的点都用 \(1\) 到 \(n\) 之间的整数编号。每棵树的根结点都是 \(1\)。第一棵树上的边都是蓝色,第二课树上的边都是红色。我们也称第一棵树是蓝色的,第二棵树是红色的。 对 ......
CF1889D
题意 给定\(n\)个栈,栈的大小分别为\(k_i\),每个栈内元素\(\in[1,n]\),记从第\(i\)个栈开始的答案为\(ans_i\),流程:若栈\(i\)为空,答案为\(i\);否则弹出栈顶元素\(x\),并前往栈\(x\),继续刚才的操作。 \(n\le 10^5,\sum k_i\l ......
CF1842H
传送门 description 见洛谷翻译 solution 考虑分析一下不等式 \(x_i+x_j\leq 1\)。 如果 \(x_i,x_j\leq 0.5\),一定成立; 如果 \(x_i,x_j>0.5\),一定不成立; 如果 \(x_i,x_j\) 中一个 \(>0.5\),一个 \(\l ......
CF1800-1900
CF1490G Old Floppy Drive 首先判断是否可以在第一圈就符合题意,记录前缀和 \(sum\) 和 \(mx\) 数组,其中 \(mx_{i}\) 为 \(sum\) 从起点到 i 的最大值,即 \(mx_{i}=\max(mx_{i-1},sum_{i})\)。 显然如果在第一圈 ......
cf353D. Queue(整体考虑转移)
D. Queue f[i]表示第i个F需要多少时间才能让所有的M都移到她后面,那么我们考虑转移,分为两种情况。 第i个F和第i-1个F挨着,那么显然f[i]=f[i-1]+1 假如中间隔着一些M, 可以分为两种情况,假如i可以在i-1完成之前追上它,那么就是f[i-1]+1,否则就说明 i一直在进行 ......