1178h cf
加训日记 Day8——关于cf一道题调了半天这件事
Day8,9.28 ·国庆假期前狠狠刷cf ·把之前比赛的题目基本上都补了(牛客的没来得及补) ·这一个星期日均四道题,确实挺不错的 ·思维还是跟不上捏 ......
题解 CF1873H【Mad City】
其他题解怎么又 Tarjan 又 Dijkstra 的,这是 div4H 的样子吗,来个简单好写的做法。 题面里的人名太复杂了,本题解中称为警察和小偷。 注意到,如果小偷成功到达了环上,那么一定不会被警察抓到。因为小偷知道警察下一步会走到哪里,他可以执行相同的操作(顺时针/逆时针/静止),使得他和警 ......
CF765F Souvenirs 解题报告
简要题意: 给定一个序列,每次查询一个区间差最小的2个数的差。 解法1(我个人最喜欢的解法): 考虑莫队。 当一个不太经典的数据结构出现时,如果能离线,那么莫队是最自然的想法。 这个问题具有一个很显然的性质就是,对一个区间排好序后,答案一定是某相邻的两个数带来的,所以我们的莫队大概率离不开维护顺序这 ......
CF1195 Codeforces Round 574 (Div. 2)
CF1195A Drinks Choosing 先将相同权值的配对直到只剩下一个,然后再配剩下的单个。 #include<iostream> #include<cstdio> using namespace std; const int N=1005; int n,k; int a[N]; int ......
CF1440 Codeforces Round 684 (Div. 2)
CF1440A Buy the String 每个点有两种决策,要么选当前的字符,要么选跟当前字符不同的字符,取个较小值相加。 #include<iostream> #include<cstdio> using namespace std; const int N=1005; int T; int ......
CF1197 Educational Codeforces Round 69 (Rated for Div. 2)
CF1197A DIY Wooden Ladder 答案为 \(\min(a_{n-1},n-2)\)。 #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=100005; ......
CF1447 Codeforces Round 683 (Div. 2, by Meet IT)
CF1447A Add Candies 可以将操作看做将 \(a_i\) 减 \(i\),然后第 \(i\) 次操作 \(i\) 就是合法的。 #include<iostream> #include<cstdio> using namespace std; int T; int n; void so ......
CF1008 Codeforces Round 497 (Div. 2)
CF1008A Romaji 直接模拟。 #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=105; int n; char s[N]; int main() { scanf( ......
CF1011 Codeforces Round 499 (Div. 2)
CF1011A Stages 每次记下上一个选的位置,贪心能填就填。 #include<iostream> #include<cstdio> using namespace std; const int N=55; int n,k; char s[N]; int cnt[27]; int main( ......
CF1020 Codeforces Round 503 (by SIS, Div. 2)
CF1020A New Building for SIS 分类讨论 \(a,b\) 两个端点的几种情况就好了,特判 \(t_a=t_b\) 的情况。 #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> usi ......
CF1036 Educational Codeforces Round 50 (Rated for Div. 2)
CF1036A Function Height 答案为 \(\lceil \frac{k}{n}\rceil\)。 #include<iostream> #include<cstdio> using namespace std; long long n,k; int main() { scanf(" ......
CF1072 Codeforces Round 517 (Div. 2, based on Technocup 2019 Elimination Round 2)
CF1072A Golden Plate 第 \(i\) 个矩形的周长为 \(2(w - 4(i - 1))+2(h - 4(i - 1))-4\),枚举 \(i\) 求和。 #include<iostream> #include<cstdio> using namespace std; int n ......
CF1079 Codeforces Round 522 (Div. 2, based on Technocup 2019 Elimination Round 3)
CF1079A Kitchen Utensils 令 \(c_i\) 表示餐具 \(i\) 出现的数量,最小的餐具套数为 \(t=\lceil \frac{\max\{c_i\}}{k}\rceil\),按照这个计算就好了。 #include<iostream> #include<cstdio> # ......
CF1162 Codeforces Round 557 (Div. 2) [based on Forethought Future Cup - Final Round]
CF1162A Zoning Restrictions Again 每个位置越高越好,暴力模拟即可。 #include<iostream> #include<cstdio> using namespace std; const int N=55; int n,h,m; int a[N]; int m ......
CF957 Codeforces Round 472 (rated, Div. 2, based on VK Cup 2018 Round 2)
CF957A Tritonic Iridescence 如果原序列中有两个相同的字符,显然不合法。 如果开头或者结尾为 ?,或者有两个连续的 ?,或者一个 ? 两边的字符不同显然合法。 否则一定不合法。 #include<iostream> #include<cstdio> using namesp ......
CF992 Codeforces Round 489 (Div. 2)
CF992A Nastya and an Array 答案为非零数的个数。 #include<iostream> #include<cstdio> #include<map> using namespace std; const int N=100005; int n; int a[N]; map< ......
CF996 Codeforces Round 492 (Div. 2) [Thanks, uDebug!]
CF996A Hit the Lottery 直接贪心尽可能的分配到 \(k_5\),剩下的依次分配给 \(k_4,k_3,k_2,k_1\)。 #include<iostream> #include<cstdio> using namespace std; int n; int k[6]; int ......
CF364D Ghd 题解
CF364D Ghd 题解 题目大意 给定一个长度为 \(n\) 的序列 ,你需要从中选出一个元素个数不少于 \(\left\lceil{\frac{n}{2}}\right\rceil\) 的子序列,使得这个子序列中所有元素的 \(\gcd\) 最大。 分析 数据范围吓人。 \(10^6\),但是 ......
[题解] CF1882D - Tree XOR
CF1882D - Tree XOR 知识点:换根 DP 。 主要难点是要思考如何操作使得代价最小,这个过程是一个贪心的过程。想到怎么操作,计算答案的过程就是一个板子换根了。 题意 给定一颗 \(n\) 个节点的树,点 \(i\) 具有权值 \(a_i\) 。现在需要你不断执行以下操作,使得树上所有 ......
[题解]CF1878E Iva & Pav
CF 是没题考了吧,每场都出二进制拆位。 思路 首先我们可以二分 \(r\),因为 \(r\) 越大,按位与一定只会小于等于 \(r\) 小的情况。 那么,我们可以用 \(num_{i,j}\) 记录 \(a_j\) 第 \(i\) 位的二进制情况。 如果我们对 \(num_{i,j}\) 做一个前 ......
CF1878 A-G 题解
前言 赛时代码可能比较难看。 A 判定 \(a\) 中是否有 \(k\) 即可。 赛时代码 B 奇怪的构造题。 令 \(a_1=1,a_2=3\),其他项由上一项加一开始枚举判定可行性即可,可以简单证明时间复杂度为 \(O(n)\)。 赛时代码 C 容易发现当 \(x\in \left[\dfrac ......
CF1861E Non-Intersecting Subpermutations
原题 翻译 一道很显然是 \(dp\) 的题 我们设 \(f_{i,j}\) 表示钦定了前 \(i\) 个数,其中 \([i-j+1,i]\) 这些数中没有重复(就是说有成为 \(1\sim K\) 的排列的可能性)时的成本之和 我们可以用刷表法来表示这个 \(dp\) 的转移方法: \[\begi ......
CF1878D Reverse Madness
观察式子发现结论。 有这样一个结论,由 \(x\) 得到的反转区间 \([a,b]\) 的对称轴就是 \(x\) 所在的题给区间 \([l,r]\) 的对称轴,且 \([a,b]\subset [l,r]\)。 这个结论有什么用?如果没有这个结论,我们离线 \(q\) 次询问得到的是一系列散乱的反转 ......
CF1791G2 Teleporters (Hard Version) 题解
CF1791G2 Teleporters (Hard Version) 题解 题目大意 题意挺清楚的,给个传送门吧。 分析 比较简单的贪心题,很容易就能看出来是贪心,也很容易就能看出来贪什么。 我没做简单版(Teleporters (Easy Version)),但是我去看了一眼。那个也非常简单,不 ......
CF1777E
problem & blog 反转的边最大权值最小,想到二分。 于是二分代价即可。 反转代价小于二分的代价的边可以反转,所以再建一条反向边即可。 在 DAG 中,存在一个点可以到达所有的点的条件是入度为 \(0\) 的点有且只有一个。 所以二分判断的时候将可以反转的边转化为无向边,然后缩点,形成 D ......
CF1882 div.2 做题记录
A 题面 扫一遍,令 \(b_i\rightarrow b_{i-1}+1\),若 \(b_i=a_i\),\(b_i\rightarrow b_i+1\)。 点击查看代码 #include<bits/stdc++.h> #define ull unsigned long long #define ......
CF1882C Card Game
某种程度上的抽卡游戏? 有这样一个结论:一个后缀中\([i+1,n]\) 中所有的正数都可以被取到,所以维护一个正数后缀和 \(s_i\),枚举每个位置 \(i\),如果 \(i\) 为奇数,答案对 \(a_i+s_{i+1}\) 取 \(\max\),否则对 \(s_{i+1}\) 取 \(\ma ......
CF1879D Sum of XOR Functions
异或和按位处理的典型例题。 要求所有子区间异或和乘区间长度的总和,朴素的方法是 \(O(n^2)\) 地枚举区间,显然无法通过。 因为涉及异或和,而异或运算不进位,故自然地想到把 \(a_i\) 写成二进制形式,单独研究每一位的贡献,最后再合并。这是处理此类问题的一般思路。 1. 二进制拆分 比方说 ......
Educational Codeforces Round 155 D (CF1879_D)
题目大意 给一个长度为 \(n\) 的数组,求 \(\Sigma_{i=1}^{n} \Sigma_{j=i}^{n} 区间异或和 \times (j-i+1)\) 其中 \(n\leq 3e5,~a[i]\leq 1e9\) 分析 首先注意到由 \(l\) 到 \(r\) 的区间异或和可以转化为 ......