28 C. The Very Beautiful Blanket 随机化构造

陈小白     2023.03.28     算法相关     抢沙发     230人打酱油
题目链接:https://codeforc.es/contest/1802/problem/C 大意是构造一个n*m的矩阵,使得2*2的子矩阵与它相邻的对角2*2的子矩阵异或和相等,求存在多少不同的数,构造出来。 很显然我们需要满足任意子矩阵,做法就是随机化这个矩阵,然后用一个...

27 D. Accommodation

陈小白     2023.03.27     算法相关     抢沙发     220人打酱油
题目链接:https://codeforces.com/contest/1804/problem/D 差点做出来的D题了,两千分的难题! 大意是存在n层楼,每个楼有m个窗户,存在m/4个两居室和m/2个单居室,双居室一个灯亮就视为这个居室亮灯了 询问每层楼最少亮灯的居室和,每层...

27 C. Candy Store

陈小白     2023.03.27     算法相关     抢沙发     215人打酱油
题目链接:https://codeforces.com/contest/1798/problem/C 数论方面的题,大意是给出n个商品的数量和价格,求存在多少段l-r之间连续包装的价格组合? 需要明白的一点0和其他数的公约数等于其他数。 很明显我们需要求出任意连续ai*b...

27 舞台矩形,线段树维护平面矩形

陈小白     2023.03.27     算法相关     抢沙发     203人打酱油
题目链接:https://ac.nowcoder.com/acm/contest/53284/F 大意是给出n个人的左边范围,求对于任意两个人的左边,输出能够覆盖他们之间所有人的矩形最小面积 解决方法: 大小的线段树维护一下当前x所指到的最大y和最小y,这样矩阵的最小面积...

27 等腰三角形数量问题

陈小白     2023.03.27     算法相关     抢沙发     226人打酱油
题目链接:https://ac.nowcoder.com/acm/contest/52441/F 小白月赛的hard难度,数据量是3000个点。 在这里有些地方比赛的时候想到了,但是没有想到能够很好具体实现的方法,尤其是在共线那里。 easy不用说了,比赛的时候直接暴力过...

27 D - Three Days Ago

陈小白     2023.03.27     算法相关     抢沙发     204人打酱油
https://atcoder.jp/contests/abc295/tasks/abc295_d 好题,本来以为需要从区间问题上考虑,奈何算法世界无奇不有。 大意是求一个0-9的子串中区间内的所有元素是成双成对出现的,串的长度为5e5. 很明显我们可以前缀和维护然后去暴...

24 洛谷3个简单黄dp总结

陈小白     2023.03.24     算法相关     抢沙发     269人打酱油
感觉脑子确实钝了。。。 dp一直是知识框架的弱项。 https://www.luogu.com.cn/problem/P1806 跑步,大意是跑n圈,要求每次比上一次跑的多,问多少种跑法。 很明显这个问题可以当作背包计数来考虑。每次直接用j-i来转移就可以。 ...

21 C. Sequence Master

陈小白     2023.03.21     算法相关     抢沙发     199人打酱油
题目链接:https://codeforces.com/contest/1806/problem/C 一个蓝名的入门题。 大意是给出一个2*N的数组,你需要构造一个数组(不需要输出),使得该数组符合任意n长度的子区间的乘积等于其他未被选择的元素的和。求是否存在一个这样的子区间,...

08 线性基

陈小白     2023.03.08     算法相关     抢沙发     235人打酱油
今天学习了线性基 线性基就是用了一个贪心的手法,使得维护这一位一直是1。 线性基中不含重复的异或。 它的构造方法是,每次取某个数字的最高位值。如果存在过直接异或,否则令线性基等于这个值。 线性基的构造代码还是挺简洁的 voidinit(lolbox){ for(in...

08 洛谷绿蓝题选做总结(数论、线代)

陈小白     2023.03.08     算法相关     抢沙发     363人打酱油
TalentShowG蓝 题目链接:https://www.luogu.com.cn/problem/P4377 类型:二分法与01分数规划 大意是根据n头奶牛的体重和才艺值选择出战的一组奶牛,才艺和体重比值最大的获胜,有体重下限限制(需要凑够这些重量)。 solu...

06 矩阵快速幂加速递推

陈小白     2023.03.06     算法相关     抢沙发     217人打酱油
题目链接:http://poj.org/problem?id=3233 大意就是求一个s=a+a*a+a*a+a...... 指数很大。 根据一个递推式,我们最终可以确定的是答案s可以转换为只跟f(n-1)*a即a^k*[f(0)e]有关。快速求出a^k,这里的a要转换为...

05 C - Convex Quadrilateral

陈小白     2023.03.05     算法相关     抢沙发     227人打酱油
题目链接:https://atcoder.jp/contests/abc266/tasks/abc266_c 大意是顺时针给出一个四边形,求是否存在凸包 计算几何的凸包问题,当不存在凸包时,也就是所有内角都小于180度。 对于顺时针给出的四边形,我们可以通过叉积判断一下是否存在...

04 莫比乌斯反演+分块+前缀预处理

陈小白     2023.03.04     算法相关     抢沙发     203人打酱油
题目链接:https://www.acwing.com/problem/content/217/ 很棒的题解:https://www.acwing.com/solution/content/63012/ 大意是给出abd,求存在多少x<=a,y<=b使得gcd(a,...

03 习题杂选

陈小白     2023.03.03     算法相关     抢沙发     222人打酱油
E.EasyAssembly:https://codeforces.ml/contest/1773/problem/E 大意是给出n个塔,和塔顶到塔底的数字。 给出两种操作: 1.将塔顶上的元素单独移动到一个新的塔+1 2.将整个塔的元素移动到另一塔上-1 求最小操作数量使得成为一个...