html5韩国网站模板,网页布局的设计步骤,北京优化seo排名,公司网站维护怎么做1.四元组问题 我的这个代码有点问题#xff0c;我也找不出来#xff0c;哪位大佬指正一下
// 四元组问题
//思路
// 是否存在 a b c d, 使得nums[d] nums[c] nums[a] nums[b]
//分别维护二元组 (a, b) 和 (c, d), 对合法 b 维护前缀 max 的 n…1.四元组问题 我的这个代码有点问题我也找不出来哪位大佬指正一下
// 四元组问题
//思路
// 是否存在 a b c d, 使得nums[d] nums[c] nums[a] nums[b]
//分别维护二元组 (a, b) 和 (c, d), 对合法 b 维护前缀 max 的 nums[a], 同理维护 (c, d) 等等 枚举c即可
//所以 要对每个 b 找到最大的nums[a] 使得a b且 nums[a] nums[b]
#includebits/stdc.h
using namespace std;
using ll long long;
#define inf 1,000,000,000void solve(const int Case)
{int n; cin n;vectorint a(n);for(auto x : a)cin x;vectorint pre(n, (-inf - 1)), suf(n);int mn (inf 1);setint s; // 前缀的 nums[a] 的值 for (int i 0;i n; i){// 找大于等于nums[b] 的 num[a] 中的最小值 auto it s.lower_bound(a[i]);if(it s.begin());else {it prev(it); // 获得小于 nums[b] 的 nums[a] 中的最大值 int p *it;pre[i] p; // pre[i] 记录的是合法的 b 的值的nums[a] 的前缀 max }s.insert(a[i]);}for(int i n - 1;i 0; -- i){if(a[i] mn) // nums[c] nums[d]{// sud[i] 表示 c i时是否存在合法的 d 满足 suf[i] 1;}mn min(mn, a[i]);}for(int i 1;i n; i)pre[i] max(pre[i - 1], pre[i]);for(int i 1;i n - 1; i) // 枚举c i 1 {if(pre[i] a[i 1] suf[i 1]){cout YES\n;return;}}cout NO\n;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t 1;for(int i 1;i t; i)solve(i);return 0;
}
这个是我学的对的
思路
把四个数的不等式关系降低为3个数的不等式关系如果我们已经判断num[c]nums[a]nums[b]。
那么我们只需要再判断下标c的后面是否存在比nums[c]小的数据。这里我们可以通过另外一个数组min_r来求出每一个num[i]后面的最小值min_r[i]即可。
以下是详细的解题思路
1.构建一个单调递减栈st存储元素。
栈顶st.top()表示目前的最大值nums[b]。并需要用一个k来不断刷新最大值。
2.依次遍历数组nums,nums[i]表示当前正在遍历第i个元素。
如果栈为空则入栈若不为空且nums[i]st.top(),则弹出栈顶元素
并更新最大值K,直到num[i]st.top()不成立最后一次出栈的元素一定是nums[a]。
最后一次出栈时k为nums[a]的值。
再继续遍历判断nums[i]k是否成立若成立则找到了nums[c]
(此时恰好构成了一个完整的nums[c]nums[a]nums[b])
4.判断下标c的后面是否存在一个比nums[c]还要小的数nums[d]
若min_r[i]nums[c],则返回true
#includebits/stdc.h
using namespace std;bool FoursNumberFind(vectorintnums){stackintst;int n nums.size(),k INT_MIN, INF INT_MAX;//用min_r[i]来存储num[i]右边的最小值nums[i1]vectorintmin_r(n,INF);//i的初值为什么是n-2,下标从0开始,范围为0~n-1,因为需要找num[i]右边的最小值nums[i1]for(int i n-2;i0;--i){min_r[i] min(min_r[i1],nums[i1]);}//用单调栈求下标未nums[c]nums[a]nums[b]的情况for(int i 0;in;i){if(nums[i]k){if(nums[i]min_r[i])return true;}while(!st.empty() st.top()nums[i]){k max(k,st.top());st.pop();}st.push(nums[i]);}return false;
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n;cinn;vectorintnums(n);for(int i 0;in;i) cinnums[i];if(FoursNumberFind(nums)) coutYESendl;else coutNOendl;return 0;
}
2.肖恩的投球游戏加强版 样例输入
4 4 2
3 2 9 10
7 2 1 7
10 4 8 4
1 1 2 1
4 1 4 3 1
3 3 4 4 3
样例输出
3 2 9 10
7 2 1 7
10 4 11 7
2 2 6 4
#include bits/stdc.h
using namespace std;
#define int long long
const int N 1000 3;
int a[N][N], d[N][N];void solve()
{int n, m, q; cin n m q;for (int i 1;i n; i)for(int j 1;j m; j)cin a[i][j]; // 输入for(int i 1;i n; i)for(int j 1;j m; j)d[i][j] a[i][j] - a[i][j - 1]; // 差分while(q -- ){int x1, y1, x2, y2, c; cin x1 y1 x2 y2 c;for(int i x1;i x2; i){d[i][y1] c; // 只取x1y1x2y2d[i][y2 1] - c;}}for (int i 1;i n; i)for(int j 1;j m; j)a[i][j] a[i][j - 1] d[i][j]; // 前缀和还原for(int i 1;i n; i)for(int j 1;j m; j)cout a[i][j] \n[j m]; // 输出
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);solve();return 0;
}
