网站建设都需要哪些东西,微网站建设及微信公众号,展馆设计布展,建筑设计方案汇报pptCF1660D Maximum Product Strikes Back 题解 题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 思路点拨#xff08;分类题#xff09;缩小研究对象范围除0的分析加上0的分析 代码实现小方法陈述 题目描述
你有一个长度为 n n n 的数组#xff0c;每一个元素都在 … CF1660D Maximum Product Strikes Back 题解 题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 思路点拨分类题缩小研究对象范围除0的分析加上0的分析 代码实现小方法陈述 题目描述
你有一个长度为 n n n 的数组每一个元素都在 − 2 -2 −2 到 2 2 2 的整数之间当从数组首删去 x x x 个元素从数组末删去 y y y 个元素时数组剩下的乘积最大输出 x x x 和 y y y 。
特别地当存在多种情况时输出任意一种即可 当数组为空时这个数组的乘积被认为是 1 1 1 。
输入格式
第一行包含一个正整数 t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) —小测试点的总数
对于每个小测试点
第一行包含一个正整数 n n n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 1 \le n \le 2 \cdot 10^5 1≤n≤2⋅105 ) — a a a数组的总长度 .
下一行包含 n n n 个正整数 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an ( − 2 ≤ ∣ a i ∣ ≤ 2 -2 \leq |a_i| \le 2 −2≤∣ai∣≤2 ) — a a a数组的每个元素 .
保证 ∑ n ≤ 2 ⋅ 1 0 5 \sum n \leq 2 \cdot 10^5 ∑n≤2⋅105 .
输出格式
对于每个测试点输出共一行包含2个非负整数 x x x 和 y y y ( 0 ≤ x y ≤ n 0 \le x y \le n 0≤xy≤n ) — 使数组乘积最大的操作
样例 #1
样例输入 #1
5
4
1 2 -1 2
3
1 1 -2
5
2 0 -2 2 -1
3
-2 -1 -1
3
-1 -2 -2样例输出 #1
0 2
3 0
2 0
0 1
1 0思路点拨分类题
缩小研究对象范围
题目中限定了 − 2 ≤ a i ≤ 2 且为整数 -2\leq a_i\leq 2且为整数 −2≤ai≤2且为整数限定了 a i a_i ai的值只能为 − 2 , − 1 , 0 , 1 , 2 -2,-1,0,1,2 −2,−1,0,1,2
除0的分析
假设没有 0 0 0的存在应该怎么做 非常容易发现删 1 1 1并不会对数组绝对值符号有任何优劣影响删 − 1 -1 −1只会控制数组乘积的符号 2 、 − 2 2、-2 2、−2才是对于数组绝对值起绝对性影响。
因此得出除0之外的分析结论
若数组乘积为正不用删任何数若数组乘积为负则在数组收尾 2 2 2边中选 ∣ a i ∣ 2 较少的一边删除其所在前缀或后缀 |a_i|2较少的一边删除其所在前缀或后缀 ∣ai∣2较少的一边删除其所在前缀或后缀
加上0的分析 ∵ \because ∵题目说明若数组为空默认乘积为 1 1 1所以 0 0 0是坚决不能存在于数组之中必须全部删除。 ∴ \therefore ∴本题相当于拿 0 0 0做挡板把原数组分为很多细分的除0的区间只需要对这部分取 ∣ a i ∣ 2 |a_i|2 ∣ai∣2较多的区间作为留下的数组即可
代码实现
#includebits/stdc.h
using namespace std;const int maxn2e510;
int t,n,cnt0,tot,ansl,ansr;
int a[maxn];
struct node{int u,v,dis;
}f[maxn];
//除0的情况
inline int solve(int l,int r){int num10,num20,mi2maxn,mx20;for(int il;ir;i){if(a[i]0)num1;else {num2;mi2min(mi2,i);mx2i;}}if(num2%20){ansll-1;ansrn-r;}else{int w10,w20;bool flagfalse;for(int il;imi2;i){if(abs(a[i])2)w1;} for(int imx2;ir;i){if(abs(a[i])2)w2;}if(w1w2){ansll-1;ansrn-mx21;}else {anslmi2;ansrn-r;}}int all0;for(int iansl1;in-ansr;i){if(abs(a[i])2)all;}return all;
}
inline bool cmp(node nx,node ny){return nx.disny.dis;}
int main(){scanf(%d,t); while(t--){cnt0tot0;scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);if(a[i]0)cnt0;}if(cnt0n){printf(%d 0\n,n);continue;}if(n1){if(1a[1])printf(1 0\n);else printf(0 0\n);continue;}//有0的预处理分段排序if(cnt00){int k1,k1n;while(a[k]0)k;while(a[k1]0)--k1;int xk,yk;if(kk1){f[tot].ux;f[tot].vy;f[tot].dissolve(f[tot].u,f[tot].v);f[tot].uansl;f[tot].vansr;}for(int ik1;ik1;i){if(a[i-1]0a[i]!0)xyi;if(a[i]!0a[i-1]!0)y;if(a[i]0||ik1){f[tot].ux;f[tot].vy;f[tot].dissolve(f[tot].u,f[tot].v);f[tot].uansl;f[tot].vansr;} }sort(f1,ftot1,cmp);printf(%d %d\n,f[1].u,f[1].v);}else {int osolve(1,n);printf(%d %d\n,ansl,ansr);}}return 0;
} 小方法陈述
应用背景当CF的题目单测试点内的小测试点过多且单一当某小测试点出现错误但因为省略隐藏而不知道错误 实践可以去骗测试点发现问题不断进行历史修补论的内容直到最后 A C AC AC
