本文主要是介绍CodeForces 490D Chocolate，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
2块矩形巧克力 如果边长可以整除2 则可以从一半出掰开 吃掉一半 如果可以整除3 则可以从1/3处掰开 吃掉1/3 问 最少吃几次 能使得2块面积相同 输出最后时刻的边长
思路：
面积最多只有10^18 因此形成的面积的种类数最多几万种 我们可以利用面积来暴搜出所有状态 然后找面积相同时的最少步数
PS：数论的方法更好
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long LL;
#define N 1000010int a[2], b[2];
map<LL, int> res[2];
map<LL, pair<int, int> > way[2];
map<LL, int>::iterator it1, it2;
struct node {int x, y;
} f1, f2;
queue<node> q;
int ans;
LL fzc;int main() {LL u, v;int now;scanf("%d%d%d%d", &a[0], &b[0], &a[1], &b[1]);res[0][(LL) (a[0]) * b[0]] = 0;res[1][(LL) (a[1]) * b[1]] = 0;way[0][(LL) (a[0]) * b[0]] = make_pair(a[0], b[0]);way[1][(LL) (a[1]) * b[1]] = make_pair(a[1], b[1]);for (int i = 0; i <= 1; i++) {f1.x = a[i];f1.y = b[i];q.push(f1);while (!q.empty()) {f1 = q.front();u = (LL) (f1.x) * f1.y;q.pop();now = res[i][u];if (u % 2 == 0) {v = u / 2;if (!res[i].count(v)) {res[i][v] = now + 1;if (f1.x % 2 == 0) {f2.x = f1.x / 2;f2.y = f1.y;} else {f2.x = f1.x;f2.y = f1.y / 2;}way[i][v] = make_pair(f2.x, f2.y);q.push(f2);}}if (u % 3 == 0) {v = u / 3 * 2;if (!res[i].count(v)) {res[i][v] = now + 1;if (f1.x % 3 == 0) {f2.x = f1.x / 3 * 2;f2.y = f1.y;} else {f2.x = f1.x;f2.y = f1.y / 3 * 2;}way[i][v] = make_pair(f2.x, f2.y);q.push(f2);}}}}ans = -1;for (it1 = res[0].begin(), it2 = res[1].begin();it1 != res[0].end() && it2 != res[1].end();) {if ((*it1).first == (*it2).first) {if (ans == -1 || (*it1).second + (*it2).second < ans) {ans = (*it1).second + (*it2).second;fzc = (*it1).first;}it1++;it2++;} else if ((*it1).first > (*it2).first)it2++;elseit1++;}printf("%d\n", ans);if (ans >= 0) {pair<int, int> tp1 = way[0][fzc], tp2 = way[1][fzc];printf("%d %d\n", tp1.first, tp1.second);printf("%d %d\n", tp2.first, tp2.second);}return 0;
}这篇关于CodeForces 490D Chocolate的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
