题解codeforces round div3
ARC166 B Make Multiples 题解
Link ARC166 B Make Multiples Question 给出 \(N\) 个整数, \(A_1...A_N\) ,还有三个数 \(a,b,c\) 我们可以给 \(A_i\) 加上 \(1\) 需要使得数组 \(A\) 满足,存在一个数是 \(a\) 的倍数,一个数是 \(b\) ......
CF1899 C Yarik and Array 题解
Link CF1899 C Yarik and Array Question 给定一个数组,求数组中连续子数组之和的最大值,但要求子数组必须满足:相邻两项奇偶性不同 输出最大总和 定义 \(F[i]\) 为以 \(i\) 为终点的连续子串的最大加和 \(F[i]\) 初始为 \(a[i]\) 如果 ......
CF1899 E Queue Sort 题解
Link CF1899 E Queue Sort Question 给出一个序列 \(\{a\}\) ,可以进行一种操作:把第一个数放到最后,然后向前移,直到前面的那个数比它小为止 求把序列变成非降序列的次数 Solution 先来考虑无法变成非降序列的情况 如果第一个数最小,在一次操作后,第一个数 ......
CF1764H Doremy's Paint 2 题解
题目链接 先断环成链,由于对于多组询问不好一起处理,我们先考虑单组询问的处理方式。 一个很暴力的想法是每次模拟题目要求的操作并且最后数颜色,我们这是在通过下标进行操作最后再数颜色,而很多对于下标的操作都是不必要的,考虑直接枚举颜色进行判定。 对于每种颜色,它对于最后答案有贡献当且仅当它可以存活到那个 ......
CF1901 D Yet Another Monster Fight 题解
Link CF1901 D Yet Another Monster Fight Question 现在给你一堆怪物,你拥有法术(一个法术可以连续攻击这n个所有怪物),你可以选择任意一个怪物作为法术的第一个攻击目标(伤害为 \(x\) ),然后除了第一个攻击目标可以任意,其他攻击目标只能为曾经攻击目标 ......
UVA1658 Admiral 题解
Link UVA1658 Admiral Question 给出一个图,找出 \(1 \sim n\) 的两条,使得路径和最小 Solution 可以把点拆开,把除了 \(1\) 和 \(n\) 的点 \(i\) ,拆成 \(i\) 和 \(i'\) ,\(i\) 到 \(i'\) 连一条费用为 \ ......
P2341 受欢迎的牛 G 题解
Link P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G Question 牛栏中有 \(N\) 头奶牛,和一些 \(M\) 对爱慕关系,A->B 表示 A 爱慕 B。每个奶牛都喜欢自己,被所有奶牛喜欢就是一头明星奶牛,求明星奶牛的数量 Solution 考虑一个强连通 ......
Codeforces Round 914 (Div. 2)
Codeforces Round 914 (Div. 2) A - Forked! 解题思路: 枚举皇后和国王能被骑士吃到的位置,重合的点数就是答案。 代码: #include <bits/stdc++.h> using namespace std; using ll = long long; ty ......
题解 QOJ1359【Setting Maps】 / accoders::NOI 5682【apers】
https://qoj.ac/contest/506/problem/1359 problem 给定一张大小为 的有向图 。现在告诉你敌军大本营在节点 \(s\) 和友军基地在节点 \(t\)。你需要在每个点上放置一定数量的APERS bounding mine来杀伤敌方步兵。 为了达成战术效果,你 ......
题解 QOJ1173【Knowledge Is...】 / accoders::NOI 5681【interval】
https://qoj.ac/contest/537/problem/1173 problem 给定 \(n\leq 10^6\) 个区间,你需要求出能够最多选出多少对区间,使得两个区间不交(区间为闭区间)。要求一个区间最多属于一对选出的区间。 solution 这是一般图匹配问题的特殊情况,所以放 ......
P5048 [Ynoi2019 模拟赛] 题解
题意 给定 \(n\) 个数,有 \(m\) 个询问,每个询问给定 \(l\) 和 \(r\),求出区间 \(l\) 到 \(r\) 中的最小众数出现次数,强制在线。 数据范围:\(n\le 500000\),空间限制:\(62.5MB\)。 思路 这道题的弱化版是 蒲公英,这道题加强的地方在于数据 ......
P4180 [BJWC2010] 严格次小生成树 题解
原题链接:P4081 题意 给定一颗 \(n\) 个点 \(m\) 条边的树,求这棵树的严格次小生成树。 严格次小生成树指:边权和大于最小生成树,且边权和最小的生成树。 思路 首先可以用克鲁斯卡尔求出这棵树的最小生成树,然后考虑用类似于反悔贪心的思路来做。 对于每一条不在最小生成树中的边 \(u \ ......
CF1842E Tenzing and Triangle 题解
题意不多赘述。 思路 如果两个所选的三角形有重合部分的话,那么这种情况肯定是不会出现的。因为如果把这两个三角形合成一个大三角形的话,不仅覆盖面积会增大,而且花费的代价还不会多。 于是我们可以想到用 dp 来解决,设 \(dp_{i}\) 表示删完横坐标为 \(0\) 到 \(i\) 中的点的最小代价 ......
[ABC304Ex] Constrained Topological Sort 题解
题意 给定一张有向图 \(G\),有 \(n\) 个点和 \(m\) 条边,问是否存在一种拓扑序的排列 \(P\) 使得 \(l_{i} \le p_{i} \le r_{i}\)。 思路 首先对于一条边 \(u \to v\),如果限制满足 \(r_{v}\le r_{u}\) 或者 \(l_{v ......
【题解】AtCoder abc322_f Random Update Query
传送门:https://atcoder.jp/contests/abc332/tasks/abc332_f 容易发现,对于一个位置 $i$,$A_i$ 的最终值是由对 $i$ 的最后一次赋值操作决定的;因此,将所有操作按时间顺序倒过来考虑,则由第 $j$ 次操作决定 $A_i$ 最终值的概率为"在第 ......
【题解】AtCoder abc332_g Not Too Many Balls
传送门:https://atcoder.jp/contests/abc332/tasks/abc332_g 看完题,第一眼反应为最大流。 建模方式为:以颜色为左部点,盒子为右部点,源点 $S$ 向颜色 $i$ 连一条容量为 $A_i$ 的边,盒子 $j$ 向汇点 $T$ 连一条容量为 $B_j$ 的 ......
CodeForces 575F Bulbo
洛谷传送门 CF 传送门 提供一个傻逼 \(O(n^2)\) 做法。 首先考虑暴力 dp,设第 \(i\) 轮后在 \(j\) 坐标上的最小花费为 \(f_{i, j}\),有: \[f_{i, j} = \min f_{i, k} + |j - k| + \begin{cases} l_i - j ......
2023HFOI小学组 题解
2023HFOI小学组 题解 存钱(saving) 题目传送门 前置芝士:数学 很明显,数据范围过大,考虑用周期性来解决。 周一至周日节省的钱数相同,很明显是一个周期。 算出来所有周期,再把剩下来的天数节省的钱累加。 /*Written by smx*/ #include<bits/stdc++.h ......
Codeforces Round 914 (Div. 2)
Codeforces Round 914 (Div. 2) A. Forked! #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; void solve(){ int a,b; ......
[Codeforces] CF1793C Dora and Search
CF1793C Dora and Search 题意 给定一个长度为 \(n\) 的排列 \(a\) ,问是否存在正整数 \(l,r\) 使得 \(a_l,a_r\) 均不为 \(a_{l...r}\) 中的最大值或最小值。 思路 很明显的双指针,虽然我最开始的思路是二分 预处理当前序列的最大值和最 ......
[Codeforces] CF1790D Matryoshkas
CF1790D Matryoshkas 题意 ZYH 的玩具有很多种类,每种玩具都是一段连续的区间(如 \([3,4,5]\) ) ZYH 有很多种玩具,但是他不慎把所有玩具的元素乱序混合到了一起。例如玩具 \([1,2,3,4]\) 和玩具 \([2,3]\) 混合到一起后可能是 \([2,2,3 ......
Codeforces Round 803 (Div. 2)
基本情况 A题秒了。 B题经典+2。(经典不开longlong) C题读错题,没得思路。 B. Rising Sand Problem - B - Codeforces 思路好想,分类讨论找规律就行。 这里还是要强调一下认真分析数据: Input The second line of each te ......
Codeforces Round 802 (Div. 2)
基本情况 A题秒了。 B题经典+4。 C题没想法(大概想了半小时)。 B. Palindromic Numbers Problem - B - Codeforces 起步 首先很明显是高精。 然后要求加上的数字位数和给的位数相同。 答案不限制,只要回文就行。 第一思路就是口胡几个万能的回文答案。 给 ......
20.Explain how the following reasoning fails to address the complexity of the issue involved, and rebut it. “Sanya is warm all year round and has beautiful beaches,
Round 1: Identifying the Failure in Reasoning Speaker 1 (Student A): Hello, everyone! Let's kick off our discussion by examining the reasoning: "Sanya ......
CF848C Goodbye Souvenir 题解
原题链接:CF848C。 题意:给定一个序列 \(a\),维护两个操作。 操作一:将 \(a_x\) 修改为 \(y\) 操作二:对于区间 \(l,r\) 中出现的每一种数 \(x\),求出 \(\sum f(x)\)。 \(f(x)\) 表示区间 \(l\) 到 \(r\) 内 \(x\) 最后一 ......
P2487 [SDOI2011] 拦截导弹 题解
题意:求出一个序列 \(q\) 的最长二维不上升子序列,以及求出每个数出现在这个最长二维不上升子序列中的概率。 很显然,三维偏序问题可以用 cdq 分治来优化 dp。 对于第一问,直接把这道题的 \(n^{2}\) dp 优化到 \(\log^{2}\) 即可。具体来讲,设 \(l_{i}\) 表示 ......
P7735 [NOI2021] 轻重边 题解
是一道树剖好题,之前听 lsl 讲过一点,于是很快就做出来了。 题意:有一个 \(n\) 个节点的树,最开始的时候所有边都是轻边,维护两个操作: 操作一:将 \(u\) 到 \(v\) 的路径中经过的所有点的邻边变为轻边,再将这条路径上的边变为重边。 操作二:求出 \(u\) 到 \(v\) 这条路 ......
AT_cf17_final_j Tree MST 题解
题意:给定一颗 \(n\) 个点的树,点 \(i\) 有权值 \(a_{i}\),边有边权。现在有另外一个完全图,两点之间的边权为树上两点之间的距离加上树上两点的点权,求这张完全图的最小生成树。 首先有一个很显然的暴力,把完全图中每两点之间的边权算出来,然后跑一边最小生成树,时间复杂度 \(O(n^ ......
Codeforces Round 914 (Div. 2)
基本情况 脑子最卡的一集。 A题读假题,卡了快一小时。 B题代码太复杂,出错不好修改,一直调。 虽然最后都出来了,但是没有剩下任何时间看后面题目了。 A. Forked! Problem - A - Codeforces 一开始不知道犯得什么病,觉得可以斜着走一格算作一步,然后情况就太多了,非常不好 ......
Codeforces Round 914 (Div. 2)
C. Array Game 题意:给定一个n的数组以及k的操作数,每次可以选择下表为i,j(i<j)得到一个abs(a[i]-a[j])的数放在数组末尾,问你k次操作后,数组中最小的数是多少? 思路:首先k>=3 选相同的下表两次,一定结果是0,是最小。 k==1 遍历出下表两两相减的绝对值最小以及 ......