题解codeforces round div3
【题解】Trees and XOR Queries Again - Codeforces 1902F
https://codeforces.com/contest/1902/problem/F 方法一 可以从树上路径想到轻重链剖分(也可以用其他种类的LCA算法),然后从数的异或表示很容易想到线性基。 然后因为是无修改的,所以可以轻重链剖分+ST表+线性基。具体来说就是: 先进行轻重链剖分。然后把每次 ......
Codeforces Round 590 (Div. 3)
Codeforces Round 590 (Div. 3) A Equalize Prices Again x10664 B1 Social Network (easy version) x8758 B2 Social Network (hard version) x6295 C Pipes x38 ......
Educational Codeforces Round 159 (Rated for Div. 2)
A - Binary Imbalance 如果全是 0 则显然输出 YES。对至少有一个 1 的情况,如果存在 0 则一定存在一个 0 和 1 挨在一起的位置,一直往这中间加 0 即可满足要求。 于是只要字符串包含 0 就是 YES,全 1 就是 NO。 Submission B - Getting ......
[AGC061C] First Come First Serve 题解
题目链接 点击打开链接 题目解法 易知总情况数为 \(2^n\) 考虑重复计算的情况为:存在 \([l_i,r_i]\),满足没有 \([l_j,r_j](i\neq j)\) 选在此区间中 可以得到一个容斥的 \(dp\) 做法 这个转移虽然感觉很显然,但卡了我一个晚上,一直调不出 令 \(f_i ......
[CF1902] Educational Codeforces Round 159 A~E 题解
[CF1902] Educational Codeforces Round 159 A~E 题解 A. Binary Imbalance 很快观察到如果有不同的相邻元素,那么一定有解,意味着如果全是 1 无解,其他有解 B. Getting Points 题面很长,可以发现,最好的偷懒方式一定是把所 ......
Codeforces Beta Round 18 (Div. 2 Only) E
111 感觉写的好多都是2000分 dp + 路径 这个dp 很明显发现只和 行相关 然后我们发现每行最多俩个 那么肯定就是ababab这种交叉 dp i a b 就是我们第i行选了 a b 交叉的min 转移也是26*26 预处理 cost i a b 作为每行的转移代价即可 最后要注意就是m== ......
CF1833G Ksyusha and Chinchilla 题解
题意: 思路: 当 $ n \not \equiv 0 \space (mod \space 3) $ 时,无解; 当 $ n \equiv 0 \space (mod \space 3) $ 时,设 $ size_u $ 表示以 $ u $ 为根的子树还剩余的节点个数,自根节点向叶子节点递归,返回 ......
[Educational Codeforces Round 159 (Rated for Div. 2)](https://codeforces.com/contest/1902)
Educational Codeforces Round 159 (Rated for Div. 2) 好困,差点没打 A - Binary Imbalance #include <bits/stdc++.h> #define int long long #define endl '\n' usin ......
CF1681D Required Length 题解
题意: 思路: $ BFS $ : 对于每一个数 $ x $ ,枚举其数位 $ num \space (0 \le num \le 9) $ ,将 $ x $ 与 $ num $ 的乘积 $ y $ 放入队列。重复该过程,直至 $ y $ 的位数与 $ n $ 相同。 剪枝: $ 1 $ . 对于重 ......
Codeforces Round 800 (Div. 2)
Codeforces Round 800 (Div. 2) 基本情况 A题秒了。 B题写了个递推,但是T了,这种构造题还是得多练。 B. Paranoid String 我的解法 #include <iostream> #include <cstdio> #include <cstring> #in ......
CF1695C Zero Path 题解
题意: 思路: 设 $ minv $ 表示路径最小权值和, $ maxv $ 表示路径最大权值和。 当且仅当路径长度 $ n + m - 2 \equiv 0 \space (mod \space 2) $ 且 $ minv \le 0 \le maxv $ 时,一定有权值和为 $ 0 $ 的路径; ......
[ARC120E] 1D Party 题解
提供二分+DP做法。 Solution 题意 给出 \(n(\le 2\times 10^5)\) 个单调递增偶整数 \(a_i\),求最小的 \(k\) 满足每一个 \(i\) 都可以在 \(k\) 时刻之前(含)与相邻的数相遇。每个单位时间可以移动一个单位距离。 思路 启发式思考 在想到正解之前 ......
Codeforces Beta Round 10 C
111 发现d(x)只有0-9的值 我们可以把按d(x)来分类 发现要只计算 我们就可以枚举d(C)d(a)d(b)贡献就是 这三个任选 要是有前面限制呢 我打了一下表 发现要是AB=C 那么肯定满足后面 这样我们就只用枚举C然后算他有多少对因子即可 然后发现C是1-n 连续的 可以直接枚举因子A ......
CF1163B2 Cat Party (Hard Edition) 题解
题意: 思路: 对于满足条件的区间 $ [1,x] $ ,有如下三种情况: $ 1 $ . 所有元素出现次数都为 $ 1 $ ; $ 2 $ . 除了一个元素出现次数为 $ 1 $ 之外,其余元素出现次数都相等; $ 3 $ . 除了一个出现次数比其他数的出现次数多 $ 1 $ 的元素之外,其余元素 ......
CF1198B Welfare State 题解
题意: 有一个长度为 $ n $ 的序列 $ a $ ,给定 $ q $ 次操作,每次操作为以下两种之一: $ 1 $ . $ 1 $ $ p $ $ x $: $ a_p = x $ $ 2 $ . $ 2 $ $ x $: $ a_i $ $ = $ $ max $$($$ a_i $ ,$ x ......
Codeforces Round 912 (Div. 2) - sol
Codeforces Round 912 (Div. 2) - sol Codeforces Round 912 (Div. 2) 一直是因为晚上打太晚了就没有打过 cf,所以只能 vp 了。/kk 四道题有关位运算——不好评价。 A. Halloumi Boxes 给出 \(n\) 个数 \(a_ ......
ABC331G 题解
盒子里有 \(n\) 张 \(m\) 种卡片,第 \(i\) 种卡片有 \(c_i\) 张。\(\sum c_i=n\)。 每次均匀随机选一张,再放回去。求拿出过的卡片包含全部种类所需要的取出次数的期望。 对 \(998244353\) 取模。 \(1\leq n,m\leq 2e5,c_i\gt0 ......
CF1442D Sum 题解
题目链接 点击打开链接 题目解法 \(n^3\) 的 \(dp\) 是显然的 但我们没用到 \(a\) 不降的性质 考虑一个很妙的结论:最优选法中,至多只有一个序列取了且未取满 为什么? 如果最优情况下,存在选且未选满的序列为 \(a,b\),第一个未选的元素为 \(x,y\) 如果 \(a_x>a ......
Codeforces Round 909 (Div. 3)
Codeforces Round 909 (Div. 3) A #include <bits/stdc++.h> #define int long long #define endl '\n'; using namespace std; int n; void solve(){ cin>>n; fo ......
Codeforces Round 910 (Div. 2)
Codeforces Round 910 (Div. 2) A. Milica and String wa麻了,,,不知道自己在干什么 #include <bits/stdc++.h> #define int long long #define endl '\n' using namespace s ......
Codeforces Round 911 (Div. 2)
Codeforces Round 911 (Div. 2) A. Cover in Water ,,,mc无限水 #include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; void so ......
Codeforces Round 912 (Div. 2)
Codeforces Round 912 (Div. 2) 什么位运算专场 A. Halloumi Boxes #include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; int a[11 ......
Educational Codeforces Round 158 (Rated for Div. 2)
Educational Codeforces Round 158 (Rated for Div. 2) A EDU的题总是感觉写起来怪怪的 #include <bits/stdc++.h> #define int long long #define endl '\n' using namespace ......
洛谷 P1044 [NOIP2003 普及组] 栈 题解
洛谷 P1044 [NOIP2003 普及组] 栈 题解 Sol 本题通过分析可得: 假设现在进行 \(12\) 次操作,我们把 push 认为是在地图上向右走,pop 向上走,那么其中一个合法的步骤可以是(\(p1\) 代表 push,\(p2\) 代表 pop):\(p1, p1, p2, p1 ......
Codeforces Round 912 (Div. 2)补题B、C、D1
Codeforces Round 912 (Div. 2) B. StORage room 思路 \(a_i\) = \(M_i\)\(_1\) & \(M_i\)\(_2\) & \(M_i\)\(_3\) & ...& \(M_i\)\(_n\) \((i != j)\) ac代码 #inclu ......
CF1692G 2^Sort 题解
题意: 思路: 必要性: 对于任意一个符合条件的区间[l,r],任意相邻两项,满足a_i < 2 * a_{i + 1}(l \le i \le r - 1)。 充分性: 对于任意一个长度为k + 1的区间[l,r],如果任意相邻两项满足a_i < 2 * a_{i + 1}(l \le i \le ......
CF1901 C Add, Divide and Floor 题解
Link CF1901 C Add, Divide and Floor Question 给定一个长度为 \(n\) 的序列,每次操作你需要选择一个整数 \(x\) ,并将所有 \(a_i\) 替换为 \(\lfloor \frac{a_i+x}{2} \rfloor\) 。求至少多少次操作后能将所 ......
Educational Codeforces Round 159 (Rated for Div. 2)
Educational Codeforces Round 159 (Rated for Div. 2) 基本情况 A题秒了。 B题想出来贪心思想,也想出来怎么找最优解了,但实现极其复杂繁琐,最后以先超时优化后又错误的结果告终。 B. Getting Points 明显越后面开始学收益越高。 然后写了 ......
CF1902 D Robot Queries 题解
Link CF1902 D Robot Queries Question Robot 初始在 \((0,0)\) ,有一个字符串 \(s\) ,表示运行列表 \(U\):y+1 \(D\):y -1 \(L\) :x -1 \(R\) :x+1 之后有 \(Q\) 次询问,有\(L,R,x,y\), ......
Codeforces Beta Round 8 C
提炼 首先看到24 那无疑是状态压缩 这样我们dp[1<<24]就是 收集到state状态的min 关于转移 我们需要枚举当前状态下的两个0位 复杂度显然是2424(1<<24)级别的 虽然有剪枝 但是 我们仔细一想 我们的答案 不需要 任何的顺序 证明我们可以随便拿出最优的一组即可 我们找到第一个 ......