题解rounding maximum 1857b

Codeforces Round 800 (Div. 2) 基本情况 A题秒了。 B题写了个递推，但是T了，这种构造题还是得多练。 B. Paranoid String 我的解法 #include <iostream> #include <cstdio> #include <cstring> #in ......

题意： 思路： 设 $ minv $ 表示路径最小权值和， $ maxv $ 表示路径最大权值和。 当且仅当路径长度 $ n + m - 2 \equiv 0 \space (mod \space 2) $ 且 $ minv \le 0 \le maxv $ 时，一定有权值和为 $ 0 $ 的路径； ......

提供二分+DP做法。 Solution 题意 给出 \(n(\le 2\times 10^5)\) 个单调递增偶整数 \(a_i\)，求最小的 \(k\) 满足每一个 \(i\) 都可以在 \(k\) 时刻之前（含）与相邻的数相遇。每个单位时间可以移动一个单位距离。 思路 启发式思考 在想到正解之前 ......

111 发现d（x）只有0-9的值 我们可以把按d(x)来分类 发现要只计算 我们就可以枚举d（C）d(a）d（b）贡献就是 这三个任选 要是有前面限制呢 我打了一下表 发现要是AB=C 那么肯定满足后面 这样我们就只用枚举C然后算他有多少对因子即可 然后发现C是1-n 连续的 可以直接枚举因子A ......

题意： 思路： 对于满足条件的区间 $ [1，x] $ ，有如下三种情况： $ 1 $ . 所有元素出现次数都为 $ 1 $ ； $ 2 $ . 除了一个元素出现次数为 $ 1 $ 之外，其余元素出现次数都相等； $ 3 $ . 除了一个出现次数比其他数的出现次数多 $ 1 $ 的元素之外，其余元素 ......

题意： 有一个长度为 $ 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) 一直是因为晚上打太晚了就没有打过 cf，所以只能 vp 了。/kk 四道题有关位运算——不好评价。 A. Halloumi Boxes 给出 \(n\) 个数 \(a_ ......

盒子里有 \(n\) 张 \(m\) 种卡片，第 \(i\) 种卡片有 \(c_i\) 张。\(\sum c_i=n\)。 每次均匀随机选一张，再放回去。求拿出过的卡片包含全部种类所需要的取出次数的期望。 对 \(998244353\) 取模。 \(1\leq n,m\leq 2e5,c_i\gt0 ......

题目链接 点击打开链接 题目解法 \(n^3\) 的 \(dp\) 是显然的 但我们没用到 \(a\) 不降的性质 考虑一个很妙的结论：最优选法中，至多只有一个序列取了且未取满 为什么？ 如果最优情况下，存在选且未选满的序列为 \(a,b\)，第一个未选的元素为 \(x,y\) 如果 \(a_x>a ......

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) A. Milica and String wa麻了，，，不知道自己在干什么 #include <bits/stdc++.h> #define int long long #define endl '\n' using namespace s ......

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) 什么位运算专场 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) A EDU的题总是感觉写起来怪怪的 #include <bits/stdc++.h> #define int long long #define endl '\n' using namespace ......

洛谷 P1044 [NOIP2003 普及组] 栈 题解 Sol 本题通过分析可得： 假设现在进行 \(12\) 次操作，我们把 push 认为是在地图上向右走，pop 向上走，那么其中一个合法的步骤可以是（\(p1\) 代表 push，\(p2\) 代表 pop)：\(p1, p1, p2, p1 ......

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 ......

题意： 思路： 必要性： 对于任意一个符合条件的区间[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 ......

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) 基本情况 A题秒了。 B题想出来贪心思想，也想出来怎么找最优解了，但实现极其复杂繁琐，最后以先超时优化后又错误的结果告终。 B. Getting Points 明显越后面开始学收益越高。 然后写了 ......

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\)， ......

提炼 首先看到24 那无疑是状态压缩 这样我们dp[1<<24]就是 收集到state状态的min 关于转移 我们需要枚举当前状态下的两个0位 复杂度显然是2424（1<<24）级别的 虽然有剪枝 但是 我们仔细一想 我们的答案 不需要 任何的顺序 证明我们可以随便拿出最优的一组即可 我们找到第一个 ......

Link CF1902 C Insert and Equalize Question 有一个 \(n\) 个元素的数组 \(a\)，每个元素都不一样 现在我们需要在 \(a\) 中添加一个数字 \(a_{n+1}\)，和之前的元素都不一样 然后选择一个数 \(x\)，可以在一个元素上加 \(x\)， ......

Link CF1902 B Getting Points Question Monocarp 的一个学期有 \(n\) 天，需要修 \(P\) 个学分，完成一节课程加 \(l\) 个学费，完成一个任务加 \(t\) 个学分 Monocarp 一天可以完成一节课+两个任务 任务每周分配一个，也就是 d ......

题目链接 点击打开链接 题目解法 好难想的构造题！！！到底是怎么想到的？？？ 首先无解的条件是好判的，如果有 \(i\neq j,\;a_i=a_j\) 且 \(b_i\neq b_j\)，那么就无解 将 \(a\) 从小到大排序 考虑下面的构造方式：\(y=curmax+x\)，这样可以使最大值清 ......

Link CF1902 A Binary Imbalance Question 给出一个 01串，可以在任意一个位置 \(i\) 插入一个字符，如果 \(a_i \ne a_{i+1}\) 插入的字符为 \(0\) 否则插入的字符为 \(1\) 问，是否可以通过任意次操作使得串中 \(0\) 的数量 ......

ez_apkk 解题过程： 将apk拖入jadx，查看MainActivity，发现是简单RC4加密，密钥是“55667788”，最后再将加密结果+1 public String Encrypt(String plainText, String key) { int[] S = new int[25 ......

题意： 思路： 考虑离散化： 枚举 $ x $ 中出现的每一个数 $ val $ ， $ val $ 出现的次数为 $ cnt $ ，记录 $ val $ 每一次出现的索引 $ idx_i(1 \le i \le cnt) $ 。设 $ x $ 中与 $ val $ 相等的数贡献为 $ +1 $ ， ......

题意：给一个序列。一个pair，不同时被序列中的某个数整除。求有多少个这样的pair。 题解：也就是他们的gcd并不是某一个数的倍数。只需要做一个gcd卷积。。？后缀和 gcd卷积 #include <cstdio> #include <vector> #include <queue> #inclu ......

题意： 思路： 考虑四维 $ dp $ ： 设 $ dp[i][j][k][l] $ 表示两条路径分别走到 $ (i，j) $ 和 $ (k，l) $ 时所能获取的最大和，显然会超时。 考虑三维 $ dp $ ： 设 $ dp[i][j][k] $ 表示两条路径走了 $ i $ 步分别走到第 $ j ......

题意： 给定一个长度为 $ n $ 的序列 $ a $ ， $ q $ 次操作，每次操作为以下之一： \(0\) \(x\) \(y\)：将 \(a_x\) 修改为 \(y\) \(1\) \(l\) \(r\)：询问区间 \([l，r]\) 的最大连续子序列和 思路： 考虑线段树维护区间最大连续子 ......