传送门 拿到这题第一思路肯定是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 …
传送门 题目大意 《飞行员兄弟：跟随条纹象》游戏中有一个任务，玩家需要打开一个冰箱。冰箱门上有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, …