题解1071 cf
CF1867D Cyclic Operations
前言 赛时没调出来，赛后调了一个上午，最后发现是有个地方没清零。 思路 首先对于位置 \(i\)，我们必须要保证进行的操作中，最后一次出现 \(i\)，\(i\) 的后面一定是 \(a_i\)。 那么我们考虑统计所有位置上的要求，用有向边链接，那么就会出现一个有环有向图（一定有环，因为点数等于边数） ......
CF1867A green_gold_dog, array and permutation
思路 很简单的一道题，洛谷大概都不会开放题解通道？（实际上貌似每场比赛的 A 都没开放？） 显然，对于原数组较小的数，我们尽量让大的数，取全排列的较小的数，这样可以保证差是逐渐变小的，也就让 \(c\) 数组差异变大。 所以直接拿个 struct 存，然后两边排序就好。 AC code #inclu ......
CF1867C Salyg1n and the MEX Game
思路 看着无从下手，实际上又是一道诈骗题。 假设原数列不存在 \(0\)，那么我们可以直接加入 \(0\)，然后游戏结束，假设答案是 \(k\)。那么，如果我们选择加入 \(k\)，来试图让答案变大，那么 Bob 就会移除一个数，最优的话是 \(1\)，这样的话，你无论加入 \(1\) 还是 \(0 ......
CF1867E1 Salyg1n and Array (simple version)
思路 首先考虑，\(n\) 是 \(k\) 的倍数的情况，直接枚举询问所有每一段就好，然后输出每一段的异或和的异或和。 如上图，每次询问都没有重叠部分，颠转互不干扰。 那么，\(n\) 不是 \(k\) 的倍数的情况呢？ 可以看到，与第一种情况的区别就是末尾多了一小截，那么我们需要考虑如何计算这一小 ......
CF1867E2 Salyg1n and Array (hard version)
其实如果你在做 E1 的时候想到正解了，这道题都甚至不需要改 E1 的代码，直接交就好，这大概也是 E2 的分还没 E1 的高的原因。 因为一摸一样的思路，所以这里就不作介绍了，可以看看我的题解。 在这里呢，主要是稍微证明一下询问次数不会超，如下： 可以发现，有余数的情况，只会增加两次询问，而后面的 ......
202309 at&cf题目选讲
题目链接 题解 目录A AtCoder abc318_c Blue SpringB AtCoder abc318_d General Weighted Max MatchingC AtCoder abc318_e SandwichesD AtCoder abc318_f OctopusE AtCod ......
CF1867B XOR Palindromes
思路 题目问的是改 \(i\) 位，能不能让原串变成回文串，其中 \(0\le i \le n\)。 首先，我们可以统计前后对称位置不一样的对数，记为 \(k\)，那么至少也得改 \(k\) 次，假设剩下前后对称位置一样的有 \(m\) 对（如果 \(n\) 为奇数，则最中间的一位不计入 \(m\) ......
CF1718F Burenka, an Array and Queries
显然先考虑把每个 \(a_i\) 只因数分解，令 \(S(x)\) 表示 \(x\) 只因子的集合。 令 \(S_{l,r}=S\left(\prod\limits_{i=l}^ra_i\right)=S(a_l)\cup S(a_{l+1})\cup\cdots \cup S(a_r)\)。假如我 ......
CF1559D1&D2 Mocha and Diana
原题(Eazy Version) 原题(Hard Version) 翻译 首先我们先考虑Eazy Version。容易发现，在\(A,B\)两个森林中一定有一个是一棵树。这个结论说明： 选边顺序没影响 能选就选 因此我们枚举\(n^2\)条边，用并查集判断连通性即可 最终复杂度\(O(n^2 \al ......
【题解】CF1819A Constructive Problem
你考虑这道题中判 No 显然有两种情况： 如果说 mex 是 n 的话，即我们的所有数都是必不可少不能更改的，那么就是 No 如果说原序列中有 mex+1 那么我们就可以发现添加 mex 显然会有很大的问题，我们显然要将所有的 mex+1 的区间替换为 mex，并且保证其他的数的 mex 和原序列的 ......
P3616 富金森林公园 题解
P3616 富金森林公园 题解 题意 给你 \(n\) 个点，有 \(m\) 次操作，每次操作可以改变一个数的值，也可以查询有多少连续的块，满足这个块内的所有数的值都大于查询的值。 分析 还是比较容易想到用数据结构或分块的，毕竟有同时存在修改和查询操作。但是维护什么？怎么维护？ 既然我们无法直接维护 ......
【ABC105D】题解
题解 题意简述 给定 \(n\) 个数，求这 \(n\) 个数中有多少个二元组 \((x,y)\) 满足其中每一个数都是 \(m\) 的倍数。 思路 前缀和，\((x,y)\) 内每一个数 \(\bmod \ m = 0\)，可以用 \((sum_y - sum_{x - 1}) \bmod \ m ......
【题解】AtCoder-ABC319
AtCoder-ABC319A Legendary Players 使用 map 即可。 提交记录：Submission - AtCoder AtCoder-ABC319B Measure 依题意模拟。 提交记录：Submission - AtCoder AtCoder-ABC319C False ......
ABC319 A-E 题解
A 用 map <string, int> 将名字对应的值存下来即可。 赛时代码 B 按照题意暴力模拟，注意细节。 赛时代码 C 答辩题，卡了我半个小时。 枚举 \(1\sim 9\) 的全排列，然后按照顺序计算即可，但代码实现比较答辩。 赛时代码 D 显然具有可二分性，直接二分并判定可行性即可，注 ......
题解 Gym 104531D【Coffee】
2022 SYSU School Contest 题目不想翻译了，自己看能看懂。 problam The girls of HTT like drinking tea. But one day, they wanted a change and decided to try coffee in th ......
CF1864E Guess Game
原题 翻译 非常好的一道题，不过前半部分的逻辑推理比较难理解，这很博弈 由于或运算是有\(1\)就为\(1\)，因此我们对于一对数\((a,b)\)，我们不需要看\(a|b\)中为\(0\)的那些位，因此我们只需要考虑\(a|b\)全\(1\)的情况即可 我们考虑一下如果\(Alice\)说"我不知 ......
CF1869B 2D Traveling
思路 首先思考，除了 \(a\) 和 \(b\) 我们不应该到达任何非主要城市。 理由很简单，两点之间线段最短，如果我们目前要从 \(u\) 前往 \(v\) 且 \(u\) 和 \(v\) 不都是主要城市，即 \(u\) 到 \(v\) 需要花钱，那么如果再选择一个不是主要城市的 \(k\)，那么 ......
CF1868B1 Candy Party (Easy Version)
思路 首先想要均分糖果，那么必须满足糖果总数 \(sum\) 是人数 \(n\) 的倍数。 然后我们再取平均值，令 \(s=\frac{sum} n\)。 因为每个人必须收到一次糖果且只能送出一次糖果，所以对于每一个 \(a_i\)，我们首先需要满足 \(a_i-s\) 可以被表示为 \(2^x-2 ......
CF1868B2 Candy Party (Hard Version)
建议先看简单版本以及我的题解。 思路 可以发现困难版本比简单版本唯一不一样的地方就是可以给糖也可以不给，可以收糖也可以不收。 首先还是需要求和，如果无法平分，肯定无解，再算出平均数 \(s\)。 还是考虑每一个 \(a_i\)，如果 \(|a_i-s|\) 不是二次幂，那么肯定必须同时给糖和收糖，判 ......
230909 NOIP 模拟赛 T1 cake 题解
原题 题意 有一块 \(n\times m\) \((1\le n,m\le 14)\) 的蛋糕，每个位置上有一个权值 \(a_{i,j}\) \((1\le a_{i,j}\le 1000)\)，现在你要把它切开。每次你可以平行与某一边界把蛋糕切开，所以共有 \(n-1\) 个可以竖着切的位置，以 ......
CF1864C Divisor Chain
原题 翻译 好题难想 首先考虑\(x = 2^k\)怎么做，显然每次\(- 2^{k-1}\)即可 然后我们考虑对于\(x \neq 2^k\)怎么把他变成\(2^k\)，答案就是\(x -= lowbit(x)\) 操作次数\(O(logn)\)的，\(< 1000\)，正确性显然 ......
【CF1513C】Add One（动态规划）
题目大意： 给\(n()\)的每个数码加一，重复\(m(1\le m\le 2\times 10^5)\)次，求最终结果的长度，询问\(t(1\le \times)\)次。 #include<bits/stdc++.h> using namespace std; typedef long long ......
【题解】Educational Codeforces Round 142（CF1792）
没有手速，再加上被 E 卡了，废掉了。 A.GamingForces 题目描述： Monocarp 正在玩电脑游戏。他打算杀死 \(n\) 个怪兽，第 \(i\) 个的血量为 \(h_i\)。 Monocarp 的角色有两个魔法咒语如下，都可以以任意顺序用任意次（可以不用），每次使用相当于一次操作。 ......
CF *2600 DP选练
CF258D 题目描述： 有一个长度为 \(n\) 的排列，有 \(m\) 次操作，操作为交换两个数 \(a,b\) ，每次操作都有 \(50\%\) 的概率进行，求进行 \(m\) 次操作后期望逆序对个数 \(n,m\le1000\) 题目分析： 看到 \(n\) 和 \(m\) 都只有 \(10 ......
[ABC319G] Counting Shortest Paths 题解
题意 给定由 \(N\) 个节点组成的无向完全图 \(G\)，并删去 \(M\) 条边，求该图的最短路数量。 （\(2 \le N \le 2 \times 10^5, 0 \le M \le \min\left\{2 \times 10^5, \dfrac{N(N - 1)}{2}\right\} ......
题解 LOJ6738【王的象棋世界】
problem 一个 \(R\times C\) 的棋盘，你有 \(Q\) 组询问，每次询问国王走 \(R-1\) 步从 \((1,a)\) 到达 \((R,b)\) 有多少种方案。你只需要输出答案对 \(998244353\) 取模的结果。\(2\le C\le 10^5, C\le R\le 1 ......
sol. CF1680F Lenient Vertex Cover
CF1680F Lenient Vertex Cover 下面用 \(G\) 表示一个环的边集，记作环 \(G\)。 我们令一个环 \(G\) 的价值为它经过的返祖边数量，记作 \(Z(G)\)，下面给出核心结论： 若存在一条边 \(e_0\) 经过所有 \(Z(G) = 1\) 的奇环，且不经过任 ......
【题解】CF1830D Mex Tree
我们考虑这道题一看题就特别难受，所有路径？\(mex\) 之和？这是什么东西？ 我们考虑 \(mex\) 之和其实是有一点诈骗的感觉，毕竟是 \(0\) 或 \(1\)，还比较简单。就是路径上全都是 \(1\) 的时候是 \(0\)，全都是 \(0\) 的时候是 \(1\)，有 \(0\) 和 \( ......
【题解】CF1830E Bully Sort
考虑一次交换，我们发现，被选出来的 \([i,j]\) 的区间里 \(p_i\) 一定是最大的，\(p_j\) 一定是最小的。 然后我们会发现，我们原序列的逆序对数量会减少 \(2(j-i) - 1\)，而 \(\sum|p_i-i|\) 会减少 \(2(j-i)\) 那么答案就是原序列的两部分相减 ......