codeforces记忆turtle round
Codeforces Round 911 D
111 排序之后 我们可以枚举最大值 因为之前的任意两个gcd都不能超过这个最大值 但是 我们每次往下枚举 就要加入这个最大值 我们可以枚举他的因子 要是之前出现过 那么这个因子的贡献显然就可以求出来 但是这样有可能 多算了贡献比如 20可能算到 20 也算了 2 我们设sum_i 表示gcd为i的 ......
Codeforces Round 913 (Div. 3)
A. Rook #include <bits/stdc++.h> using namespace std; #define int long long using pii = pair<int, int>; using node = pii; using i32 = int32_t; void so ......
Codeforces Round 913 (Div. 3)
Codeforces Round 913 (Div. 3) 基本情况 A、B题秒了。 C题找了好几个规律,一开始一直找错,但是最后终于对的。 因为C题耗时太久,D、E题看都没看。准备先做一下再补题。 ......
CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
Preface 补题,经典不会F,看了会题解发现看不懂,索性直接开摆 A. Jagged Swaps 判断\(a_1\)是否为\(1\)即可 #include<cstdio> #include<iostream> #include<utility> #include<vector> #include ......
CodeForces 1497E2 Square-free division (hard version)
洛谷传送门 CF 传送门 感觉和 CF1889C2 Doremy's Drying Plan (Hard Version) 有异曲同工之妙。 显然去除每个数的平方因子后,两个数相乘为完全平方数当且仅当它们相等。 考虑若确定了分段方案,那么修改次数就是,每一段重复出现的数的个数。 那么我们设 \(f_ ......
Codeforces Round 913 (Div. 3)B(预处理)
[Codeforces Round 913 (Div. 3)B]{https://codeforces.com/contest/1907} 预处理: 如果说一个数据是静态的,那可用预处理来减少运行时间。 在这里,我们对字符串的大小写字母做一个预处理,提前用数组记录下他们的位置,然后再根据题目要求对对 ......
Codeforces Round 805 (Div. 3)
Codeforces Round 805 (Div. 3) 基本情况 A、B、C题秒了。 D题一开始读错题了,以为是DP,后面发现是简单贪心,拖了点时间才AC。 不过无所谓,因为E题没思路了。 但是总感觉 C 做的太不优雅。 C. Train and Queries 我的做法 就纯用STL无脑模拟。 ......
[Codeforces Round 855 (Div. 3)](https://codeforces.com/contest/1800)
Codeforces Round 855 (Div. 3) A. Is It a Cat? 为什么这个A这么麻烦 #include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; void so ......
Educational Codeforces Round 159 总结
最失败的一集。 C 开题顺序搞错,不小心先开了C,以为是A。还好C不难。 题意大概是在给定的数组最后添一个数(所有数两两不同),再自定义一个数 \(k\) ,数组中每个数可以加上若干个 \(k\) ,最后使得所有数字相等。要求加 \(k\) 的次数最少。 如果不加最后一个数,那么显然把所有的数加到与 ......
【题解】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 ......
期望dp——用记忆化搜索
https://www.luogu.com.cn/problem/P4316 本题暂时只写了用期望dp经典套路,套上期望DP的基本套路,设dp(u)为到达u点的期望长度。 期望dp,也叫概率dp 一般来说,期望dp找到正确的状态后,转移是比较容易想到的。 但一般情况下,状态一定是“可数”的 事实上, ......
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 ......
[CF1902] Educational Codeforces Round 159 A~E 题解
[CF1902] Educational Codeforces Round 159 A~E 题解 A. Binary Imbalance 很快观察到如果有不同的相邻元素,那么一定有解,意味着如果全是 1 无解,其他有解 B. Getting Points 题面很长,可以发现,最好的偷懒方式一定是把所 ......
csp认证202109-4——之状态压缩dp加期望(记忆化搜索
https://www.acwing.com/problem/content/description/4012/ #include <bits/stdc++.h> using namespace std; #define ll long long //# define int long long # ......
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== ......
[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 ......
Codeforces Round 800 (Div. 2)
Codeforces Round 800 (Div. 2) 基本情况 A题秒了。 B题写了个递推,但是T了,这种构造题还是得多练。 B. Paranoid String 我的解法 #include <iostream> #include <cstdio> #include <cstring> #in ......
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 ......
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_ ......
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 ......
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 ......
Educational Codeforces Round 159 (Rated for Div. 2)
Educational Codeforces Round 159 (Rated for Div. 2) 基本情况 A题秒了。 B题想出来贪心思想,也想出来怎么找最优解了,但实现极其复杂繁琐,最后以先超时优化后又错误的结果告终。 B. Getting Points 明显越后面开始学收益越高。 然后写了 ......
Codeforces Beta Round 8 C
提炼 首先看到24 那无疑是状态压缩 这样我们dp[1<<24]就是 收集到state状态的min 关于转移 我们需要枚举当前状态下的两个0位 复杂度显然是2424(1<<24)级别的 虽然有剪枝 但是 我们仔细一想 我们的答案 不需要 任何的顺序 证明我们可以随便拿出最优的一组即可 我们找到第一个 ......
CodeForces 1900F Local Deletions
洛谷传送门 CF 传送门 操作没有什么性质,唯一一个性质是,操作次数不超过 \(\log n\)(每次至多保留一半元素)。于是我们可以直接模拟操作。 但是肯定不能直接模拟。考虑先对原序列模拟一次,求出经过 \(i\) 次操作后保留的位置集合 \(S_i\)。那么只保留 \([l, r]\) 的元素, ......
Codeforces Round 904 (Div. 2) D. Counting Rhyme
题意:给一个序列。一个pair,不同时被序列中的某个数整除。求有多少个这样的pair。 题解:也就是他们的gcd并不是某一个数的倍数。只需要做一个gcd卷积。。?后缀和 gcd卷积 #include <cstdio> #include <vector> #include <queue> #inclu ......