2023中国传媒大学程序设计竞赛J题
计数DP
回退背包
————————————————————————
5.27更
atabc303DE，小白月赛73，ccpc河南，ccpc2023江苏
...
题目链接：https://codeforces.com/contest/1899/problem/G
离线每次查询。对于每一个查询的x，在搜索时将小区间合并到大区间里，然后直接二分查询出来
structtdata{
intl,r,i;
};
constintnn=1e5+10;...
15 202309-3 梯度求解
陈小白 2023.11.15 算法相关 抢沙发 28人打酱油
题目链接：http://118.190.20.162/view.page?gpid=T173
大意是给出逆波兰表达式，给出每个x的值求对某x的偏导。
整理了一些模板，参考https://blog.csdn.net/qq_62571980/article/details/1339...
05 Educational Codeforces Round 157 (Rated for Div. 2) A - D
陈小白 2023.11.05 算法相关 抢沙发 92人打酱油
比赛地址：https://codeforces.com/contest/1895
A：大意是给出宝箱和钥匙的坐标，可以向前或向后走，花费1秒。抱起宝箱最多可以走k秒。
宝箱在右，x
宝箱在左，考虑x+k>=y，y；x+k<y，y+(y-(x+k))
co...
15 山东管理学院周赛10.14
陈小白 2023.10.15 算法相关 抢沙发 85人打酱油
这次比赛的题我没写，简单浏览了一下，前六题是很基础的题。然后三题是图论的题，第一个重码力，后两个重思维。最后一个是防AK的探究性数论题，可以忽略掉。具体代码可以通过题库找到该题，然后查看别人提交的代码。
下面只给出了各个题的思路，看了思路还有不懂的同学可以来问...
只做出来了一个题。。。。。。
https://www.nowcoder.com/discuss/505731702297219072题解。
先存了，怕找不到了。C题应该是能做，嫌麻烦了。
B：
题意：两个人轮流对xxx操作，减10/除以6（必须是12的倍数），谁先...
04 ICPC夏令营计算几何
陈小白 2023.07.04 算法相关 抢沙发 91人打酱油
https://www.educoder.net/paths/kjvfxps8
ASatellites
大意就是给定两个卫星到地球距离，都是一样的。给出角度、或许是分。求两个卫星之间的圆弧距离和直线弦距离。
需要注意的是圆弧角度大于180就需要转换
code：
...
这个学期收获很多，包括实力与奖项。
总结一下本学期参加的比赛，锐评一下。
传智杯：省二迷迷糊糊进国赛了，发挥还不错。
做出了四道题，离国一差点罚时，没去掉非正式参赛距离国一差两名，去掉后相差不到十名。
发挥的挺好，该出的题都出了，没想到高中写过的希尔排序居然在算法竞赛中用...
比赛地址：https://ac.nowcoder.com/acm/contest/60063
先说好消息，搞出模拟了。
再说坏消息，就A了三个.......DE真的很巧妙，尤其D
D：大意是给出给出n*m的矩阵，从11走到nm。求最小花费时间。
两类操作，向上下左右四个反向走，...
01 2023 年上海市大学生程序设计竞赛 - 六月赛 AB题
陈小白 2023.07.01 算法相关 抢沙发 94人打酱油
比赛地址：https://acm.ecnu.edu.cn/contest/676/problem/A/
AB感觉都挺难，比赛做了B，A没想出来。A这个数没猜到不会很大，应该打表或者数学分析一下的。==
A：大意就是你需要构造一个n*m的矩阵，要求长宽均>=2的矩阵，四角不...
30 Educational Codeforces Round 151 (Rated for Div. 2)
陈小白 2023.06.30 算法相关 抢沙发 120人打酱油
比赛地址：https://codeforces.com/contest/1845
这次很幸运的做出来了四个题，感觉这次D题还挺简单的吧。
这次赛题难度不大，基本上就是贪心，贪心，再贪心！
A：大意就是从1-k之间，凑出来一个和为n的数，无限供应，x不能用。
解法：当x不是...
29 D. Tenzing and His Animal Friends 好题当赏
陈小白 2023.06.29 算法相关 抢沙发 195人打酱油
题目链接：https://codeforces.com/contest/1842/problem/D
借鉴：https://blog.csdn.net/Tanya_xiaomai/article/details/131393112
没看懂这个题
大意：丁真和他的n个动物朋...
题目链接：https://codeforc.es/gym/104354/attachments
大意是构造一个n的排列，使得所有相邻的数的差的绝对值是素数
这个题是队友做的，狠狠C了一把。
大概的做法就是，小的全排列，大的找规律
当n为奇数时，从1每次+2构造到n，...
30 D. The BOSS Can Count Pairs （根号分治）
陈小白 2023.05.30 未分类 抢沙发 179人打酱油
题目链接：https://codeforc.es/contest/1831/problem/D
大意是给出两个长度为n的数组a和b，确定存在多少个i和j，使得ai*aj=bi+bj，ai和bi范围在n以内。
考虑根号分治。
不太好求解，但是数据范围是有限的，通过题意我们可...
题目链接：https://codeforc.es/gym/444200/problem/F
大意是存在一个类字符串为ababa，修改为类似马拉车算法的，&|a|b|a|b|a|，给出每个位置以它为中心的回文半径的长度。
构造一个仅包含a和b的字符串，满足输入的2*n+2...
03 松鼠的新家 LCA+树上差分
陈小白 2023.05.03 算法相关 抢沙发 167人打酱油
题目链接：https://www.luogu.com.cn/problem/P3258
大意：从a1走到an，所经过的位置+1，求每个位置的值。
重点在于利用lca进行树上差分，考虑对于x走到y，令x走到公共祖先的点+1，y走到公共祖先的点+1。公共祖先只加一次，所以减去，公共...
29 P1351 [NOIP2014 提高组] 联合权值
陈小白 2023.04.29 算法相关 抢沙发 159人打酱油
题目链接：https://www.luogu.com.cn/problem/P1351
大意是给出一个无向图，求距离为2的相乘权值之和，和最大相乘。
根据公式可以推导
显而易见，这个公式是很容易推导的。
剩下的就是遍历所有的节点，然后去寻找这些值，很水（标签...
https://codeforc.es/contest/1606/problem/C
先来个比较简单的。
大意是给出一个数组a，ai代表一种10^ai的纸币。给出一个数k，你需要找出无法用k个纸币来表示的最小正整数。
贪心的看待这个问题。
a次方和b次方，我们定义a...
28 C. The Very Beautiful Blanket 随机化构造
陈小白 2023.03.28 算法相关 抢沙发 170人打酱油
题目链接：https://codeforc.es/contest/1802/problem/C
大意是构造一个n*m的矩阵，使得2*2的子矩阵与它相邻的对角2*2的子矩阵异或和相等，求存在多少不同的数，构造出来。
很显然我们需要满足任意子矩阵，做法就是随机化这个矩阵，然后用一个...
27 D. Accommodation
陈小白 2023.03.27 算法相关 抢沙发 153人打酱油
题目链接：https://codeforces.com/contest/1804/problem/D
差点做出来的D题了，两千分的难题！
大意是存在n层楼，每个楼有m个窗户，存在m/4个两居室和m/2个单居室，双居室一个灯亮就视为这个居室亮灯了
询问每层楼最少亮灯的居室和，每层...
27 C. Candy Store
陈小白 2023.03.27 算法相关 抢沙发 144人打酱油
题目链接：https://codeforces.com/contest/1798/problem/C
数论方面的题，大意是给出n个商品的数量和价格，求存在多少段l-r之间连续包装的价格组合？
需要明白的一点0和其他数的公约数等于其他数。
很明显我们需要求出任意连续ai*b...
27 舞台矩形，线段树维护平面矩形
陈小白 2023.03.27 算法相关 抢沙发 142人打酱油
题目链接：https://ac.nowcoder.com/acm/contest/53284/F
大意是给出n个人的左边范围，求对于任意两个人的左边，输出能够覆盖他们之间所有人的矩形最小面积
解决方法：
大小的线段树维护一下当前x所指到的最大y和最小y，这样矩阵的最小面积...
题目链接：https://ac.nowcoder.com/acm/contest/52441/F
小白月赛的hard难度，数据量是3000个点。
在这里有些地方比赛的时候想到了，但是没有想到能够很好具体实现的方法，尤其是在共线那里。
easy不用说了，比赛的时候直接暴力过...
27 D - Three Days Ago
陈小白 2023.03.27 算法相关 抢沙发 145人打酱油
https://atcoder.jp/contests/abc295/tasks/abc295_d
好题，本来以为需要从区间问题上考虑，奈何算法世界无奇不有。
大意是求一个0-9的子串中区间内的所有元素是成双成对出现的，串的长度为5e5.
很明显我们可以前缀和维护然后去暴...
24 洛谷3个简单黄dp总结
陈小白 2023.03.24 算法相关 抢沙发 199人打酱油
感觉脑子确实钝了。。。
dp一直是知识框架的弱项。
https://www.luogu.com.cn/problem/P1806
跑步，大意是跑n圈，要求每次比上一次跑的多，问多少种跑法。
很明显这个问题可以当作背包计数来考虑。每次直接用j-i来转移就可以。
...
21 C. Sequence Master
陈小白 2023.03.21 算法相关 抢沙发 141人打酱油
题目链接：https://codeforces.com/contest/1806/problem/C
一个蓝名的入门题。
大意是给出一个2*N的数组，你需要构造一个数组（不需要输出），使得该数组符合任意n长度的子区间的乘积等于其他未被选择的元素的和。求是否存在一个这样的子区间，...
今天学习了线性基
线性基就是用了一个贪心的手法，使得维护这一位一直是1。
线性基中不含重复的异或。
它的构造方法是，每次取某个数字的最高位值。如果存在过直接异或，否则令线性基等于这个值。
线性基的构造代码还是挺简洁的
voidinit(lolbox){
for(in...
08 洛谷绿蓝题选做总结（数论、线代）
陈小白 2023.03.08 算法相关 抢沙发 252人打酱油
TalentShowG蓝
题目链接：https://www.luogu.com.cn/problem/P4377
类型：二分法与01分数规划
大意是根据n头奶牛的体重和才艺值选择出战的一组奶牛，才艺和体重比值最大的获胜，有体重下限限制（需要凑够这些重量）。
solu...
题目链接：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 算法相关 抢沙发 159人打酱油
题目链接：https://atcoder.jp/contests/abc266/tasks/abc266_c
大意是顺时针给出一个四边形，求是否存在凸包
计算几何的凸包问题，当不存在凸包时，也就是所有内角都小于180度。
对于顺时针给出的四边形，我们可以通过叉积判断一下是否存在...
04 莫比乌斯反演+分块+前缀预处理
陈小白 2023.03.04 算法相关 抢沙发 147人打酱油
题目链接：https://www.acwing.com/problem/content/217/
很棒的题解：https://www.acwing.com/solution/content/63012/
大意是给出abd，求存在多少x<=a,y<=b使得gcd(a,...
E.EasyAssembly：https://codeforces.ml/contest/1773/problem/E
大意是给出n个塔，和塔顶到塔底的数字。
给出两种操作：
1.将塔顶上的元素单独移动到一个新的塔+1
2.将整个塔的元素移动到另一塔上-1
求最小操作数量使得成为一个...
28 AtCoder Beginner Contest 291 （D、E）
陈小白 2023.02.28 算法相关 抢沙发 171人打酱油
比赛链接：https://atcoder.jp/contests/abc291/tasks
D题：大意是给出n张卡片的正面和反面的数值，卡片正反面为不同数字，求翻某些卡片的一面使得向正的一面的数值全都不一样的集合的数量。
解决方法：考虑使用01动态规划解决。f[i][0/1]，...
24 拓扑排序（旅行计划+神经网络）
陈小白 2023.02.24 算法相关 抢沙发 155人打酱油
旅行计划
题意
大意是给出n个城市以及他们之间的道路，求从1点到其他各点（以各点为终点）所经过的最多城市的数量
思路
其实很明显可以想到dp的部分。但是如何dp是一个问题。这个dp的状态转移其实并不难，只需要从源点转移过来就ok。但是我们需要想到应该从哪个点开始去d...
存一下https://blog.csdn.net/Philkk/article/details/120570763...
18 C - Tea Tasting 区间查询修改问题（三种方法）
陈小白 2023.02.18 算法相关 抢沙发 156人打酱油
放在前面 这次比赛的表现十分拉胯，高光点只有13分钟做出了前两题，然后直接罚坐。 经常遇到这类问题但是总是感觉少点东西才能做出来，总会有些地方不知道应该怎么处理。其实总结来看，无非就是这么几种情况，有些情况之前的博客已经说过了。例如二分和尺取，但是尺...
17 STL —— 位运算函数之 __builtin_
陈小白 2023.02.17 算法相关 抢沙发 128人打酱油
转载一下，感觉很有用。。。。https://blog.csdn.net/Scar_Halo/article/details/89552658...
17 山东管理学院寒假集训round3
陈小白 2023.01.17 算法相关 抢沙发 194人打酱油
比赛链接：https://vjudge.csgrandeur.cn/contest/538238#overview
这次比赛做出了六道题。需要手动计算的题有点多，有点恶心，计算题就做了一个G题，主要是规律已经发现了做不出来有点可惜，BC目测应该也需要手动算一下。
BC感觉自己不...
第一天是计算几何。
先讲了魔改bfs和魔改二分。魔改二分基本上听懂了实现的思路，应该也能实现。魔改bfs还是挺难的，尤其是状态压缩那里很难想明白，还需要再学习学习。
重点：计算几何。其实计算几何并不难，基本上都是高中学过的一些知识。比较吃板子和高中数学功底，但不是属于不可做的题...
14 各大OJ爬取做题数量总结
陈小白 2023.01.14 技术教程 抢沙发 200人打酱油
花费一天的时间，爬取了codeforces、vjudge、蓝桥云课、洛谷、牛客竞赛的AC数量。
杭电打不开，所以没有去弄（老OJ了，应该好爬一些）
codeforces：非常简单的爬取，直接通过单独的用户页面就可以访问到所有的信息。
vjudge：同codeforces
...
13 AtCoder Beginner Contest 284
陈小白 2023.01.13 算法相关 抢沙发 188人打酱油
比赛链接：https://atcoder.jp/contests/abc284
做出了四个题。第五个题很简单可以直接暴力，但是怂了。
E题：大意是给出n个点，m条边，度最多为10。求从1开始的简单图。超过1e6输出1e6。
注意到度最多为10和1e6就可以直接暴力，简简单...
11 山东管理学院寒假集训round2
陈小白 2023.01.11 算法相关 抢沙发 168人打酱油
比赛链接：https://vjudge.csgrandeur.cn/contest/536832#overview
总结：可做的题还是有的。DEHJ没有去尝试。没什么太多思路。
这些应该是可补的题，外加一个J题，很好的思维题不会做但可以学
B题明显是个状压dp。但...
10 平面锐角三角形的数量
陈小白 2023.01.10 算法相关 抢沙发 166人打酱油
题目链接：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 算法相关 抢沙发 193人打酱油
比赛链接：https://vjudge.csgrandeur.cn/contest/537670#overview
多少因为服务器卡没有好好做。
不过，只AC了三个题真的非常离谱！
题确实简单。感觉自己没脑子。。。。或者说想的有点多。
B题：大意是用a表示1，z表示...
07 Hello 2023
陈小白 2023.01.07 算法相关 抢沙发 152人打酱油
比赛链接：https://codeforces.ml/contest/1779
这次比赛还行吧，蓝名表现分上青了。D题有点虐，可以用dp、单调栈、rmq、树状数组、并查集做。我一个也没想到，现在弄明白了单调栈做法和rmq做法。感觉E题说不定能出，随便看两眼D题没思路，直接开E了
...
02 山东管理学院寒假集训round1
陈小白 2023.01.02 算法相关 抢沙发 252人打酱油
比赛链接：https://vjudge.csgrandeur.cn/contest/536129#problem
难度评测：
codeforcesdiv3前四题。难度最高D题1400分构造题。洛谷两红两橙。
有两个构造题。难度还可以，需要认真分析一下。不能想的太复杂，这两...
28 蓝桥杯 11道黄橙dp题总结
陈小白 2022.12.28 算法相关 抢沙发 204人打酱油
题目链接：https://www.luogu.com.cn/problem/list?tag=363,361%7C3&page=1&orderBy=difficulty&order=asc
先说3个橙题。现在感觉都是比较简单的dp题，都是通过递推的形式转换过来...
26 状压dp 解决 哈密顿回路问题
陈小白 2022.12.26 算法相关 抢沙发 159人打酱油
步骤：
确定采用状压dp范围20左右。
状态转移f[i][j]表示对于第i个节点，它走到的第j个状态。对于任意状态，遍历任意节点，找到此节点并确定另一节点与其重合。
路径确定i>>j&1路径重合i-(1<<j)>>k&1
...
23 砝码称重 线性dp+备份表/滚动数组
陈小白 2022.12.23 算法相关 抢沙发 148人打酱油
题目链接：https://www.luogu.com.cn/problem/P8742
大意是给出砝码，求称出的重量的数量。
经过观察，发现新给出的第i个砝码，只是在第i-1个砝码的基础上产生印象。因此只需要两张映射表做一个滚动数组即可
code:
constintn...
18 夜深人静写博客——研究筛法找到半素数序列
陈小白 2022.12.18 算法相关 抢沙发 210人打酱油
想法来源于抖音刷到的一个小学规律题33,34,35,(),39中间填什么数?
通过规律我们可以看到每个元素都可以由两个素数相乘得到，中间填"38"2*19=38
不难发现这样的半素数可以组成数列4,6,9,10....
如果找到第n项？通过这几天（期末考前）的研究...
题目链接：https://codeforces.ml/problemset/problem/1765/N
删数问题，存在0元素，且首位不能为0，求删除k个数后的最小值为多少。
思路：删数问题一般跑不了贪心。因为我们总应该要贪婪的选择删除前面的数，将靠前的大数消灭掉。
我们需要解...
01 第47届ICPC济南赛站/第一次ACM区域赛总结
陈小白 2022.12.01 算法相关 抢沙发 291人打酱油
时间：11月27日参加了亚洲区域赛济南站。
比起省赛的爆零，这次区域赛的情况要好很多，这得益于在cf刷的250道题。解决了K和M，但是在一个不可能做出来的题上费了3个多小时
在看到签到思维题的那一刻，想法几乎是一瞬间。但是很不幸的是被数据卡了memset和cin，签到题签的并...
01 Codeforces Global Round 20
陈小白 2022.12.01 算法相关 抢沙发 172人打酱油
比赛链接：https://codeforces.ml/contest/1672
讲真的，做的挺拉的。A题没读懂，看了题解。BC每个题都WA了好几次。D题直接看答案了
A题：大意是现有数组a,errorgorn和maomao90分别先后轮流将数组a中的某个元素拆分成两个不小于1的...
26 G. SlavicG's Favorite Problem
陈小白 2022.11.26 算法相关 抢沙发 195人打酱油
题目链接：https://codeforces.ml/contest/1760/problem/G
div4最接近ak的一场，这个题没有读明白。其实上一个题也应该要整理的，做法还是有些复杂。这个题我的写法和别人写的相比也复杂一些。尤其是在树的遍历操作上，开sign是容易出错的==
...
21 Codeforces Round #834 (Div. 3) A-E
陈小白 2022.11.21 算法相关 抢沙发 248人打酱油
比赛链接：https://codeforces.ml/contest/1759
A题：大意是给出一个字符串，每个字符串是否能够被Yes识别到。设字符串长度为n，则主串为n个Yes，求是否存在输入的字符串。
读题还是挺麻烦的，心态有点崩。做起来很简单，需要注意如果不存在s.fin...
链接：https://www.luogu.com.cn/problem/P1045
算是比较裸的板子题，需要注意的是需要考虑后50即可。这个点当时没有好好像，开大了容易g
位数不用多说了，可以直接log算出来
code：
#include<iostream>...
14 Codeforces Round #833 (Div. 2) A-C
陈小白 2022.11.14 算法相关 抢沙发 262人打酱油
比赛链接：https://codeforces.ml/contest/1748
A题：水题，大意是给出n，存在n个方块，边长为n/i，向下上取整。
根据样例直接找规律。
B题：给出0-9的字符串，找出有多少组l-r中，每个数字出现的次数不超过l-r中所有不同类别数字的组数...
09 P1026 [NOIP2001 提高组] 统计单词个数
陈小白 2022.11.09 算法相关 抢沙发 194人打酱油
题目链接：https://www.luogu.com.cn/problem/P1026
感觉可以贪心，但是贪心只过了两个点╮(╯▽╰)╭
我的思路是这样的：我们从后往前去记录出现单词，数据量小完全可以暴力，然后将单词标记一下，首字母额外标记一下。
最后我们统计出有多少个单词，下面开始...
04 有依赖的背包问题——有线电视网
陈小白 2022.11.04 算法相关 抢沙发 188人打酱油
题目链接：https://www.luogu.com.cn/problem/P1273
树形dp。但这个本质上是个背包问题，一时间没有想起来有依赖的背包问题。
读题的时候没有发现客户端一定是接在转发器上的，想成了一颗比较自由的树。
做的时候要当作一个有依赖的背包问题来做，分好组...
题目链接：https://www.luogu.com.cn/problem/P1040
大意是给出一个树的中序遍历，这个树每个子树都有一个加分，得分=左子树分数*右子树分数+根的分数。
在每个节点都有一个分数，第i个节点分数为di。其实就是给出的中序。求最大加分并输出先序遍历
...
01 Codeforces Round #831 (Div. 1 + Div. 2)
陈小白 2022.11.01 算法相关 抢沙发 299人打酱油
比赛链接：https://codeforces.ml/contest/1740
A题：水题，两个素数相加一定是偶数。
B题：大意是给出一堆长方形（包含正方形），纵向放置不能堆叠，求最短周长，可以任意旋转。
思路：最长的一个边可以包含其他长方形最长的边，然后所有的长方形的最...
28 温温的那些年(easy)
陈小白 2022.10.28 算法相关 抢沙发 224人打酱油
题目链接：https://ac.nowcoder.com/acm/contest/38105/J
大意是给出一堆数，求是否存在一个图，它的顶点的连接数量与序列相对应。
困难版本不考虑，，，
思路：优先队列从大数量边的点开始考虑，一个个进行满足，存在无法满足的no，直到最后...
感觉codeforces也是来到了能做D题的水平。
在解决完子区间的查询问题之后，感觉C题能做的就多了。
codeforces的D题多是一些C题的加强版，这里往往涉及到某些规律，例如二进制位。
同样D题往往也容易出现一些简单的树和图的问题，尽管我目前的水平仍然做不出来，但是可以...
25 关于区间内的子区间查询问题的探究
陈小白 2022.10.25 算法相关 抢沙发 303人打酱油
这是一类什么问题，在一个区间内要想求得某个区间，你需要什么样的复杂度？
n*(n-1)/2？你需要暴力出所有的情况。
能否找到一个方法使得我们所得到的满足子区间是最优的且一定使我们想要的？
这里存在两种方法：尺取法（两个指针）和二分。
那么先来说说尺取和二分，尺取是固定一边去寻找另一...
19 D.Problem with Random Tests 知识盲区（bitset,lambda表达式）
陈小白 2022.10.19 算法相关 抢沙发 291人打酱油
题目链接：https://codeforces.ml/contest/1743/problem/D
bitse类似数组，用于存储二进制位，可以直接进行位运算
lambda表达式，之前看过，但是没有系统的总结。
https://blog.csdn.net/qq_37085158/...
19 论文——整点正多边形
陈小白 2022.10.19 未分类 抢沙发 243人打酱油
先说结论，不存在一个除了正四边形之外的正多边形的各个顶点在“整点”上，整点即(x,y)，对于任意xy取整数
一个中学生写的论文，整的厉害orz
...
18 构造问题？？？（持续更新）
陈小白 2022.10.18 算法相关 抢沙发 247人打酱油
第一题：https://codeforces.ml/contest/1720/problem/A
构造前置题，唯一构造：大意是给出abcd，a/bc/d的分数。他可以让abcd乘以任意一个整数，使得两个分数相同，求最少操作次数。
你需要想办法使得两个数相同，找到这个数，这个是构...
18 Codeforces Round #828 (Div. 3)A-D
陈小白 2022.10.18 算法相关 1条评论 355人打酱油
比赛链接：https://codeforces.ml/contest/1744
第一次排名挺高，到了2500+，也是如愿的在定级赛内要上绿了。这次比赛E题的构造题听恶心的，其他发挥的还可以，C题稍微有些失误但不多，还是有些需要注意的点。构造题单独总结一下。
A题：水题，主要是哈...
17 第1届ICPC青少年程序设计竞赛D题
陈小白 2022.10.17 算法相关 抢沙发 197人打酱油
思路：从两个方面进行考虑。k内的点和k外的点。对于k内的点，每一个i点都有i-1个点可以选择，情况为fi-1的一个累乘情况数量。对于剩下的点，可以选择任意情况进入。
code：
#include<bits/stdc++.h>
usingnamespacestd;
#...
15 Codeforces Round #827 (Div. 4) A-G
陈小白 2022.10.15 算法相关 抢沙发 328人打酱油
比赛链接：https://codeforces.ml/contest/1742
A题：水题
B题：水题
C题：思维+审题。大意是给出一个8*8的矩阵，每次操作可以画一行红色或者是一列蓝色，每次绘制可以覆盖之前的颜色。求出最后画的是哪一笔？题目保证给出一个正确解。
这...
12 Codeforces Round #825 (Div. 2) ABC
陈小白 2022.10.12 算法相关 抢沙发 298人打酱油
比赛链接：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 算法相关 抢沙发 255人打酱油
题目链接：https://codeforces.ml/contest/1735/problem/D
大意是，给出n个卡片，每个卡片有k个元素，每个元素有012三种取值。
存在三个卡片，卡片上的对应元素要么全部相等，要么全部不相等。求存在多少个这样的集合。
%3的规律，全部相等值...
07 ShanDong Multi-University Training #6 (AEG)
陈小白 2022.10.07 算法相关 抢沙发 194人打酱油
比赛链接：https://vjudge.csgrandeur.cn/contest/518332#overview
A题：大意是给出一个字符串，字符串遇到aeiou就会翻转，并将元音放到最开头，求出有多少种可能可以构造这个字符串。
两种最容易发现的情况，不存在元音为1，存在一个...
05 Educational Codeforces Round 136 (Rated for Div. 2)
陈小白 2022.10.05 算法相关 抢沙发 213人打酱油
比赛链接：https://codeforces.ml/contest/1739
这样有点难，B使劲WA，C题直接解不出来，思维上要求很高。C题更是赛出了组合数学
A题：水题，棋盘固定走法，求哪个格子没有可走的步子。
code：
#include<bits/stdc...
30 杭电A + B Again
陈小白 2022.09.30 算法相关 抢沙发 224人打酱油
链接：https://acm.hdu.edu.cn/showproblem.php?pid=2057
大意是给出十六进制的数字字符串，完成两个相加。有正负号。
感觉很可怕是不是？？？确实很可怕，自己想用字符串处理，写了八十多行硬是啃不下来。看看大佬代码
code：
#inc...
27 平面分割（直线/折线）
陈小白 2022.09.27 算法相关 抢沙发 208人打酱油
转载：https://blog.csdn.net/summerxiachen/article/details/63252964...
26 第46届昆明站签到题
陈小白 2022.09.26 算法相关 抢沙发 220人打酱油
比赛链接：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 算法相关 抢沙发 178人打酱油
比赛链接：https://codeforces.ml/contest/1691 夜深人静写博客~ c题做不出来555~ A题：大意是给出一个n的数组，求删除一些数后，使得每两个数相加的和为偶数。求最少删除量。 剩下的数都需要是一致的奇偶性，所以删除奇数数量和偶数数量最小的那一个。 code：...
18 C. Schedule Management
陈小白 2022.09.18 算法相关 抢沙发 211人打酱油
题目链接：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 算法相关 抢沙发 387人打酱油
比赛链接：https://codeforc.es/contest/1729
本场比赛赛后补题，感觉比较轻松的做出前四题，第五题看不懂，是一个交互题（做的还是太少了）
A题：大意就是有两个电梯，第一个电梯在a楼，如果你使用第一个电梯，它会直接来1楼接你。第二个电梯在b楼，如果你使...
题目链接：https://www.lanqiao.cn/problems/2110/learning/
动态规划一直是我的弱项，这个题其实是一个很简单的动态规划的题非板子题。
这个题的精髓在于递推上面。
下面来仔细分析一下。
首先当n=1,2,3时s=1,2,5这是...
13 C. Color the Picture
陈小白 2022.09.13 算法相关 抢沙发 237人打酱油
题目链接：https://codeforc.es/contest/1711/problem/C
大意是给一个n×m的矩形，有k种颜料，每种颜料有ai个，一个颜料可以涂一格方格，问是否能构建一幅美丽的画，一幅美丽的画被定义为一个方格周围至少有3个格子和他颜色相同，同时，定义第1行和第n...
13 C. Digital Logarithm
陈小白 2022.09.13 算法相关 抢沙发 206人打酱油
题目链接：https://codeforc.es/contest/1728/problem/C
单独拿出来做一个博客，感觉我平时很少遇到的题。
大意就是，给出两个数组a和b，你可以对任意元素进行一个log10(x)的操作，也就是说，你可以将这个数改变为它的位数。
最后求出最少通...
08 Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
陈小白 2022.09.08 算法相关 抢沙发 234人打酱油
比赛地址：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 算法相关 抢沙发 247人打酱油
比赛链接：https://codeforc.es/contest/1722
在学校里，一直没时间参赛。
在D题上出现了比较大的问题。把题拆开来考虑结果导致有些麻烦。
前三题中规中矩吧，基本一次过，题并不是很难
A题：大意是有个人叫Timur，对于他名字的任意排列都是对的。...
题目链接：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 算法相关 抢沙发 232人打酱油
比赛链接：https://codeforc.es/contest/1721
没参加比赛，之后补的题，有点难==。居然是教育周的题。做出来了两个题，第三个题有点没读明白。
A题：大意是给出四个字母，你每次可以操纵不超过两个相同颜色的字母，使得变成一个字母，求最少操作数。
直接分情...
22 codeforces cf-tool 脚本交题方式
陈小白 2022.08.22 算法相关 抢沙发 204人打酱油
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 算法相关 抢沙发 226人打酱油
比赛链接：https://codeforc.es/contest/1715
总体难度除了AB题之外，其他的题几乎不可做。但是B题出现的问题太大了，WA了五次。最开始的思路没有直接去实现，因为感觉实现不了，最后发现自己写的n+k的复杂度根本过不去。回过头来又考虑的n+计算的思路。
...
20 Codeforces Round #814 / 815 (Div. 2) C题
陈小白 2022.08.20 算法相关 抢沙发 209人打酱油
比赛链接：https://codeforc.es/contest/1719
https://codeforc.es/contest/1720
1.大意是，给出一个1-n的排列，ai表示运动员的实力，每次前两名运动员进行比较，实力强的保留，实力弱的排到最后。
每次给出一个询问i和...
15 Codeforces Round #813 (Div. 2)
陈小白 2022.08.15 算法相关 抢沙发 236人打酱油
比赛链接：https://codeforc.es/contest/1712
这次比赛做了ABC，A题有些失误，大概十二分钟才AC，中途WA了一次。
B题做的很快6分钟一次过
C题WA了三次，改完一个bug后，手贱多加了一条语句，导致后面WA了两次。
A题：大意是给出...
12 多重背包的二进制优化
陈小白 2022.08.12 算法相关 抢沙发 188人打酱油
题目链接：https://www.acwing.com/problem/content/5/
最近没有比赛可打，好好看看基础。
多重背包的朴素写法很简单，基本上都能写，复杂度nmk级别的，在数据量几千的情况下就处理不了了。
因此我们考虑用空间换时间，对物品进行二进制优化，...
11 最长公共上升子序列 加强理解版
陈小白 2022.08.11 算法相关 抢沙发 227人打酱油
题目链接：https://www.acwing.com/problem/content/description/274/
两个序列a,b求最长公共上升子序列
我们定义f[i][j]为a序列的前i个和b序列的前j个元素的最长公共上升子序列
那么当前的f[i][j]可以继承f[i-...