题解1738c cf
CF1500F Cupboards Jumps 题解
题目链接 点击打开链接 题目解法 感觉是一个融合了许多技巧的题,很巧妙 题目要求 \(\max(h_i,h_{i+1},h_{i+2})-\min(h_i,h_{i+1},h_{i+2})=w_i\),这可以转化成另一个只和两项有关的形式为:\(\max(|h_i-h_{i+1}|,|h_i-h_{ ......
CF 1612 E
看到k等于20 我们大胆猜测这个选择的个数不会超过20条 枚举我们要选i条 然后计算权值的话 要是大于等于i的k都是算1的 否则就算 k/i 我们按照这个给每一个计算一下权值 选最大的i条即可 void solve(){ int n;cin>>n; vector<int>t[21],cz[21],v ......
[Codeforces] CF1737C Ela and Crickets
CF1737C Ela and Crickets 题意 给定一个 \(n\times n\) 的棋盘,棋盘上有且仅有三颗排成 \(\text{L}\) 形的棋子。 对于 \(\text{L}\) 形的定义,有且仅有以下四种情况: 棋子的移动规则和跳棋相同。它可以水平、垂直或斜向移动。当且仅当一个棋子 ......
[CF839E] Mother of Dragons
最优方案一定是选择一个团,并在团里平均分配点权。 实际上,定义一个点 \(u\) 的权重 \(w_u\) 为 \(\sum\limits_{(u,v)}s_v\),那么如果方案中 \(w_x>w_y\),将 \(y\) 去掉并将其点权加在 \(x\) 上一定更优,所以答案一定会被调整成一个团。 对于 ......
CF1900D Small GCD
Link 这是一个需要欧拉反演的题目 首先,可以知道只和数字之间的大小有关,数列的顺序无关,那么就可以首先排一个序方便解决该问题。 根据欧拉函数的性质,知道\(n=\sum_{d|n}\phi{(n)}\) 那么我们每次先确定中间的数\(a_j\),然后根据公式,得他它得贡献是\(\sum_{i=1 ......
[ARC106F] Figures 题解
题目链接 点击打开链接 题目解法 这么神仙的推式子题 看到生成树计数,第一反应是 \(prufer\) 序列 考虑在 \(prufer\) 序列上搞这个东西 可以得到 \(ans=\sum\limits_{\sum\limits_{i=1}^n d_i=n-2}\binom{n-2}{d_1,d_2 ......
CF1388D
最开始以为有环 发现没环之后 发现是有负数的 把第三个样例画出来 发现疑似是拓扑序之后要是该点为正肯定 放前面 否则放后面 但是发现好像 有些点为负数的可以通过+变回正的也要放前面 那我们贪心跑一遍即可 void solve(){ int n;cin>>n; vector<int>a(n+1),b( ......
AtCoder Beginner Contest 332 题解
A - Online Shopping 题目链接 Atcoder Luogu 简要题意 共有 \(n\) 件商品,第 \(i\) 件商品的价格为 \(p_i\) 日元,数量为 \(q_i\) 件。 除了购买商品所需的的钱数,还要支付运费:如果所买商品的总价小于 \(s\) 日元,那么要支付运费 \( ......
CF1793C Dora and Search
CF1793C Dora and Search Difficulty:1200 题意翻译 题目描述 给定一个长度为 \(n\) 的排列 \(a\) ,问是否存在正整数 \(l,r\) 使得 \(a_l,a_r\) 均不为 \(a_{l...r}\) 中的最大值或最小值。 输入输出格式 第一行一个正整 ......
CF1368H2 Breadboard Capacity
题面传送门 首先这个是比较经典的最大流:从源点向红点连 \(1\) 流量的边,网格中每条边流量为 \(1\),蓝点向终点连流量为 \(1\) 的边,最大流就是答案。 最大流不好算,我们考虑最小割。最小割相当于给每个点染上红色或者蓝色,要使得两端点异色的边最少。 直接做还是不好做,我们考虑挖掘一点性质 ......
CF1253F Cheap Robot
题意 给定一个图,走过一条边的花费为权值,其中有 \(k\) 个充电点。 你需要确定一个电量的上限,使得满足从 \(a\) 走到 \(b\)。 Sol 先对于每个点求出她走到充电点最近的距离,用 \(dij\) 随便跑跑。 考虑从 \(a \to b\) 一条边的贡献。设当前的电量上限为 \(c\) ......
CF 思维题随记
CF1487B Cat Cycle 首先小猫 A 的行动是确定的,我们可以算出它走的圈数和最后的位置。然后根据 \(n\) 分情况讨论: 偶数不会相遇,直接做。 奇数。如果猫 A 不动那么猫 B 每圈只需要走 \(n-1\) 步。现在猫 A 会动其实就是猫 A 每多走一圈,它们就多相遇一次,猫 B ......
CF1610H Squid Game
题意 给定一棵树,以及 \(m\) 条路径。 让你选出最少的点,使得对于每一条路径,都有一个点距离链上的点离端点更近。 Sol 考虑将每一条路径分为直链和曲链考虑。 注意到所有的曲链最多对答案有 \(1\) 的贡献。 考虑直链的情况。 注意到一个很显然的东西。 对于一个选择的点,如果她的上方不是端点 ......
[CF1603E] A Perfect Problem
A Perfect Problem 题面翻译 一个序列是好的当且仅当集合最大值乘上集合最小值大于等于集合元素的加和; 一个序列是完美的,当且仅当这个序列的任何子序列都是好的(包括自己不包括空集); 你要求的是:长度为 \(n\) 的并且每一个元素都大于等于 \(1\) 并且小于等于 \(n+1\) ......
[CF1253F] Cheap Robot
Cheap Robot 题面翻译 给你一张 \(N\) 个点的带权无向连通图,其中结点 \(1,2,…,k\) 为充电中心。 一个机器人在图中行走,假设机器人的电池容量为 \(c\),则任何时刻,机器人的电量 \(x\) 都必须满足 \(0\le x\le c\)。如果机器人沿着一条边权为 \(w\ ......
「杂题乱刷」CF1272D
题目链接 CF1272D Remove One Element 题意简述 给定一个长度为 \(n\) 的序列,你需要求出至多删除一个数后的这个序列的最长上升子串。 解题思路 首先我们可以想一下这题的弱化版,给定一个长度为 \(n\) 的序列,你需要求出至多删除一个数后的这个序列的最长上升子序列。 这 ......
[CF704E] Iron man
题目链接 树的情况不好做。先树剖,现在变成了链的问题。 考虑对时间扫描线,会发现所有人的相对顺序变化的时候,就是有人相遇了。所以他的相对顺序可以用一个 set 维护。而将会相遇的人一定是插入时相对顺序相邻的人,可以 check 一下取个最小值。可以把时间线设成全局变量,这样就可以跑 set 的排序了 ......
[CF1592F2] Alice and Recoloring 2
题目链接 操作 2 和 3 可以用另两个代替,没有任何用。 设 W 表示 \(t_{i,j}=0\),B 表示 \(t_{i,j}=1\) 考虑差分。设 \(t_{i,j}=s_{i,j}\oplus s_{i+1,j}\oplus s_{i,j+1}\oplus s_{i+1,j+1}\),那么目 ......
[CF1416F] Showing Off
题目链接 如果把方向看做有向边,整个图是一个内向基环树。 所以考虑哪些点有可能放在基环树的非环部分上,当且仅当一个点周围有严格小于他的点。 由于图一定是二分图(黑白染色),没有奇环,所有偶环一定可以拆成二元环,所以可以看做找匹配。两个点能匹配当且仅当他们 \(s\) 相等。 发现一个周围没有严格小于 ......
luogu P9753题解
题意描述 有一个字符串, 请你求出有多少个字串可以经过若干次, 使它变成空串 其中每次操作可以从字符串中删除两个相邻的相同字符,操作后剩余字符串会拼接在一起。 ## 思路1 可以枚举左端点, 再枚举右端点, 一边枚举一边判断是否合法 时间复杂度 $O(n^2)$ 空间复杂度 $O(n)$ ## 思路 ......
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 考虑一个强连通 ......
题解 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 这是一般图匹配问题的特殊情况,所以放 ......