Kick Start

Google Kick Start 2019 round E 题解

查阅更多的题解,请点击
github传送门

A. Cherries Mesh

题目地址

Solution

解法

这个点心本身就构成了一个完全图,其中的边权值为1或者2,去掉一些边使得甜度最小,并且仍然连通,问题就相当于求一个带权完全图的最小生成树的权值,那么可以采用prim算法,这里是O(n^2) time. 这样的解法可以通过test 1.

注意题目的特殊性:边的权值要么为1,要么为2。我们的结果要求尽可能保留多的权值为1的边。不如根据输入,构建一个仅有权为1的边的图,求这个图的生成森林,设有x个。生成森林之间以权为2的边相连(共x-1条边),那么最终结果为2*(x-1)+n+x

复杂度分析

求生成森林可以用dfs算法,则复杂度为O(n) time. (note: 注意整个dfs过程中,遍历的边数是不超过n的)

代码

code

#include <algorithm>
#include <bitset>
#include <climits>
#include <iostream>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;

const int INF = 1000000000;

typedef struct
{
    int cur;
    vector<int> adv;
} Node;

void dfs(int cur, const vector<vector<int>> &graph, vector<bool> &visited)
{
    visited[cur] = true;
    if (graph[cur].empty())
    {
        return;
    }
    for (auto next : graph[cur])
    {
        if (visited[next])
            continue;
        dfs(next, graph, visited);
    }

}

int slove(int n, vector<vector<int>> &graph)
{
    int cnt = 0;
    vector<bool> visited(n, false);
    for (int i = 0; i < n; ++i)
    {
        if (!visited[i]){
            dfs(i, graph, visited);
            cnt++;
        }
    }
    return 2 * (cnt - 1) + n - cnt;
}
int main()
{

    auto t = 0;
    cin >> t;
    for (int i = 1; i <= t; ++i)
    {

        int n, m;
        cin >> n >> m;
        vector<vector<int>> graph(n);
        for (int j = 0; j < m; j++)
        {
            int x1, x2;
            cin >> x1 >> x2;
            graph[x1 - 1].emplace_back(x2 - 1);
            graph[x2 - 1].emplace_back(x1 - 1);
        }
        auto res = slove(n, graph);
        cout << "Case #" << i << ": " << res << endl;
    }
    return 0;
}

B. Code-Eat Switcher

題目地址

Solution

令request代表一天的要求

解法

对于每个slot,可以用c_i/e_i从大到小排序,即将slot按照code效率从高到底排序,可以用code效率高的slot来满足request中的code要求,再判断剩下的slot能否满足eat的要求。该过程可以通过前缀和来加速:

  • sumCode[i]代表前i个slot全部用于code所得结果,sumEat[i]代表从i+1到第k个slots全部用于eat所得结果

该算法可以通过Test set 1.

上述算法可以通过对requests按code由小到大排序来优化,可以直接利用前一个request的结果来判断后一个request.

复杂度分析

n=max(D,S),那么每个测试用例是O(nlogn) time.

代码

code

#include <algorithm>
#include <bitset>
#include <cfloat>
#include <climits>
#include <iostream>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
const double EPS = 2e-8;

typedef struct
{
    ll code, eat, id;
    char res;
} Node;

void slove()
{
    ll d, s;
    cin >> d >> s;
    vector<pair<ll, ll>> slots(s);
    vector<Node> requests(d);
    vector<ll> sumCode(s + 1, 0), sumEat(s + 1, 0);
    for (ll i = 0; i < s; i++)
        cin >> slots[i].first >> slots[i].second;

    sort(slots.begin(), slots.end(), [](const pair<ll, ll> &a, const pair<ll, ll> &b) { return a.first * b.second > a.second * b.first; });

    for (ll i = 0; i < d; i++)
    {
        cin >> requests[i].code >> requests[i].eat;
        requests[i].id = i;
    }

    sort(requests.begin(), requests.end(), [](const Node &a, const Node &b) { return a.code < b.code; });
    for (ll i = 1; i <= s; ++i)
        sumCode[i] = slots[i - 1].first + sumCode[i - 1];
    for (ll i = s - 1; i >= 0; --i)
        sumEat[i] = slots[i].second + sumEat[i + 1];

    vector<char> res(d);
    for (ll i = 0, pos = 0; pos < d; ++pos)
    {
        auto &cur = requests[pos];
        while (i < s - 1 && sumCode[i + 1] < cur.code)
            i++;
        if (sumCode[i + 1] >= cur.code && sumEat[i + 1] >= cur.eat)
            cur.res = 'Y';
        else
        {
            auto code = cur.code - sumCode[i];
            auto eat = cur.eat - sumEat[i + 1];
            if (slots[i].first < code || slots[i].second < eat)
                cur.res = 'N';
            else if (slots[i].first == 0)
                cur.res = slots[i].second >= eat ? 'Y' : 'N';
            else
            {
                double f = code / ((double)slots[i].first + EPS);
                cur.res = (1 - f) * slots[i].second + DBL_MIN >= eat ? 'Y' : 'N';
            }
        }
    }
    sort(requests.begin(), requests.end(), [](const Node &a, const Node &b) { return a.id < b.id; });

    for (auto item : requests)
        cout << item.res;
}
int main()
{
    auto t = 0;
    cin >> t;
    for (ll i = 1; i <= t; ++i)
    {
        cout << "Case #" << i << ": ";
        slove();
        cout << endl;
    }
    return 0;
}

C. Street Checkers

题目地址

Solution

解法

将题意翻译一下:Alice会涂上颜色的瓷砖个数为X的奇数因子的个数;Bob会涂上颜色的瓷砖个数为X的偶数因子的个数,该题就变成了因式分解相关的问题。

注意一个特性:

  • X=2^k_P, 其中P是一个奇数,设P的奇数因子集合为O,那么X的奇数因子集合同样为O且偶数因子集合为E={2_O,2^2_O,\dots,2^k_O}

note: 2^{k-1}*P和2^k*P可能存在交集,在集合E中取不相交的部分

有了这样的特性,我们只需要关注X的奇数因子集合O。题目给出1\leq L\leq R\leq 10^6,则一定有1\in O,由此若 X=2^k_P,其中k>2\ and\ p>1时,那么游戏一定是无聊的,因为count(O,2^2_O)>2

基于以上的观察,我们有以下的结论,对于X=2^k*P

  • k=0,X不存在偶数因子,若奇数因子的个数大于2(P不是质数),则游戏无聊;若P为质数,则游戏有趣
  • k=1, X的偶数因子和奇数因子个数相同,游戏有趣
  • k=2, 若奇数因子的个数大于2(P不是质数),则游戏无聊;若P为质数,则游戏有趣
  • k=3,当且仅当p=1时,游戏有趣
  • k>3,游戏一定无趣

最后该问题变成了一个判断是否为质数的问题,采用Miller–Rabin

复杂度分析

Miller–Rabin的时间复杂度为O(log^3n) time.

代码

code

#include <algorithm>
#include <bitset>
#include <cfloat>
#include <climits>
#include <iostream>
#include <random>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;

namespace Prime
{
default_random_engine e;
long long power_mod(long long x, long long n, long long mod)
{
    long long ret = 1;
    while (n)
    {
        if (n & 1)
            ret = x * ret % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ret;
}
long long mulmod(long long x, long long y, long long n)
{
    return x * y % n;
}
bool witness(long long a, long long n, long long u, long long t)
{
    long long x0 = power_mod(a, u, n), x1;
    for (int i = 1; i <= t; ++i)
    {
        x1 = mulmod(x0, x0, n);
        if (x1 == 1 && x0 != 1 && x0 != n - 1)
            return false;
        x0 = x1;
    }
    if (x1 != 1)
        return false;
    return true;
}

bool miller_rabin(long long n, int times = 20)
{
    if (n < 2)
        return false;
    if (n == 2)
        return true;
    if (!(n & 1))
        return false;
    long long u = n - 1, t = 0;
    while (u % 2 == 0)
    {
        t++;
        u >>= 1;
    }
    uniform_int_distribution<long long> rand(1, n - 1);
    while (times--)
    {
        long long a = rand(e);
        if (!witness(a, n, u, t))
            return false;
    }
    return true;
}
}; // namespace Prime

bool isPrime(ll x)
{
    return x == 1 || Prime::miller_rabin(x);
}

void slove()
{
    ll l, r;
    cin >> l >> r;
    int res = 0;
    for (ll i = l; i <= r; ++i)
    {
        ll cnt = 0;
        ll cur = i;
        while (cur % 2 == 0)
        {
            cnt++;
            cur /= 2;
        }
        if (cnt == 1)
        {
            res++;
        }
        else if (cnt == 0 || cnt == 2)
        {
            if (isPrime(cur))
                res++;
        }
        else if (cnt == 3)
        {
            if (cur == 1)
                res++;
        }
        else
        {
            continue;
        }
    }
    cout << res << endl;
}
int main()
{
    auto t = 0;
    cin >> t;
    for (ll i = 1; i <= t; ++i)
    {
        cout << "Case #" << i << ": ";
        slove();
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注