文章目錄

• • 1. 比賽結果
  • 2. 題目
  • • 1. 樹木規劃
    • 2. 正三角形拼接
    • 3. 大樓間穿梭
    • 4. 對稱前后綴

1. 比賽結果

通過了 3 題，第245名，進入復賽了，收獲 T恤 一件，哈哈。

2. 題目

1. 樹木規劃

題目鏈接

描述

在一條直的馬路上，有 n 棵樹，每棵樹有一個坐標，代表它們距離馬路起點的距離。 如果每相鄰的兩棵樹之間的間隔不小于 d，那么我們認為這些樹是美觀的。 請計算出最少移除多少棵樹，可以讓這些樹變得美觀。

樹木的棵樹為 n，1 <= n <= 10^5。 樹木的坐標用 trees 表示，0 <= trees[i] <= 10^9。 最小美觀間隔為 d，1 <= d <= 10^9。 保證輸入的坐標是排好序的，且兩兩不相同。

說明

樣例中，將位置 2 和 6 的樹木移走，剩下 [1, 3, 5] ，它們是美觀的。

示例 輸入： [1,2,3,5,6] 2 輸出： 2

---

解題：

• 直接遍歷，不滿足的移除

class Solution { public:/*** @param trees: the positions of trees.* @param d: the minimum beautiful interval.* @return: the minimum number of trees to remove to make trees beautiful.*/int treePlanning(vector<int> &trees, int d) {// write your code here.int prev = trees[0], s = 0;for(int i = 1; i < trees.size(); ++i){if(trees[i]-prev < d)//不滿足{s++;//移除}else{prev = trees[i];}}return s;} };

2. 正三角形拼接

題目鏈接

描述

給出 n 根木棍，每次切割可以將1根木棍切成 2 段。請計算出最少切割幾次，可以從所有木棍中選出 3 根，組成一個正三角形。

一開始的木棍根數為 n，3 ≤ n ≤ 1000。所有木棍的長度為一個整型數組 lengths，1 < length_i ≤ 10^9。
切割必須要將木棍分成 2 根整數長度的木棍，而且總長度要和原木棍相等。

說明

可以從長為7的木棍中，切出2根長為3的木棍，那么木棍的長度應該為[2，3，1，3，3，5]，可以拼出邊長為3的正三角形。

示例 輸入： [2，3，7，5] 輸出： 2

---

解題：

class Solution { public:/*** @param lengths: the lengths of sticks at the beginning.* @return: return the minimum number of cuts.*/int makeEquilateralTriangle(vector<int> &lengths) {// write your code here.map<int, int> m;int cut = 2;//最多切兩次for(int i = 0; i < lengths.size(); i++) m[lengths[i]]++;//長度計數for(auto& mi : m){if(mi.second == 2)//有2段了{if(m.lower_bound(mi.first+1) != m.end())cut = min(cut, 1);//有更長的，切1次}else if(mi.second >= 3)//有3段了，不用切return 0;if(mi.first%2==0 && m.count(mi.first/2))cut = min(cut, 1);//如果能被平均切開，且有1段一樣的，切1次就可以}return cut;} };

3. 大樓間穿梭

題目鏈接

描述

蜘蛛俠在大樓間穿梭。大樓的高度可以看作是一個從左到右排列的數組。
現在蜘蛛俠站在第一棟大樓上，他想跳到最后一棟上。

• 蜘蛛俠的視野為 k，他可以花費 x 點體力，用蛛絲移動到右側k幢建筑中第一棟比當前位置高的大樓（應該是 高或者相同高度，題目有問題）。
• 或者蜘蛛俠可以花費 y 點體力，跳躍到右側接下來兩棟大樓其中一棟。

請計算蜘蛛俠最少花費多少體力，到達最后一棟上。

大樓的高度為數組 heights，一共有 n 棟大樓，2 ≤ n ≤ 10^5，1 <= heights_i ≤ 10^9.蜘蛛俠的視野為 k，1 ≤ k ≤ n。兩種行動的體力花費滿足 1 ≤ x，y ≤ 10^9。

說明
樣例中，先花費6點體力跳到第三棟建筑，再花費10點到達最后一棟。

示例 輸入： heights=[1，5，4，3，3，5] k=3 x=10 y=6 輸出： 16

---

解題：

• 單調棧算出右側高度 >= 當前的 第一個位置（逆序遍歷）
• 然后簡單的動態規劃即可

class Solution { public:/*** @param heights: the heights of buildings.* @param k: the vision.* @param x: the energy to spend of the first action.* @param y: the energy to spend of the second action.* @return: the minimal energy to spend.*/long long shuttleInBuildings(vector<int> &heights, int k, int x, int y) {// write your code here.int n = heights.size(), i, j, K;stack<int> s;vector<int> rightTall(n, -1);//右側高或者相等的第一個位置for(int i = n-1; i >= 0; i--) //單調棧{while(!s.empty() && heights[s.top()] < heights[i])//右側比我小的，沒有用s.pop();if(!s.empty() && s.top()-i <= k)//有大于等于我的，且距離在 k 以內rightTall[i] = s.top();//記錄下來s.push(i);}vector<long long> dp(n, LONG_LONG_MAX);dp[0] = 0;for(int i = 0; i < n; i++) // DP{if(dp[i] == LONG_LONG_MAX)continue;if(i+1 < n && dp[i+1] > dp[i]+y)//右側1dp[i+1] = dp[i]+y;if(i+2 < n && dp[i+2] > dp[i]+y)//右側2dp[i+2] = dp[i]+y;if(rightTall[i] != -1 && dp[rightTall[i]] > dp[i]+x)dp[rightTall[i]] = dp[i]+x;//直接跳到 k 以內的 第一個 >= 我的位置}return dp[n-1];} };

4. 對稱前后綴

題目鏈接

描述

給定一個字符串 s。我們令一個字符串的權值為一個字符串的最長對稱前后綴長度。
請求出 s 的所有子串的權值的總和。
例如，”abcxyzcba” 的最長對稱前后綴的長度為3，因為“abc”和“cba”對稱。
字符串的長度為 n，1 ≤ n ≤ 3*10^3。字符串均由小寫英文字符組成。

說明

樣例中，單個字符的子串的權值為1，它們的和為 7。
另外的權值為：
"bacb"->1，
"bacbdab"->2，
"bdab"->1，
"acbda'->1，

所以權值和為12。

示例 輸入： "bacbdab 輸出： 12

---

解題：

• 區間DP

class Solution { public:/*** @param s: a string.* @return: return the values of all the intervals.*/long long suffixQuery(string &s) {// write your code herelong long n = s.size(), ans = n;//區間DP，dp[i][j] 表示區間內的 子串的最大權值vector<vector<int>> dp(n, vector<int>(n, 0));for(int i = 0; i < n; i++)dp[i][i] = 1;for(int len = 1, i; len < n; len++){for(i = 0; i+len < n; i++){if(s[i] == s[i+len])//子串首尾相同{int length = len-1;//除去首尾 里面的子串[i+1, i+len-1]的長度if(dp[i+1][i+len-1] == length)// 里面正反序都相同dp[i][i+len] = dp[i+1][i+len-1]+2;//把兩個端點都可以加上elsedp[i][i+len] = dp[i+1][i+len-1]+1;//只能加上1端}ans += dp[i][i+len];}}return ans;} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的阿里云 超级码力在线编程大赛初赛 第1场（第245名）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。