Nebius Welcome Round (Div. 1 + Div. 2) 题解 A - D，这四题的整体难度不大，都是过题人数上千的题。 很久没打Codeforces了，在此记录一篇题解，开学了也会不断更新的。 🎈 作者：Eriktse 🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中… […]

题目链接：D-排名估算_牛客挑战赛36 (nowcoder.com) 分析 / Analyse 看完题意有点懵，我们来分析一下，一共有n个人，已知抽了m次都没有比排名比自己高的，不妨将“已知事件”的设为事件A：“抽了m次都没抽中比自己高的”。 而抽人的前提是自己有一个排名，所以我们可以设事件Xi为“当前排名为i“，而在没有事件A的前提下，排名是均匀随机的，所以P(Xi) = 1 / n。 我们要求 […]

链接：G-生蚝接柿子_"夜莺杯"武汉理工大学第四届新生程序设计竞赛 (nowcoder.com) 去年新生赛的一道题。 现在补一下。 分析 不难定义出状态dp[i][j]表示，到从下往上第i个柿子的时候，此时左手在j位置可以接到的最多柿子个数。 状态的转移也比较简单，dp[i][j] -> dp[i + 1][L ~ R]，其中L， R是可以j到达的最远的位置。 当然从i - 1转移到i也可以，只 […]

题目链接：Palindrome - HDU 6230 - Virtual Judge (vjudge.net) 从这里进也可以：Problem - 6230 (hdu.edu.cn) 题目大意 / Problem 有多组样例。 每组样例给一个字符串，问有多少个“一个半回文串”，一个半回文串的定义是，第一个回文串的右端点是第二个回文串的中心，第一个回文串的中心是第二个回文串的端点。 比如abcbab […]

快要比赛了，要抓紧时间力！ 1.拓展欧几里得exgcd 用于求ax+by=c的解，当c = k * gcd(a, b)时有解。 解集为\(x = x_0 + k * (b / d), y = y_0 - k * (a / d)\)，其中d为gcd(a, b)。 不难发现，x的最小正整数解一定是mod(b / d)意义下的，所以一般对方程的解法是先将x扩大c / d倍，再模上b / d即可。 模板题 […]

题目链接：最长的 X - Problem - Daimayuan Online Judge ETOJ：P1003 - 最长的1 - ETOJ (eriktse.com) 有两种做法，第一种是二分。 解法一：二分 先将给定的序列转换成01串，其中'.'换成0，'X'换成1。 再给01串求一个前缀和记录0的个数，现在开始枚举右端点，然后二分得到左端点。 不难发现左端点应该尽可能原理右端点且区间[l, […]

题目链接：Problem - D - Codeforces 给定一个长度N，和一个取值范围M，现在要我们构造长度为[1, N]，元素大小为[1, M]的数组，使得其被删除的方法大于1种，问构造方案数有多少。 删除方法定义为：对于数组中任意一个元素ai，如果gcd(ai, i) == 1，那么这个元素就可以被删除，删除之后，右边的所有元素向左移动，长度减1。 现在我们考虑任意一个数组，一定存在至少一 […]

比赛传送门：第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（沈阳） G - The Witchwood（签到） 选出最大的K个数字求和即可。 F - Kobolds and Catacombs（排序 + Hash） 给定一个序列，将其划分为若干份，将每一份分别排序后，可以使得整体序列非降序，问怎样划分使得份数最多。 读入a序列，再将b序列作为a序列排序后的序列，从前往后遍历，如果某个区间 […]

题目传送门：最大异或和 - Problem - Daimayuan Online Judge 分析 不难发现用可以先预处理出异或前缀和，然后一段区间[l, r]的异或和可以用prefix[r] ^ prefix[l - 1]来表示。 现在问题就转化为对于一个r，在[1, r]的区间内找到一个l（当l == r说明区间内只有一个点），使得prefix[r]^prefix[l - 1]最大，那么l - […]

比赛传送门：第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京） 题解按照难度从小到大排序。 K.K Co-prime Permutation（构造 + 签到） ，给定一个排列大小N和一个数字K要求构造一个有K个值与下标的最大公因数为1的排列。 比如样例5, 3，构造如下的排列： val 1 4 5 2 3 idx 1 2 3 4 5 样例 我看可以看到其中下标为1, 3, 5的三对二 […]