rounding maximum 1857b cf

CF1704C Virus 题意 有一个长度为\(n\)的环，即对于\(1\leq i\leq n\)，满足第\(i\)个与第\(i+1\)个房子相邻，特别地，第 \(n\) 个房子与第 \(1\) 个房子也相邻。 一开始，这 \(n\) 个房子中有 \(m\) 个房子被病毒感染了。在之后的每天早上 ......

CF1703E Mirror Grid 题意 给定一个 \(n\times n\ (n\le100)\) 的 01 矩形，求至少修改多少次后能使矩形旋转 0°，90°，180°，270°后所形成的矩形都完全相同。 思路 吸纳分为两种情况讨论： \(n\)为奇数 那么会出现这种情况：（以\(5\tim ......

我们知道要是任意位置交换就是环长-1 那我们肯定要让环尽量少即可 那我们的环最多就是 出现最多的那个数字的 次数 构造策略 就是把其他不同的数字 都提出来 然后往后挪一下就可以构造出环了 void solve(){ int n;cin>>n; vector<int>a(n+1),v[n+1]; fo ......

基本情况 ABC秒了。 DE都给了我希望，但都做不下去。 两道题反复横跳，结果最后谁也没做出来。 E还是比D亲切的，先补E吧。 E. Add Modulo 10 做的时候想着说对每个个位数的变化找找规律，但是没有进一步的发现。 实际上就应该从这里下手。 首先共识：相同的两个数经过操作后必然相同。 分 ......

题意： 思路： 当 $ k \ge n $ 时，一定无法构造。 证明： $ n $ 个点的无向图，每个点的度数 $ d ∈ [1，n - 1] $ ，度数的种数一定不会超过 $ n - 1 $ 。 当 $ k \le n - 1 $ 时，构造方案如下： 首先，选取前 $ k + 1 $ 个点，构造成 ......

CF1894E 数据范围多少有点诈骗 首先考虑 \(m=1\) 的情况 容易发现这个 \(l_i,r_i\leq 10^{17}\) 不是很对劲，因为直觉上感觉如果区间可取范围过大答案就是 \(0\) 我们可以取一个不是那么严格的限制条件来约束他，当 \(r-l>n\) 时，答案肯定是 \(0\)。 ......

题意： 思路： 由于需要维护极差，因此将 $ a $ 排序；由于相同的数对因子的种类和极差的贡献重复，因此将 $ a $ 去重。 设满足条件且极差最小的方案为： $ a_1 $ ， $ a_3 $ ， $ a_4 $ ， $ a_7 $ ， $ a_9 $ ，该方案等价于区间 $ [1，9] $ 。 ......

题意： 思路： 构造： $ n $ 行 $ m $ 列，先填奇数行，每行填 $ m $ 个，第 $ 2i - 1 $ 行依次填入 $ (i - 1) \cdot m + 1 $ ， $ (i - 1) \cdot m + 2 $ ， $ ... $ ， $ i \cdot m - 1 $ ， $ i ......

CF1894D 退役之后啥也不会了/kk 首先容易想到 \(b_i\) 递减插入更优。考虑答案的下界显然是 \(LCA(a)\) ，答案的上界为 \(LCA(a)+1\)，因为我们总是可以在任意位置插入递减的 \(b_i\) 来得到。因此我们只需要考虑怎么判断当前答案取上界还是下界即可。 实际上，答 ......

题意： 思路： 树形 $ dp $ ： 设 $ cnt_u $ 表示以 $ u $ 为根的子树中叶子节点的数量，那么状态转移方程有： 当 $ u $ 为叶子节点时， $ cnt_u = 1 $ ； 当 $ u $ 不为叶子节点时， $ cnt_u = \sum_{i ∈ Son_u} cnt_{v_ ......

题意： 思路： 或运算的性质：当 $ u $ 某一位的数字变为 $ 1 $ ，这一位永远都不会变为 $ 0 $。 因此，当某个栈的栈顶元素 $ v_i $ 满足 $ v_i | x = x $ 时，取出该栈顶元素 $ v_i $ ，令 $ u = u | v_i $ ；反之，不再从该栈取出元素。 不 ......

A. Rook 打印出象棋车的下一步 using namespace std; void solve(){ string s; cin>>s; char a=s[0]; char b=s[1]; set<string>ans; for(char i='1';i<='8';i++){ string t ......

题目链接 对于一种元素 \(v\)，假设它在给出可重集合中出现了 \(t\) 次，那么容易把它表示成基础的生成函数形式：\(1+x+x^2+x^3+\dots+x^t\)。 显然，把所有元素的生成函数卷一下就是答案。但是这样最坏情况为 \(O(nm\log n)\)的，不能通过这道题。 在思考优化方 ......

本题解于洛谷同步发布 洛谷传送门 CF传送门 思路 首先， 一眼丁真， 题目中说， 要 \(\prod \limits_{i=1}^n a_i \bmod k = 0\), 即 \(a_1\) 至 \(a_n\) 中有能够 \(\bmod k\) 为零的， 则遍历一遍数组， 答案取 $ \min \ ......

传送门 description 用一下方式生成一个序列： 初始序列里有一个数，是什么无所谓。给定 \(n\) 个整数，对第 \(i\) 个整数 \(d_i\)，若 \(d_i\ge 0\)，重复 \(d_i\) 次加入一个值比序列里最后一个值大 1 的数；若 \(d_i<0\)，重复 \(-d_i\ ......

题意 维护一个序列 \(s\)，有以下操作。 区间加。 区间覆盖。 求 \(l\) 到 \(r\) 的第 \(k\) 小元素。 求 \(l\) 到 \(r\) 的每个元素的 \(x\) 次方之和膜 \(y\)。 输入由给定种子 随机 生成。 Sol 珂朵莉树。 本质上就是拿 \(set\) 乱搞。 ......

CF104160 记 \(dis(T,a,b)\) 为在树 \(T\) 上 \(a,b\) 之间的距离。 给定两棵各 \(n\) 个点的树 \(T_1,T_2\)，\(q\) 次询问，每次给定两个数 \(a,b\)，询问 \[\max_{i=1}dis(T_1,a,i)+dis(T_2,b,i) \ ......

CF1870 F - Lazy Numbers 题意 给定 \(n,k\) ，设 \(rank_i\) 表示 \(i\) 的无前导 \(0\) 的 \(k\) 进制串在 \([1,n]\) 所有数的无前导 \(0\) 的 \(k\) 进制串中的字典序排名（从小到大）。求 \(rank_i=i,i\i ......

D - Two-Colored Dominoes by yzt E - Speedrun 题意 给定 \(n,m,k\) 。你需要考虑一个序列 \(t\)。 \(n\) 个要求：\(t_i \equiv h_i\mod k\)。 \(m\) 个要求：\(t_{u_i} \le t_{v_i}\)。 ......

CF821 Codeforces Round 420 (Div. 2) CF821A link CF821A题意 Okabe要改进他的实验室。实验室用一个 \(n\times n\) 的正方形网格表示（\(n\) 为正整数）。他认为，一个“好实验室”的网格内每一个不等于 \(1\) 的数字都可以用同 ......

玩一下样例就能知道 这个是和 每个seg的最大间隔相关 为了好写我们可以直接写成元素间隔 这样我们用两个multiset维护元素间隔以及元素即可 注意删除的时候我们只删一个值 需要删指针 还有考虑长度为1的情况 multiset<int>st,st1; void Erase(int x){ auto ......

前言 这道题的弱化版 CF1720D1 出现在模拟赛上，大家都用了弱化版的思路即向前扫描256个元素暴力计算 DP。如果想具体了解的就去看看弱化版的题解吧。 但弱化版的思路（除 DP 外）在此题几乎毫无落脚之地，甚至毫无关系。我在考场上曾对 $ 0 \leq a_i \leq 10^2 $ 感到了疑 ......

警告&题外话 赛时看都没看这道题，赛后看感觉还行。 （虽然这题我两个小时写不完，TLE十几次） 此题偏难，代码难度较大（对于我的方法），建议评黑，不建议没做完 数列分块入门九道 的人做，因为不会讲分块基本操作。 如果有更好方法的不要嘲讽我。 如果发现我方法正确性与时空复杂度有误的请私聊。（免得丢脸） ......

Codeforces Round 913 (Div. 3) 比赛链接 ROOK 题目 思路： 我没有下过国际象棋，但这个题跟国际象棋真是没有一点关系，就是一个简单的输出 代码： #include<bits/stdc++.h> using namespace std; #define int long ......

CF1071 Codeforces Round 517 (Div. 1, based on Technocup 2019 Elimination Round 2) CF1071A link CF1071A题意 现在你有两天的时间备考NOI，两天各有 \(a\) 小时，\(b\) 小时（时空扭曲）。 ......

CF786D Rap God 洛谷：CF786D Rap God Codeforces：CF786D Rap God Problem 给定 \(n\) 个点的树，每条边有小写字母，定义 \(str(a,b)\) 是 \(a\) 到 \(b\) 的最短路径上将每条边的字符拼接起来所得的字符串。 \(q ......

Codeforces Round 913 (Div. 3) div3 两题 新纪录.. 我再也不喝完酒打cf了 A. Rook #include <bits/stdc++.h> //#define int long long #define endl '\n' using namespace std ......

Array Equalizer 题面描述 Jeevan 有两个长度为 \(n\) 的数组：\(a\) 和 \(b\)。他有以下两种操作： 选择一个 \(k\)（\(1 \le k \le n\)），对所有满足 \(1 \leq i \leq n\) 并且 \(1 \le i \times k \le ......

Preface 补题，妈的现在Edu E都做不来这搞毛啊 A. Line Trip 签到 #include<cstdio> #include<iostream> #include<utility> #include<vector> #include<cstring> #include<cmath> ......

题意 给定一个长度为 \(n\) 的括号序列，求该括号序列满足下列条件的子序列个数。 长度为偶数 设长度为 \(2m\)，则 \(s_{1 \ldots m} =\) (，\(s_{m + 1 \ldots 2m} =\) )。 Sol 设 \(i\) 为最后一个 (，\(a\) 表示 \(\sum ......