题解codeforces round 871
贴一些我CF题的题解
CF1916B 分析 题目给出的是 \(x\) 的两个小于 \(x\) 的最大因子,首先考虑 \(a\) 不整除 \(b\) 的情况。既然 \(a\) 不整除 \(b\),那么 \(a\times b\) 必定是 \(x\) 的倍数,但是此时 \(a,b\) 就不一定是最大的,所以需要除以一些东西, ......
Codeforces Round 918 (Div4)刷题
title: Codeforces Round 918 (Div.4)刷题 type: "tags" Codeforces Round 918 (Div. 4) A.Odd One Out // Problem: A. Odd One Out // Contest: Codeforces - Cod ......
杭州电子科技大学2023新生赛 G 逃离节奏面 题解
Question 杭州电子科技大学2023新生赛 G 逃离节奏面 题太长自己看吧 Solution 考虑到如果走了几步后走到了相同节奏面的相同点是没有意义的,所以直接 BFS ,对于走过的节奏面的哪个点不需要走就能刷出最短路了 实际上实现的时候细节很多,要注意一下 Code #include<bit ......
杭州电子科技大学2023新生赛 E 树 题解
Question 杭州电子科技大学2023新生赛 E 树 给定一颗包含 \(n\) 个节点的带边权的树,定义 \(xordist(u,v)\) 为节点 \(u\) 到 \(v\) 的简单路径上所有边权值的异或和 有 \(q\) 次询问,每次给出 l r x 求 \(\sum_{i=l}^r xord ......
Codeforces Round 918 (Div. 4) (前缀和,权值树状数组,二维偏序, python + golang)
Dashboard - Codeforces Round 918 (Div. 4) - Codeforces from collections import * def solve(): a, b, c = list(map(int, input().split())) hs = defaultdi ......
【省选联考2020】树 题解
省选题解第一发~ 【省选联考2020】树 我和这道题还挺有缘分的。 有一次看大佬的省选游记(不知道是哪一年),然后提到有一道是01trie整体加一,当时我就印象深刻,然后在 oiwiki 上看了一下,心想这整体加一也只能从低位到高位维护 01trie 啊,又不能查询最大值,有什么卵用(划掉)。 这是 ......
[Codeforces] CF1547E Air Conditioners
CF1547E Air Conditioners 题目传送门 这道题我的思路严重劣于题解思路,所以请慎用 但是自认为我的贪心比dp好理解点 题意 有 \(q\) 组数据,每组第一排表示有 \(n\) 个方格和 \(k\) 个空调,第二排是每个空调的位置 \(a_i\) ,第三排是每个空调的温度 \( ......
codeforces刷题(1100):1862C_div3
这位大佬想出来的题解是真的牛,很强的逻辑推理能力。大佬博客为:https://blog.csdn.net/Muelsyse_/article/details/132385030?spm=1001.2014.3001.5501 ......
codeforces刷题(1100):1863B_div1+div2
B、Split Sort 跳转原题点击此:该题地址 1、题目大意 给定一个长度为n的排列(该排列的数字是包含\(1\sim n\),每个数必须出现一次)。你可以执行以下操作: 选中一个数x,比x小的数按照原来的顺序放在x的左边,大于等于x的数按照原来的顺序放在x的右边。问你 将 原始排列组成\(a_ ......
codeforces刷题(1100):1863C_div1+div2
C、MEX Repetition 跳转原题点击此:该题地址 1、题目大意 给定一个数组,要求每次依次从左到右将\(a_i\)替换为当前数组的最小非负整数(每次替换一个数后,最小非负整数也会发生改变)。问你,经过k次的操作后,最终数组是什么。 注意:该数组的数 和 最小非负整数,是从\(0,1,\cd ......
题解 [SDOI2016] 游戏
可以看出来出题人很想出一道把李超和别的什么东西凑起来的题目,于是给了这么一个缝合怪。 https://www.luogu.com.cn/problem/P4069 符号有点混乱。比如箭头又可以表示路径又可以表示赋值,代入语境应该还是好理解的。 看到 \(a\times dis + b\) 就应激反应 ......
Codeforces Round 918 (Div
Codeforces Round 918 (Div. 4) 这是本人打的第一把div4,比赛中AC到了E,算是打cf以来这一个多月的最成绩了,但是div4似乎只有EFG较难,ABC签到题,D是div3签到题。 A. Odd One Out 判断就行 #include<bits/stdc++.h> u ......
CF1884D Counting Rhyme 题解
Problem - D - Codeforces Counting Rhyme - 洛谷 法1: 我们之前肯定看过这样一道非常经典的题: 求 \(a_i\) 中有多少对 \((i,j)\),满足 \(\gcd(a_i,a_j)=1\) \(n \leq 10^6\) 这题是莫反板子题,但显然可以不用 ......
Codeforces Round 918 (Div. 4)
基本情况 做出了a,b,c,a题和b题在看题目的时候马上就有了思路,但是实际操作的时候出现代码错误,c题题目花了一部分时间理解后大概花了5分钟左右找到思路,d题一条路走到黑 A. Odd One Out 1.一开始用来键盘读入next.Int和next.Line在运行中如果手打一个个的话结果是不会报 ......
codeforces刷题(1100):1864B_div1+div2
B、Swap and Reverse 跳转原题点击此:该题地址 1、题目大意 给你一个字符串和k,你可以对该字符串做一下两个操作: 交换\(a_i\) 和 \(a_{i+2}\)的字符; 对 \([i, i+k-1]\) 这个区间的字符就行反转; 问你通过这两个操作后,原字符串所能生成新的字典序最小 ......
[ABC334C] Socks 2 题解
题目传送门 一道贪心题。 数量为 \(2\) 的袜子不用考虑,因为最好的情况就是相同颜色的配一对。 我们只需要考虑那 \(k\) 种只有 \(1\) 个的袜子,如果 \(k\) 为偶数,答案为相邻两数之差之和;如果 \(k\) 为奇数,就枚举删掉一个数,让剩下的数按照 \(k\) 为偶数的情况做,最 ......
[ABC334E] Christmas Color Grid 1 题解
题目传送门 一道 dfs 题。 先统计出绿连通块数量,然后对于每个红色方块统计涂成绿色方块后会变成多少个连通块。正常涂成绿色后应该会增加一个大小为 \(1\) 的绿连通块,但若是有不同的绿连通块与其相邻,答案又会减少 \(1\)。 Code #include <bits/stdc++.h> cons ......
Codeforces 1876G Clubstep.md
首先考虑暴力的贪心。 从 \(r\) 到 \(l\) 依次遍历,若 \(a_i < x\) 则一直进行题目中的操作。 正确性是能保证的,因为选后面的 \(j\) 只能 \(+ 1\),而选 \(i\) 可以 \(+2\),且 \(i\) 前面的部分都是 \(+1\)。 考虑转化一下,把对 \(i\) ......
CF1917F Construct Tree 题解
Description 给你一个数组 \(l_1,l_2,\dots.l_n\) 和一个数字 \(d\)。问你是否能够构造一棵树满足以下条件: 这棵树有 \(n+1\) 个点。 第 \(i\) 条边的长度是 \(l_i\)。 树的直径是 \(d\)。 只需要判断是否有解即可。 \(2\le n\le ......
Codeforces Round 918 (Div. 4)赛后总结(前缀和)(set部分用法)
Codeforces Round 918 (Div. 4)赛后总结 a,b题没啥好说的 c题典中典 没开long long 一回事,还有判断数a是否为完全平方数直接用sqrt(a)\(^2\)=a的判断就可以 d题经典字符串问题 首先,我们以一个字符数组的形式存数据。再根据已知cv,cvc两种形式, ......
Codeforces Round 887 (Div. 1)
Codeforces Round 887 (Div. 1) A 先来个二分。注意到这样一件事:考虑是 \(a_i\) 失效的最小时间 \(t_i\),发现 \(t\) 有单调性。所以从大到小考虑 \(a\),每次相当于将二分的值减去一个值,复杂度 \(O(\sum n(\log n + \log k ......
【题解】BZOJ 4403序列统计
tg.BZOJ 4403序列统计 pj.BZOJ 4403序列统计 没啥用的题解 \(QWQ\)——无脑思考 首先要想怎么求单调不上升序列的个数,因为可能会有重复的数,所以不能直接用排列组合。 那这道题怎么打呀? 我不知道啊\(\dots\) \((~:\) 因为原来是单调不下降序列,将第 \(i\ ......
Codeforces Round #843 (Div. 2)
安利一个叫codeforces better的插件 https://greasyfork.org/zh-CN/scripts/465777-codeforces-better 今天装了后使用cf体验非常舒适 A.Gardener and the Capybaras (easy version) 问字 ......
CF1806F GCD Master 题解
题目链接 Easy version Hard version 题目解法 参考 DeaphetS 的题解 很有意思的题,感觉 \(F1\) 不到 \(*2900\),\(F2\) 超过 \(*2900\) F1 简化题目中的操作:把 \(n\) 个数放到 \(n-k\) 组中,求 \(\max(\su ......
[CF30E] Tricky and Clever Password 题解
[CF30E] Tricky and Clever Password 题解 注意到一个合法字符串首尾相同,考虑用 S 的反转和 S 跑 KMP。 对于只有一个串,暴力 manacher 即可。 匹配到某一位置 \((i, j)\) 时,查询区间最长的奇回文串长度,用二分 + ST 表解决,因为回文串 ......
P9992 [Ynoi Easy Round 2024] TEST_130 题解
最开始没看到子树的限制,以为是个极其困难题。 思路 由于问题是在子树下,可以考虑在 dfn 序上扫描线。 考虑一个点 \(u\) 对 \(v,d\) 的贡献。 令 \(dep_u\) 为 \(u\) 的深度,\(mdep_u\) 为 \(u\) 的子树下的最大深度。 \(dep_u< dep_v\) ......
P9993 [Ynoi Easy Round 2024] TEST_133 题解
思路 看到时限这么大,考虑暴力做法。 我们将原序列分为 \(\text{B}\) 个块,每个块类似线段树三一样的维护 \(add,maxadd\),表示这一块需要加的值,加的值的历史最大值。 同时对于每个数可以维护一个真实值与一个历史最值。 那么下传标记可以写成这样。 inline void pus ......
P9994 [Ynoi Easy Round 2024] TEST_132 题解
题解怎么都是用暴力日过去的啊。 思路 考虑根号分治,设阈值为 \(B\)。 对于第二维出现次数超过 \(B\) 的,我们可以在修改时暴力更改,这部分复杂度为 \(O(\frac{nm}{B})\)。 对于第二维出现次数小于 \(B\) 的,我们可以在修改是打标记,查询时遍历一遍,这部分的复杂度为 \ ......
P9995 [Ynoi2000] rspcn 题解
思路 比较典的 ODT 题目。 发现排序是一个非常有性质的操作。 它对区间的更改与颜色段均摊差不多。 那么我们可以想到用 ODT 来维护这一整个序列。 具体的,区间排序操作可以用 ODT 维护每次排序产生的段,每段用线段树维护排序后的结果。 每次修改就可以进行线段树的分裂与合并。 如何查询。 可以发 ......