题解1545b cf
题解
题目大意 有 \(n\) 个杯子,第 \(i\) 个杯子里装有 \(W_i\) 升水,且有 \(n\) 对正整数 \(l_i,r_i\)。Yuri 和 Muri 两人在玩一个游戏:两人轮流进行操作,最先不能进行操作者输。 一次操作定义为:操作者选择一个杯子 \(i\),从中喝掉 \(x_i\) 升水 ......
CF662C
题面传送门 description 给定一个 \(n\times m(n\le 20,m\leq 10^5 )\) 的 01 矩阵,你可以把若干行的 01 反转,再把若干列的 01 反转。求若干操作后可能的最少的 1 的个数。 solution 显然操作相当于每行每列要么取反一次,要么不取反。 行数 ......
S16.23.12.2. 集合论 题解
原题连接 可以发现集合对称差就是异或运算。 每个点都记一个长度为值域的 bitset,每一位都表示根到他有没有奇数个这个数字。 那么 \(a_x\) 改为 \(v\) 的修改就变成了修改子树的所有点的 bitset,每次将子树中所有点的第 \(a_x\) 位取反,再将第 \(v\) 位取反。 查询就 ......
AT_abc321_f [ABC321F] #(subset sum = K) with Add and Erase 题解
AT_abc321_f [ABC321F] #(subset sum = K) with Add and Erase 题解 题目大意 现在有一个空箱子。给你两个数 \(Q, K\),然后给你 \(Q\) 行,每一行代表一个操作: \(+ x\),即向箱子里加一个权值为 \(x\) 的小球。 \(- ......
【题解】AtCoder-ABC321
AtCoder-ABC321A 321-like Checker 依题意判断。 提交记录:Submission - AtCoder AtCoder-ABC321B Cutoff 枚举 \(a_n\),依题意模拟即可。 提交记录:Submission - AtCoder AtCoder-ABC321C ......
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\) 秒以后: ......
CF986F 解题报告
显然要关于 \(k\) 离线。 对于固定的 \(k\),关于 \(k\) 的质因子的个数讨论: 如果 \(k\) 是形如 \(p^\alpha\) 的素数幂 只需判断 \(p|n\) 即可。 否则 我们可以跑类似同余最短路。 当 \(\min p_i\) 很大的时候,过不去。 但是,极限数据只能在形 ......
[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}\),要求从它的所有因子中选择尽可能多的元素组成一个好的集合。 问这个 ......
CF1267I
有一种很玄妙的做法,非常简洁。 我们考虑每两个为一组,令每对小的构成的集合为 \(S\), 另一个为 \(T\)。 令 \(S\) 里最大的下标为 \(x\),和其一对的另一数的下标为 \(y\)。 容易发现 \(y\) 一定在答案里。 proof:我们先钦定 \(T\) 为答案,再进行替换,发现一 ......
题解 ARC165F【Make Adjacent】
区间排序问题,主席树优化建图,最小字典序拓扑排序(priority_queue) problem 给定一个长度为 \(n*2\) 的序列,其中每种元素恰好出现了 2 次。 允许每次选择任意两个相邻的元素交换。 那么必定存在一个最小 \(k\):使得 \(k\) 次交换以后所有相同的元素都是相邻的。 ......
题解 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 ......
[CF1229E]Marek and Matching
This is a harder version of the problem. In this version, \(n \le 7\).Marek is working hard on creating strong test cases to his new algorithmic probl ......
CF1466E Apollo versus Pan
原题 翻译 xjk:降智题。orz \[\begin{align} \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}(x_i \ \operatorname{and}\ x_j)\times(x_j\ \operatorname{or}\ x_k) &= \sum ......
题解 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。那么我们可以推断出,只有当起点和终点间每个结点的状态相同但是起点(或者终点或起点到终点之间 ......
CF842A Kirill And The Game
如果考虑 \([x,y]\) 中什么位置能乘到 \([l,r]\) 就比较麻烦,简单的做法是考虑 \(l\) 和 \(r\) 对应到 \([x,y]\) 中的位置。左边界至少是 \(\frac{l-1}{k}+1\),右边界至多是 \(\frac{r}{k}\),判断一下与 \([x,y]\) 是否 ......
CF1467B Hills And Valleys
修改一座山可能改变其两侧山的类型。贪心地考虑,要么是修改成其左侧山的高度要么是修改成其右侧山的高度,这样能够在使得当前山不成为山峰和山谷的同时让两侧的山尽可能不成为山峰和山谷。如果不在左右两座山高度之间,那一定是山峰或者山谷,修改后肯定不劣。 修改第一座山或最后一座山也是无意义的,完全可以修改第二座 ......
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 与 ......