本文主要是介绍Playing with Numbers（Kattis - playingwithnumbers）（预处理瞎搞），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://vjudge.net/problem/Kattis-playingwithnumbers
题目描述：给定n组a b的值，每组表示一个数值2^a*3^b，共进行n次操作，第i次操作可以进行i-1次gcd操作和 n - i次lcm操作，求每次操作后所得最大值及最小值对应的ab分别是多少。每次选取任意两个数进行gcd操作时，只将结果放回这些数字中，lcm也是。
思路：当至少进行2次gcd操作时，一定能将两个最小的ab值mina minb组合到一起，所得最小值一定是2^mina*3minb;至少进行2次lcm操作时，一定能将两个最大的ab值mina minb组合到一起，所得最大值一定是2^maxa*3maxb。当只进行gcd或lcm时，所得结果是唯一的，输出即可。当只进行1次gcd时，也就是要选取一个数与其他n-1个数的lcm进行gcd操作，可以预处理好数组lcm1[i]代表除第i个数的a值以外，其他n-1个数的a值进行lcm结果，遍历一遍取最小值，b值求法相同;当只进行1次lcm时，也就是要选取一个数与其他n-1个数的gcd进行lcm操作得到最大值，可以预处理好数组lcm1[i]代表除第i个数以外的a值，其他n-1个数的a值进行lcm结果，遍历一遍取最大值，b值求法相同。代码写的有点麻烦，但是思路还是很简单的，只要别写晕了就行。吐槽一下只有25组测试数据真的很水，场上我的思路不对队友都可以举出反例来竟然照样能AC，没办法最后五分钟算是交着玩了我也不知道会AC啊，队友对此表示难以接受哈哈。写这道题做的最多的就是复制粘贴，醉了。
代码如下：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=50000+10;
int n;
int a[maxn],b[maxn];
const int inf=0x3f3f3f3f;
struct node{int a, b;int id;node(int a = 0, int b = 0, int id = 0) : a(a), b(b), id(id) {}
}num[maxn];
int gcd1[maxn], lcm1[maxn], gcd2[maxn], lcm2[maxn];
int max1[maxn], max2[maxn], min1[maxn], min2[maxn];
int mmax1[maxn], mmax2[maxn], mmin1[maxn], mmin2[maxn];
int main(){while(~scanf("%d",&n)){int maxa=0,maxb=0,mina=inf,minb=inf;int dyb,dya,ddyb,ddya;for(int i=1; i<=n; i++){scanf("%d%d",&num[i].a,&num[i].b);if(num[i].a > maxa) maxa = num[i].a;//分别找出最大最小的ab值if(num[i].b > maxb) maxb = num[i].b;if(num[i].a < mina) mina = num[i].a;if(num[i].b < minb) minb = num[i].b;}if(n==1){printf("%d %d %d %d\n",num[1].a,num[1].b,num[1].a,num[1].b); continue;}if(n==2){printf("%d %d %d %d\n",maxa,maxb,maxa,maxb);printf("%d %d %d %d\n",mina,minb,mina,minb);continue;}min1[2] = num[1].a; min2[2] = num[1].b;max1[2] = num[1].a; max2[2] = num[1].b;for(int i = 3; i <= n; ++i){min1[i] = min(num[i - 1].a, min1[i - 1]);//min1[i]表示前i-1个数a中的最小值，也就是i前面所有a的gcd结果min2[i] = min(num[i - 1].b, min2[i - 1]);//i前面所有b的gcd结果max1[i] = max(num[i - 1].a, max1[i - 1]);//i前面所有a的lcm结果max2[i] = max(num[i - 1].b, max2[i - 1]);//i前面所有b的lcm结果}mmin1[n - 1] = num[n].a; mmin2[n - 1] = num[n].b;mmax1[n - 1] = num[n].a; mmax2[n - 1] = num[n].b;for(int i = n - 2; i >= 1; --i){mmin1[i] = min(num[i + 1].a, mmin1[i + 1]);//i后面所有a的gcd结果mmin2[i] = min(num[i + 1].b, mmin2[i + 1]);//i后面所有b的gcd结果mmax1[i] = max(num[i + 1].a, mmax1[i + 1]);//i后面所有a的lcm结果mmax2[i] = max(num[i + 1].b, mmax2[i + 1]);//i后面所有b的lcm结果}gcd1[1] = mmin1[1]; lcm1[1] = mmax1[1];gcd2[1] = mmin2[1]; lcm2[1] = mmax2[1];gcd1[n] = min1[n]; lcm1[n] = max1[n];gcd2[n] = min2[n]; lcm2[n] = max2[n];for(int i = 2; i < n; ++i){gcd1[i] = min(min1[i], mmin1[i]);//除第i个数以外其他n-1个a的gcd结果gcd2[i] = min(min2[i], mmin2[i]);//除第i个数以外其他n-1个b的gcd结果lcm1[i] = max(max1[i], mmax1[i]);//除第i个数以外其他n-1个a的lcm结果lcm2[i] = max(max2[i], mmax2[i]);//除第i个数以外其他n-1个a的lcm结果}int cnt = 0;int u,v;int tmp1, tmp2, tmp3, tmp4, x, y;for(int i = 1; i <= n; ++i){tmp1 = tmp2 = 0;tmp3 = tmp4 = 1e9;u = i - 1;//gcdv = n - i;//lcmif(!u){//gcd次数为0，lcm次数为n-1,即求这n个数的最小公倍数，所得结果是唯一的2^maxa*3^maxbprintf("%d %d %d %d\n", maxa, maxb, maxa, maxb); continue;}if(!v){//gcd次数为n-1，lcm次数为0,即求这n个数的最大公约数，所得结果也是唯一的2^mina*3^minbprintf("%d %d %d %d\n", mina, minb, mina, minb); continue;}if(v == 1){//只进行一次lcm时，枚举所有结果取最大值tmp1 = max(num[1].a, gcd1[1]); tmp2 = max(num[1].b, gcd2[1]);for(int i = 2; i <= n; ++i){x = max(gcd1[i], num[i].a); y = max(gcd2[i], num[i].b);//第i个数与其他n-1的数的gcd结果进行lcm操作，也就是取较大者if(x * log(2) + y * log(3) > tmp1 * log(2) + tmp2 * log(3)){tmp1 = x; tmp2 = y;}}}if(u == 1){//只进行一次gcd时，枚举所有结果取最小值tmp3 = min(num[1].a, lcm1[1]); tmp4 = min(num[1].b, lcm2[1]);for(int i = 2; i <= n; ++i){x = min(lcm1[i], num[i].a); y = min(lcm2[i], num[i].b);//第i个数与其他n-1的数的lcm结果进行gcd操作，也就是取较小者if(x * log(2) + y * log(3) < tmp3 * log(2) + tmp4 * log(3)){tmp3 = x; tmp4 = y;}}}if(v >= 2){//进行两次以上lcm，所得最大值一定是2^maxa*3^maxbtmp1 = maxa; tmp2 = maxb;}if(u >= 2){//进行两次以上gcd，所得最小值一定是2^mina*3^minbtmp3 = mina; tmp4 = minb;}printf("%d %d %d %d\n", tmp1, tmp2, tmp3, tmp4);}}return 0;
}/*4
0 0
1 2
2 1
2 23
1 5
4 2
1 15
1 7
2 6
4 5
2 1
9 0*/
这篇关于Playing with Numbers（Kattis - playingwithnumbers）（预处理瞎搞）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
