题解p4069 2016 sdoi
ABC321题解
A 从低位到高位判断是否递增就行了。 B 直接暴力枚举。 C 深搜一下,答案最多 1023 个,然后要开 long long !!! D 从小到大枚举 a 的同时从大到小枚举 b,然后前缀和优化一下就行了。 E 考虑把这棵树分成两部分,分界线为从 1 到 n 的路径。 然后在路径上从下往上dp出长为 ......
星空 (Easy version & Hard Version) 题解
星空 (Easy version & Hard Version) 题解 不知道简单版有没有单独的做法,反正我不会 很明显如果 \(a\) 中有大于 \(x\) 的数直接无解,输出 \(0\)。 发现每个 \(a_i\) 都是 \(2\) 的整数次幂,这告诉我们每个 \(a_i\) 在二进制表示下只会 ......
洛谷P6767 [BalticOI 2020/2012 Day0] Roses 题解
题解 P6767 Roses 题目传送门 \(a,c\) 为每束花的朵数,\(b,d\) 为每束花需要的钱 首先简单了解一下题意,大概就是现在给你 \(n\) 朵花,每 \(a\) 朵花 \(b\) 元,每 \(c\) 朵花 \(d\) 元,求最少需要多少钱? 注意: 这里 \(n\) 的范围是 \ ......
CF877F 题解
CF877F 题解 更好的阅读体验 提供一个扫描线 + 根号分治做法。 首先,可以把题目的条件转化成求 $sum_r-sum_{l-1}=k$ 的区间数。 考虑扫描线,当区间的右端点从 $r-1$ 移动到 $r$ 时,新增的区间的左端点就是所有满足 $sum_{l-1}=sum_r-k,l\le r ......
题解 Gym 104077I【[ICPC2022 Xi'an R] Square Grid】
题解 Gym 104077I【[ICPC2022 Xi'an R] Square Grid】 problem 二维棋盘,边界是 \((0,0)\) 到 \((n,n)\)。 对于某个棋子,单次移动可以朝着上下左右四个方向之一移动一格。 对于 \(q\) 个独立的棋子,分别问时间 \(T\) 秒以后: ......
[COCI2016-2017#4] Osmosmjerka 题解
[COCI2016-2017#4] Osmosmjerka 题解 我们发现对于每个点,只有八个方向,也就是说,最终能得到的字符串只会有 \(8nm\) 个,那我们可以考虑把这些字符串的哈希值求出来,相同的哈希值代表选到相同字符串的一种可能,直接统计即可。 现在的问题就在于,怎么快速地求出这 \(8n ......
题解 CF1257G【Divisor Set】
problem 我们说一个集合 \(D\) 是一个好的集合,当不存在集合中的两个不同元素 \(a,b\) 使得 \(a\) 是 \(b\) 的约数。 给定一个超大整数的素数表示形式 \(N = \prod_{i=1}^n{p_i}\),要求从它的所有因子中选择尽可能多的元素组成一个好的集合。 问这个 ......
题解 ARC165F【Make Adjacent】
区间排序问题,主席树优化建图,最小字典序拓扑排序(priority_queue) problem 给定一个长度为 \(n*2\) 的序列,其中每种元素恰好出现了 2 次。 允许每次选择任意两个相邻的元素交换。 那么必定存在一个最小 \(k\):使得 \(k\) 次交换以后所有相同的元素都是相邻的。 ......
P6667 [清华集训2016] 如何优雅地求和 -Binomial Sum
题面 有一个多项式函数 \(f(x)\),最高次幂为 \(x^m\),定义变换 \(Q\): \[Q(f,n,x)=\sum_{k=0}^{n}f(k)\binom{n}{k}x^k(1-x)^{n-k} \]现在给定函数 \(f\) 和 \(n,x\),求 \(Q(f,n,x)\bmod99824 ......
题解 CF1873H Mad City
题意描述 马塞尔和瓦勒里乌(Valeriu)所在的疯狂城市由 \(n\) 栋建筑和 \(n\) 条双向道路组成。 马塞尔和瓦勒里乌(Valeriu)分别从 \(a\) 号和 \(b\) 号建筑开始。马塞尔想赶上瓦勒里乌(换句话说,与他在同一栋楼里或在同一条路上相遇)。 在每次移动过程中,他们都会选择 ......
CF1842F Tenzing and Tree 题解
Tenzing and Tree 感觉很典型的题,就是树的重心+绝对值等式 解法: 以每个点 \(i\) 为根分别 \(bfs\) ,得到一个距离数组 \(dis\) ,取前 \(k\) 个值的权值为和,更新 \(w[k]\) 的值, \(n\) 个点分别为根,更新 \(n\) 遍之后,得到 \(w ......
砝码称重 题解
砝码称重 题解 前言 这道题时限完全可以开到 1s,空间也开不到 1024kb 白想那么多优化( 不过这个复杂度可能是目前来看最合理(算出来保证能过)的。 题意简述 有一个长度为 \(n\) 的序列 \(a\),有两种操作: 把 \(l\) 到 \(r\) 的所有数改为 \(x\); 查询用 \(l ......
题解 ABC267 A~H
ABC267 solution https://atcoder.jp/contests/abc267/ Problem A. 题目描述 输入一个表示星期的英文字符串,输出:还有多少天到星期六? solution 依题意模拟。\(O(1)\)。 Problem B. 题目描述 Robin 有十个小球, ......
P5836 [USACO19DEC] Milk Visits S - 洛谷题解
题目链接 :[P5836] USACO19DEC] Milk Visits S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 这道题可以用并查集来解决。 题目中每个结点只有两个状态:H和G。那么我们可以推断出,只有当起点和终点间每个结点的状态相同但是起点(或者终点或起点到终点之间 ......
CF49E 题解
problem & blog。 提供一个逻辑顺畅的思路(然而做法相同的)。 手玩样例,Sample1 是 \(\texttt{ac}\to[\texttt{a}][\texttt{baba}]\) 与 \([\texttt{a}][\texttt{ba}]\)。很显然样例有分段性质,所以 DP,\( ......
9.20模拟赛T3题解【限时公开,阅后即焚】
考场做法。 复杂度是优美的\(\Theta(n^2 \log n)\)。 强烈谴责高复杂度碾标算行为 考虑一个观察:对于一个左上角 \((x, y)\) ,如果我们确定了它的边长一个区间 \([L,R]\),使得这个区间内 至少存在 \(k\) 行 \(k\) 列1,(可能还有一些多余的1),那么我 ......
[题解] CF1873H - Mad City
CF1873H - Mad City 知识点:基环树找环 题意 给定一张具有 \(n\) 个点 \(n\) 条边的无向图。现在有两个人,第一个人在 \(a\) 点,第二个人在 \(b\) 点,第一个人要追到第二个人。 两个人每一回合都同时进行操作,要么停留在当前位置,要么走邻接的下一个点。同时,第一 ......
题解 P8670 [蓝桥杯 2018 国 B] 矩阵求和
题目描述 \[\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)^2 \]具体思路 solution 1 显然可以每次枚举 \(\gcd(i,j)\) 的取值。 \[\sum_{k=1}^n k^2 \sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=k] ......
CF38H 题解
problem & blog。 远古场翻到的一个不错的题,提供一个好想很多的做法。 求出任意两点的路径在全部路径中是第几个。然后随便找两个人,钦定他们是 Au 吊车尾与 Cu Rank1。这样子就可以直接求出全部人可以是否可以拿 Au Ag Cu 了。 然后就是傻子 DP 了,往状态里塞 Au 与 ......
MUH and Cube Walls 题解
MUH and Cube Walls 前言 怎么题解区同质化这么严重,16 篇题解全是 差分 + KMP,就没有人写别的做法吗。 (好吧其实是我一开始没想到差分才有了这么多奇怪做法) 题目大意 给定两个序列 \(a,b\),求 \(b\) 在 \(a\) 中出现了多少次。 我们定义 \(b\) 在 ......
P1417 烹调方案 题解&贪心杂谈
## _Description_
一共有 $n$ 个食物,每个食物有3个属性,分别为 $a,b,c$,其中 $c$ 表示做这道菜的耗时。
一个食物的贡献为 $a-b\times t$,其中 $t$ 表示做完这道菜的总耗时,求在 $T$ 个单位时间内,最多能产生多少贡献 ......
容斥原理应用Acwing890借鉴题解
参考文献 简单的容斥原理介绍请看下图: C++ 代码 简单的容斥原理介绍请看下图: 本题思路: 将题目所给出的m个数可以看成是m位的二进制数,例如 当p[N]={2,3}时,此时会有01,10,11三种情况 而二进制的第零位表示的是p[0]上面的数字2,第1位表示p[1]上面的数字3 所以当i=1时 ......
题解 ARC141D【Non-divisible Set】
这个题不是网络流。 problem 我们说一个集合 \(D\) 是一个好的集合,当不存在集合中的两个不同元素 \(a,b\) 使得 \(a\) 是 \(b\) 的约数。 给定 \(N\) 个整数的一个集合 \(S\),值域均落在 \([1, 2*M]\) 内。 对 \(S\) 中的每个元素 \(A_ ......
Little Victor and Set 题解
Little Victor and Set 题目大意 在 \([l,r]\) 中选不超过 \(k\) 个相异的数使得异或和最小,输出方案。 思路分析 分类讨论: 当 \(k=1\) 时: 显然选 \(l\) 是最优的。 当 \(r-l+1\le 10\) 时: 直接 \(O(n2^n)\) 暴力枚举 ......
题解 P9019 [USACO23JAN] Tractor Paths P
显然,对于给定的 \(l,r\),最短路可以贪心求出,即每次走与当前区间相交且左端点最大的区间,这个可以用倍增加速。 定义 \(f_{i,j}\) 表示从区间 \(i\) 往右走 \(j\) 步后到达的区间,\(g_{i,j}\) 表示往左走的情况。 正反遍历一下即可求出 \(f_{i,1}\) 和 ......
To_Heart—题解——不算很少!
1.AGC061C link && submission 很神仙的一道题。先考虑所有的人都选择 \(a_i\) 时刻登记。那么对于一个人来说他变成 \(b_i\) 的时会增加贡献当且仅当 \([a_i,b_i]\) 之间有其他人被登记。 定义 \(C\) 数组, \(C_i\) 为 0 表示第 \( ......
To_Heart—题解——好多好多!
很多时候它们只是路过我的天空变化出许多场景让我哭了笑了不用再说。有好多多的题,多的 trick 你不在我脑子里。 ......
P3958 [NOIP2017 提高组] 奶酪 - 洛谷题解
题目链接 :[P3958] NOIP2017 提高组] 奶酪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 这道题可以用并查集求解,我参考了一些大佬的题解,判断底层和顶层是否连通的条件可以为 find(0) == find(n + 1) 其中0为底层,n+1为顶层。 #inclu ......
题解 P8905 [USACO22DEC] Strongest Friendship Group G
显然不同连通块互不影响,答案分开算。 对于当前连通块,假如我们希望所选的子图中最小的度数为 \(x\),那么只需要保留度数大于等于 \(x\) 的所有点,然后将这些点能连的边连上,再保留其中度数合法的,以此类推,最后剩下的点数就是子图最大的大小。 这些操作就相当于,对于当前图,如果度数最小的点不满足 ......