题目链接：M-Stone Games_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明） (nowcoder.com) Problem 给定一个正整数组成的数组，每次询问一个区间[l, r]内不能组成的最小的正整数。 区间内的数字最多被用一次，可以一个都不选（结果为0）。 比如对于题目样例的数组：\(\{ 1 4 2 1 6 \}\)，询问区间\([3, 5]\)也就是\(\{ 2, […]

题目链接：C-Sum of Log_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海） (nowcoder.com) 题意 求一个式子的值。 $$ \sum\limits_{i = 0}^{X} \sum\limits_{j=[i=0]}^{Y} [i \& j==0] \lfloor log(i + j) + 1 \rfloor$$ 分析 不难发现，当满足条件\([i \& […]

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

比赛传送门：第 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的三对二 […]

比赛链接：[牛客竞赛]第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海） G.Fibonacci（规律 + 组合数学） 在经典的斐波那契数列（1, 1, 2, 3, 5, 8...）中，给出一个N求出满足以下条件的(f(i), f(j))二元组个数： \(1 \le i < j \le N\)且\(f(i) * f(j) % 2 == 0\)。 分析一下，斐波那契数列如果对2取 […]

题目传送门：第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（上海） D Strange_Fractions（解方程，数论） 解方程，设\(t = \frac{b}{a}\)，将方程两边同时乘\(t\)可以得到\(qt^2 - pt + q = 0\)，通过小学二年级学的一元二次方程求根公式可知：当\(p^2 - 4q^2 \ge 0\)时方程有解。由求根公式可以得到\(t = \frac […]

可以在PTA补题。 题目大意 / Problem 给定两个字符串s和t，求一个s的子串s'使得s'和t的最大公共子串长度不超过1，问s'的最大长度。 子串可以不连续。 思路 / Thought 先把字符转换成[0, 25]的数字方便处理。 根据题意判断应该是个DP。由于是一个和位置和字符有关的dp，状态可以设为\(dp[i][j]\)，表示到s的第i个位置为止，最后一个敏感字符（定义为存在于t中的 […]

题目链接：The 2022 ICPC Asia Regionals Online Contest (I) (pintia.cn) 在PTA可以补题。 题意 / Problem 给定一个长度为N的01串，有Q次询问。 对于一个01串，每次可以代价为0的删除任意一个1以及和它相邻的两个数字，或者代价为1的将某个0翻转为1。 注意这个01串是环形的，也就是头尾相连，比如100也可以代价为0的进行一次删除 […]

题目链接：B-Bitwise Exclusive-OR Sequence_第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳） (nowcoder.com) 题意 / Problem 给定N个点，M条边，点权未知但是每条边上的边权就是其所连接的两个点的点权的异或和。问怎样规划点权可以使得所有点的点权加和最小，输出最小和。 注意：图不一定连通。（这个特别坑！！！） 思路 / Though […]

题目传送门：I-Mr. Main and Windmills_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明） (nowcoder.com) 今天和学长进行了一场icpc昆明重现赛，被打爆了。这道题都没做出来，思路其实差不多了，但是考场上没想到可以用一个eps来解决斜率为无穷的情况，shit！ 题目大意 从点S，沿直线走到T点，问当点(x, y)恰好变化k次时，人所处的位置。 思路 […]