题解 算法
Omkar and Akmar 题解
题意:有一个 \(n\) 个点的环,以及两个人。每个人可以向环中任意一个位置放置一个 \(A\) 或者 \(B\),但是相邻的位置不能相同,不能行动者输。问最终的局面有多少种。 一个结论是:后手必胜。 证明:最终肯定不可能出现两个连续的空格,否则一定可以在其中一个上填 \(A\) 或 \(B\)。所 ......
Animals and Puzzle 题解
原题链接:CF713D 题意:给定一个 \(n\times m\) 的地图 \(a\),\(a_{i}\) 为 \(0\) 或 \(1\)。有 \(t\) 次询问,每次询问给定一个矩形,求出这个矩形中最大的由 \(1\) 构成的正方形的边长是多少。 首先考虑预处理出 \(d_{i,j}\) 表示以 ......
Freezing with Style 题解?
好像不是题解,算是记录。 记一个 Trick:当求路径边权的中位数的最大值的时候,可以先二分一个答案 \(mid\),然后把大于 \(mid\) 的边设为 \(1\),否则设为 \(-1\)。这样只需要看路径长度是否大于零就可以判断出有没有中位数大于等于 \(mid\) 的情况了。 当然类似到求一个 ......
Square-free division (easy version) 题解
题意:给定一个长度为 \(n\) 的序列,求最少能将这个序列分成多少段使得任意一段中不存在两个数的积为完全平方数。 一个小 Trick:如果两个数乘起来为平方数,可以先将每个数的平方因子除掉,然后这两个数必然相等。于是这道题被转化为了一个区间不能有相等的值,这就很典了。 设 \(pos_{a_{i} ......
Square-free division (hard version) 题解
题意:给定一个长度为 \(n\) 的序列,求最少能将这个序列分成多少段使得任意一段中不存在两个数的积为完全平方数。你还可以将其中 \(k(k \le 20)\) 个数修改为任意的值。 一个小 Trick:如果两个数乘起来为平方数,可以先将每个数的平方因子除掉,然后这两个数必然相等。于是可以先将每个 ......
C0392 B 【1109 B组】预处理器 题解
题意:求有多少个长度为 \(n\) 的数组 \(a\) 满足以下条件。 条件一:\(l_{i} \le a_{i} \le r_{i}\)。 条件二:\(a_{i}\) 模 \(2\) 等于 \(p_{i}\)。 条件三:\(s \le \sum a_{i} \le t\)。 求答案模 \(mod\ ......
A Simple Task 题解
这道题比较简单,简述一下思路。 考虑状压 \(DP\)。 设 \(dp_{i,j}\) 表示走到第 \(i\) 个点,之前走过的点的状态为 \(j\) 的环的数量。这里有一个细节,就是我们都钦定每个走过的第一点是整个状态中编号最小的点,这样不会重复计算。 考虑如何进行转移。如果当前点的编号比走过的最 ......
P1450 [HAOI2008] 硬币购物 题解
原题链接:P1450 这道题被教练放到了状压 \(DP\) 的题单里面,但是正解却不是状压 \(DP\),而是背包 \(+\) 神奇容斥,只不过是用到了一些二进制状压的思想。 思路 首先看到题目立马就想到了多重背包,但是时间复杂度肯定接受不了,于是考虑优化背包。我们可以想到一个很神奇的性质:假设只有 ......
CF1900D Small GCD 题解
原题链接:CF1900D,题意不多赘述。 首先可以将 \(a\) 数组排序,并且枚举中间的那个数 \(a_i\)。那么答案就是 \(\sum_{j=1}^{i-1} \gcd(a_j,a_i)\times (n-i)\)。重点在于求前面的 \(\gcd\)。可以用欧拉反演,但是也可以不用,因为我不会 ......
CF1902D Robot Queries 题解
题意:有一个二维平面直角坐标系,给定一串向某个方向移动 \(1\) 个单位的操作。 有 \(q\) 个询问,对于每个询问给定 \(x,y,l,r\),问如果倒着做 \(l\) 到 \(r\) 这段区间中的操作,是否会经过 \((x,y)\)。 ds 题。先预处理出 \(sx_i,sy_i\) 表示执 ......
P3959 [NOIP2017 提高组] 宝藏 题解
原题链接:P3959 乍一看,感觉像是一道图论的最短路这类的题,但是细想发现用图论似乎不可做。再看到这道题的数据范围 \(n<=12\),立马就可以想到用状压 \(DP\),因为数据范围很状压/。 思路 设计状态 首先来考虑状态的设计。如果按状压 \(DP\) 的套路来设的话,设 \(dp_{i,j ......
Group Projects 题解
原题链接:Group Projects 题意 有 \(n\) 个学生,每个学生有一个能力值 \(a_{i}\) 。现在要把这些学生分成一些(任意数量的)组,每一组的“不和谐度”是该组能力值最大的学生与能力值最小的学生的能力值的差。求所有不和谐度之和不超过 \(k\) 的分组方案总数。 思路 根据题目 ......
Partition into Groups 题解
原题链接:Partition into Groups PS:这是今天上午NOIP模拟赛的T3。 题意 N个小朋友,每个小朋友最多有3个敌对小朋友, 问是否能把他们分成两组,使得这N个小朋友最多只有一个敌对小朋友在一组。 思路 考场上想肯定与二分图有关,最后没想出来,打了15分暴力就走了(最后还只有1 ......
CF575A Fibonotci 题解
原题链接:CF575A 前言 今天模拟赛考到了这道题,最近正好在学习矩阵,于是就来写了这道题,发现这道题是矩阵快速幂好题。 题意 题意不多赘述,大概就是一个广义斐波那契数列的升级版,可以修改 \(m\) 个系数。 思路 因为题目是求斐波那契数列的第 \(k\) 项,显然用矩阵去维护。又因为题目说了, ......
[AGC012C] Tautonym Puzzle 题解
原题链接:Tautonym Puzzle 前言 这道题是一道很有趣的构造题。我认为这道题的重点在于对题目要求的转化与转化过程中细节的处理。(有些细节问题也困惑了我很久)。 题意 构造一个字符串 \(S\) ,使 \(S\) 的所有子序列中,恰好有 \(N\) 个好串。 好串:一个字符串能分成两个相同 ......
【0823 B组】模拟测试 mit 题解
原题传送门:mit 前言 这道题是今天模拟赛T1,赛时只有 \(60\) 分。还有一位巨佬这道题保龄了。 题意 给定一个正整数 \(n\),将 \(n\) 拆分成 \(k\) 个数之和。(\(k\) 为任意正整数) 求:\(k\) 个数的乘积最大是多少?乘积的期望是多少? 思路 首先看第一个问题。易 ......
P1903 [国家集训队] 数颜色 / 维护队列 题解
原题链接:P1903 题意 对于一个序列,维护两个操作: 将 \(a_{x}\) 改为 \(p\)。 求 \(l\) 到 \(r\) 中有多少个不同的数 思路 这道题本来是带修莫队的板子的,但是我是使用分块做的。 具体思路挺板的...但是这道题其实有个 \(trick\)。就是我们先预处理记录 \( ......
P3464 [POI2007] WAG-Quaternary Balance 题解
题意 给定一个数 \(n\),要求将 \(n\) 表示成一些 \(4^{k}\) 的数之和或差的形式,要求用的数最少,求方案数。 思路 首先看到这道题的数据范围 \(n\le10^{1000}\),又是求方案数,所以想到用数位 DP。因为每一个数都是 \(4\) 的次幂,显然我们需要讲原数转化为 \ ......
P7532 [USACO21OPEN] Balanced Subsets P 题解
原题链接:P7532 前言 这道题是今天 NOIP 模拟赛的 T1,赛时只有 5 分。 题意 简化一下题意,即在一个 \(n\times n\) 的方阵中,求出有多少个满足条件的连通块,使得: 同一行或列的两点中间没有空 连通块内全是草 可以发现,其实连通块就是一个凸多边形。 思路 很显然,这道题是 ......
CF1901E Compressed Tree 题解
原题链接:CF1901E,树形 dp + 神奇分类讨论。 很容易想到树形 dp。难点在于如何转移以及统计答案,需要大量分讨。 父亲(及其以上)和自己组成连通块,不缩。(只保留自己并且往上传递) 连通块中只有自己一个(记录答案) 一个儿子和自己组成连通块,且自己作为根节点,不和父亲收缩(记录答案) 一 ......
P1462 通往奥格瑞玛的道路 题解
题意 简述一下题意。给定一张图,每条边是双向的。给定一个数\(b\),求一个最小\(ans\)和一条从\(1\)到\(n\)的路径,使边权和\(<=b\),点权最大值\(<=ans\)。 思路 看到求点权最大值最小,想到二分。又要让边权和最小,想到最短路。具体来讲,二分一个\(mid\),对于每个\ ......
华中师范大学2023新生赛 H 龙 题解
Link 华中师范大学2023新生赛 H 龙 Question 有 \(m\) 个宝石孔,有 \(n\) 个宝石,每个宝石可以提升 \(a_i\) 点战斗力 每次镶嵌一个宝石,被选中的宝石会 随机 选择一个宝石孔进去,如果这个孔原来有宝石,则原来的宝石会被损坏 你可以任意决定镶嵌宝石的顺序,她想知道 ......
KMP算法
用于解决字符串匹配问题 名词解释 前缀表 前缀:包含首字母不包含尾字母的所有子串 比如aabaaf的前缀有a aa aab aaba aabaa 后缀:包含尾字母不包含首字母的所有子串 比如aabaaf的后缀有f af aaf baaf abaaf 最长相等前后缀:比如aabaa,最长的,相等的,前 ......
华中师范大学2023新生赛 D 身无彩凤双飞翼 题解
Link 华中师范大学2023新生赛 D 身无彩凤双飞翼 Question 给出一个 \(n\times m\) 的网格,网格上有一些障碍,问最少添加多少障碍才能使 \((1,1)\) 和 \((n,m)\) 不连通 Solution 我好像用了一种和标答不一样的写法 我们先对图 bfs 一次,如果 ......
【面试官版】【持续更新中】融合滤波算法+数据结构+激光视觉SLAM+C++面试题汇总
C++部分 什么时候需要写虚函数、什么时候需要写纯虚函数? 只继承接口为纯虚函数 强调覆盖父类重写,或者父类也需要实现一定的功能,为虚函数 指针传参和引用传参区别? 引用传参本质上是传递原参数地址,指针传参本质还是值传递,生成拷贝指针,拷贝指针和原指针指向的为同一块内存。因此改变拷贝指针的指向不影响 ......
CF1905 B Begginer's Zelda 题解
Link CF1905 B Begginer's Zelda Question 给出一棵树,每次能把一条路径压缩成一个点,求最少几次把树压缩成一个点 Solution 贪心的想,路径肯定越长越好,所以肯定是以一个儿子节点为起点,以一个儿子节点为终点,儿子节点合并了儿子到根的父节点也合并了,每次合并两 ......
CF1905 A Constructive Problems 题解
Link CF1905 A Constructive Problems Question 有一个 \(N\times M\) 的矩阵,你需要建造一些房子,把这个矩阵填满 当一个 \(2\times 2\) 的正方形左上和右下有房子时,左下和右上房子会自动生成 当一个 \(2\times 2\) 的正 ......
【题解】CodeForces-1913
CodeForces-1913A Rating Increase 依题意模拟。 提交记录:Submission - CodeForces CodeForces-1913B Swap and Delete 交换免费就是能任意重排,从头开始尽量填相反的,剩下只能删去了。 提交记录:Submission ......
【题解】CodeForces-1905
CodeForces-1905A Constructive Problems 发现沿着对角线放就行了,答案是 \(\max(n+m)\)。 提交记录:Submission - CodeForces CodeForces-1905B Begginer's Zelda 最优操作每次删两个叶子(除了最后一 ......
用MATLAB实现遗传算法程序
用MATLAB实现遗传算法程序/B2F.m , 658用MATLAB实现遗传算法程序/changes.m , 959用MATLAB实现遗传算法程序/cross.m , 1155用MATLAB实现遗传算法程序/de2bi.m , 1048用MATLAB实现遗传算法程序/F2B.m , 540用MATL ......