共 102 篇文章
传送门 树状数组板子题。借这道题整理一下树状数组的模板 class NumArray { private: vector<int> tree; vector<int> arr; int n; int lowbit(int x) { return x & -x; } // 求前缀和 // [0, x) int query(int x) { int res = 0; for (int i = x; i > 0; i -= lowbit(i)) { res …
开篇文章记录一下C++在算法竞赛中好用的一些小技巧。 // string转int int num = atoi(str.c_str()); // 数组最大元素 int maxElement = *max_element(arr.begin(), arr.end()); // 数组最大元素下标 int *p = max_element(arr.begin(), arr.end()) - arr.begin(); // 数组最小元素 int minElement = *min_element(arr.begin(), arr.end()); // 判断是否是数字 if(isdigit(c)) // 计算一个数二进制形式数位中1的个数 __builtin_popcount(n) // 用数组初始化set // unordered_set也可以 set<int> myset(arr,arr+n) // 两个集合求交集 // 结果返回在ans数组里 set_intersection( set1.begin(), …
传送门 这是我做过最简单的 。 先考虑非法的情况。显然，如果n个缺失的骰子全置为6都不能使骰子值之和满足题设条件，这组数据就找不到合法答案。同理可得，n个缺失骰子全为1都不满足题设也是一种镜像情况。这样我们就得到了这道题的边界条件。 接着考虑合法解法。我们可以根据rolls数组之和与mean值计算出n个缺失数据的平均值，将这个值向下取整，就是每个缺失骰子的“最低值”。再依次给n个骰子分配点数，直到分完为止。这样就能依次得出合法的答案序列。 class Solution { public: vector<int> missingRolls(vector<int>& rolls, int mean, int n) { int m = rolls.size(); int tot = 0; for (auto roll : rolls) tot += roll; int idealSum = (n + m) * mean; if (idealSum - tot > n …
传送门 水题，一眼栈 class Solution { public: int calPoints(vector<string>& ops) { stack<int> stk; for (auto el : ops) { if (el[0] == 'C') { if (!stk.empty()) { stk.pop(); } } else if (el[0] == 'D') { int score = stk.top(); stk.push(score * 2); } else if (el[0] == …
传送门 对于任意一个数，×10就能使它尾部多一个0。分析一下样例，n=5时n!=12345=120，其实就是134(25) = 12 * 10。即，产生一个末尾0的原因是累乘的数里能凑一个“10”出来。那么我们只需要统计相乘的n个数有能凑几个10就行。更进一步简化， 由于10=2*5，且固定的范围内，因子5总是比因子2要少。所以，可以直接统计所有累乘的因子里5的数量。 class Solution { public: int trailingZeroes(int n) { if (n == 0) return 0; /* * 对于任意一个数，×10就能使它尾部多一个0 * 分析一下样例，n=5时n!=1*2*3*4*5=120，其实就是1*3*4*(2*5) = 12 * 10 * 即，产生一个末尾0的原因是累乘的数里能凑一个“10”出来 * 那么我们只需要统计相乘的n个数有能凑几个10就行 * 更进一步简化， 由于10=2*5，且固定的范围内，因子5总是比因子2要少 * 所以，可以直接统计所有累乘的因子里5的数量。 */ int cnt = 0; for (int i …
传送门 二维前缀和，定义f[i][j]为从矩阵左上角(0,0)到当前位置(i-1,j-1)的元素之和，那么任意一个3x3小矩阵内的9个元素之和就是tot=f[i+2][j+2] - f[i+2][j-1] - f[i-1][j+2] + f[i-1][j-1] 提一下这个状态转移方程需要注意的几个点：因为多减了一次f[i-1][j-1]，所以要加回来；f[i][j]做了下标偏移是因为需要用到f[i+2][j-1]和f[i-1][j+2]来计算区域和。 class Solution { public: vector<vector<int>> imageSmoother(vector<vector<int>>& img) { int m = img.size(); int n = img[0].size(); vector<vector<int>> f(m+1, vector<int>(n+1)); vector<vector<int>> ans(m, vector<int>(n)); // 二维前缀和 // f[i][j]表示从(0,0)到(i-1,j-1)的区域内元素之和 // 比起传统的二维前缀和，做了下标偏移 // 因为后面计算时需要用到f[lx][ry+1]和f[rx+1][ly]计算区域和 for (int i = 1; i <= m; …
传送门 思路 往位运算想就是想复杂了。根据题目意思，perm[i]的范围是[1,n]，且每个perm[i]不重复。这就意味着perm[0]^perm[1]^...^perm[n]是已知的。 假设： perm=[a,b,c,d,e]，encoded=[f,g,h,i]; 显然有： f = a^b; g = b^c; h = c^d; i = d^e; 我们再设已知的perm[0]^perm[1]^...^perm[n]=k，根据异或的性质：一个数异或自己得到0，任意一个数异或0等于它自己。所以我们可以用k去异或g = b^c与i = d^e来让k==a，这样我们就算出了perm[0]。再根据递推关系perm[i+1] = perm[i]^encoded[i]就可以算出整个perm。 代码 class Solution { public: vector<int> decode(vector<int>& encoded) { vector<int> perm; int a = 0; const …
一级标题 行内代码 import os def fun(): return "python" class Solution { public: int minDays(vector<int>& bloomDay, int m, int k) { const int n = bloomDay.size(); if (m * k > n) return -1; vector<bool> flag(n); int l = 0, r = *max_element(bloomDay.begin(), bloomDay.end()); while(l < …
传送门 思路 题目是很标准的“找到最大或最小”，也就是说假设正解为ans，(-∞,ans)范围内都无法满足题设条件，而[ans,+∞)都能满足要求，且ans是满足要求的值中最小的那个，这样ans就是一个“合法与非法”的分割点。对于形如这样的题设，就可以对答案序列进行二分来在一个较优的复杂度内枚举到答案。 就本体内容具体地看，天数显然就是我们二分的目标。枚举的左边界是0，右边界是bloomDay中最大值，这是显然地。 每次获取一个mid，然后去检查这个天数mid能否满足要求。如果可以的话，说明mid落在了[ans,+∞)范围内，令r=mid，继续； 如果不可以满足要求，那么说明mid落在了(-∞,ans) 范围内，令l=mid+1，缩小范围继续查找。 值得一提的是，与传统的二分不同，我们在缩小右边界时并非是r=mid-1，这是因为答案区间[ans,+∞)是左闭右开的，是可能存在r==ans的，如果这时还去-1，就会导致答案错误。 代码 ```cpp class Solution { public: int minDays(vector& bloomDay, int m, int k) { const int n = bloomDay.size(); if (m * k > n) return -1; vector flag(n); int l = 0, r = *max_element(bloomDay.begin(), bloomDay.end()); …
传送门 思路 题目读完，很容易想到DFS的思路，很快就可以撸一个标准的dfs解法： ```cpp class Solution { public: int ans = INT_MAX; int minimumTimeRequired(vector& jobs, int k) { vector works(k); const int n = jobs.size(); dfs(0, works, jobs, 0, n, k); return ans; } void dfs(int now, vector& w, vector& j, int maxn, int n, …
传送门 思路 记录这道题主要是为了记录二位前缀和的做题思路，毕竟CSP都遇见现题了，当时还只过了8个点... 其实前缀和也是一种形式的dp，这里借用LeetCode-304官方题解的图片，它画得很清晰了 [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2021/04/1614650837-SAIiWg-1-1024x576.png 我们设dp[i][j]表示从矩阵左上角(0,0)到当前位置(i,j)的所有值之和，则不难得出图中的转移方程。减去dp[i-1][j-1]的原因是它在计算dp[i][j-1]+dp[i-1][j]中被计算了两次，要减掉多余的那一次。 这种思路在LeetCode周赛#225的T3中也有体现。 当我们对所有的(i,j)都算出前缀和后，用四重循环去依次枚举每一对左上角与右下角就行了。虽然纸面复杂度有O(n²* m²)，但每一个右下角一定在左下角后面，所以对右下角的枚举并没有严格的平方级复杂度，所以还是能把题混过去的。 代码 ```cpp int sum[110][110]; class Solution { public: int maxSumSubmatrix(vector>& mat, int k) { int m = mat.size(), n = mat[0].size(); for(int i = 1; i <= m; …
传送门 T1：截断句子 思路 签到题，用python会比cpp简单很多。直接按空格split然后分片就行。 代码 ```python class Solution(object): def truncateSentence(self, s, k): """ :type s: str :type k: int :rtype: str """ ss = s.split(" ") if k == len(ss): return s ans = " ".join(ss[:k]) return ans ``` 赛后感觉写的太冗长了，可以精简成一句： ```python class Solution(object): def truncateSentence(self, …
传送门 拿到这题第一思路肯定是n³直接暴，但肯定会超时，事实上定一动二的n²都能超，那么根据传统优化思路，只枚举一个就行。 根据枚举位置的不同，有两种不一样的思路。 方法一：有序集合(枚举k) 思路 枚举j，即寻找一个满足“i<j<k且nums[i]<nums[k]<nums[j]”的j。因为最左侧的i同时满足下标最小与值最小，所以可以用一个变量来记录当前最小值，也就省去了枚举i的开销。 在这同时，用一个有序集合来维护自当前枚举的位置到nums尾部的序列，它的作用是从其中找k。 在枚举时，没枚举到一个j，就从该有序集合中找到“第一个大于nums[i](也就是上文提到过的'当前最小值')的值”，根据贪心思想，它就最可能是满足条件的k。如果此时的nums[j]大于该值，则可以直接返回true；否则维护nums[i]的最小性，维护该有序集合的长度，再进行下一轮枚举，直到尾部。 代码 ```cpp class Solution { public: bool find132pattern(vector& nums) { // 左区间最小值 int left = nums[0]; // 右区间序列 multiset right; const int n = nums.size(); if (n < 3) { return false; } // 右维护 for …
传送门 思路 这题其实挺基础的，开这篇博文也只是为了记录一下该类“异型遍历”题型的套路，主要就是突出一个代码清晰逻辑明确。 代码 ```cpp class Solution { public: vector spiralOrder(vector>& matrix) { vector ans; int left = 0; int right = matrix[0].size() - 1; int top = 0; int bottom = matrix.size() - 1; int area = matrix.size() * matrix[0].size(); // 一圈一圈向内收 while (area …
传送门 思路 最粗暴的方法就是O(n²)，这题也没卡暴力，可以击败5%混过去，但可以用单调栈来优化。 众所周知，单调栈致力于解决“寻找首个大于(小于)当前位置的值”，要明白单调栈的优势，就要搞清楚它的原理。 常规方法慢在挨个枚举，对每个元素都去一个个的找满足条件的值，那自然是慢的。如果说暴力的思路是“用每个值去找答案”，那单调栈的思路可以形象地理解为“让答案自己去找值”。 就本题而言，单调栈中存的是还没有找到答案的下标，他们自底向上严格上升。在遍历中，如果当前栈顶下标对应的值比nums[i]小，那么nums[i]就是当前值答案，将nums[i]计入ans中并弹出当前下标即完成一次操作。 这样做的正确性是显然地，因为有栈的后入先出特性做保证，当前nums[i]一定最有可能是栈顶元素的答案。 更具体地，因为这题是循环数组，所以需要遍历两次，初始化ans数组为全-1就可以避免最后再来为栈内未出栈的元素赋-1的操作。 代码 ```cpp class Solution { public: vector nextGreaterElements(vector& nums) { const int n = nums.size(); stack stk; vector ans(n, -1); stk.push(0); for (int i = 0; i < n; i++) { while(!stk.empty() && nums[stk.top()] < nums[i]) { …
Trie树是一个很有价值的中级数据结构啊，花点功夫再深究一下。 模板 Trie树的实现比较特殊，每一个节点上不是一个单独的字符，而是一个映射表： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2021/02/image-1-1024x686.png 如上图所示，每一个节点里包含当前位置字母的一个映射表，然后再有每个字母指向下一层节点。 代码 ```cpp class Trie { private: bool isEnd; Trie *next[26]; public: /** Initialize your data structure here. */ Trie() { isEnd = false; memset(next, 0, sizeof(next)); } /** Inserts a word into the trie. */ void insert(string word) { Trie *node = this; …
传送门 思路 这是一道hard题，但感觉并不是很hard。 题目要求一个无向图在保证其连通性下能删除的最大边数。那么用并查集的思想，可以理解为“给一个n个节点的图添加数量最少的无向边使其连通。” 为Alice和Bob两人各单独维护一个并查集，挨个加入每条边。如果当前边的两个顶点已经连通了，那么这个边就是一个多余边，直接计数器++。 值得注意的是，添加边的时候应该优先考虑type3的边，即公共边。因为公共边是共用的，考虑一种极端情况：对于同一个图，图中仅有type1、2边与仅有type3边。 因为对于每一个人，都要确保图的连通性，所以前者情况下，边数需要2*n=2n条，因为私有边不能公用；而后者情况下仅需要n条边，因为type3的边可以共用。以这个极端例子可以讨论在添加边的时候公有边优先级更高。 考虑非法状态，如果题目所给图对于二人中至少一人是非连通的，那么显然应该返回-1。 代码 ```cpp class Disjoint { private: unordered_map father; unordered_map rank; public: int cnt; void init(int n) { cnt = n; for (int i = 0; i < n; i++) { rank[i] = 1; father[i] = …
传送门 T1替换隐藏数字得到的最晚时间 思路 签到题，注意一些细节就行。 代码 ```cpp class Solution { public: string maximumTime(string time) { if (time[0] == '?' && time[1] >= '4' && time[1] != '?') time[0] = '1'; else if (time[0] == '?') time[0] = '2'; if (time[1] == '?' && time[0] == '2') …
传送门 思路 力扣这个月的daily哟，已经变成了并查集的形状了。 题意很裸，本质上就是求联通分量的个数，和LeetCode每日一题：移除最多的同行或同列石头很像。两个连通分量相接通需要1条边，n个就需要n-1条边，求这个n并返回n-1作为答案就行了。 根据题设，显然有connections.size() < n-1时，返回-1. 代码 ```cpp class Solution { private: unordered_map father; unordered_map rank; public: int cnt; void init(int n) { cnt = n; for (int i = 0; i < n; i++) { rank[i] …
传送门 思路 题意挺简单的，就是在一个直角坐标系内给出若干点，求一个最小生成树，可以用prim直接写，也可以建图用 并查集维护边集再Kruskal。二者的介绍详见博客：最小生成树--Prim算法&Kruskal算法。 代码 prim ```cpp class Solution { public: int minCostConnectPoints(vector>& points) { const int n = points.size(); int ans = 0, mp[1005][1005], dis[1005]; bool flag[1005]={0}; memset(dis, 0x3f, sizeof(dis)); for (int i = 0; i < n; i++){ for (int j = …
传送门 T1 可以形成最大正方形的矩形数目 思路 签到题，半分钟直接来。 代码 ```cpp class Solution { public: int countGoodRectangles(vector>& rectangles) { int ans = 0; int maxLen = -1; for(auto el : rectangles) { maxLen = max(maxLen, min(el[0], el[1])); } for(auto el : rectangles) { if(min(el[0], el[1]) == maxLen) { …
传送门 思路 可以把所有在同一行和同一列的石子连起来，这样就能构成若干个连通分量。而根据题意，不难想到每一个连通分量最后都能删到只剩一颗石子，所以答案显然就是石子总数减去连通分量的个数。 用并查集来维护连通关系。 代码 第一种是最直接的O(n²)连图。 ```cpp class Solution { private: unordered_map father; unordered_map rank; public: int cnt; void init(int n) { cnt = n; for(int i = 0; i < n; i++) { father[i] = i; rank[i] = 1; } } int …
法1：hash 思路 很简单的思路，用一个hash表，键为字符，值为一个pair，pair的first成员存字符的出现次数，second成员为该字符的下标，维护一个下标最小值为答案即可。 代码 ```cpp class Solution { public: int firstUniqChar(string s) { unordered_map> mp; for(int i = 0; i < s.size(); i++) { mp[s[i]].first++; mp[s[i]].second = i; } int pos = INT_MAX; for(auto el: mp) { if((el.second).first == 1) { pos = min(pos, (el.second).second); } } return …
传送门 思路 很标准的dp。设dp[i]为当前状态下最小花费，因为可以一次爬一步或者一次爬两步，所以dp[i]=min(dp[i-1], dp[i-2])+cost[i]。又因为可以从第0级或第1级台阶开始爬，所以初始状态为dp[0]=cost[0],dp[1]=cost[1]。 值得注意的是，这题判断到达终点的条件并不是走到最后一级(cost.size()-1)，你直接跨过去也算，也就是说在倒数第二级台阶上时你直接上两级也算为上到顶(或者理解为最后一级台阶之后还有一级无消耗的台阶)，即第一组样例给出的情况。对于这种特殊情况，我们手动给cost数组pushback一个0就行了。 代码 ```cpp class Solution { public: int minCostClimbingStairs(vector& cost) { int dp[1010]; cost.push_back(0); dp[0] = cost[0], dp[1] = cost[1]; for(int i = 2; i < cost.size(); i++) { dp[i] = min(dp[i-1], dp[i-2]) + cost[i]; } return dp[cost.size() - 1]; } …
传送门 T1重新格式化电话号码 思路 周赛经典的字符串处理题。难倒是不难，但是处理起来感觉比往期的签到题麻烦不少啊... 主要思路就是replace掉'-'与空格，然后每三个一组分片，塞进列表，最后再对单出来的元素特殊处理。 代码 ```python class Solution: def reformatNumber(self, number: str) -> str: number = number.replace('-', '').replace(' ', '') ans, N = [], len(number) for i in range(0, N, 3): ans.append(number[i:i+3]) if len(ans[-1]) == 1: last = ans.pop() sec_last = ans.pop() ans.append(sec_last[:2]) …
传送门 好水的周赛啊，建议改名为Python赛 T1-设计 Goal 解析器 简单的字符串模拟题，别像我一样看到括号就栈栈栈qaq。 我是用Python replace搞的，这样会简洁不少，贴一个lc评论区C++简单模拟的。 Python ```python class Solution(object): def interpret(self, command): command = command.replace('()', 'o') command = command.replace('(al)', 'al') return command ``` C++ ```cpp class Solution { public: string interpret(string command) { string ans = ""; int i = 0; int …
最近几天LeetCode高强度推送单调栈的题目，以往对这个数据结构的认识都只是停留在肤浅的表层上，看了这些题目后发现这个看似简单的栈结构其实用法很多，也很灵活，于是单独开一篇文章记录学习。 单调栈介绍 顾名思义，单调栈是满足一定单调性的栈结构。现在我们通过模拟实现一个单调递减栈来了解它具体的结构。 有一组数[10,3,7,4,12]。从左到右依次入栈。当且仅当栈为空或入栈元素值小于栈顶元素值时入栈；否则将所有比入栈元素小的元素全部出栈，再进行入栈操作，以确保栈的单调性不被破坏。 10入栈时，栈为空，直接入栈，栈内元素为10。3入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。7入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7。4入栈时，栈顶元素7比4大，则入栈，栈内元素为10，7，4。12入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。 单调递增的栈反之即可。了解了单调栈的概念，接下来就该撸题了。 单调栈例题 LeetCode-402：移掉K位数字 传送门 思路 题目要计算一个整数去掉k个数位后的最小新整数。最直接的思路就是枚举每一种取法然后维护最小值，但这么做的复杂度显然是指数级，不能这么莽。 考虑O(n)的方法：从左到右遍历num，对每一位数字决定它是否保留，这个操作执行k次即可。那么以什么依据来判断当前数字是该留还是该舍呢？ 假设有两个数字，123a456与123b456，怎么去判断它们谁大谁小呢？显然，a>b时前者大于后者，反之亦然。即，判断两个数大小关系的依据是两者第一个不同的数位大小关系。 根据上面的思路，我们只需要在枚举到每一位的时候去维护一个局部单调递增栈作为答案就好了。为什么是“局部”递增栈呢？因为题目要求我们要去掉k位数位，单调栈在不满足入栈条件的情况下会一直弹出栈内元素直到满足入栈条件，我们显然不能让它把答案全弹出去，所以当不能再弹的时候(即(n-k)-ans.size()>=n-i时)就继续去枚举下一位数位。 代码 ```cpp class Solution { public: string removeKdigits(string num, int k) { int n = num.size(); string ans = ""; if(n == k) return "0"; if(k == 0) return num; for(int …
传送门 题目意思很好理解，就是维护一个单调栈。 ```cpp class Solution { public: vector mostCompetitive(vector& nums, int k) { int n = nums.size(); if(k == n) return nums; stack st; for(int i = 0; i < n; i++) { while(!st.empty() && st.top() > nums[i] && k - st.size() < n - …
传送门 好久没写博客了啊...考试周真是烦人。216周赛可以说是最简单的一次周赛了吧，贪就vans了。 T1 检查两个字符串数组是否相等 签到打卡。 ```cpp class Solution { public: bool arrayStringsAreEqual(vector& word1, vector& word2) { string str1 = "", str2 = ""; for(auto el : word1) { str1 += el; } for(auto el : word2) { str2 += el; } return str1 == …
传送门 题目描述 给定一个起始单词，一个目标单词与一个备选字典，通过以下规则将起始单词变到目标单词去： 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 求最短变化步数。 思路 看到最短步数，首先想到BFS。但使用BFS的前提是有一个可以用来搜索的图或者树，于是思维转向如何建立图/树。 思路还是很清晰的：任何两个只差一个字母的单词之间可以连成一条无向边，所有的边共同构成整张单词图。建成图后再判断endWord是否在图中就行了。真正复杂的地方在实现。 单个的字符串并不好节点化，我们可以把每个单词映射为一个id值，然后用一个int的邻接矩阵来存储整个词图。 对于添加边的操作，朴素思路枚举每一对单词，判断它们之间是否可以存在一条边，如果是，则将其加入词图，但这样显然太慢了。 可以考虑构造间接节点。假设当前单词为hit，那么显然地，_it、h_t、hi_三个长相的单词都可以与hit连成一条边。那么我们只需要构造出这三个间接节点，然后将当前单词连在间接节点上就行了。不难得知，每一个可以与hit连边的单词都一定会连向这三个间接节点。 值得注意的是，这样的操作虽然节省了时间，但人为的增加了一些“不需要的边”。假设有两个相邻单词，他们原来可以直达彼此，现在需要通过间接节点来访问，所以说真实的步数应该等于当前步数/2。又因为初始化时会将beginWord也加入词图，所以最后的总步数还得额外的+1。 代码 ```cpp class Solution { public: unordered_map wordId; vector> mp; int idNum = 0; void addWord(string& str) { if(!wordId.count(str)) { wordId[str] = idNum++; mp.emplace_back(); } } void addEdge(string& …
传送门 题目大意 在一条只能前进后退的一维路径上，给定起点n与重点k，只有三种移动方式： 前进一步后退一步使坐标变为当前值的两倍 问走到终点最短需要几步。 思路 很经典的bfs板子题，直接bfs去枚举每一种走法。每次操作依次将三种移动方式计算所得的目标坐标放进队列，然后出队判断就行了。 代码 ```cpp #include #include #include #include using namespace std; const int LIM = 100000; queue que; bool vis[LIM + 10]; int steps[LIM + 10]; int bfs(int n, int k) { int now, next; que.push(n); …
传送门 题目大意 一个序列s，题目定义两种编码方式： 第一种方式是p，其中pi表示第i个右括号之前的左括号数；第二种是w，其中wi表示第i个右括号(包括它本身)之前完成匹配的括号对数。 现给出序列s在p方式下的编码，求出它在w方式下的编码序列。 思路 已知条件是p序列，那就从p序列入手。 对于pi，设j<i，那么pi-pj的含义显然是第j个右括号与第i个右括号之间的左括号数。而且不难得知，wi能达到的最大值就是i-j，因为括号能匹配成功的前提是有富余的右括号。那么按照这个逻辑去枚举每一对(i,j)就行了。 代码 ```cpp #include #include using namespace std; int t, n; int str[110]; int main() { cin >> t; while(t--) { cin >> n; for(int i = 0; i < n; i++) { scanf("%d", &str;[i]); int j = i - …
传送门 题目大意 给定一个由10种字符(p,q,r,s,t,N,K,A,C,E)组成的逻辑表达式，其中pqrst为逻辑变量，NKACE为逻辑运算符，他们的含义分别是 K==and：x && yN==not：!xA==or：x || yC==implies：(!x)||y E==equals：x==y 要求判断这个逻辑表达式是否为重言式，如果是就输出tautology，否则输出not 思路 根据题设，我们不难判断，单目运算符一定在整个字符串的后半部分，双目运算符一定在整个字符串的前半部分。例如ApNp，它应该被判为A(p,N(p))，所以上述结论的正确性是显然的。那么就可以像常规的表达式计算一样，从尾部压入栈，然后弹一个计算一个。 因为只有5个逻辑变量，所以最多只会有2^5=32种情况，依次枚举就好。 代码 我的写法 五重循环枚举每一位，最内层去枚举长度。 ```cpp #include #include #include #include using namespace std; string str; bool input(stack& sta, char ss, int p, int q, int r, int s, int t) …
传送门 题目大意 用2x1与2x2的小方块去填满一个2xn的长条形区域，问有多少种填法。 思路 很标准的dp。假设当前填到第i个位置，那么能继续往后推进的办法只有三种：竖着放一个2x1的方块，或者横着放两个2x1的方块、亦或者直接放一个2x2的方块。即，dp[n]的填法直接取决于dp[n-1]与dp[n-2]。 在n-1时只有一种方法可以填，所以dp[n-1]对dp[n]的贡献就是1*dp[n-1]；在n-2时有三种方法：竖着放俩、横着放俩、放块大的，因为“竖着放俩”的方法与n-1时重叠了，所以dp[n-2]对dp[n]的贡献就是dp[n-2]*2，最终得到转移方程： ```cpp dp[n] = dp[n-1] + dp[n-2] * 2; ``` 样例很善良的提醒了我们这题还是一个大数题目，所以用string来模拟大数加法，避免爆变量。 ```cpp string add(string a, string b) { //维护a长于b if(a.length() < b.length()) swap(a,b); //进位值 int up = 0; //自尾向头计算 for(int i = a.length() - 1, j = b.length() - 1; …
传送门 题目大意 一个学校有n(n<=50000)个学生，他们都可能信仰不同的宗教，你不能一个一个去问他们的信仰，但你可以通过询问得知两个学生的信仰是否一致，询问有m(m<=n*(n-1)/2)次。通过询问你可以知道校内学生的信仰总数上限，找到这个上限作为答案。 思路 其实就是一个并查集，题目翻译过来就是说给你一个图与它的一些边，找到所有的联通分量。 代码 ```cpp #include #include #include #include #include using namespace std; const int N = 55000; int cnt; int n, m; int dad[N]; void init(int top) { for(int i = 1; i <= top; i++) { …
传送门 冷知识：Y2K就是常说的千年虫。（这题的题意是真的搞，建议语文太差的人不要参与出题） 题目大意 微软公司每个月都可能盈余s元或者亏损d元，但具体是盈余还是亏损不知道。知道的是每连续的五个月统计一次总收入，都是亏损的(不难知道这样的统计一共有八次)。现问在这种条件下一年到头能盈利吗？如果能，找出最大盈利，如果不能就输出"Deficit"。 思路 这题抛开晦涩难懂的题干，其实挺简单的，两位数的数据范围，怎么都能过。有一种做法是统计出所有可能出现的盈亏情况，然后直接对sd判断就行了。 但我本着练算法的原则刷oj，肯定还是采用贪心的思路。 先假设每个月都是盈利的，然后对每个连着的五个月进行判断。如果满足题设的“亏损”条件，就挪到下一个连续的五个月继续判断；如果不满足，就将当前五个月中最后一个不亏损的月份置为亏损，继续上述操作。 代码 ```cpp #include #include #include using namespace std; int s, d; int arr[20]; int calcSum(int pos) { int res = 0; for(int i = pos; i < pos + 5; i++) res += arr[i]; …
传送门 题目大意 假设海岸是一条无限长的直线。陆地在海岸的一边，海洋在另一边。每个小岛都是位于海边的一个点。而任何位于海岸线上的雷达装置，只能覆盖d距离。所以如果小岛与一个雷达之间的距离最多为d，那么它可以被这个雷达覆盖。 我们使用笛卡尔坐标系，定义海岸是x轴，海边在x轴上方，陆地在下方。给定海洋中每个岛屿的位置，给定雷达装置覆盖的距离，你的任务是编写一个程序，找到覆盖所有岛屿的最小数量的雷达装置。请注意，岛屿的位置由其(x,y)坐标表示。如果无法完成覆盖，则输出“-1”。 思路 给定覆盖半径与一系列散点，问最少用多少雷达可以覆盖到所有小岛。 很明显是一个贪心问题。在思考贪心策略之前我们需要考虑一下输出“-1”的情况。首先，因为雷达只能装在岸边，所以如果至少存在一个点，它距岸边的距离大于雷达半径，显然就无法完成覆盖了。其次，数据中存在d<0的情况，这种情况也是输出-1. 接下来思考贪心。要让雷达尽可能少，那就要让每个雷达尽可能的多覆盖小岛。如何去判断多个小岛能否被同一个雷达覆盖就成了这道题的核心问题。 以每个岛屿为圆心，d为半径做一个新圆，圆与x轴相交的两点会构成一个区间。不难想到，如果任意两个岛屿的区间存在重合，那么它们就能被同一个雷达覆盖。 所以对每个岛屿计算出它的区间值，以左边界为关键字排序，然后去判断就行了。 代码 ```cpp #include #include #include #include #include #include #define PAIR pair using namespace std; const int N = 1010; int n, d, cnt; class Node { public: int …
传送门 经 典 老 番 最近算法课讲到递归，顺手写一点经典的回溯题来巩固基础。 回溯是一种通过枚举出所有可能情况来得到解答的算法，很直白也很经典。当确定当前情况不是解或不是最后一个解时，算法会逐步退回到之前的步骤，通过更改部分组成来枚举下一种情况。 放在这道题里，要得出n个数的全排列，不难得出它的递归思路，设cur为当前操作到的元素下标： cur==n，排列完了所有数，当前排列作为一个答案存储。cur<n，考虑第cur个位置填哪个数。这个数不能被用过，所以需要借助一个vis数组来判断。如果vis[nums[cur]]==0，那么可以填入当前数，填入后继续递归dfs(cur+1,n,nums)执行下一次操作。 回溯时会撤销这个被填入的数与标记，并尝试下一个数。 上述思路是回溯的基本想法，但就这题而言可以避免vis数组的使用，以节约少部分空间。 上述算法需要借助标记数组，是为了去判断当前数可否填入。 考虑一种新的做法，以cur为界，左边是已经执行过操作的数，右边是等待操作的数。为了维护这种结构，可以使用swap直接在nums数组上操作。 ```cpp class Solution { private: vector< vector > ans; void dfs(int cur, int len, vector& nums) { if(cur == len) { ans.push_back(nums); return; } for(int i = cur; i < len; i++) { …
传送门 题目大意 《飞行员兄弟：跟随条纹象》游戏中有一个任务，玩家需要打开一个冰箱。冰箱门上有16个把手。每个把手都可以处于两种状态之一：打开或关闭。只有当所有把手都打开时，冰箱才是打开的。手柄用矩阵4х4表示。你可以在任何位置(i,j)改变一个把手的状态(1≤i, j≤4)。然而，这也会同时改变第i行和第j列的所有手柄的状态。你的任务是找到打开冰箱所需的最小把手切换次数。 思路 与poj1753类似，每个格子只有0或1两种状态，那么只有奇数次的操作是有效地。结合题目4x4的小规模，考虑直接枚举答案。 接下来就是思考枚举方式。因为我们知道偶数次的操作等于没有操作，那么我们可以等效处理：在对(i,j)进行切换操作时，同时对同行列的把手也进行一次操作，那么整个过程等效为仅对(i,j)进行了一次有效操作。 [图片缺失] 原图：https://images0.cnblogs.com/i/470524/201407/281650033524598.png图源：https://www.cnblogs.com/Java-tp/p/3873557.html 参照上图，黄色区域的方格被操作了两次，等效为0次；红色区域的方格被操作了四次，等效为0次；黑色方格被操作了七次，等效为1次。 那么我们就得到了一个策略：在对某个方格(i,j)进行切换时，同时对同行列的方格也进行切换就能确保只改变(i,j)的状态。 那么我们只需要对所有"+"执行上述策略，并记录相关方格被操作的次数，最后在统计被操作数是奇数的方格就能得到所有有效操作。 代码 ```cpp #include #include using namespace std; int ans = 0; int cnt[5][5]; bool mp[5][5]; void switchOn(int x, int y) { for(int i = …
传送门 题目大意 Flip Game是在一个4x4的矩形棋盘上进行的游戏，16个方格中的每一个方格上都放置了有两面的棋子。每块棋子的一面是白色的，另一面是黑色的。每一轮你都要翻转3到5个棋子，从而将其上边的颜色从黑色变为白色，反之亦然。每轮要翻转的棋子按照以下规则选择。 1、在16枚棋子中任选一枚。 2、将所选棋子和所有相邻棋子向左、向右、向上、向下翻转（如果有的话）。游戏的目标是翻转所有棋子白面朝上或所有棋子黑面朝上。你要写一个程序，寻找实现这个目标所需的最少回合数。 思路 一个棋子有且仅有两个状态，非黑即白。所以，对同一颗棋子而言，翻动偶数次显然是没有意义的，只有奇数次的翻动才会改变棋子状态，所以只用考虑第一次翻面操作。一共十六个格子，最多16步就能全部翻完，所以从0~16枚举每个操作，只要某一次成功了，这次的步数就是最优的。 用dfs来翻，如果到叶子节点还没成功就回溯。需要注意的是回溯需要把之前翻过的所有棋子翻回来。 代码 ```cpp #include #include using namespace std; int ans; bool flag; bool mp[5][5] = {0}; //方向数组: //左、右、下、上、中 const int dx[5] = {-1, 1, 0, 0, 0}; const int dy[5] = {0, 0, -1, 1, …
为了提升自己的码力，我会去做一些LeetCode上的专题练习，我认为它们都很有价值，于是专门开一篇文章来记录我刷专题的痕迹。 以下内容按时间升序排列。 dp专题训练查找表类算法专题训练二叉树专题训练数组与字符串专题训练
传送门 之前忙着开学，有相当一段时间没有做题了，实在是罪过... 数组 t1寻找数组的中心索引 找到数组中的一个位置，这个位置之前的所有元素和等于这个位置之后的所有元素和。如果没有就返回-1。 感觉思路有点滑动窗口的味道。维护两个变量lsum与rsum，分别表示当前位置左边的元素和与右边的元素和，然后根据题意O(n)遍历判断就行了。 ```cpp class Solution { public: int pivotIndex(vector& nums) { int rsum = 0, lsum = 0; const int n = nums.size(); if(n == 0) return -1; for(auto& el: nums) rsum += el; rsum -= nums[0]; if(rsum == 0) return …
传送门 t1 圆形赛道上经过次数最多的扇区 有一个圆形区域，被分成n块扇区，给出一系列起点与终点，问跑到最后经过次数最多的扇区是哪些。 赛时居然没过这题... 当时写了一个模拟，因为没处理好边界问题，死活过不去。赛后下来看了发现确实想复杂了。 我们要发现一个事实，因为赛道是圆形的，所以除了结尾的那一圈“不完整”的赛程，之前若干圈赛程都是没有意义的，因为每个扇区都同时累加了经过次数，“同时”在本题中是没有讨论意义的。所以我们的答案只用关注最后那不完整的赛程经过了哪些扇区。 值得注意的是，起点不一定是第一块扇区，所以要处理越界问题。同时，观察样例不难发现答案是有序的，所以还要对最终答案数组做一个排序。 ```cpp class Solution { public: vector mostVisited(int n, vector& rounds) { vectorans; int l = rounds[0]; int r = rounds[rounds.size()-1]; while(l != r) { if(l == n+1) { l %= n; continue; } ans.push_back(l++); } ans.push_back(r); …
传送门 t1 千位分隔数 给定一个整型数，给它每三位加上一个分隔符。 做法有很多，憨一点可以用取出每一位数字来做，但看这个范围估计是要炸的，所以我这里选择转成string来做。 转成string，计数，每三位加上一个"."最后翻转一下就行了，记得处理一下前缀“.”。 ```cpp class Solution { public: string thousandSeparator(int n) { string str = to_string(n); if(n < 1000) return str; int m = str.size(); string ans = ""; int cnt = 0; for(int i = m-1; i >= 0; i--) { …
这次要记录的是做leetbook：二叉树的经历，这是一本很小的book，所以决定用一晚上的时间做完。传送门 树的遍历 t1 二叉树的先序遍历 常规操作，简单题要做难，所以考虑用多种方法来写。 递归法 最常规的递归法，按照根->左->右的顺序来写就可以了。 ```cpp class Solution { public: void solve(TreeNode*root, vector& a) { if(root == NULL) return; a.push_back(root->val); solve(root->left, a); solve(root->right, a); } vector preorderTraversal(TreeNode* root) { vector ans; solve(root, ans); return ans; } }; ``` 迭代法 迭代法是用栈模拟递归的操作。因为栈具有先入后弹的特性，所以优先压右儿子进栈。 ```cpp class Solution …
传送门 t1 存在连续三个奇数的数组 签到题，直接O(n²)遍历就能过。 ```cpp class Solution { public: bool threeConsecutiveOdds(vector& arr) { const int n = arr.size(); if(n < 3) return false; for(int i = 2; i < n; i++) { int cnt = 0; for(int j = i-2; j <= i; j++) …
LeetBook传送门 LeetCode最近一次更新中更新了大量高质量的LeetBook，做起来很舒心，于是打算开一些博文来记录我刷Book的经历。 集合set的使用 t1两个数组的交集 求两个集合的交集，重复元素计算一次。 思路很简单，C++里set元素具有唯一性，所以用两个set给两个数组去重再求交集即可。 ```cpp class Solution { public: vector intersection(vector& nums1, vector& nums2) { setset1; setset2; vector ans; for(int i = 0; i < nums1.size(); i++) set1.insert(nums1[i]); for(int i = 0; i < nums2.size(); i++) set2.insert(nums2[i]); set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), back_inserter(ans)); return …
传送门 题目大意 现在有四种随从： 圣盾亡语圣盾亡语白板 如果对方随从没有免疫，以上随从都能做到一击必杀。 词缀的效果如下： 圣盾：免疫一次伤害，免疫后圣盾消失。亡语：死亡时召唤一只1/1的藤蔓。 每回合只能发动一次攻击，游戏结束时你还有随从存活就算你获胜。你很会玩，所以你一定能找到制胜策略，哪怕只有一点可能。 给你双方随从信息，请告诉我你能否获胜。 思路 贪心处理。 藤蔓没法拿来解场，只能破圣盾，因为每个随从的血量都是1e9。没有藤蔓时只能硬解，为了亏得少一些，优先用有亡语的随从解。上述条件都满足不了了，用圣盾亡语的随从。 ```cpp #include using namespace std; int t; int a[5], b[5]; void battle() { if(b[3]) { b[3]--; b[5]++; } else if(b[4]) b[4]--; else if(b[1]) { b[1]--; b[3]++; } else { b[2]--; b[4]++; } …
传送门 题目大意 有n个球队，每个球队都和其它所有球队比一场，即一共有 [图片缺失] 原图：https://www.nowcoder.com/equation?tex=%5Cfrac%7Bn(n-1)%7D%7B2%7D&preview=true 场比赛，每天只有一场比赛。每个球队会在第一场比赛开始时到，最后一场比赛后走。请安排一个日程表，使所有球队停留的天数之和最小。输出这个日程表。 思路 样例害人啊，出题人编了一个长得很像全排列的样例... 其实仔细一想会发现全排列不仅不是通解，而且大多数情况下都不是答案。当队伍多起来时，全排列会优先满足第一个队伍，这时候其他队伍只能一个一个挨着上场，浪费了大量的等待时间。 所以最优的方案可能会是一种“折中”的方案，即不去强调每一个队的最优。 ```cpp #include using namespace std; const int INF = 0X7F7F7F7F; int t, n; int main() { cin >> t; while(t--) { cin >> n; for(int i = 2; i <= n/2; i++) …
传送门 很经典的字符串问题。给定一个字符串，返回它最长且无重复字符的子串。 可以很直接的想到一个枚举的做法，两重循环遍历字符串去枚举子串，复杂度略小于O(n²)，但肯定会超时。于是想到滑动窗口。 滑动窗口可以在母串上维护一个检索区间，从而避免因为匹配失败而导致的低效下标回溯操作。 具体来说，如果窗口右端检索到一个重复字符，那么左端收缩，直到不存在重复字符位置。每次滑动结束后维护ans字符串即可。 ```cpp class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.size(); int ans = -INT_MAX, left = 0; unordered_setstr; if(!n) return 0; for(int right = 0; right < n; right++) { while(str.find(s[right]) != str.end()) { str.erase(s[left]); left++; } …
传送门 题目大意 定义S(x)为x数位和，给出N,满足S(A)>S(B),1≤A≤B≤N的A,B组数。 ```cpp #include using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll dp[110][1810][2][2]; char c[910]; int l; ll dfs( int x, int y, int u, int v ) { ll res = 0, a, …
传送门 题目大意 定义矩阵压强=F/S，其中压力F=矩阵所有项之和，面积S=矩阵最后一行的所有项之和，求出最大压强的子矩阵，并输出这个压强。 思路 根据题设老老实实算就行了，因为面积由最后一行的元素和决定，所以倒过来去枚举每一列的所有子列求最大值就行了。 ```cpp #include using namespace std; int t; double a[205][205]; int main() { scanf("%d", &t;); while(t--) { int n, m; scanf("%d%d", &n;, &m;); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) scanf("%lf",&a;[i][j]); …
传送门 题目大意 给定n,k，构造一个1-n的排列P，满足对于1-n中的每个i，P都存在一个长为i的子序列，并且每个子序列的和模n都余k。有解则输出任意P，无解输出-1。 思路 首先考虑判断解存在的问题。根据题意，因为P也是自己的子集，所以一定也应该满足“所有元素的和模n余k”的题设，也就是sum(1~n)%n==k，如果不满足，那自然无解。 假设k满足上述条件，接下来的命题就是判断k了。 这种看似要进行复杂的动态处理的问题大多都有规律，这题也不例外。多写两行数据会发现，当n为奇数时，sum(1~n)一定是n的整数倍，即k==0；n为偶数时，k==n/2。 根据这个写代码就好了。 ```cpp #include using namespace std; int n, k; int main() { scanf( "%d%d", &n;, &k; ); if ( n % 2 ) { if ( !k ) { for ( int i = 1; …
传送门 题目大意 有一个n 维向量空间，从这里面拿出n个01向量，设fn为选出的这n个01向量相互线性独立的概率，求 f1^ f2^...^ fn 的值。 思路 有n个向量，它们都线性无关，所以它们的空间秩也是n。每次随机的向量都会加入之前的向量空间，那么每一个向量都一定不属于之前的空间，则一共有2n个向量。 观察规律不难得到对于每个i，都有2i个向量线性相关，那么反之则有2n-2i个向量线性无关。那么有： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/image-1.png 递推计算出每个f就行了。 ```cpp #include using namespace std; typedef long long ll; const int N = 2e7 + 10; const ll MOD = 1e9 + 7; const ll INF = 500000004; …
传送门 题目大意 游戏地图可以解释为一个无穷大的矩形网格。在每个格子里，你可以安放一台金矿，或者是一部圣水采集器，又或者是大本营。你也可以把一些格子留成绿色，充满生机。然而，存在一个限制：一个大本营必须紧挨着至少一个金矿和至少一个圣水采集器。请让你地图中的大本营数量尽可能地多，并输出它在地图中的占比。 思路 赛时这题卡了很久，最后队友的答案因为精度问题就差了0.000001，属实倒霉。 情况其实挺好想的。让金矿与圣水采集器相间排布，任意的一台金矿与一部圣水采集器都不相邻，大本营插在它们之间。 ```cpp #include using namespace std; int main() { printf("%.6f", 2.0 / 3); return 0; } ```
动态规划是一个非常非常重要的算法。众所周知LeetCode周赛中十hard九dp，接触算法那么多年，动态规划始终没有做到完全的掌握，趁着这月LeetCode周赛的主题是dp，也争取完全掌握这门 算法。 内容会不定期更新，初步目标二十道，由易到难。 LeetCode-121:买卖股票的最佳时机 传送门 lc上的dp老题了，其实它只是借用了dp思想而已，和传统的dp有一点点差别。 首先考虑暴力做法。题意不难理解，找出数组中差值最大的两个数，输出他们的差值，要求较小数的下标要小于较大数。那么可以很简洁的写出一个直译： ```cpp class Solution { public: int maxProfit(vector& prices) { int n = prices.size(); int ans = 0; for(int i = 0; i < n; i++) for(int j = i; j < n; j++) ans = max(prices[j]-prices[i], ans); return …
传送门 题目大意 有t(t<1e5)次查询，每次查询给出两个数a,b(a,b<2e6)。输出一组满足下列要求的四个正整数cdef作为答案。若不存在满足条件的cdef，则输出"-1 -1 -1 -1" [图片缺失] 原图：https://uploadfiles.nowcoder.com/images/20200719/272741694_1595159660992_6C354C0B6A13C2EFCC877EBE585BFDD3 ```cpp #include using namespace std; typedef long long ll; int a, b, g, t; ll c, d, e, f; int gcd( int a, int b ) { if ( b == 0 ) return(a); return(gcd( …
传送门 题目大意 按顺时针或逆时针顺序给出n个端点的平面坐标，它们组成一个形如下图的二维几何图形， [图片缺失] 原图：https://uploadfiles.nowcoder.com/images/20200709/329336_1594306194154_C59ABE339F9E82759BF07A316C74BFF6 判断这个图形是右手形还是左手形。图形可以被旋转但不能被缩放。 思路 题设中提到图形的大小不会被改变，也就是说即使所给出的点不同，但他们之间的相对大小是绝对地，可以从这个关系入手。 可以看见，图示中最长边就是底边，它的长度是9，而大拇指是一条紧挨着它且长度为6的边，小拇指则为8。 那么可以去找相邻的3个点，如果找到长度为9的边，就去验证是否存在长度为6或8的相邻边。因为方向不确定，所以使用向量积来判断，向量积大于0时验证大拇指，反之验证小拇指。 具体地，因为题中数据均为浮点数，所以计算距离时存在小数点的精度问题。而例图中的长度均是整数。这里采用忽略小数位的方法来近似判等，即用计算所得的距离值-目标距离值，如果所得差小于一个极小数e，那么则判二者相等。 ```cpp #include using namespace std; const double E = 1e-5; const int LIM = 20; struct node { double x, y; } a[30]; int t; bool isLeft; double dis( node x, node …
传送门 题目大意 一个游戏包含n个阶段，每个阶段有四种类型： 类型0：没有鱼也没有蛤。类型1：只有一只蛤。类型2：只有一条鱼。类型3：有一条鱼和一只蛤。 在每个阶段都可以执行四种操作之一： 用一只蛤换一包鱼饵。如果有一条鱼，可以无需鱼饵抓到这条鱼。无论在此阶段有没有鱼，都可以使用一包鱼饵捕获一条鱼。跳过阶段。 要求求出每局游戏中能抓到鱼的最大条数。 思路 采用贪心的思想。首先，对于类型2、3，显然直接抓鱼是最优的，即有鱼抓鱼。但是类型0时只能用鱼饵抓鱼，类型1时只能做鱼饵或者用鱼饵抓鱼。 根据上面的分析，前导0是可以忽略的，因为我们什么都做不了。忽略后如果遇到类型2、3就直接答案++。其余情况下，优先用鱼饵抓鱼，其次用蛤来换鱼饵。在执行完整个过程后如果还有鱼饵，那么消耗两次类型1来换一条鱼。 值得注意的是，第一次遇见类型0时是没有鱼饵去捕鱼的，所以需要用一个bool来判断当前遇到类型0时是否有鱼饵。 ```cpp #include using namespace std; string s; int t, n, bait, ans; int main() { scanf( "%d", &t; ); while ( t-- ) { int i = 0; scanf( "%d", &n; ); …
传送门 题目大意 现有函数 [图片缺失] 原图：https://www.nowcoder.com/equation?tex=%5Cbegin%7Balign%7D%0Af_c(x)%26%3D%5Cmax_%7Bi%3D1%20%5Cdots%20x-1%7D%20c%20%5Ccdot%20f_c(%5Cgcd(i%2C%20x))%20%26%20x%20%3E%201%5C%5C%0Af_c(x)%26%3D1%20%26%20x%3D1%0A%5Cend%7Balign%7D 给定一些正整数对(ni, ci)，输出fci(ni)在模1e9+7意义下的函数值。 思路 观察公式不难看出fc(x)=ck，k与函数递归次数相关。要求到最大值，贪心的想法是尽可能多地递归，这样就能累乘到更多的c。最好的情况是每次递归都只消去一个 质因子，这样k=质因子的个数。 实现上，从x开始递归 ，找每个数除了自己外最大的因数，直到当前数是质数或1。记录这个过程中递归层数，这个层数就是k。可以先预存好值来提升效率。 ```cpp #include using namespace std; typedef long long ll; const int LIM = 1e6 + 10; const ll MOD = 1e9 + 7; //arr[i]中存i的质因子个数 int arr[LIM], t, n, …
传送门 题目大意 给定一个由小写字母组成的字符串S。你要执行一系列操作。有以下两种操作：1、修改：给定一个整数x，你需要根据x的值来修改S。如果x是正数，就把S中最左边的x个字母移到S的右边；否则，就把S中最右边的|x|个字母移到S的左边。2、查询：给定一个正整数x，输出字符串中第x个字符。 思路 题面很简单，朴实的字符串位移操作。上手十分钟写了个string模拟 ```cpp #include using namespace std; int q; string str; int main() { cin >> str; scanf("%d", &q;); while(q--) { int x; char op; scanf("%d", &op;); switch (op) { case 'A': scanf("%d", &x;); printf("%c\n", str[x-1]); break; case 'M': scanf("%d", &x;); …
传送门 题目大意 对于字符串s，定义s∞=ss...sss。给定字符串s,t，判断 s∞ 与 t∞ 的字典序大小关系。(|s|<1e5) 思路 两个字符串长度相等自然没话说，直接比较就行。这题的核心在处理字符串长度不等的情况。 最开始想到的朴素做法是延长两个字符串至长度为二者的最小公倍数，再来比较，但是会双超。参阅了大佬的题解后了解到了一种全新的做法：直接比较s+t与t+s。 这样做的正确性是显然地。设s的长度为lens，t的长度为lent，lens<lent。在前lens个字符进行比较时，s[i]与t[i]是一一对应的，不存在对齐问题，而进行到lens+1时，如果执行s+t操作，相当于把之前已经确认相等的子串接在s后面，即两个字符串做了等价放大。 ```cpp #include using namespace std; string x, y; int main() { while(cin >> x >> y) { if(x + y < y + x) puts("<"); else if(x + y > y + x) puts(">"); …
传送门 题目大意 给一个长度为n的序列A={1,2,3,...,n}以及置换的次数k，在对A使用k次置换P后得到新的排列B。 输入n,k和B，输出A，如果无解则输出-1。 思路 这种“给出原序列、目标序列与置换规则”的题一般都是置换群。 首先给你一个序列，假如： s = {1 2 3 4 5 6} 然后给你一个变换规则 t = {6 3 4 2 1 5} 就是每一次按照t规则变换下去 比如这样 第一次：6 3 4 2 1 5 第二次：5 4 2 3 6 1 第三次：1 2 3 4 5 …
传送门 题目大意： 给出n个点，圆心和半径任意取的情况下，要求这n个点尽可能多的点出现在圆上。该圆一定经过坐标原点(0,0)。求满足要求的圆上至多有多少个点。 思路很清晰，三点确定一个圆，题目中又给死了一个点，那么O(n²)枚举剩下的两个点，把找到的圆心放在集合里，然后再去找出现次数最多的圆心枚举圆上点就可以了。 三点共圆圆心的寻找公式如下： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/IMG_392620200716-011621-1024x981.jpg 那么不难得到它的代码表达： ```cpp point findCenter(const point &p;, const point &q;, const point &r;) { double a = 2 * (p.x - q.x); double b = 2 * (p.y - q.y); double c = p.x * p.x + …
传送门 题目大意： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/equation-1024x94.png 答案一定是一个有理数，以n=p·q-1的形式并模上998244353给出。 q-1 表示q的逆元，可以用扩欧或费马小定理来算。 如果p是一个质数，而整数a不是p的倍数，则有a(p-1)≡1(mod p) 费马小定理 有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是显然地。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解，它可以用来计算模反元素(也叫模逆元)。扩展欧几里得算法 [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/IMG_390520200714-224509-1024x931.jpg ```cpp #include using namespace std; typedef long long ll; int const LIM = 2e6 + 5; int const MOD = 998244353; ll n; ll fac[LIM]; ll qmod(ll …
传送门 题目大意 如果通过插入 "+"和 "1 "可以从中得到一个形式完整的数学表达式，那么一个带括号的序列 就被称为正确。例如，"(())()"、"() "和"(()())) "等序列是正确的，而")("、"(()) "和"(()))("则不正确。 老师给德米特里的班级布置了一个非常奇怪的任务：她要求每个学生想出一个任意长度的序 列，只由开头和结尾的括号组成。之后，所有学生轮流说出自己想出的序列。轮到迪马时，他突然发现，所有同学都得到了正确的括号序列，而他是否得到了正确的括号序列，他不知道。 迪马现在怀疑自己只是漏掉了任务书中的 "正确 "二字，所以现在他想通过稍微修改自己的序 列来挽救局面。更准确地说，他可以任意次数（可能是零）地执行重排序操作。 重排序操作包括选择序列中任意一个连续的子串，然后以任意的方式对其中的所有字符进行重 排序。这种操作需要l纳秒，其中l是被重新排序的子段的长度。很容易看出，重新排序操作并 不会改变开括号和收括号的数量。例如对于"))(("，他可以选择子串")("，然后进行重排 序")()("(这个操作需要2纳秒)。 由于Dima很快就要回答，他想尽快让自己的序列正确。帮助他做到这一点，或者确定这是不可能的。 输入输出 输入 第一行包含一个整数n(1≤n≤10e6)表示序列的长度。 第二行包含长度为n的字符串，仅由字符"("和") "组成。 输出 打印一个整数：使序列正确的最小纳秒数，如果不可能做到，则打印"-1"。 难度不大的栈括号，遇到左括号就压进去，右括号弹，如果栈不空就输出-1，否则输出答案。 ```cpp #include using namespace std; typedef long long ll; …
传送门 ```cpp #include typedef long long ll; using namespace std; const int LIM = 100010; ll ans = 0; int n, m, k, p = 0;; int a[LIM]; int b[LIM]; int c[LIM]; int main() { cin >> n >> m >> k; for ( …
题目大意：有n(n一定是偶数)堆硬币，他们的重量依次是21,22,...,2n。现在需要把他们分成两份，并让这两份硬币总质量之差的绝对值尽可能的小，请找到这个方案并输出质量之差的绝对值作为答案。 分法不难想， 将重量为2n的给第一份，重量为2n-1~2n-n/2-1的部分给第二份，剩下的再分给第一份。 原因很简单，2~ 2n 中 2n 大于其他n-1个数之和，所以先把 2n 拉出来单独放一堆，然后让另一堆的值尽可能大就行了。 观察答案： n=2,ans=2n=4,ans=6n=6,ans=14n=12,ans=30...... 不难得出上一个数*2+2就是下一个答案。 ```cpp #include using namespace std; typedef long long ll; int main() { int t; cin >> t; while(t--) { int n; cin >> n; ll k = 0; for(int i = 2; i <= …
传送门 二叉搜索树是一颗特殊的二叉树，它满足以下条件： 若左子树非空，则左子树所有节点的值一定小于根节点若右子树非空，则右子树所有节点的值一定大于等于根节点左右子树也都是二叉搜索树 显然这是一个递归定义，而且不难想到，对于同样一组数据，它们转化得到的二叉搜索树是不唯一的。树的长相取决于根节点的值以及左右子树的取值。 但是一颗太过于畸形的二叉搜索树会给查找带来很高的时间复杂度，所以我们定义了平衡二叉搜索树。它的定义与二叉搜索树稍有不同： 若左子树非空，则左子树所有节点的值一定小于根节点若右子树非空，则右子树所有节点的值一定大于等于根节点左子树与右子树的高度差的绝对值小于等于1左右子树也都是平衡二叉搜索树 同时定义平衡因子为节点左子树与右子树深度之差。 那么看回这道题。题目要求构建一颗高度平衡的二叉搜索树，那么不难想到做法：取序列的中间值为根，其左右两边的数据为左右子，递归执行上述操作。这种做法的正确性是显然地，详见这里。那么代码就不难写了。 ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), …
传送门 一个栈作为数据存储空间，另建一个辅助栈。每个入队的新元素就插入在存储栈的栈尾。每次删除就将存储栈里的元素依次弹出并压入辅助栈，操作结束后返回辅助栈栈顶元素作为答案，然后再依次将元素弹回存储栈。 ```cpp class CQueue { public: stack s1; stack s2; CQueue() { while (!s1.empty()) s1.pop(); while (!s2.empty()) s2.pop(); } void appendTail(int value) { s1.push(value); } int deleteHead() { if(s1.empty()) return -1; while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } int tmp = s2.top(); s2.pop(); while(!s2.empty()) { s1.push(s2.top()); …
传送门 题目要求在一个无序数组中找到第K大的元素，不能使用排序。 最开始的想法是借用冒泡的思想两重循环去枚举，但是显然会超时，于是想到了二叉堆。 题目要求输出第K大，那么只需要在原数组上构建一个二叉堆，然后执行k-1次删除操作，堆顶即使答案。 ```cpp class Solution { public: void update(vector& arr, int i, int maxSize) { int maxn = i; int left = i * 2 + 1; int right = i * 2 + 2; if (left < …
二叉堆简介 二叉堆是一种特殊的数据结构，它是一颗具有独特优势的二叉树。 简单地说，二叉堆即是一颗父节点与左右子节点间具有严格大小关系的二叉树。其中父节点大于左右子节点的堆被称为最大堆，反之为最小堆。 二叉堆的操作 插入 二叉堆中新元素的插入位置总是最后一个叶子节点所在位置。通过将新节点上浮至合法位置来维持二叉堆的特性。 删除 与插入相对应，二叉堆总是删除当前的根节点，也就是它的堆顶。删掉当前堆顶后，将最后一个叶子节点放在堆顶并下沉至合法位置，以此来维护二叉堆的特性。 构建 二叉堆的构建是从最后一个叶子节点开始，依次通过执行上浮与下沉操作将每一个节点都归位到合法位置的过程。 二叉堆的存储 不同于传统二叉树，二叉堆的存储采用顺序存储，即数组。在不存在左右儿子指针的情况下，假设父节点为parent，那么它的左右儿子分别为2*parent+1与2*parent+2。 ```cpp #include #define get(x) scanf("%d", &x;) #define lget(x) scanf("%lld", &x;) #define set(a,b) memset(a, b, sizeof(a)) #define rep(a, b, c) for (int a = b; a <= c; a++) using namespace std; const int INF = 0X7F7F7F7F; //上浮叶节点 …
传送门 T1去掉最低工资和最高工资后的工资平均值 签到题，直接写。 ```cpp class Solution { public: double average(vector& salary) { int n = salary.size(); double sum = 0; int ma = -INT_MAX, mi = INT_MAX; for(int i = 0; i < n; i++) { ma = max(ma, salary[i]); mi = min(mi, salary[i]); sum …
传送门 这题很巧妙的。 题意是这样的：一个长度为n的nums数组，在自然状态下这个数组内的成员应该是(1,2,3,...,n)，但现在这个数组被打乱并拿走了一些数，我们要做的就是找出nums中缺失的第一个正数。 题目要求时间复杂度O(n)，空间复杂度O(1)。 这是一道hard，刚刚拿到手的时候挺懵的，在查阅大佬题解后了解到了一种“hash碰撞法”，以下做思路转述。 首先，合法的元素应该∈[1,n]，所以非正数成员直接标记为非法。第一次遍历，对于每个合法的成员，我们把它与自己位置上当前的元素做交换。第二次遍历去找出第一个与自己下标不相等的成员，答案就是这个下标。如果遍历到尾都没找到这样的成员，则答案为n+1。 上述思路的正确性是显然地，因为它严谨地把每一个成员放到自己应该在的下标上了，如果出现下标与值不等的情况，说明数组中缺失了这个成员。那么我们所找到的第一个缺失的成员自然就是符合题意的答案。 不难分析出这个算法的时间复杂度是线性的，也符合要求。 ```cpp class Solution { public: int firstMissingPositive(vector& nums) { for (int i = 0; i < nums.size(); i++) { if (nums[i] != i+1) { while (0 < nums[i] && nums[i] <= nums.size() && nums[nums[i]-1] …
传送门 思路：简单的链表去重，用一个set保存已有数据，每一步检测当前val是否出现过，未出现过就入集合，出现过就删除它。 ```cpp class Solution { public: ListNode* removeDuplicateNodes(ListNode* head) { if (head == nullptr) return head; unordered_set s = {head->val}; ListNode* p = head; while (p->next != nullptr) { ListNode* cur = p->next; if (!s.count(cur->val)) { s.insert(cur->val); p = p->next; } else { p->next …
传送门 LC的daily真是越来越骚了，本来打算写一个O(n3)T了后再来优化，结果居然过了，虽然击败感人... ```cpp //时间击败6.58% //空间击败7.14% class Solution { public: int threeSumClosest(vector& nums, int target) { int n = nums.size(); int minn = INT_MAX; int ans; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) for(int k = 0; …
传送门 T1数组异或操作 签到题，直接翻译 ```cpp class Solution { public: int xorOperation(int n, int start) { vector nums; int ans; for(int i = 0; i < n; i++) nums.push_back(start + 2*i); ans = nums[0]; for(int i = 1; i < n; i++) ans ^= nums[i]; return ans; …
传送门 给出一个英文句子，要求判断它是否是回文串。判断时忽略大小写、标点以及空格，同时空字符串视为回文串。 我的思路是O(n)扫过去清掉标点和空格并统一大小写，然后翻转字符串判断它与初始字符串是否相等。确实可以A但是时间复杂度惨不忍睹，感觉可以优化到O(1)，学习后会更新。 ```cpp class Solution { public: bool isPalindrome(string s) { string str = ""; int n = s.size(); for(int i = 0; i < n; i++) if(isalpha(s[i])) str += tolower(s[i]); else if(isdigit(s[i])) str += s[i]; string str1 = str; reverse(str1.begin(), str1.end()); return str1 …
传送门 题目要求要从一组数据中找出两个值之和减去下标差最大的数。 看到这个题目，瞟一下范围，50000的范围可以尝试一下暴力： ```cpp class Solution { public: int maxScoreSightseeingPair(vector& A) { int n = A.size(); int ans = -1; for(int i = 0; i < n-1; i++) for(int j = i+1; j < n; j++) { int tmp = A[i] + A[j] + i …
传送门 T1一位数组的动态和 维护一个nums数组的前缀和，直接写。 ```cpp class Solution { public: vector runningSum(vector& nums) { vector pre; int n = nums.size(); pre.push_back(nums[0]); for(int i = 1; i < n; i++) { int tmp = pre[i-1] + nums[i]; pre.push_back(tmp); } return pre; } }; ``` T2不同整数的最小数目 题意很直观：给出一组整数arr与一个整数k，要求删除k个元素并使剩下的元素尽可能地少。 思路也很清晰，其实就是一个贪心策略。统计每个元素出现的次数，优先从出现次数少的开始删，最后剩下的元素个数就是答案。 考虑到数组中的元素范围是[0,1e9]，所以用hash表来离散处理。将统计用的hash表以出现次数为关键字做排序然后从头开始删就可以了。 …
传送门→ T1： 商品折扣后的最终价格 签到题，挺简单的。按照题意直接写就行。 ```cpp class Solution { public: vector finalPrices(vector& prices) { vector ans; int n = prices.size(); for(int i = 0; i < n; i++) { bool flag = 0; int tmp; for(int j = i+1; j < n; j++) { if(prices[j] …
传送门→ 很经典的DP。设dp[i]为走到第i级台阶的总方案数，那么显然可以得到状态转移方程：dp[i]=dp[i-1]+dp[i-2]。因为每一步能走一级或者两级台阶。 初始化dp[1]=1,dp[2]=2，然后跑循环就行了。 ```cpp class Solution { public: int climbStairs(int n) { int dp[100]; dp[1] = 1; dp[2] = 2; for(int i = 3; i <= n; i++) dp[i] = dp[i-1] + dp[i-2]; return dp[n]; } }; ```
传送门→ 很经典的题目，这里贴出一个简单地通用思路。 考虑折半这个串，比较折半后的两个串是否相等即可。 ```cpp class Solution { public: bool isPalindrome(int x) { if(x < 0 || (x % 10 == 0 && x != 0)) return false; int p = 0; while(x > p) { p = p * 10 + x % 10; x …
传送门→ T1重新排列数组 签到题，按题意模拟就行 ```cpp class Solution { public: vector shuffle(vector& nums, int n) { vector ans; for(int i = 0; i < n; i++) { ans.push_back(nums[i]); ans.push_back(nums[n+i]); } return ans; } }; ``` T2 数组中的 k 个最强值 就是根据题目要求重新定义排序规则，在排序后取前k项即是答案 ```cpp int m; bool cmp(int a, …
数据结构的学习马上就会告一段落，这里打算用C++去挨个的写一遍也就算是做复习了，文章会持续更新。 链表 常规链表 ```cpp // // linklist.cpp // 链表 // // Created by edisoncgh on 2020/4/4. // Copyright © 2020 edisoncgh. All rights reserved. // #include #include #include using namespace std; //构建节点类 class Node { public: int data;//数据域 Node* next;//指针域 }; class List//构建链表类 { public: List();//构建函数 ~List();//析构函数 …
传送门→ T1 数组中两元素的最大乘积 签到题，两个for。 ```cpp class Solution { public: int maxProduct(vector& nums) { int n = nums.size(); int maxn = -1; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(i != j) maxn = max((nums[i]-1) * (nums[j]-1), …
[图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/06/图-xmind-589x1024.png 图 逻辑结构 遍历 dfs 栈/递归 ①从图中某个顶点V0出发②找出刚访问的顶点的第一个邻接点，访问它并将他置位当前节点③重复步骤2直至当前节点不再有邻接点④返回上一个仍有邻接点并未被访问过的节点，重复步骤 bfs 队列 依次访问当前节点的每一个邻接点 存储结构 邻接矩阵 定义 设矩阵A，对于任意的Vi与Vj，若∈VR，则Aij＝1，反之为0 实现 有权图的邻接矩阵初值赋为∞，无权图初值为0. 再通过循环存入每一条弧。 复杂度 时间复杂度 存弧的时间复杂度为O(e)，赋初值的时间复杂度为O(n²) 空间复杂度 空间复杂度为O(n²) 特性 便于运算 因为使用矩阵存储，所以可以便捷地访问每一条弧。显然，判断弧存在、求顶点的度都可以在短时间内较优地完成 …
传送门→ T1:通过翻转子数组使两个数组相等 这题挺水的。题目允许任意次的变换，所以理论上只要两个数组的长度和组成元素一样那么一定可以在有限次变换后变为等价数组。统计一下两个数组的sum和length然后判断就好。 其实排序后判断每一个元素是否相同也可以，但是用一遍循环求和会更快一点点。 ```cpp class Solution { public: bool canBeEqual(vector& target, vector& arr) { int n = target.size(); int m = arr.size(); if(n != m) return false; int sum1 = 0, sum2 = 0; for(int i = 0 ; i < n; i++) { …
A 中国象棋 [图片缺失] 原图：https://img-blog.csdnimg.cn/20200506201533473.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxMDMyMA==,size_16,color_FFFFFF,t_70#pic_center 一道挺标准的DFS模板，只不过走法换成了走日字。 ```cpp #include using namespace std; char g[10][9]; bool book[10][9]; int dx[] = { -2,-1,1,2,2,1,-1,-2 }; int dy[] = { 1,2,2,1,-1,-2,-2,-1 }; bool dfs(int x, int y) { book[x][y] = true; if (g[x][y] == 'T')return true; for (int i = 0; i < 8; …
传送门 题面挺直接的，让人第一眼看到就想用hash。但它有不让开额外的空间，所以第一时间还硬是没想出来这么做。后来看了讨论，发觉还是自己知识学的不够活啊。 这里的解法是利用位运算中的异或运算。异或具有以下特性：任意一个数与0异或还是原来的数、任意一个数与自己异或得到的一定是0。并且异或满足常规的计算率，即存在交换律。 那么对于题目给出的一串数字nums，只需要计算整个数组的异或，最后得到的就一定是那个单独的数。 ```cpp class Solution { public: int singleNumber(vector& nums) { int res = 0; for(int i : nums) res ^= i; return res; } }; ```
传送门→ 就是实现一个能在常数时间内返回最小值的栈。根据常规思维，减少时间开销的代价一般都是增大空间开销，所以往这个方向去思考。因为栈可能随时都在弹出元素，所以单纯的用一个变量去维护最小值是不够的，这里可以用另一个栈来辅助。 单独设置一个栈mini用以保存当前栈顶元素进栈时的最小值，即每一个新元素进站时从此元素与当前mini栈顶元素中得到较小值，在x进栈的同时将这个最小值压入mini栈。这样mini栈顶就一定是当前栈内的最小值。 ```cpp class MinStack { protected: vector data; vector mini; public: /** initialize your data structure here. */ MinStack() { mini.push_back(INT_MAX); } void push(int x) { int tmp = min(mini.back(), x); data.push_back(x); mini.push_back(tmp); } void pop() { if(data.empty()) return; data.pop_back(); mini.pop_back(); } int …
传送门→ A猴子摘桃 小学奥数，掰手指都能数出来是22. B平方和 也没啥好说的，填空题暴力就完事了。 ```cpp #include #include using namespace std; bool check(int x) { while(x > 0) { int t = x % 10; if(t == 2 || t == 0) return true; x /= 10; } return false; } int main() …
传送门→ 据说是高频面试题。 大意是不用sqrt去实现开平方根计算，小数向下取整。 pow做法 第一想法是用pow函数，众所周知开平方＝½次方： ```cpp class Solution { public: int mySqrt(int x) { int ans = pow(x, 1.0/2); return ans; } }; ``` 过是过了，但是时间复杂度很高，仅击败36%。于是开始学习更先进的算法。 对数做法 还有一种算法是利用自然对数的换底公式来计算。 $$ \sqrt{x} = x^ \frac{1}{2} = e^ \ln x \frac{1}{2} $$ ```cpp class Solution { public: …
传送门 这题还是一道贪心。（最近LC很喜欢出贪心啊）因为nums[i]表示在第i个位置时每一步能向前走0~nums[i]的长度，所以若每一步都走的尽量远，最后到达终点时消耗的步数一定最短。（如果这题改成在i位置时只能走nums[i]长度那就变成一道dp了）所以对于每一步，我们都去选择能够到的最远位置。 在具体实现的时候选择一个循环从左向右遍历。维护一个maxpos值表示当前这个位置能走到的最远位置，并把它更新为边界。当走到边界的时候step++表示走了一步，然后继续更新边界。 值得一提的是，遍历过程仅访问0~n-1个元素，因为在跳到最后一个位置前，border值肯定是大于等于n的，不然就不符合题中“ 总是可以到达数组的最后一个位置”的设定了。如果border==n，step会多加一次。 ```cpp class Solution { public: int jump(vector& nums) { int maxpos = 0, border = 0, step = 0; int n = nums.size(); for (int i = 0; i < n - 1; i++) { if (maxpos >= i)//还没走到边界 { …
传送门→ 这双周赛改成贪心赛算了，fo了。 A拥有糖果最多的孩子 贪心+暴力。两重循环外层枚举每一个小朋友，内层去找当前的最大糖果数量。如果当前小朋友的糖加上额外给的能大于等于这个最大值就push一个1进去，否则push一个0。 ```cpp class Solution { public: vector kidsWithCandies(vector& candies, int extraCandies) { vector ans; int n = candies.size(); for(int i = 0; i < n; i++) { int maxn = 0; for(int j = 0; j < n; j++) if(i == j) …
A有趣的数字 我们称一个数是质数，而且数位中出现了 5 的数字是有趣的。例如 5,59,457 都是有趣的，而 15,7 不是。求 1 到 100000 中有趣的数的个数。 没啥好说的，就硬来。先用筛法打出素数表，再用check函数确认数位里是否含5。时间复杂度肯定是不优的，但填空题嘛能解出来就是AC。最后答案是3282. ```cpp #include #include #include #include #define get(x) scanf("%d", &x;) #define lget(x) scanf("%lld", &x;) #define set(a,b) memset(a, b, sizeof(a)) #define rep(a, b, c) for (int a = b; a <= c; a++) using namespace std; typedef long long ll; const int …
```cpp // // linklist.cpp // 链表 // // Created by edisoncgh on 2020/4/4. // Copyright © 2020 edisoncgh. All rights reserved. // #include #include #include using namespace std; //构建节点类 class Node { public: int data;//数据域 Node* next;//指针域 }; class List//构建链表类 { public: List();//构建函数 ~List();//析构函数 void createList(int n);//创建一个n结点的链表 …
日常爆零，平生夙愿是不要再爆了。比赛传送门→ A大吉大利 题目给定n(<1e5)个整数a1,a2,...,an，计算 [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/03/2020032714292561.png“&”为位与运算符 输入第一行一个整数n.第二行n个整数ai. 输出一个整数表示上述求和式的答案. 样例 样例输入 5 1 2 3 4 5 样例输出 33 赛时写了一个很老实的循环，果不其然T了。这时候基础不牢就地动山摇啊，硬是没想出来巧解，还是赛后去研究的，哎。 考虑到位与运算的特性，将样例化为二进制来分析： 0 0 10 1 00 1 11 0 01 0 1 根据题意计算，以右起第一列为例，第一个1与所有的1位与得到3，第二个1与所有的1位与也得到3....就这样得到了3个3也就是9。显然，对于数据中所有整数的第i位，运算结果就是1的个数的平方。 即，设有t[i]个数在二进制下的第i位为1，那么答案就会累加t2[i]个二进制下的1。所以就转化为了求： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/03/2020032715275392.png 因为答案以十进制输出，所以最后还要按位权乘2的i次幂转回10进制。 #include <cmath> #include <cstdio> #include …
这么水的校内赛居然能卡掉五道，真是人间奇葩，能给自己气死。 D-矩阵 题面体育老师觉得继续刁难小R不太好，所以他对小R发起了“扣平时分”威胁！这一次他和之前不一样了，让所有同学站成一个矩形，然后他会随机点一个人，被点中的人的那一行和那一列上的所有人都会加上一个值，经过若干次点名之后，老师想让小R告诉他，数值最大的和最小的相差多少？ 输入第一行输入三个整数n（表示矩阵的行数），m（表示矩阵的列数）和q（表示老师点名的次数）。之后q行，每行三个整数（x，y，val），x和y表示被点名同学的坐标，val表示加上的值。 输出输出一行，表示最大和最小相差的值。 样例 样例输入 3 3 3 1 1 1 2 2 2 3 3 3 样例输出 4 数据范围 1 <= x <= n <= 2000 1 <= y <= m <= 2000 -1000000 <= val <= 10000000 <= q <= 10000 基础模拟题，没什么好说的。需要注意的点是对于每一个被查询的点(x,y)需要预先减去一个v值，不然会重复计算，赛时就死在这，fo了。 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define get(x) scanf("%d", &x) #define lget(x) scanf("%lld", &x) #define set(a,b) …
传送门 题面 我的某室友学过素描，墙上有n张他的作品。这些作品都是宽度为1，高度不定的矩形，从左到右排成一排，且底边在同一水平线上。宿舍评比就要来了，为了及格，我们决定买不多于m块的矩形木板，把这些作品和谐掉。要求木板也从左到右排成一排，且底边与作品的底边在同一水平线上。在能够把所有作品和谐掉的前提下，我们希望这些木板的面积和最小，问最小面积和。 [图片缺失] 原图：http://lx.lanqiao.cn/RequireFile.do?fid=FaHtNHE3 输入 第一行两个数n和m，表示作品数和木板数；第二行n个数Hi，表示从左到右第i个作品的高度。 输出 一行一个数ans表示答案。 样例数据 样例输入 5 2 4 2 3 5 4 样例输出 22 数据规模 对于30%的数据：1<=n，m<=10；对于100%的数据：1<=n，m<=100，1<=Hi<=10000。 思路 题面意思转述一下就是：将若干幅矩形的画作通过不同的相邻组合方式，在用尽m块木板的情况下，使得覆盖它们的面积最小。显然这个面积由被覆盖区间中最高的画作来决定，所以需要设hmax[i][j]为hi~hj中画的最大高度。 设 dp[i][j]为用j块板子覆盖前i幅画的最小面积，记k为在dp[i][j]状态下还剩的板子数量。可以得到状态转移方程： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/03/2020031713184378-1024x61.png 关于初始状态的确定，这里在求最小值，所以dp初始化为INF。如果用一块板子来覆盖前i幅画，显然面积只能为i·hmax[1][i]，所以dp[i][1]初始化为 i·hmax[1][i] 。 ```cpp #include #include …
A-小乔与小灰灰 题面：小乔和小灰灰是好朋友，现在如果一个字符串中同时出现子序列“XiaoQiao”和“XiaoHuiHui”，那么小乔和小灰灰都会感到开心。 输入：输入包含一行一个字符串S字符串中仅包含大写字母和小写字母 输出：如果这个串会让小乔和小灰灰都感到开心，那么输出“Happy”，否则输出“emm”。 样例数据 样例输入1： XiaoQiaoheHuiHui 样例输出1： Happy 样例输入2： Xiaohuihuihexiaoqiao 样例输出2： emm 签到题，按下标匹配。 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define get(x) scanf("%d", &x) #define set(a,b) memset(a, b, sizeof(a)) #define rep(a, b, c) for …
筛法 计算机中常使用筛法来计算素数。筛法的基本思想都是从一个区间中删去不符合要求的数，从而得到一个符合要求的区间，所以形象的称呼为筛法。 埃拉托斯特尼筛法(埃筛) 它又叫线性筛。埃筛可以快速获取小于等于n的素数集合。首先明确一点：对于任意合数x，它必有一个小于等于sqrt(x)的因子，因为如果两者均大于sqrt(x)那么其积必大于x。那么判断x是否为素数只需要判断2~sqrt(x)能否与x整除即可，如果一直计算到sqrt(x)都没有出现x的因数那x就是一个素数了。 埃筛基于以下原理：对于一个素数n(n>1)，它的k(k>1)倍数一定是一个合数。 假设要计算100以内的素数，从2开始遍历。 将2在100以内的所有倍数标记为合数。指针后移，检查3是否为合数。3不是合数，那么把3的所有倍数也标记为合数。指针后移，检查4是否为合数。4已经被标记为合数，跳过它。重复上述流程一直到sqrt(100)。 事实上埃筛可以进行优化，即每次标记从大于等于自身的倍数开始进行。如5，只要标记5 × 5, 5 × 6, 5 × 7…为合数，因为5 × 2, 5 × 3, 5 × 4…已经被之前出现的数的倍数标记过了。 ```cpp //时间复杂度O(sqrt(n)) void findPrimes(int n) { int p[n]; p[0] = 0;//放个0占位 int s = sqrt(n); for (int i = 2; i <= s; i++)//从2到sqrt(x)计算 if (p[i] …