题解1249 div cf
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 ......
CF613D Kingdom and its Cities
题意 给定一棵树,每次询问给出 \(k\) 个点。 问最少删除多少个 节点 (不能删这 \(k\) 个点) 使得这 \(k\) 个点两两不连通。 Sol 无解的情况是 \(trivial\) 的。 判断是否有相邻的两个关键点就行了。 但是 \(dp\) 是不太 \(trivial\) 的。 设 \( ......
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\), ......
CF1902 C Insert and Equalize 题解
Link CF1902 C Insert and Equalize Question 有一个 \(n\) 个元素的数组 \(a\),每个元素都不一样 现在我们需要在 \(a\) 中添加一个数字 \(a_{n+1}\),和之前的元素都不一样 然后选择一个数 \(x\),可以在一个元素上加 \(x\), ......
CF1902 B Getting Points 题解
Link CF1902 B Getting Points Question Monocarp 的一个学期有 \(n\) 天,需要修 \(P\) 个学分,完成一节课程加 \(l\) 个学费,完成一个任务加 \(t\) 个学分 Monocarp 一天可以完成一节课+两个任务 任务每周分配一个,也就是 d ......
[AGC063C] Add Mod Operations 题解
题目链接 点击打开链接 题目解法 好难想的构造题!!!到底是怎么想到的??? 首先无解的条件是好判的,如果有 \(i\neq j,\;a_i=a_j\) 且 \(b_i\neq b_j\),那么就无解 将 \(a\) 从小到大排序 考虑下面的构造方式:\(y=curmax+x\),这样可以使最大值清 ......
CF1902 A Binary Imbalance 题解
Link CF1902 A Binary Imbalance Question 给出一个 01串,可以在任意一个位置 \(i\) 插入一个字符,如果 \(a_i \ne a_{i+1}\) 插入的字符为 \(0\) 否则插入的字符为 \(1\) 问,是否可以通过任意次操作使得串中 \(0\) 的数量 ......
湖南省网络攻防邀请赛 RE 题解
ez_apkk 解题过程: 将apk拖入jadx,查看MainActivity,发现是简单RC4加密,密钥是“55667788”,最后再将加密结果+1 public String Encrypt(String plainText, String key) { int[] S = new int[25 ......
CF1692H Gambling 题解
题意: 思路: 考虑离散化: 枚举 $ x $ 中出现的每一个数 $ val $ , $ val $ 出现的次数为 $ cnt $ ,记录 $ val $ 每一次出现的索引 $ idx_i(1 \le i \le cnt) $ 。设 $ x $ 中与 $ val $ 相等的数贡献为 $ +1 $ , ......
Codeforces Round 904 (Div. 2) D. Counting Rhyme
题意:给一个序列。一个pair,不同时被序列中的某个数整除。求有多少个这样的pair。 题解:也就是他们的gcd并不是某一个数的倍数。只需要做一个gcd卷积。。?后缀和 gcd卷积 #include <cstdio> #include <vector> #include <queue> #inclu ......
P1004 [NOIP2000 提高组] 方格取数 题解
题意: 思路: 考虑四维 $ dp $ : 设 $ dp[i][j][k][l] $ 表示两条路径分别走到 $ (i,j) $ 和 $ (k,l) $ 时所能获取的最大和,显然会超时。 考虑三维 $ dp $ : 设 $ dp[i][j][k] $ 表示两条路径走了 $ i $ 步分别走到第 $ j ......
[Codeforces] CF1807E Interview
题目翻译 有 \(n\) 堆石头,其中 \(n-1\) 堆都只有重量为一克的石头,剩下一堆有则有一块有两克的石头和若干重量为一克的石头。 你的任务是在 \(30\) 次询问内推理出那一堆有重量为两克的石头是第几堆。 首先输入 \(n\),接下来输入 \(n\) 个数 \(a_1,a_2\dots a ......
SP1716 GSS3 - Can you answer these queries III 题解
题意: 给定一个长度为 $ n $ 的序列 $ a $ , $ q $ 次操作,每次操作为以下之一: \(0\) \(x\) \(y\):将 \(a_x\) 修改为 \(y\) \(1\) \(l\) \(r\):询问区间 \([l,r]\) 的最大连续子序列和 思路: 考虑线段树维护区间最大连续子 ......
Codeforces Round 881 (Div. 3)
Codeforces Round 881 (Div. 3) A:ABC A. Sasha and Array Coloring 题意:求最大的着色成本(着色成本是指同一个颜色的最大值-最小值) 思路:肯定不能是相同的,直接最大-最小就行 #include <bits/stdc++.h> using ......
Codeforces Round 911 (Div. 2)
Preface 忙里偷闲补一下之前欠下的一些CF 这场前5个题都极其一眼,然而F瞪了好久愣是屁都不会 感觉现在水平有有点到瓶颈了,以前是Div2D卡现在是Div2E卡,但至少还是在进步的 A. Cover in Water 如果存在某个空地块的长度大于\(2\)则可以用两个块造出无限水,否则答案就是 ......
[Codeforces] CF1753A1 Make Nonzero Sum (easy version)
题目大意 给你一个数组 \([a_1,a_2,...a_n]\) ,其中每一项 \(a_i\) 都为 \(1\) 或 \(-1\) ,你需要构造一个划分 \([l_1,r_1],[l_2,r_2],[l_3,r_3],...[l_k,r_k]\) 使得: 将每一个区间内的数按照以下方法计算出\(s_ ......
Codeforces Round 911 (Div. 2)
Codeforces Round 911 (Div. 2) A - Cover in Water int main() { IOS; for (cin >> _; _; --_) { cin >> n >> s + 1; int ans = 0; bool f = 0; for (int i = 1 ......
Codeforces Round 904 (Div. 2) C. Medium Design
jly:开始的想法:首先枚举max的位置。包含它的一定是全加,剩下的一定都不加。然后求所有位置的最小值。 初始全0,枚举max之后,因为是加区间,min一定在两端(最左或最右)。所以不需要枚举max,我们枚举min就好(因为加区间和初始全0,这个题的特殊性)。 写法注意的点:下标从0开始,区间的左端 ......