Home
Punipuni?
Cancel

「置顶」老年康复中心使用说明

年纪大了,玩不了刺激的题目,只做LeetCode简单题和Codeforces弱智题,当作休闲爱好 所以这里也没啥好看的,没事还是逛点别的网站吧 主站:记录工业垃圾 旧站:记录学业垃圾

Codeforces-1690A Print a Pedestal (Codeforces logo?)

Description 给定\(n\),求构造\(x + y + z = n\),其中\(x \gt y \gt z \gt 0\),要求\(x\)尽可能小,答案输出\(y, x, z\)。 Constraints \(6 \le n \le 10^5\) Solution 很显然要将三个数往\(n/3\)靠拢。观察\(n \% 3 = m\)的情况,在总和上补齐\(m\)即可,解法不唯一。 Code #include <bits/stdc++.h> using namespace std; int main() { int t; cin >&g...

LeetCode-935 Knight Dialer

Description 国际象棋中的马放在一个拨号器的任意位置,求走\(n\)步后能生成多少个电话号码。 1 2 3 4 5 6 7 8 9 * 0 # 拨号器如上表所示(其中*和#不可用)。 另外补充马的走法,如上图所示。 Constraints \(1 \le n \le 5000\) Solution 没啥意思的题目,思路见LeetCode-688,仅需消除后效性。 我本以为需要做一个转换表,比如\(convert[nums][8]\)表示数字\(nums\)能跳到哪里。其实是不需要的,因为电话上每个数字都是唯一的。 偶尔用点离谱的写法当题解吧。 Cod...

LeetCode-907 Sum of Subarray Minimums

Description 给定一个长度为\(n\)的数组\(a\),求该数组中所有子数组的最小值之和。 Constraints \(1 \le n \le 3 \cdot 10^4\) \(1 \le a_i \le 3 \cdot 10^4\) Solution 假设你知道每个最小值\(a_i = min\_v\)所覆盖的区间范围\([lo, hi]\),那么可以通过组合数得知子答案:\(sub\_ans_i = (i - lo + 1) * (hi - i + 1) * min\_v\)。 然后通过子答案之和就可以得到答案:\(ans = \sum_{i=0}^...

LeetCode-638 Shopping Offers

Description 你需要买\(n\)个商品,商品\(i\)需要的数目为\(needs_i\),单价为\(price_i\)。同时有\(m\)个打包优惠,每个优惠\(special_i\)均为一个长度\(n+1\)的数组,其中前\(n\)个元素对应商品\(i\)的数目,最后一个元素对应打包优惠价格。求最低买入价格。 Constraints \(1 \le n \le 6\) \(0 \le price_i \le 10\) \(0 \le needs_i \le 10\) \(1 \le m \le 100\) \(0 \le special_{ij} \...

LeetCode-149 Max Points on a Line

Description 给定\(n\)个整数点的二维坐标\((x_i, y_i)\),求最多的连在同一直线上的点数目。 Constraints \(1 \le n \le 300\) \(-10^4 \le x_i, y_i \le 10^4\) 不存在重复的点 Solution 计算几何就从来没做过,还好这题思路简单。 哈希表配合gcd记录斜率即可。需要注意的是横竖两种情况要特殊维护。 Code class Solution { public: int maxPoints(vector<vector<int>>& ...

LeetCode-678 Valid Parenthesis String

Description 给定一个长度为\(n\)的字符串\(s\)。每个字符只可能是:(、)或者*。其中*可以表示为(、)或者是空字符。问字符串\(s\)是否满足括号匹配。 Constraints \(1 \le n \le 100\) Solution 一眼区间DP。除了要求细心以外没啥特别的,只是个人想复习一下区间DP。 Code class Solution { public: bool checkValidString(string s) { bool dp[103][103] {}; bool vis[103][103] {...

LeetCode-446 Arithmetic Slices II - Subsequence

Description 给定一个长度为\(n\)的数组\(a\),求具有公差的子序列的方案数,子序列要求长度大于等于3。 Constraints \(1 \le n \le 1000\) \(-2^{31} \le a_i \le 2^{31}-1\) Solution 想到一个不好做的递推公式:设\(dp[i][j]\),表示以\(i\)结尾且公差为\(nums[i]-nums[j]\)的子序列方案数。设想美好但是推不动,似乎没法在\(dp[i-1][?]\)反推\(nums[j]\)…… 那改一改:设\(dp[i][d]\),表示以\(i\)结尾的公差为\(d...

LeetCode-312 Burst Balloons

Description 给定\(n\)个元素,值为\(a_i\)。每取出一个元素\(i\)可以得到贡献\(a_{i-1} * a_i * a_{i+1}\),注意这里\(i-1\)和\(i+1\)指的是当前相邻的元素,如果没有相邻元素则当作1。求取出所有元素的最大贡献。 Constraints \(1 \le n \le 300\) \(0 \le a_i \le 100\) Solution 一眼区间DP。 设\(dp[l][r]\)为区间\((l, r)\)的最大贡献,枚举区间中最后一个取出的元素\(i\),那么递推公式为\(dp[l][r] = max_{i...

LeetCode-632 Smallest Range Covering Elements from K Lists

Description 给定\(k\)个数组,从每个数组中各取最少一个数,使得取的数当中最大值与最小值之差最小 Constraints \(1 \le k \le 3500\) \(1 \le nums[i].length \le 50\) Solution 将所有数都放到一个数组中,标好归属的原数组编号并排序,然后跑一遍滑动窗口即可 Code class Solution { public: vector<int> smallestRange(vector<vector<int>>& nums) { ...

LeetCode-621 Task Scheduler

Description 给你一个用字符数组\(tasks\)表示的CPU需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在\(1\)个单位时间内执行完。在任何一个单位时间,CPU可以完成一个任务,或者处于待命状态。 然而,两个相同种类的任务之间必须有长度为整数\(n\)的冷却时间,因此至少有连续\(n\)个单位时间内CPU在执行不同的任务,或者在待命状态。 你需要计算完成所有任务所需要的最短时间。 Constraints \(1 \le task.length \le 10^4\) \(0 \le n \le 100\...

LeetCode-646 Maximum Length of Pair Chain

Description 给定\(n\)个区间\([lo_i, hi_i]\),求最长不重叠区间个数 Constraints \(1 \le n \le 1000\) \(-1000 \le lo_i \lt hi_i \le 1000\) Solution 解释同435 Code class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { ranges::sort(pairs, [](auto &a, aut...

LeetCode-629 K Inverse Pairs Array

Description 给定\(n\)和\(k\),求包含数字\(1 \ldots n\)且恰好有\(k\)个逆序对的数组方案数。答案对\(10^9+7\)取模 Constraints \(1 \le n \le 1000\) \(0 \le k \le 1000\) Solution 设\(dp[i][j]\)为使用\(1 \ldots i\)构成长度\(i\)的数组,且恰有\(j\)个逆序对的方案数。这里下标从1开始算起 问题在于怎么做状态转移 如果算出\(dp[i-1]\)的答案,把数字\(i\)插入到原\(1 \ldots i-1\)中,则得到\(dp[...

LeetCode-526 Beautiful Arrangement

Description 假设有从 \(1\) 到 \(n\) 的 \(n\) 个整数。用这些整数构造一个数组 \(perm\)(下标从 1 开始),只要满足下述条件 之一 ,该数组就是一个 优美的排列 : \(perm[i]\) 能够被 \(i\) 整除 \(i\) 能够被 \(perm[i]\) 整除 给你一个整数 \(n\) ,返回可以构造的 优美排列 的 数量 。 Constraints \(1 \le n \le 15\) Solution 状压DP,用\(dp[S]\)表示数字的选取情况 就凭感觉写的方案数,我也不知道为啥能AC Code clas...

LeetCode-1131 Maximum of Absolute Value Expression

Description 给定两个数组\(arr1\)和\(arr2\),求\(max\{ \ \mid arr1_i - arr1_j \mid + \mid arr2_i - arr2_j \mid + \mid i - j \mid \ \}\) Constraints 时间复杂度不超过\(O(n)\) Solution 这道题就是求三维的曼哈顿距离,每一个点\(i\)的坐标是\((x_i, y_i, z_i) \to (arr1_i, arr2_i, i)\)的形式 计算公式在未展开时为\(\mid \Delta x \mid + \mid \Delta y \mi...

LeetCode-354 Russian Doll Envelopes

Description 俄罗斯套信封问题,给定\(n\)封信,每一封信\(i\)有长宽\(h_i, w_i\),每一封信嵌套要求长宽均满足严格递增关系,问最多能嵌套多少封信 Constraints 时间复杂度不超过\(O(nlogn)\) Solution 二维LIS,使用排序降低维度,后面就是LIS模板 \(O(nlogn)\)的LIS忘记怎么写了,翻了下书 它的定义是比较特殊的:设\(dp[i]\)为长度为\(i+1\)的上升子序列中末尾元素的最小值 Code class Solution { public: int maxEnvelopes(vector&...

LeetCode-456 132 Pattern

Description Given an array of \(n\) integers nums, a 132 pattern is a subsequence of three integers \(nums[i]\), \(nums[j]\) and \(nums[k]\) such that \(i < j < k\) and \(nums[i] < nums[k] < nums[j]\). Return true if there is a 132 pattern in nums, otherwise, return false. Constrai...

LeetCode-1235 Maximum Profit in Job Scheduling

Description 有\(n\)个任务,每个任务需要在\([lo_i, hi_i]\)时间区间内调度并占用时间,可以从中获得\(p_i\)利润。求不重叠的任务调度能获得的最大利润 Constraints 时间复杂度不得超过\(O(nlogn)\) Solution 这题和630有点像,但是时间是固定的不能自由安排,固定的区间可以考虑dp 设\(dp[i]\):前\(i\)个区间子集合的最大利润。\(dp[i]\)需要找到某个\(j \in [0, i-1]\),使得\(dp[i] = max(dp[j] + p_i, dp[i-1])\) 为了能找到\(j\),原区间先...

LeetCode-315 Count of Smaller Numbers After Self

Description Given an integer array nums, return an integer array counts where \(counts[i]\) is the number of smaller elements to the right of \(nums[i]\). Constraints \(1 \le nums.length \le 10^5\) \(-10^4 \le nums[i] \le 10^4\) Solution 模板题,回顾一下也好 Code class Solution { public: v...

51NOD-1364 最大字典序排列

Description 给出一个\(1-N\)的排列,允许不超过\(k\)次操作,每次操作交换相邻两个数,求最大字典序排列 Constraints \(1 \le N \le 10^5\) \(0 \le k \le 10^9\) Solution 贪心局部解,先决定第一大的数尽量大,处理好后继续决定第二大。只需维护每步操作在\(O(logn)\)内 Code 忘记线段树怎么写了唉 Link 51NOD-1364 最大字典序排列

LeetCode-1673 Find the Most Competitive Subsequence

Description 给定字符串\(s\)以及常数\(k\),移除\(\mid s \mid - k\)个字符使得字典序最小 Constraints \(\mid s \mid\)不超过\(10^5\) Solution 单调栈秒了 Code class Solution { public: vector<int> mostCompetitive(vector<int>& nums, int k) { stack<int> stk; int max_delete = nums.size()...

LeetCode-122 Best Time to Buy and Sell Stock II

Description 炒股,每天股票有不同价格\(p_i\),你每天可以买卖股票,求最大利润 Constraints 要求时间复杂度不超过\(O(nlogn)\),\(n\)为交易日期长度 Solution 我不想说得太失礼,但这道题只看样例都知道答案了啊 但是重点还是学会证明 这道题等于算若干不重叠区间的两端差值,设第\(i\)个区间范围是\([L_i, R_i]\),即:\(\sum_{i=1}^{n}(p_{Li} - p_{Ri})\) 这里每个区间\(i\)的起点\(L_i\)、长度\(R_i - L_i + 1\)以及区间个数\(n\)均没有限制,目标是\(...

LeetCode-698 Partition to K Equal Sum Subsets

Description Given an integer array \(nums\) and an integer \(k\), return true if it is possible to divide this array into \(k\) non-empty subsets whose sums are all equal. Constraints \(1 \le k \le nums.length \le 16\) \(1 \le nums_i \le 10^4\) The frequency of each element is in the ra...

LeetCode-688 Knight Probability in Chessboard

Description 给定\(n \times n\)大小的棋盘,以及马的起始坐标\((row, column)\)(坐标是从0算起),求\(k\)次移动后马仍在棋盘上的概率 补充国际象棋中马的移动方式,见上图 Constraints \(1 \le n \le 25\) \(0 \le k \le 100\) \(0 \le row, column \le n - 1\) Solution 可以定义一个\(step\)来消除后效性 设\(dp[step][i][j]\): 从\((i, j)\)出发,走了\(step\)步仍在chessboard的概...

LeetCode-436 Find Right Interval

Description 给定\(n\)个区间\([lo_i, hi_i]\),每个区间的\(lo_i\)互不重复,求每一个区间的右侧区间下标。某区间\(i\)的右侧区间\(j\)指的是\(lo_j \ge hi_i\)且\(lo_j\)是所有可选答案中最小的那位 Constraints 时间复杂度不超过\(O(nlogn)\) Solution 不知道要说什么,总之排序就对了 Code class Solution { public: vector<int> findRightInterval(vector<vector<int>>...

POJ-1456 Supermarket

Description 给定长度为\(n\)的数组\(a[]\),每个元素\(a_i\)为\(\{p_i, d_i\}\),其中\(p_i\)表示贡献值,\(d_i\)表示期限,每个元素的贡献需要花费\(1\)时间单位,超过期限则无法贡献。求期限内最大的总贡献值 Constraints \(n\)不超过\(10^4\) Solution 这道题适合作为反悔贪心的第一题 从直觉来看,按照期限\(d_i\)进行排序。维护一个小根堆,堆上按照贡献\(p_i\)作为关键字,并且假设当前时间为\(x\),则堆大小也为\(x\) 维护反悔的过程:如果在\(d = 1\)选好了\(a_i...

LeetCode-435 Non-overlapping Intervals

Description 给定\(n\)个区间\([lo_i, hi_i]\),求最少移除区间数,使得剩余区间互不重叠 Constraints 要求时间复杂度不超过\(O(nlogn)\) Solution 很多年前做过的题,就是反过来求的最多不重叠区间,结论就是按右端点排序。但是为什么呢? 如果不介意看我用Microsoft Paint 11.2205.9.0画出来的玩意,那应该可以解释一下 首先假设从左到右处理,最左端的若干区间并没有重叠部分,那我们自然是选择最左边的区间开始;但是如果有重叠部分呢?比如我们现在选取了最左边的左端点\(L_i\)对应的区间,现在存在重叠了,...

LeetCode-316 Remove Duplicate Letters

Description 给定一个字符串\(s\),移除相同的字符使得每个字符只保留一份,且要求输出最小字典序 Constraints \(s\)的长度不超过\(10^4\) Solution 我讨厌字典序,用单调栈糊弄过去吧。意思很简单,就是看后面还有大字典序的话就pop() Code class Solution { public: string removeDuplicateLetters(string s) { stack<char> stk; int cnt[256] {}; bool in[256...

LeetCode-373 Find K Pairs with Smallest Sums

Description 给定两个已排序的数组\(nums1[]\)和\(nums2[]\),和一个常数\(k\)。设元组\(p(u, v)\)为从\(nums1[]\)拿取\(u\),且从\(nums2[]\)拿取\(v\) 返回\(k\)个元组\(p(u_i, v_j)\)使得它们的和最小 Constraints \(nums1[]\)和\(nums2[]\)长度不超过\(10^5\) \(nums1[i]\)和\(nums2[i]\)都在int范围内 \(k\)不超过\(10^4\) Solution 假设你拿了\(u_i\)和\(v_j\),那么可以确定...

LeetCode-719 Find K-th Smallest Pair Distance

Description 给出数组\(a[0, n)\),设距离\(d(i, j) = \mid a_i - a_j\mid\),求第\(k\)大距离 Constraints \(n\)不超过\(10^4\) Solution 排序然后二分答案,每次猜一个距离 Code class Solution { public: int smallestDistancePair(vector<int>& nums, int k) { std::sort(nums.begin(), nums.end()); int lo = 0...

LeetCode-1363 Largest Multiple of Three

Description 给出\(digits[]\)数组,每个元素范围\([1, 9]\),让它拼接出最长的能被3整除的字符串 Constraints \(digits[]\)长度不超过\(10^4\) Solution 首先,一个非负整数被3整除的性质是数位之和也被3整除;其次,可以用桶按\(%3\)进行分类讨论,这里筛除最小的无法拼凑的数位,剩下的只需按从大到小排列即可 Code class Solution { public: string largestMultipleOfThree(vector<int>& digits) { ...

LeetCode-201 Bitwise AND of Numbers Range

Description 给定两个整数\(lo\)和\(hi\),表示一个区间\([lo, hi]\),求该区间内AND操作后的结果 Constraints \(0 \le lo \le hi \le 2^{31} - 1\) Solution 拆成32位看,只要高位不一致,从\(hi\)到\(lo\)是要经历0-bit的 Code class Solution { public: int rangeBitwiseAnd(int left, int right) { int ans = 0; auto highFunc = [](int...

LeetCode-134 Gas Station

Description 在一条环路上有 \(n\) 个加油站,其中第 \(i\) 个加油站有汽油 \(gas[i]\) 升。 你有一辆油箱容量无限的的汽车,从第 \(i\) 个加油站开往第 \(i+1\) 个加油站需要消耗汽油 \(cost[i]\) 升。你从其中的一个加油站出发,开始时油箱为空。 给定两个整数数组 \(gas\) 和 \(cost\) ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 \(-1\) 。如果存在解,则 保证 它是 唯一 的。 Constraints \(1 \le n \le 10^5\) \(0 \le gas[i...

LeetCode-630 Course Schedule III

Description 给定一个数组\(a[1, n]\),每个元素\(a_i\)具有2种属性\(\{d_i, l_i\}\),其中\(d_i\)表示消耗时长,\(l_i\)表示最后期限(含)。每单位时长只能同时消费\(1\)个元素。求最多能消耗的元素个数 Constraints \(1 \le n \le 10^4\) \(1 \le d_i, l_i \le 10^4\) Solution 这道题适合作为反悔贪心的第二题。关联:第一题 数组按\(l_i\)排序,大根堆按\(d_i\)排序。这样保证了堆内操作时任意元素都是合法的 维护\(sum\)表示总时长,...

LeetCode-664 Strange Printer

Description TL;DR 粉刷匠 给定一个字符串\(s\)和空串\(t\),每次操作可以覆盖任意连续长度的字符,但必须是相同字符。求从\(t\)串到\(s\)串的最少操作次数 Constraints \(s\)长度不超过\(100\) Solution 区间DP即可 Code class Solution { public: int strangePrinter(string s) { int dp[102][102]; memset(dp, 0x3f, sizeof dp); for(int i = 0;...

LeetCode-546 Remove Boxes

Description TL;DR 消消乐 给出一个数组\(boxes[0, n)\),数组每个元素均为正整数。每一次操作可以从中消掉一些相同数值的元素,直至数组为空。每消除\(k\)个元素得到的贡献是\(k^2\),求最大贡献 Constraints \(1 \le boxes.length \le 100\) \(1 \le boxes[i] \le 100\) Solution 关键在于定义\(dp\)的含义:设\(dp[l][r][x]\)为区间\([l,r]\)且\(r\)右侧拥有与\(boxes[r]\)相同数值的\(x\)个元素 定义好就可以递推了...

LeetCode-502 IPO

Description 有\(n\)个项目,每个项目可以获得利润\(p_i\),但需要前提资本\(c_i\)才能启动。初始时你有资本\(w\),求最多\(k\)个项目的最大利润 Constraints 时间复杂度不超过\(O(nlogn)\) Solution 这种一眼是排序+堆操作的贪心,最近品鉴得有点多了。排序按能合法操作的来,堆按所求最优的做关键字,因此是按资本排序,并用利润作为大根堆关键字 剩下的就是一个模拟过程(这点有别于反悔操作) Code class Solution { public: int findMaximizedCapital(int k,...

LeetCode-480 Sliding Window Median

Description 给出数组\(nums[]\),窗口大小\(k\),求滑动窗口中的(排序后)中值。具体见下面样例: Window position Median --------------- ----- [1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3...

LeetCode-352 Data Stream as Disjoint Intervals

Description 给出数据流\(a[1...n]\),要求实现SummaryRanges类以提供三种操作: SummaryRanges():初始化流 void addNum(int value):添加value到流中 int[][] getIntervals():查询返回若干不相交的区间\([lo_i, hi_i]\)(按照\(lo_i\)排序) Constraints 最多\(3 \times 10^4\)次addNum(int value)和getIntervals()操作 最多\(10^2\)次getIntervals()操作 Soluti...

LeetCode-239 Sliding Window Maximum

Description 给出数组\(nums[]\),滑动窗口大小\(k\),求每个滑动窗口的最大值 Constraints \(nums[]\)长度不超过\(10^5\) \(nums[i]\)可以是负数 Solution 单调队列即可,维护单调最大值 Code class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { if(nums.size() <= k) return {*std::max...