Ryan's WorkSpace
  • 首页
  • 关于我
  1. 首页
  2. 算法
  3. 正文

2018 计蒜之道 初赛 第五场

2018年05月29日 1115点热度 0人点赞 0条评论

内容纲要

由题可知最大情况为(n + 1) * 3 * 3 - n,然而我们无法得知最小情况时三个数之间的关系。

故考虑DP打表,算出某个数两个数相乘时最小的值,由该值递推第三个数。

打表算法O(nlogn),查询O(1)

A题代码

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#include <deque>
#include <cmath>
#include <cstring>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 1e6 + 6;
int T, n;
array<int, maxn> dp, dp2;

int main() {
    ios::sync_with_stdio(false);
    ([&]() -> void {
        dp.fill(1e9);
        dp2.fill(1e9);
        for (int i = 1; i <= 1e6; ++i) {
            for (int j = 1; i * j <= 1e6; ++j) {
                dp[i * j] = min(dp[i * j], (i + 2) * (j + 2));
            }
        }
        for (int i = 1; i <= 1e6; ++i) {
            for (int j = 1; i * j <= 1e6; ++j) {
                dp2[i * j] = min(dp2[i * j], dp[i] * (j + 1));
            }
        }
    })();
    cin >> T;
    while (T--) {
        cin >> n;
        int ansmax = (n + 1) * 3 * 3 - n;
        int ansmin = dp2[n] - n;
        cout << ansmin << " " << ansmax << endl;
    }
}

B

根据题意枚举n范围内的f(x),用哈希表保存,打表结束后对表进行枚举,算出符合条件的个数即可

B/C题代码:


#pragma GCC optimize("O3")

#include <iostream>
#include <algorithm>
#include <array>
#include <limits>
#include <cmath>
#include <map>
#include <iomanip>
#include <unordered_map>
#include <regex>
#include <queue>
#include <functional>

using namespace std;
using ll = long long;
using db = double;
using pll = pair<ll, ll>;
const ll mod = 998244353;

ll f(ll x) {
    ll ans = 1;
    while (x) {
        ans *= (x % 10);
        x /= 10;
    }
    return ans;
}

unordered_map<ll, ll> mp;

int main() {
    ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    ll cnt = 0;
    for (ll i = 1; i <= n; ++i) {
        ll fi = f(i);
        if (fi)
            ++mp[fi];
    }
    for (auto i:mp) {
        for (auto j:mp) {
            ll g = __gcd(i.first, j.first);
            if (g > 0 && g <= k) {
                cnt = (cnt + i.second * j.second) % mod;
            }
        }
    }
    cout << cnt << endl;
}

相关

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: C++ DP 计蒜之道
最后更新:2018年06月12日

Ryan Lee

如果帮助到你,请点击广告,谢谢!

点赞
< 上一篇
下一篇 >

文章评论

您需要 登录 之后才可以评论

如果帮助到你,请点击广告,谢谢!

用户您好!请先登录!
登录 注册
Social Media
Github: ryanlee2014
标签聚合
C++ Apache GitHub C Java php hustoj JavaScript
友链
Pacolyon
Lucien's blog
Slian's DreamWork
卡拉搜索
  • 0
  • 15,321
  • 5,558
  • 0
广告

COPYRIGHT © 2020 Ryan's WorkSpace. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

登录
注册|忘记密码?