08 线性基

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

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

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

06 矩阵快速幂加速递推

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

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

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

28 AtCoder Beginner Contest 291 (D、E)

陈小白     2023.02.28     算法相关     抢沙发     32人打酱油
比赛链接:https://atcoder.jp/contests/abc291/tasks D题:大意是给出n张卡片的正面和反面的数值,卡片正反面为不同数字,求翻某些卡片的一面使得向正的一面的数值全都不一样的集合的数量。 解决方法:考虑使用01动态规划解决。f[i][0/1],...

24 拓扑排序(旅行计划+神经网络)

陈小白     2023.02.24     算法相关     抢沙发     36人打酱油
旅行计划 题意 大意是给出n个城市以及他们之间的道路,求从1点到其他各点(以各点为终点)所经过的最多城市的数量 思路 其实很明显可以想到dp的部分。但是如何dp是一个问题。这个dp的状态转移其实并不难,只需要从源点转移过来就ok。但是我们需要想到应该从哪个点开始去d...

19 二分的几种写法

陈小白     2023.02.19     算法相关     抢沙发     23人打酱油
存一下https://blog.csdn.net/Philkk/article/details/120570763...

18 C - Tea Tasting 区间查询修改问题(三种方法)

陈小白     2023.02.18     算法相关     抢沙发     32人打酱油
放在前面  这次比赛的表现十分拉胯,高光点只有13分钟做出了前两题,然后直接罚坐。  经常遇到这类问题但是总是感觉少点东西才能做出来,总会有些地方不知道应该怎么处理。其实总结来看,无非就是这么几种情况,有些情况之前的博客已经说过了。例如二分和尺取,但是尺...

17 STL —— 位运算函数之 __builtin_

陈小白     2023.02.17     算法相关     抢沙发     25人打酱油
转载一下,感觉很有用。。。。https://blog.csdn.net/Scar_Halo/article/details/89552658...

17 山东管理学院寒假集训round3

陈小白     2023.01.17     算法相关     抢沙发     63人打酱油
比赛链接:https://vjudge.csgrandeur.cn/contest/538238#overview 这次比赛做出了六道题。需要手动计算的题有点多,有点恶心,计算题就做了一个G题,主要是规律已经发现了做不出来有点可惜,BC目测应该也需要手动算一下。 BC感觉自己不...

16 cmap总结

陈小白     2023.01.16     算法相关     抢沙发     44人打酱油
第一天是计算几何。 先讲了魔改bfs和魔改二分。魔改二分基本上听懂了实现的思路,应该也能实现。魔改bfs还是挺难的,尤其是状态压缩那里很难想明白,还需要再学习学习。 重点:计算几何。其实计算几何并不难,基本上都是高中学过的一些知识。比较吃板子和高中数学功底,但不是属于不可做的题...

13 AtCoder Beginner Contest 284

陈小白     2023.01.13     算法相关     抢沙发     70人打酱油
比赛链接:https://atcoder.jp/contests/abc284 做出了四个题。第五个题很简单可以直接暴力,但是怂了。 E题:大意是给出n个点,m条边,度最多为10。求从1开始的简单图。超过1e6输出1e6。 注意到度最多为10和1e6就可以直接暴力,简简单...

11 山东管理学院寒假集训round2

陈小白     2023.01.11     算法相关     抢沙发     37人打酱油
比赛链接:https://vjudge.csgrandeur.cn/contest/536832#overview 总结:可做的题还是有的。DEHJ没有去尝试。没什么太多思路。 这些应该是可补的题,外加一个J题,很好的思维题不会做但可以学 B题明显是个状压dp。但...

10 ACM生涯时间线

陈小白     2023.01.10     算法相关     抢沙发     79人打酱油
高中时期 高一C语言教材(啊哈C语言,C语言从入门到精通) 高二数据结构教材(啊哈算法,数据结构严蔚敏版) 大学时期 大一上 ACM校赛一等奖2021.12 参与ACM寒假公开课2022.1讲师(glt老师) ACM集训队成立并担任队长20...

10 平面锐角三角形的数量

陈小白     2023.01.10     算法相关     抢沙发     40人打酱油
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5784 参考博客:https://blog.csdn.net/qq_45458915/article/details/104218091 这次分析的代码是利用了叉积进行了一个排序。目...

10 Namomo Winter Camp 2023 Day 2

陈小白     2023.01.10     算法相关     抢沙发     56人打酱油
比赛链接:https://vjudge.csgrandeur.cn/contest/537670#overview 多少因为服务器卡没有好好做。 不过,只AC了三个题真的非常离谱! 题确实简单。感觉自己没脑子。。。。或者说想的有点多。 B题:大意是用a表示1,z表示...

07 Hello 2023

陈小白     2023.01.07     算法相关     抢沙发     42人打酱油
比赛链接:https://codeforces.ml/contest/1779 这次比赛还行吧,蓝名表现分上青了。D题有点虐,可以用dp、单调栈、rmq、树状数组、并查集做。我一个也没想到,现在弄明白了单调栈做法和rmq做法。感觉E题说不定能出,随便看两眼D题没思路,直接开E了 ...

02 山东管理学院寒假集训round1

陈小白     2023.01.02     算法相关     抢沙发     114人打酱油
比赛链接:https://vjudge.csgrandeur.cn/contest/536129#problem 难度评测: codeforcesdiv3前四题。难度最高D题1400分构造题。洛谷两红两橙。 有两个构造题。难度还可以,需要认真分析一下。不能想的太复杂,这两...

28 蓝桥杯 11道黄橙dp题总结

陈小白     2022.12.28     算法相关     抢沙发     50人打酱油
题目链接:https://www.luogu.com.cn/problem/list?tag=363,361%7C3&page=1&orderBy=difficulty&order=asc 先说3个橙题。现在感觉都是比较简单的dp题,都是通过递推的形式转换过来...

26 状压dp 解决 哈密顿回路问题

陈小白     2022.12.26     算法相关     抢沙发     48人打酱油
步骤: 确定采用状压dp范围20左右。 状态转移f[i][j]表示对于第i个节点,它走到的第j个状态。对于任意状态,遍历任意节点,找到此节点并确定另一节点与其重合。 路径确定i>>j&1路径重合i-(1<<j)>>k&1 ...

23 砝码称重 线性dp+备份表/滚动数组

陈小白     2022.12.23     算法相关     抢沙发     43人打酱油
题目链接:https://www.luogu.com.cn/problem/P8742 大意是给出砝码,求称出的重量的数量。 经过观察,发现新给出的第i个砝码,只是在第i-1个砝码的基础上产生印象。因此只需要两张映射表做一个滚动数组即可 code: constintn...

18 夜深人静写博客——研究筛法找到半素数序列

陈小白     2022.12.18     算法相关     抢沙发     77人打酱油
想法来源于抖音刷到的一个小学规律题33,34,35,(),39中间填什么数? 通过规律我们可以看到每个元素都可以由两个素数相乘得到,中间填"38"2*19=38 不难发现这样的半素数可以组成数列4,6,9,10.... 如果找到第n项?通过这几天(期末考前)的研究...

06 删数问题plus版

陈小白     2022.12.06     算法相关     1条评论     59人打酱油
题目链接:https://codeforces.ml/problemset/problem/1765/N 删数问题,存在0元素,且首位不能为0,求删除k个数后的最小值为多少。 思路:删数问题一般跑不了贪心。因为我们总应该要贪婪的选择删除前面的数,将靠前的大数消灭掉。 我们需要解...

01 第47届ICPC济南赛站/第一次ACM区域赛总结

陈小白     2022.12.01     算法相关     抢沙发     79人打酱油
时间:11月27日参加了亚洲区域赛济南站。 比起省赛的爆零,这次区域赛的情况要好很多,这得益于在cf刷的250道题。解决了K和M,但是在一个不可能做出来的题上费了3个多小时 在看到签到思维题的那一刻,想法几乎是一瞬间。但是很不幸的是被数据卡了memset和cin,签到题签的并...

01 Codeforces Global Round 20

陈小白     2022.12.01     算法相关     抢沙发     57人打酱油
比赛链接:https://codeforces.ml/contest/1672 讲真的,做的挺拉的。A题没读懂,看了题解。BC每个题都WA了好几次。D题直接看答案了 A题:大意是现有数组a,errorgorn和maomao90分别先后轮流将数组a中的某个元素拆分成两个不小于1的...

26 G. SlavicG's Favorite Problem

陈小白     2022.11.26     算法相关     抢沙发     71人打酱油
题目链接:https://codeforces.ml/contest/1760/problem/G div4最接近ak的一场,这个题没有读明白。其实上一个题也应该要整理的,做法还是有些复杂。这个题我的写法和别人写的相比也复杂一些。尤其是在树的遍历操作上,开sign是容易出错的== ...

21 Codeforces Round #834 (Div. 3) A-E

陈小白     2022.11.21     算法相关     抢沙发     119人打酱油
比赛链接:https://codeforces.ml/contest/1759 A题:大意是给出一个字符串,每个字符串是否能够被Yes识别到。设字符串长度为n,则主串为n个Yes,求是否存在输入的字符串。 读题还是挺麻烦的,心态有点崩。做起来很简单,需要注意如果不存在s.fin...

16 高精度快速幂

陈小白     2022.11.16     算法相关     抢沙发     67人打酱油
链接:https://www.luogu.com.cn/problem/P1045 算是比较裸的板子题,需要注意的是需要考虑后50即可。这个点当时没有好好像,开大了容易g 位数不用多说了,可以直接log算出来 code: #include<iostream>...

14 Codeforces Round #833 (Div. 2) A-C

陈小白     2022.11.14     算法相关     抢沙发     117人打酱油
比赛链接:https://codeforces.ml/contest/1748 A题:水题,大意是给出n,存在n个方块,边长为n/i,向下上取整。 根据样例直接找规律。 B题:给出0-9的字符串,找出有多少组l-r中,每个数字出现的次数不超过l-r中所有不同类别数字的组数...

09 P1026 [NOIP2001 提高组] 统计单词个数

陈小白     2022.11.09     算法相关     抢沙发     78人打酱油
题目链接:https://www.luogu.com.cn/problem/P1026 感觉可以贪心,但是贪心只过了两个点╮(╯▽╰)╭ 我的思路是这样的:我们从后往前去记录出现单词,数据量小完全可以暴力,然后将单词标记一下,首字母额外标记一下。 最后我们统计出有多少个单词,下面开始...

04 有依赖的背包问题——有线电视网

陈小白     2022.11.04     算法相关     抢沙发     77人打酱油
题目链接:https://www.luogu.com.cn/problem/P1273 树形dp。但这个本质上是个背包问题,一时间没有想起来有依赖的背包问题。 读题的时候没有发现客户端一定是接在转发器上的,想成了一颗比较自由的树。 做的时候要当作一个有依赖的背包问题来做,分好组...

03 加分二叉树

陈小白     2022.11.03     算法相关     抢沙发     82人打酱油
题目链接:https://www.luogu.com.cn/problem/P1040 大意是给出一个树的中序遍历,这个树每个子树都有一个加分,得分=左子树分数*右子树分数+根的分数。 在每个节点都有一个分数,第i个节点分数为di。其实就是给出的中序。求最大加分并输出先序遍历 ...

01 Codeforces Round #831 (Div. 1 + Div. 2)

陈小白     2022.11.01     算法相关     抢沙发     153人打酱油
比赛链接:https://codeforces.ml/contest/1740 A题:水题,两个素数相加一定是偶数。 B题:大意是给出一堆长方形(包含正方形),纵向放置不能堆叠,求最短周长,可以任意旋转。 思路:最长的一个边可以包含其他长方形最长的边,然后所有的长方形的最...

28 温温的那些年(easy)

陈小白     2022.10.28     算法相关     抢沙发     102人打酱油
题目链接:https://ac.nowcoder.com/acm/contest/38105/J 大意是给出一堆数,求是否存在一个图,它的顶点的连接数量与序列相对应。 困难版本不考虑,,, 思路:优先队列从大数量边的点开始考虑,一个个进行满足,存在无法满足的no,直到最后...

28 树形dp问题

陈小白     2022.10.28     算法相关     抢沙发     84人打酱油
感觉codeforces也是来到了能做D题的水平。 在解决完子区间的查询问题之后,感觉C题能做的就多了。 codeforces的D题多是一些C题的加强版,这里往往涉及到某些规律,例如二进制位。 同样D题往往也容易出现一些简单的树和图的问题,尽管我目前的水平仍然做不出来,但是可以...

25 关于区间内的子区间查询问题的探究

陈小白     2022.10.25     算法相关     抢沙发     131人打酱油
这是一类什么问题,在一个区间内要想求得某个区间,你需要什么样的复杂度? n*(n-1)/2?你需要暴力出所有的情况。 能否找到一个方法使得我们所得到的满足子区间是最优的且一定使我们想要的? 这里存在两种方法:尺取法(两个指针)和二分。 那么先来说说尺取和二分,尺取是固定一边去寻找另一...

19 D.Problem with Random Tests 知识盲区(bitset,lambda表达式)

陈小白     2022.10.19     算法相关     抢沙发     166人打酱油
题目链接:https://codeforces.ml/contest/1743/problem/D bitse类似数组,用于存储二进制位,可以直接进行位运算 lambda表达式,之前看过,但是没有系统的总结。 https://blog.csdn.net/qq_37085158/...

18 构造问题???(持续更新)

陈小白     2022.10.18     算法相关     抢沙发     106人打酱油
第一题:https://codeforces.ml/contest/1720/problem/A 构造前置题,唯一构造:大意是给出abcd,a/bc/d的分数。他可以让abcd乘以任意一个整数,使得两个分数相同,求最少操作次数。 你需要想办法使得两个数相同,找到这个数,这个是构...

18 Codeforces Round #828 (Div. 3)A-D

陈小白     2022.10.18     算法相关     1条评论     206人打酱油
比赛链接:https://codeforces.ml/contest/1744 第一次排名挺高,到了2500+,也是如愿的在定级赛内要上绿了。这次比赛E题的构造题听恶心的,其他发挥的还可以,C题稍微有些失误但不多,还是有些需要注意的点。构造题单独总结一下。 A题:水题,主要是哈...

17 第1届ICPC青少年程序设计竞赛D题

陈小白     2022.10.17     算法相关     抢沙发     101人打酱油
思路:从两个方面进行考虑。k内的点和k外的点。对于k内的点,每一个i点都有i-1个点可以选择,情况为fi-1的一个累乘情况数量。对于剩下的点,可以选择任意情况进入。 code: #include<bits/stdc++.h> usingnamespacestd; #...

15 1.9整理

陈小白     2022.10.15     算法相关     抢沙发     125人打酱油
campdiv2第二天https://vjudge.csgrandeur.cn/contest/537670#overviewok 计算几何锐角三角形数量https://blog.csdn.net/qq_45458915/article/details/104218091ok ...

15 Codeforces Round #827 (Div. 4) A-G

陈小白     2022.10.15     算法相关     抢沙发     201人打酱油
比赛链接:https://codeforces.ml/contest/1742 A题:水题 B题:水题 C题:思维+审题。大意是给出一个8*8的矩阵,每次操作可以画一行红色或者是一列蓝色,每次绘制可以覆盖之前的颜色。求出最后画的是哪一笔?题目保证给出一个正确解。 这...

12 Codeforces Round #825 (Div. 2) ABC

陈小白     2022.10.12     算法相关     抢沙发     164人打酱油
比赛链接:https://codeforces.ml/contest/1736/ A题:水题 B题:gcd构造题。大意是给出一个长度为n的数组,求是否存在一个长度为n+1的数组b,使得ai=gcd(bi,bi+1)。 这个题WA了好几发。最开始的几个猜想思路都错了。 思路:对b...

08 D. Meta-set

陈小白     2022.10.08     算法相关     抢沙发     132人打酱油
题目链接:https://codeforces.ml/contest/1735/problem/D 大意是,给出n个卡片,每个卡片有k个元素,每个元素有012三种取值。 存在三个卡片,卡片上的对应元素要么全部相等,要么全部不相等。求存在多少个这样的集合。 %3的规律,全部相等值...

07 ShanDong Multi-University Training #6 (AEG)

陈小白     2022.10.07     算法相关     抢沙发     101人打酱油
比赛链接:https://vjudge.csgrandeur.cn/contest/518332#overview A题:大意是给出一个字符串,字符串遇到aeiou就会翻转,并将元音放到最开头,求出有多少种可能可以构造这个字符串。 两种最容易发现的情况,不存在元音为1,存在一个...

05 Educational Codeforces Round 136 (Rated for Div. 2)

陈小白     2022.10.05     算法相关     抢沙发     113人打酱油
比赛链接:https://codeforces.ml/contest/1739 这样有点难,B使劲WA,C题直接解不出来,思维上要求很高。C题更是赛出了组合数学 A题:水题,棋盘固定走法,求哪个格子没有可走的步子。 code: #include<bits/stdc...

30 杭电A + B Again

陈小白     2022.09.30     算法相关     抢沙发     101人打酱油
链接:https://acm.hdu.edu.cn/showproblem.php?pid=2057 大意是给出十六进制的数字字符串,完成两个相加。有正负号。 感觉很可怕是不是???确实很可怕,自己想用字符串处理,写了八十多行硬是啃不下来。看看大佬代码 code: #inc...

27 平面分割(直线/折线)

陈小白     2022.09.27     算法相关     抢沙发     94人打酱油
转载:https://blog.csdn.net/summerxiachen/article/details/63252964...

26 第46届昆明站签到题

陈小白     2022.09.26     算法相关     抢沙发     98人打酱油
比赛链接:https://ac.nowcoder.com/acm/contest/32708 K题:大意是小g将要进行n场比赛,他的获胜概率是x=a/b,对于每一场比赛,如果期望值<=x,他将获胜,否则失败。 ans一定是n*x或者n*x+1。 我们容易发现,第一场一定会...

22 CodeCraft-22 and Codeforces Round #795 (Div. 2)

陈小白     2022.09.22     算法相关     抢沙发     92人打酱油
比赛链接:https://codeforces.ml/contest/1691 夜深人静写博客~ c题做不出来555~ A题:大意是给出一个n的数组,求删除一些数后,使得每两个数相加的和为偶数。求最少删除量。 剩下的数都需要是一致的奇偶性,所以删除奇数数量和偶数数量最小的那一个。 code:...

18 C. Schedule Management

陈小白     2022.09.18     算法相关     抢沙发     97人打酱油
题目链接:https://codeforc.es/contest/1701/problem/C 一个青名题。二分类型 大意是,给出n个人编号1-n,然后给出m个任务,每个任务a[i]对应一个值,这个值在1-n内,含义是a[i]这个人做这个任务时擅长的。 如果一个人去做他擅长的任...

17 Codeforces Round #820 (Div. 3)

陈小白     2022.09.17     算法相关     抢沙发     257人打酱油
比赛链接:https://codeforc.es/contest/1729 本场比赛赛后补题,感觉比较轻松的做出前四题,第五题看不懂,是一个交互题(做的还是太少了) A题:大意就是有两个电梯,第一个电梯在a楼,如果你使用第一个电梯,它会直接来1楼接你。第二个电梯在b楼,如果你使...

13 蓝桥杯积木画

陈小白     2022.09.13     算法相关     抢沙发     99人打酱油
题目链接:https://www.lanqiao.cn/problems/2110/learning/ 动态规划一直是我的弱项,这个题其实是一个很简单的动态规划的题非板子题。 这个题的精髓在于递推上面。 下面来仔细分析一下。 首先当n=1,2,3时s=1,2,5这是...

13 C. Color the Picture

陈小白     2022.09.13     算法相关     抢沙发     100人打酱油
题目链接:https://codeforc.es/contest/1711/problem/C 大意是给一个n×m的矩形,有k种颜料,每种颜料有ai个,一个颜料可以涂一格方格,问是否能构建一幅美丽的画,一幅美丽的画被定义为一个方格周围至少有3个格子和他颜色相同,同时,定义第1行和第n...

13 C. Digital Logarithm

陈小白     2022.09.13     算法相关     抢沙发     98人打酱油
题目链接:https://codeforc.es/contest/1728/problem/C 单独拿出来做一个博客,感觉我平时很少遇到的题。 大意就是,给出两个数组a和b,你可以对任意元素进行一个log10(x)的操作,也就是说,你可以将这个数改变为它的位数。 最后求出最少通...
比赛地址:https://codeforc.es/contest/1726 A题:大意是给出一个数组a,然后可以选择一个l和r,可以使得l和r做任意次转换al=al+1对于l-r之间的所有元素,其中ar=al。求出an-a1的最大值。 上来第一题感觉就不简单,wa了好几次。这个...

02 Codeforces Round #817 (Div. 4)

陈小白     2022.09.02     算法相关     抢沙发     133人打酱油
比赛链接:https://codeforc.es/contest/1722 在学校里,一直没时间参赛。 在D题上出现了比较大的问题。把题拆开来考虑结果导致有些麻烦。 前三题中规中矩吧,基本一次过,题并不是很难 A题:大意是有个人叫Timur,对于他名字的任意排列都是对的。...

31 01背包的数量问题

陈小白     2022.08.31     算法相关     抢沙发     102人打酱油
题目链接:http://noi.openjudge.cn/ch0206/2985/ 描述 有n个正整数,找出其中和为t(t也是正整数)的可能的组合方式。如: n=5,5个数分别为1,2,3,4,5,t=5; 那么可能的组合有5=1+4和5=2+3和5=5三种组合方式...

30 Educational Codeforces Round 134 (Rated for Div. 2)

陈小白     2022.08.30     算法相关     抢沙发     110人打酱油
比赛链接:https://codeforc.es/contest/1721 没参加比赛,之后补的题,有点难==。居然是教育周的题。做出来了两个题,第三个题有点没读明白。 A题:大意是给出四个字母,你每次可以操纵不超过两个相同颜色的字母,使得变成一个字母,求最少操作数。 直接分情...

22 codeforces cf-tool 脚本交题方式

陈小白     2022.08.22     算法相关     抢沙发     110人打酱油
https://github.com/xalanq/cf-tool/blob/master/README_zh_CN.md#%E5%AE%89%E8%A3%85 https://www.cnblogs.com/streamazure/p/12578977.html ...

21 Codeforces Round #816 (Div. 2)

陈小白     2022.08.21     算法相关     抢沙发     114人打酱油
比赛链接:https://codeforc.es/contest/1715 总体难度除了AB题之外,其他的题几乎不可做。但是B题出现的问题太大了,WA了五次。最开始的思路没有直接去实现,因为感觉实现不了,最后发现自己写的n+k的复杂度根本过不去。回过头来又考虑的n+计算的思路。 ...

20 Codeforces Round #814 / 815 (Div. 2) C题

陈小白     2022.08.20     算法相关     抢沙发     98人打酱油
比赛链接:https://codeforc.es/contest/1719 https://codeforc.es/contest/1720 1.大意是,给出一个1-n的排列,ai表示运动员的实力,每次前两名运动员进行比较,实力强的保留,实力弱的排到最后。 每次给出一个询问i和...

15 Codeforces Round #813 (Div. 2)

陈小白     2022.08.15     算法相关     抢沙发     112人打酱油
比赛链接:https://codeforc.es/contest/1712 这次比赛做了ABC,A题有些失误,大概十二分钟才AC,中途WA了一次。 B题做的很快6分钟一次过 C题WA了三次,改完一个bug后,手贱多加了一条语句,导致后面WA了两次。 A题:大意是给出...

12 多重背包的二进制优化

陈小白     2022.08.12     算法相关     抢沙发     99人打酱油
题目链接:https://www.acwing.com/problem/content/5/ 最近没有比赛可打,好好看看基础。 多重背包的朴素写法很简单,基本上都能写,复杂度nmk级别的,在数据量几千的情况下就处理不了了。 因此我们考虑用空间换时间,对物品进行二进制优化,...

11 最长公共上升子序列 加强理解版

陈小白     2022.08.11     算法相关     抢沙发     112人打酱油
题目链接:https://www.acwing.com/problem/content/description/274/ 两个序列a,b求最长公共上升子序列 我们定义f[i][j]为a序列的前i个和b序列的前j个元素的最长公共上升子序列 那么当前的f[i][j]可以继承f[i-...

11 AcWing 187. 导弹防御系统(LIS,贪心,dfs,迭代加深)

陈小白     2022.08.11     算法相关     抢沙发     134人打酱油
题目链接:https://www.acwing.com/problem/content/description/189/ 为了对抗附近恶意国家的威胁,R国更新了他们的导弹防御系统。 一套防御系统的导弹拦截高度要么一直严格单调上升要么一直严格单调下降。 例如,一套系统先后拦...

09 oi普及组 防御法阵(背包预处理+区间dp)

陈小白     2022.08.09     算法相关     抢沙发     117人打酱油
题目链接:https://ac.nowcoder.com/acm/contest/21865/D 大意是给出n个城墙,每个城墙有一定数量的法阵,破坏他们可以获得经验值,同时消耗时间。每个城墙有一个固定的最大停留时间。且最多可以破坏m个城墙。当破坏掉一个城墙后,它邻近的城墙的经验值将增...

08 Codeforces Round #812 (Div. 2)

陈小白     2022.08.08     算法相关     抢沙发     137人打酱油
比赛链接:https://codeforc.es/contest/1713 比赛的时候做出了AB,C题在比赛结束后大概十二分钟的时间解出来了。勉强算做出三道题了吧(嘎嘎掉分)。 其中B题耗费了一个多小时的时间,主要原因是在接近四十分钟的时间里读错了题,带着错误的题意去做的题。导致留给...

06 Educational Codeforces Round 133 (Rated for Div. 2)

陈小白     2022.08.06     算法相关     抢沙发     147人打酱油
比赛链接:https://codeforc.es/contest/1716 A了两道题A和B,速度还可以,但是CD态度太大一个也没做出来。 A题:给出一个数n,从0点开始到n点,每次只能走2步或3步,也可以回退。求最少多少次可以走到n点。 很简单,我们优先考虑3,如果是3的倍数可以直接/3过...

03 Codeforces Round #811 (Div. 3)

陈小白     2022.08.03     算法相关     1条评论     202人打酱油
比赛链接:https://codeforc.es/contest/1714 这次A了A题B题C题和E题,开题顺序是CBADE,D题没有什么思路就直接跳了。 div3倒着开题名次提升了不少。这次除了A题有些失误意外其他的都还好。 A题:水题,大意是给出小明睡觉的时间,小时和分钟。...

03 CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)

陈小白     2022.08.03     算法相关     抢沙发     155人打酱油
比赛链接:https://codeforc.es/contest/1704 div2第一次A了三个题,加了五十多分,我离小蓝又近了一步~ A题:大意是给出一段01串,每次我们可以使得前两个数字中的第二个数字替换成前两个数的一个,然后删除第一个数字。 给出另一个01串,询问是否能...

02 ShanDong Multi-University Training #4

陈小白     2022.08.02     算法相关     抢沙发     136人打酱油
比赛链接:https://vjudge.csgrandeur.cn/contest/506361#overview A题:简单思维题 B题:水题 C题:大意是给出一个大数,q次操作,每次操作可以往后面+一个数或者-去一个末尾的数(整除10),每次操作输出这个大数mod1e...

27 Codeforces Round #810 (Div. 2)

陈小白     2022.07.27     算法相关     抢沙发     119人打酱油
比赛链接:https://codeforc.es/contest/1711 感觉题比较难,幸亏没参赛,不然掉老多分了。感觉一个也做不出来,补题只打算补A和B了 A题:大意是给出一个n,制作一个p1-pn长度的序列,内容为1-n,对于每一个pi,如果pi%i==0则为一个权重,最...

26 P1258 小车问题 (二分逼近)

陈小白     2022.07.26     算法相关     抢沙发     157人打酱油
题目链接:https://www.luogu.com.cn/problem/P1258 大意是给出两个城市的距离,给出人行走速度和车辆行驶速度,有两个人需要同时从一个城市到达另一个城市。车上除了司机之外只能做一个人,问最快两人多长时间能够同时达到目的地。 这个题可以用公式法推导...

26 cf C. Doremy's IQ

陈小白     2022.07.26     算法相关     抢沙发     140人打酱油
题目链接:https://codeforc.es/contest/1708/problem/C 一道比较标准的蓝题难度,用到了二分 大意是:给出n个任务的难度,智商为q。如果任务难度>q,那么q会减少1,如果不做这个任务,智商不变,求最多能做出的任务的状态。 也就是做这个...

22 Educational Codeforces Round 132 (Rated for Div. 2)

陈小白     2022.07.22     算法相关     抢沙发     130人打酱油
比赛链接:https://codeforc.es/contest/1709 A了两个A和B,C题比D题难,很无语。C题是个规律题,但是我没有找到。很多人都卡在了C题上。 A题:大意是有是三个门,每个门里面可能有一把其他们的钥匙,也可能没有。你最开始拥有一把钥匙,试着开启所有门。...

20 Codeforces Round #807 (Div. 2)

陈小白     2022.07.20     算法相关     抢沙发     125人打酱油
比赛链接:https://codeforc.es/contest/1705 这个周赛没有参加。后来A了A和B。C题有思路,但是不知道怎么入手。 A题:大意是给出n个人的身高,要求排成两排,后排比前排要高出x。 运用贪心的思想,易得,在排序后的前后半边,高的对高的,矮的对矮的。 ...

19 Codeforces Round #809 (Div. 2)

陈小白     2022.07.19     算法相关     抢沙发     121人打酱油
比赛链接:https://codeforc.es/contest/1706 这次只A了A题。比赛结束后,B题通过面向样例编程看出了一些猫腻,但是是真的不理解题意。也不知道是为什么这么做,更不知道怎么凑出来的塔。 A题:大意是有一个m长度的字符串是由b组成,给出n个数,对于每一个...

17 Codeforces Round #808 (Div. 2)

陈小白     2022.07.17     算法相关     抢沙发     111人打酱油
比赛链接:https://codeforc.es/contest/1708 就A了A题,还用了40分钟。B题的题意理解上有些问题,我以为对于每一个l<=i<=r,a[i]只能使用一次。所以就一直WA,直到比赛结束。 A题:大意就是给出一个数组,你可以在任意时刻执行一...

16 cf B. Permutation

陈小白     2022.07.16     算法相关     抢沙发     122人打酱油
题目链接:https://codeforc.es/contest/1701/problem/B 大意是:给出一个数n,让我们制作一个关于1-n的排列,我们需要制作一个p,使得a[i]=a[i-1]*p的数量是最多的。 div2的思维题,题很简单,但是刚开始理解错了意思。后面做题...

15 P1024 [NOIP2001 提高组] 一元三次方程求解

陈小白     2022.07.15     算法相关     抢沙发     113人打酱油
题目链接:https://www.luogu.com.cn/problem/P1024 大意就是给出一个一元三次方程abcd,保证有三个解且解在-100-100之间 然后求出这三个解 这是一个二分的题,不过涉及到一些数学问题。 ,,,如果将x代入后的两个方程表达式异...

15 P3183 [HAOI2016]食物链

陈小白     2022.07.15     算法相关     抢沙发     122人打酱油
题目:https://www.luogu.com.cn/problem/P3183 一道记忆化搜索的题。 大意是给出一个食物链,求食物链的条数。 很明显我们可以用dfs来解这个题,从入度为0的点开始,dfs去找,找到出度为0的点算是一条食物链。用sign记录改点是否被访问...

14 P1280 尼克的任务

陈小白     2022.07.14     算法相关     抢沙发     123人打酱油
题目链接:https://www.luogu.com.cn/problem/P1280 大意,给出一个时间n和任务数k 每个任务给出开始时间和持续时间。求最大的休闲时间。 很明显这个题是一个线性动态规划的题,但是却不好推导状态转移公式,尤其是有任务的时候,状态转移公式很难...

14 P1020 [NOIP1999 普及组] 导弹拦截

陈小白     2022.07.14     算法相关     抢沙发     143人打酱油
深夜更一波啊。明天任务,分别A一道二分,线性dp和搜索题 题目链接:https://www.luogu.com.cn/problem/P1020 大意:给出一组数据,求出这种数据的最长不升子序列以及至少多少个这样的不升子序列个数。 思路:前半个题最长不升子序列正常线性dp...

13 Codeforces Round #806 (Div. 4)

陈小白     2022.07.13     算法相关     抢沙发     140人打酱油
比赛链接:https://codeforc.es/contest/1703 这次比赛做了ABCE四个题,其中D和F题疯狂TLE,我很无语。比赛的难度并不大,最后一题没有看应该是个dp问题,f题是个dp的前置题,有dp的思想在里面。 A题:ifelse水题 code: #...

12 P2196 [NOIP1996 提高组] 挖地雷

陈小白     2022.07.12     算法相关     抢沙发     131人打酱油
题目链接:https://www.luogu.com.cn/problem/P2196 大意:有n个地窖,每个地窖里有一些地雷,给出第i个地窖到i+1-n的连通性。求出最优解及路径,要求拆除地雷最多。 这个题可以爆搜(因为n的值很小),也可以dp(类似于最长子序列那种,这里不同...

12 cf E. Split Into Two Sets

陈小白     2022.07.12     算法相关     抢沙发     130人打酱油
题目链接:https://codeforc.es/contest/1702/problem/E 第一次cf周赛做到了图论的题,真的挺开心的。 这道题题的大意就是,给出一个数n,然后给出n对数a,b。让我们构造两组数,这两组数的元素都是1-n,且没有重复元素。 soluti...

11 Codeforces Round #805 (Div. 3)

陈小白     2022.07.11     算法相关     抢沙发     118人打酱油
题目链接:https://codeforc.es/contest/1702 这次比赛赛题比较简单,很多题感觉可以用stl巧做。另外感觉有必要学习一下stl容器的一些设置的规则,stl是有必要深入学习一下的。这次比赛A了四个题,有两个题用map巧做的,一个题是用了set。map嘛很多时...

08 OJ出题教程

陈小白     2022.07.08     算法相关     抢沙发     110人打酱油
b站链接:https://www.bilibili.com/video/BV13A411P7qz?spm_id_from=333.1007.top_right_bar_window_history.content.click 所用平台polygon,库textlib。 b站链接:https...

06 Codeforces Round #803 (Div. 2)

陈小白     2022.07.06     算法相关     抢沙发     130人打酱油
比赛地址:https://codeforc.es/contest/1698/ 这一场比赛是我没有参加的一场,忘记了是什么原因了,但是我还是回过头来补了一下题。 自己单独A了三道,感觉有点简单,后悔没做了┭┮﹏┭┮,804的直接打了12000多的rank,一个题没做出来,这波血亏...

06 Codeforces Round #804 (Div. 2)

陈小白     2022.07.06     算法相关     抢沙发     133人打酱油
比赛网站:https://codeforc.es/contest/1699 这次比赛一道题都没有做出来,A题很像acm省赛第一题那种规律题,B题很像第一次参加泉城赛的矩阵题(都是推导公式)。C题是个区间问题,感觉也不好做。这里只看前三题。 A题:大意就是输入一个数n,然后找到三...

04 c++ 重载运算符,晚点更先记录

陈小白     2022.07.04     算法相关     抢沙发     123人打酱油
重载运算符可以对我们自己定义的类型进行一个运算(类和对象中用的比较多一些吧),比如结构体之间的一个运算。运算符重载是一种形式的C++多态。我是为什么学呢,因为很多板子都用了这么个东西。 重载运算符基本形态 <返回类型说明符>operator<运算符符号&...

04 蓝桥杯 质数行者

陈小白     2022.07.04     算法相关     抢沙发     127人打酱油
题目链接:https://www.lanqiao.cn/problems/1027/learning/ 一道dp题,但是用普通三维dp最多只能的30%的测试点,记忆化搜索同理。 快筛一遍质数,然后用三维dp再然后剪枝可以过40%测试点的样子。 给出大佬的代码:https://b...

02 cf D. Permutation Graph

陈小白     2022.07.02     算法相关     抢沙发     129人打酱油
题目链接:https://codeforc.es/contest/1696/problem/D 上次cf比赛D题,1900分水平,当前实力不允许我做┭┮﹏┭┮ 两种解决方法: 1.官方的on解法:找到n所在的位置,二分分开求出区间的前后缀最值(从1到n一定要经过值为n的ai点,所以从...

01 cf C. Fishingprince Plays With Array

陈小白     2022.07.01     算法相关     抢沙发     152人打酱油
题目链接:https://codeforc.es/contest/1696/problem/C 大意: 给定一个长度为n的数组a、一个长度为k的数组b和一个数字m,现在对数组a进行以下操作: 选择数组a中一个m的倍数ai替换成m个ai*m 选择数组a中m...

29 cf B. A Perfectly Balanced String?

陈小白     2022.06.29     算法相关     抢沙发     134人打酱油
题目链接:https://codeforces.com/contest/1673/problem/B 大意就是,给一个字符串,对于其任意一个子串s,然后给出u、v(字符串中的元素),是的uv在子串s中出现的次数相差不大于1 如果满足就yes,不满足就no 一个智商检测题...

27 泉城赛 总结

陈小白     2022.06.27     算法相关     抢沙发     128人打酱油
这次泉城赛三人三机,队友发挥的非常好,抱大腿啦~ 队友A了三道,我A了一道(主要是我A完最简单的那道题之后,选的题竟然都是难的,我无了个大语了) 鉴于不知道其他三题具体难度,今天补了一下这几个题(有个拓扑排序的题没补,有机会出个专题总结一下拓扑排序) 下面来总结一...

26 记一次codeforces比赛

陈小白     2022.06.26     算法相关     抢沙发     117人打酱油
第一次参加cf上的比赛,还是个全球赛,不知道难度和div1、div2相比会怎么样,感觉比div1和div2的题难一些。有一说一,有点小紧张。 第一题是大概是个位运算去最大值的题,基本上没有太难的地方,需要注意的可能就是要开longlong吧。 即使是一道签到题,读题依然十分费劲,描述...

25 洛谷 P1802 5 倍经验日

陈小白     2022.06.25     算法相关     抢沙发     129人打酱油
题目链接:https://www.luogu.com.cn/problem/P1802 题目背景 现在乐斗有活动了!每打一个人可以获得5倍经验!absi2011却无奈的看着那一些比他等级高的好友,想着能否把他们干掉。干掉能拿不少经验的。 题目描述 ...

24 2022年天梯赛-全国总决赛 L2-3 龙龙送外卖

陈小白     2022.06.24     算法相关     抢沙发     131人打酱油
龙龙是“饱了呀”外卖软件的注册骑手,负责送帕特小区的外卖。帕特小区的构造非常特别,都是双向道路且没有构成环——你可以简单地认为小区的路构成了一棵树,根结点是外卖站,树上的结点就是要送餐的地址。 每到中午12点,帕特小区就进入了点餐高峰。一开始,只有一两个地方点外卖,龙龙简单就送好了;...

23 cf E. Binary Deque

陈小白     2022.06.23     算法相关     抢沙发     131人打酱油
题目链接:https://codeforces.com/problemset/problem/1692/E 前缀和+二分或双向队列双指针 大意:输入n个数,只包含0和1,输入一个数s。sum为数列的和,每次操作可以删除第一个数或最后一个数,最后求最少通过几次这样的操作可以使得s...

12 2022年山大地纬杯ACM省赛总结(上)

陈小白     2022.06.12     算法相关     抢沙发     148人打酱油
acm罚坐5个小时,太难受了,连签到都不让签 现在陆续复盘acm省赛试题,当时最有希望做出来的应该是k题然后a题比较简单,但是我们没有看出来 e和h题看赛后情况也不难,但是e题不知道怎么判0,h题没有读懂 A题: 大意是,输入n给定1-n这样n个数,通过+-*()...

12 实践周——一元多项式的加减法

陈小白     2022.06.12     算法相关     抢沙发     140人打酱油
思路:最刚开始的看到这个题想的是用map然后遍历的方式来做,考虑到老师不让用stl,就想到另一种方法,做成哈希表的方式。 做完之后老师说让用链表做,这里采用的尾插法做的。 代码: 哈希表方法: #include<stdio.h> inta[1...

09 cf C. Detective Task

陈小白     2022.06.09     算法相关     抢沙发     128人打酱油
题目链接:https://codeforces.com/contest/1675/problem/C Polycarpboughtanewexpensivepaintinganddecidedtoshowittohisnnfriends.Hehungitinhisroom.n...

09 平衡二叉树的旋转以及简便方法

陈小白     2022.06.09     算法相关     抢沙发     132人打酱油
先收藏 链接:https://blog.csdn.net/hello_program_world/article/details/115472968 ...

30 cf H2. Maximum Crossings (Hard Version)

陈小白     2022.05.30     算法相关     抢沙发     172人打酱油
链接:https://codeforces.com/problemset/problem/1676/H2 借鉴:https://blog.csdn.net/sigd/article/details/124717093 https://blog.csdn.net/qq_61057...

29 cf C. LIS or Reverse LIS?

陈小白     2022.05.29     算法相关     抢沙发     139人打酱油
链接:https://codeforces.com/problemset/problem/1682/C 题意:时间1秒范围t(1≤t≤10^4)n(1≤n≤2⋅10^5) 输入t组长度为n的数列a。 求该数列的LIS(a)和LIS(a’)a'为数组a的翻转 求出te...

24 cf A. Three Pairwise Maximums

陈小白     2022.05.24     算法相关     抢沙发     153人打酱油
题目链接:https://codeforces.com/contest/1385/problem/A 一道cf800的题,需要找规律,再想到icpc省赛,给我的启发就是算法入门应该先从找规律开始,算法还要另说 大意就是输入xyz通过求x=max(a,b),y=max(a,c)...

17 cf F. Longest Strike

陈小白     2022.05.17     算法相关     抢沙发     169人打酱油
题目链接:https://codeforces.com/contest/1676/problem/F 大意就是输入一个k和一堆数 找到一组连续的且其中每个数出现的次数大于等于k次即[L,R]中每个元素出现的次数至少k次,输出最多的那一组的左端点元素和右端点元素 如果有多组...

12 sdutoj 删数问题

陈小白     2022.05.12     算法相关     抢沙发     248人打酱油
Description 键盘输入一个高精度的正整数n(≤100位),去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的n与s,寻找一种方案,使得剩下的数字组成的新数最小。 Input 输入两个数字,分别为原始数n,要去掉的数...

12 sdutoj 数组计算机

陈小白     2022.05.12     算法相关     抢沙发     163人打酱油
Description bLue有一个神器的机器,这个机器可以读入一个数组,并按照用户要求快速地进行数组的处理和计算,它支持如下两种操作: 操作1:把数组中第p个元素的值增加v。 操作2:计算数组中[l,r]区间内所有数的和。 ...

12 杭电1009 FatMouse' Trade

陈小白     2022.05.12     算法相关     抢沙发     149人打酱油
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1009 大意:有一部分钱去买猫粮,每个仓库有一定数量的猫粮和所需要的价格。支付百分比的价格将获得百分比的猫粮 思路:贪心算法思想,计算出每个仓库内猫粮的性价比,根据性价比对仓库内元素...

04 记忆化搜索模板题/记忆化搜索和普通递归差异

陈小白     2022.05.04     算法相关     抢沙发     165人打酱油
模板题:https://acm.sdut.edu.cn/onlinejudge3/problems/2176 记忆化搜索和普通搜索的明显差距在于时间上记忆化搜索要快许多,尤其在递归调用较多的情况下 记忆化搜索保存了之前尝试过的一种可能性,这样在到达不可能到达的点时将直接返回的原...

04 给出先序和中序遍历,输出后序遍历

陈小白     2022.05.04     算法相关     抢沙发     164人打酱油
题目链接:https://acm.sdut.edu.cn/onlinejudge3/contests/3982/problems/B 模板借鉴:https://www.cnblogs.com/cynchanpin/p/6758429.html 代码的实现是以先序遍历为主,利用先...

29 蓝桥杯省赛总结(习题解惑回顾)下

陈小白     2022.04.29     算法相关     抢沙发     170人打酱油
成绩出来了,很一般的成绩省二 比赛做了九道题,感觉能对7道左右,对完答案很懵。多的不用说了,上篇已经整理了原因和一些问题。 填空没太多疑惑 直接大题 1.算个花费日子的数量,很简单,可以直接算出。当时循环做的,想做完优化,可是忘了,条件<写成了<= ...

28 拓扑排序BFS实现思路疑惑

陈小白     2022.04.28     算法相关     抢沙发     165人打酱油
拓扑排序bfs的实现既可以使用队列也可以使用栈,当路径唯一时,两者结果并无差异。原因是因为后排的元素是相互独立的。 模板题:http://poj.org/problem?id=1094 思路: 找度为0的元素,入列查找关系 对应关系减度 反复直到队列为空 没太...

23 关于堆的判断

陈小白     2022.04.23     算法相关     抢沙发     193人打酱油
题目链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805064676261888 题意大概就是在一个小顶堆里面判断下根节点,父子关系,兄弟关系 不过我感觉天梯赛的题麻烦在一些输入输出,存储的形式...