題意

給兩種顏色的數(shù)量 a 和 b，這兩種顏色恰好組成一個(gè)長(zhǎng)方形，而且至少有一種顏色在整個(gè)長(zhǎng)方形里面也是個(gè)長(zhǎng)方形，求滿足條件中周長(zhǎng)最小的情況

AC

• 當(dāng)a是里面的小長(zhǎng)方形，把a(bǔ)能組成的長(zhǎng)方形的寬記錄一下，然后枚舉大的長(zhǎng)方形的寬 i ，當(dāng)大長(zhǎng)方形的長(zhǎng)sum（a + b）/ i 大于等于小長(zhǎng)方形的長(zhǎng)a / i，這是就可以構(gòu)成一個(gè)合理的長(zhǎng)方形
• 按照上面的思路分別假設(shè)a、b為里面的小長(zhǎng)方形

#include <iostream> #include <cmath> #include <map> #include <vector> #include <set> #include <cstring> #include <queue> #include <algorithm> #define ll long long #define ull unsigned long long #define N 10000005 int len[N]; using namespace std; ll solve(ll a, ll b) {// 把A當(dāng)做矩形 ll ans = (a + b) * 2 + 2;int cnt = 0;for (ll i = 1; i * i <= a; ++i) {if (a % i == 0)len[cnt++] = i; }int now = 0;ll sum = a + b;for (ll i = 1; i * i <= sum; ++i) {if (sum % i == 0) {// 找到最緊湊的矩形 A while (now + 1 < cnt && len[now + 1] <= i) now++;// 如果可以分成寬為 i 的矩形，就更新答案 if (sum / i >= a / len[now])ans = min(ans, (i + sum / i) * 2);}}return ans; }int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endif ll a, b;while (scanf("%lld%lld", &a, &b) != EOF) {ll ans = min(solve(a, b), solve(b, a));printf("%lld\n", ans);}return 0; }

大佬 OTZ

#include <iostream> #include <cmath> #include <map> #include <vector> #include <set> #include <cstring> #include <queue> #include <algorithm> #define ll long long #define ull unsigned long long #define N 10000005 using namespace std;int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endif ll a, b;while (scanf("%lld%lld", &a, &b) != EOF) {ll ans = 1e18;ll sum = a + b;set<ll> st;for (ll i = 1; i * i <= sum; ++i) {// 將a, b能構(gòu)成的長(zhǎng)方形的長(zhǎng)放入set中 if (a % i == 0) st.insert(a / i);if (b % i == 0) st.insert(b / i);// 如果sum可以分成一個(gè)長(zhǎng)方形// 這時(shí)如果存在小長(zhǎng)方形，那么他的寬一定小于等于 i // 如果此時(shí)小長(zhǎng)方形的長(zhǎng)小于大長(zhǎng)方形的長(zhǎng)，就是符合條件的長(zhǎng)方形 if (sum % i == 0 && *st.begin() <= sum / i) ans = min(ans, (sum / i + i) * 2);} printf("%lld\n", ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #506 (Div. 3) - F. Multicolored Markers （思维）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。