喀什网站建设百度推广,重庆一次可以备案多少个网站,建网站卖广告,建设旅游网站近似乘积
jzoj 3925
题目大意
给你一个集合A和n让你求不在集合A内的x、y、z#xff0c;使∣n−xyz∣|n-xyz|∣n−xyz∣最小
输入样例
3
2 2 4
4
1 1
7
2 1 15
90输出样例
1 1 3
2 2 2
2 5 9数据范围
40% 的数据#xff1a;1⩽m⩽10#xff0c;1⩽n⩽100.1 \leqslant …近似乘积
jzoj 3925
题目大意
给你一个集合A和n让你求不在集合A内的x、y、z使∣n−x×y×z∣|n-x×y×z|∣n−x×y×z∣最小
输入样例
3
2 2 4
4
1 1
7
2 1 15
90输出样例
1 1 3
2 2 2
2 5 9数据范围
40% 的数据1⩽m⩽101⩽n⩽100.1 \leqslant m\leqslant 101 \leqslant n \leqslant 100.1⩽m⩽101⩽n⩽100. 70% 的数据1⩽m,n⩽1000.1 \leqslant m, n \leqslant 1000.1⩽m,n⩽1000. 100% 的数据1⩽m,n,Ai⩽1061⩽T⩽4.1 \leqslant m, n, Ai \leqslant 10^61 \leqslant T \leqslant 4.1⩽m,n,Ai⩽1061⩽T⩽4.
解题思路
我们可以直接枚举x和y然后z用n除x和y来求 我们保证x×y小于n 因为x×y大于n那x×y×z-n就大于x×x×z-n了xy 如果xy且x×xn那在外面在判断一次就行了具体看代码
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
ll t, n, m, w, x, y, z1, z2, ans, ansa, ansb, ansc, next, last, p[2000500], a[2000500], nx[2000500], ls[2000500];
int main()
{scanf(%lld, t);while(t--){memset(p, 0, sizeof(p));w 0;scanf(%lld, m);for (ll i 1; i m; i){scanf(%lld, x);p[x] 1;//不能选}scanf(%lld, n);for (ll i 1; i n; i){if (!p[i]) a[w] i, last i;//a是n之内能选的ls[i] last;//上一个可以选的}if (!w) a[1] 2000010;for (ll i n * 2 10; i 0; --i){if (!p[i]){next i;if (!w) a[1] min(a[1], i);//如果n之内没有能选的就选一个最小的n之外的能选的}nx[i] next;//下一个能选的}if (!w) w 1;ans (n * 2 10) * (n * 2 10) * (n * 2 10);for (ll i 1; i w; i)for (ll j i; i * j w; j){x a[i];y a[j];z1 ls[n / (x * y)];//往左对齐z2 nx[n / (x * y) 1];//往右对齐if (z1 0 !p[z1] abs(n - x * y * z1) ans)//z可以选且更优{if (abs(n - x * y * z1) ans || x ansa || x ansa y ansb || x ansa y ansb z1 ansc)//ans更优或答案更优{ansa x;ansb y;ansc z1;}ans abs(n - x * y * z1);}if (z2 0 !p[z2] abs(n - x * y * z2) ans)//同上{if (abs(n - x * y * z2) ans || x ansa || x ansa y ansb || x ansa y ansb z2 ansc){ansa x;ansb y;ansc z2;}ans abs(n - x * y * z2);}}if (abs(n - a[1] * a[1] * a[1]) ans)//保证有答案{if (abs(n - a[1] * a[1] * a[1]) ans || a[1] ansa || a[1] ansa a[1] ansb || a[1] ansa a[1] ansb a[1] ansc){ansa a[1];ansb a[1];ansc a[1];}ans abs(n - a[1] * a[1] * a[1]);}printf(%d %d %d\n, ansa, ansb, ansc);}return 0;
}
