1754c cf c1
CF1882 div.2 做题记录
A 题面 扫一遍,令 \(b_i\rightarrow b_{i-1}+1\),若 \(b_i=a_i\),\(b_i\rightarrow b_i+1\)。 点击查看代码 #include<bits/stdc++.h> #define ull unsigned long long #define ......
CF1882C Card Game
某种程度上的抽卡游戏? 有这样一个结论:一个后缀中\([i+1,n]\) 中所有的正数都可以被取到,所以维护一个正数后缀和 \(s_i\),枚举每个位置 \(i\),如果 \(i\) 为奇数,答案对 \(a_i+s_{i+1}\) 取 \(\max\),否则对 \(s_{i+1}\) 取 \(\ma ......
CF1879D Sum of XOR Functions
异或和按位处理的典型例题。 要求所有子区间异或和乘区间长度的总和,朴素的方法是 \(O(n^2)\) 地枚举区间,显然无法通过。 因为涉及异或和,而异或运算不进位,故自然地想到把 \(a_i\) 写成二进制形式,单独研究每一位的贡献,最后再合并。这是处理此类问题的一般思路。 1. 二进制拆分 比方说 ......
Educational Codeforces Round 155 D (CF1879_D)
题目大意 给一个长度为 \(n\) 的数组,求 \(\Sigma_{i=1}^{n} \Sigma_{j=i}^{n} 区间异或和 \times (j-i+1)\) 其中 \(n\leq 3e5,~a[i]\leq 1e9\) 分析 首先注意到由 \(l\) 到 \(r\) 的区间异或和可以转化为 ......
CF1106D Lunar New Year and a Wander 题解
CF1106D 题解 暑期学校军训第一天模拟赛的题,相对而言比较简单 题意: 题意其实很简单,就是有一个无向图,需要你从\(1\)号节点出发,然后一次遍历所有的点,输出其中字典序最小的遍历 思路 说说思路吧,这题既然要遍历图上所有点,那首先就会想到 \(\texttt{BFS}\) 或 \(\tex ......
CF1863 题解
CF1863 题解 A 条件很简单:如果总共的 '+' 号加上开始上线人数不到 \(n\) 人,就不可能。实时记录人数,如果某一时刻大于等于 \(n\) 人在线上,就一定是。剩余情况则可能。 #include<bits/stdc++.h> using namespace std; int main( ......
CF1869D1 Candy Party (Easy Version)
Link 首先我们想这样的问题,为什么强调是\(2^x\) 呢?我们记平均值是 \(avg\),然后可以注意到,应该有一下式子被满足 \(a_i-2^{x_i}+2^{y_i}=avg\),移项,可以得到\(a_i-avg=2^{y_i}-2^{x_i}\),而这个式子中\(x_i\)和\(y_i\ ......
cf1879 edu 做题记录
A 题面 判断有没有两维均大于等于第一个人的人即可。有就无解,否则答案为 \(s_1\)。 点击查看代码 #include<bits/stdc++.h> #define ull unsigned long long #define ll long long #define pii pair<int, ......
CF1868C Travel Plan
注意到树的深度很小,所以路径长度也很小,可以先 DP 出每种路径长度的数量。 令 \(f_{i,j,0/1}\) 表示深度为 \(i\) 的满二叉树,长度为 \(j\) 的路径,一个端点不一定/一定在根结点的数量。跨越左右子树的转移就暴力枚举两侧深度。当然这里可以直接算。 但原树只是完全二叉树。观察 ......
开学补题(cf版)(第四周)
Problem - G - Codeforces 题意:给你一个字符串,里面只包含A或者B两个字符 然后给你两种操作,一种是把AB变成BC,另外一种是把BA变成CB 然后问你给定的字符串最多可以变多少次 题解:我们可以发现无论你怎么搞,都要消耗一个a,所以看看B的附近有多少个A就有几次 但是假如B不 ......
CF_EduRound155小丑寄
一句话总结:A题理解错了,数据又水,所以寄了。 过程: 22:35 开题。 22:40 怎么还没加载出来??急急急 22:42 哦,严格大于,但是主宾对调了,乐乐乐乐乐乐乐,cout << ans;\(\rightarrow\)cout << ans - 1; 22:45 一 发 过 。 。 。 2 ......
[CF1810G] The Maximum Prefix
题目描述 You're going to generate an array $ a $ with a length of at most $ n $ , where each $ a_{i} $ equals either $ 1 $ or $ -1 $ . You generate this a ......
[CF704D] Captain America
题目描述 Steve Rogers is fascinated with new vibranium shields S.H.I.E.L.D gave him. They're all uncolored. There are $ n $ shields in total, the $ i $ -t ......
CF249E Endless Matrix 题解
@目录Description前置芝士SolutionCode Description 构造一类矩形: 先构造矩形 \(M_1=\begin{bmatrix}1\end{bmatrix}\)。 对于 \(i\geq1\),\(T_{i+1}\) 从 \(T_i\) 构造而来,方法为在最右侧和最下侧插入 ......
CF1801D The way home
原题 翻译 非常好的一个题,有两种做法 方法1:flody+dp 首先我们确定一个最优行走方案:从 \(1\) 号节点赚到足够钱后通过最短路到达 \(x_1\) ,在 \(x_1\) 赚够足够钱后到达 \(x_2\) ,在 \(x_2\) 赚够足够钱后到达 \(x_3\) ,如此往复后到达终点 现在 ......
CF1106D Lunar New Year and a Wander 题解
CF1106D 题解 暑期学校军训第一天模拟赛的题,相对而言比较简单 题意: 题意其实很简单,就是有一个无向图,需要你从\(1\)号节点出发,然后一次遍历所有的点,输出其中字典序最小的遍历 思路 说说思路吧,这题既然要遍历图上所有点,那首先就会想到 \(\texttt{BFS}\) 或 \(\tex ......
CF1710D Recover the Tree
题目链接 一个比较显然的思路就是:我们按照右端点从小到大的顺序(右端点相同按左端点从大到小)去考虑每个好的区间。 由于是连通性问题,不难想到用并查集去实时维护连通性。 根据定义,一个好的区间必定对应了一个连通块;我们考虑的是好的区间,所以当前并查集中的每个连通块必定都是一个区间。而在加入某个点前,这 ......
CF1862G The Great Equalizer
题目链接 先不考虑修改操作。 直接模拟题目意思,可以发现最后留下的一定是最小的数字(因为相同的数每次会保留第一个)。我当时是顺着这个思路做的题目,现在想想反过来想好像会让问题变得更简单,即认为每次保留最后一个相同的数字。 那么现在每次留下的就是最后一个数字,显然每次操作会让这个数字加一,只需要考虑一 ......
CF1857G Counting Graphs
题目链接 考虑每条非树边的取值,显然不能小于等于该边与树边形成的环中的最大值(当然这条非树边也可以不存在),所以每条非树边的取值范围就是 \(S - max(w) + 1\) (\(+1\)的原因是该边可能不存在)。 暴力枚举肯定会超时,考虑优化。 发现 \(kruskal\) 算法获得最小生成树的 ......
CF662C
题面传送门 description 给定一个 \(n\times m(n\le 20,m\leq 10^5 )\) 的 01 矩阵,你可以把若干行的 01 反转,再把若干列的 01 反转。求若干操作后可能的最少的 1 的个数。 solution 显然操作相当于每行每列要么取反一次,要么不取反。 行数 ......
CF877F 题解
CF877F 题解 更好的阅读体验 提供一个扫描线 + 根号分治做法。 首先,可以把题目的条件转化成求 $sum_r-sum_{l-1}=k$ 的区间数。 考虑扫描线,当区间的右端点从 $r-1$ 移动到 $r$ 时,新增的区间的左端点就是所有满足 $sum_{l-1}=sum_r-k,l\le r ......
CF986F 解题报告
显然要关于 \(k\) 离线。 对于固定的 \(k\),关于 \(k\) 的质因子的个数讨论: 如果 \(k\) 是形如 \(p^\alpha\) 的素数幂 只需判断 \(p|n\) 即可。 否则 我们可以跑类似同余最短路。 当 \(\min p_i\) 很大的时候,过不去。 但是,极限数据只能在形 ......
题解 CF1257G【Divisor Set】
problem 我们说一个集合 \(D\) 是一个好的集合,当不存在集合中的两个不同元素 \(a,b\) 使得 \(a\) 是 \(b\) 的约数。 给定一个超大整数的素数表示形式 \(N = \prod_{i=1}^n{p_i}\),要求从它的所有因子中选择尽可能多的元素组成一个好的集合。 问这个 ......
CF1267I
有一种很玄妙的做法,非常简洁。 我们考虑每两个为一组,令每对小的构成的集合为 \(S\), 另一个为 \(T\)。 令 \(S\) 里最大的下标为 \(x\),和其一对的另一数的下标为 \(y\)。 容易发现 \(y\) 一定在答案里。 proof:我们先钦定 \(T\) 为答案,再进行替换,发现一 ......
题解 CF1873H Mad City
题意描述 马塞尔和瓦勒里乌(Valeriu)所在的疯狂城市由 \(n\) 栋建筑和 \(n\) 条双向道路组成。 马塞尔和瓦勒里乌(Valeriu)分别从 \(a\) 号和 \(b\) 号建筑开始。马塞尔想赶上瓦勒里乌(换句话说,与他在同一栋楼里或在同一条路上相遇)。 在每次移动过程中,他们都会选择 ......
CF1842F Tenzing and Tree 题解
Tenzing and Tree 感觉很典型的题,就是树的重心+绝对值等式 解法: 以每个点 \(i\) 为根分别 \(bfs\) ,得到一个距离数组 \(dis\) ,取前 \(k\) 个值的权值为和,更新 \(w[k]\) 的值, \(n\) 个点分别为根,更新 \(n\) 遍之后,得到 \(w ......
[CF1229E]Marek and Matching
This is a harder version of the problem. In this version, \(n \le 7\).Marek is working hard on creating strong test cases to his new algorithmic probl ......
CF1466E Apollo versus Pan
原题 翻译 xjk:降智题。orz \[\begin{align} \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}(x_i \ \operatorname{and}\ x_j)\times(x_j\ \operatorname{or}\ x_k) &= \sum ......
CF842A Kirill And The Game
如果考虑 \([x,y]\) 中什么位置能乘到 \([l,r]\) 就比较麻烦,简单的做法是考虑 \(l\) 和 \(r\) 对应到 \([x,y]\) 中的位置。左边界至少是 \(\frac{l-1}{k}+1\),右边界至多是 \(\frac{r}{k}\),判断一下与 \([x,y]\) 是否 ......