Kick Start

Google Kick Start 2019 round D 题解

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

A. X or What?

题目地址

Solution

解法

解题关键在于异或的性质,将数都看作二进制表示,同一位上1和1异或得0, 0和1异或得0, 0和0异或得1:

  • 两数异或,若两个数的二进制表示均有偶数个1,那么异或结果也一定有偶数个1 => 1的个数以2的倍数增减
  • 两数异或,若一个数二进制表示有偶数个1,另一个有奇数个1,那个异或结果有奇数个1
  • 两数异或,若两个数的二进制表示均有奇数个1,那个异或结果有偶数个1

设一个数的二进制表示有奇数个1,则为xor-odd,那么可以得出结论:若一个子区间内中有偶数个xor-odd,那么子区间一定满足xor-even。

由此,可以计算每个数中1的个数,若为奇数,则将其位置放入集合s:

  • 若s的大小为偶数,则子区间为整个集合
  • 若s的大小为奇数,则子区间的一端为s中最小或最大的位置(取决于最后得到的子区间大小)

由于对s进行插入,删除、修改,并希望保持有序,这里可以采用c++的set

复杂度分析

  • 对于每个数求1的个数,再插入set:O(N*logN) time
  • 对于每次修改,可能增/删/查set,每次O(logN) time, 总共Q次,所以O(QlogN) time
    总的时间复杂度为(Q+N)logN time,空间复杂度为O(N) space.

代码

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;

int main()
{
    vector<bool> xorOdd(1025);
    for (int i = 0; i <= 1024; ++i)
    {
        xorOdd[i] = bitset<11>(i).count() & 1;
    }
    auto t = 0;
    cin >> t;
    for (int i = 1; i <= t; ++i)
    {
        cout << "Case #" << i << ":";
        int n, q;
        cin >> n >> q;
        set<int> indexs;
        for (int j = 0; j < n; j++)
        {
            int x;
            cin >> x;
            if (xorOdd[x])
                indexs.insert(j);
        }
        for (int j = 0; j < q; j++)
        {
            int tmp1, tmp2;
            cin >> tmp1 >> tmp2;
            if (indexs.count(tmp1))
                indexs.erase(tmp1);
            if (xorOdd[tmp2])
                indexs.insert(tmp1);
            if (indexs.size() % 2 == 0)
                cout << " " << n;
            else
            {
                int r = *indexs.rbegin();
                int l = *indexs.begin();
                cout<<" "<<max(r, n - l - 1);
            }
        }
        cout << endl;
    }
    return 0;
}

B. Latest Guests

題目地址

Solution

解法

位置的访问时间可以看做时间戳time,仅时间戳最大的会“生效”

问题看上去比较复杂,可以简化问题到简单的情况来进行分析,假设guest只有一种前进方向,不妨设为顺时针,注意此时可以确定的是,那么对于一个guest:

  • guest经过m步,最后访问的位置是确定的(不妨设为i),该位置此时可能有多个guest(m步后处于同一个位置),设这些guest组成一个group;那么此时可能有多个位置有group的存在
  • 从i逆时针向前,直至下一个存在group的位置(or 所有的位置均被遍历),对于中间的位置,group中的guest均是最后一个访问者

有了这样的观察,若guest都是顺时针前进的情况已经可解;加入逆时针的话,情况类似,此时group划分规则有了改变,同一group中:

  • guest经过m步到达的位置相同
  • guest的方向相同

有了group(记录guest最后到达的位置pos,方向dir,是最后访问者的位置个数cnt)的集合groups,问题就比较好解了:

  • 先讨论time=m的情况,groups中的单个group的cnt++, pos则根据方向更新
  • 再讨论time=m-1的情况,groups中的单个group的cnt++, pos则根据方向更新
  • ……
  • 因为只有n个位置,所以结束条件为所有位置均被访问,或者是time< m-n

具体的算法请看代码

note:如果m\ge 2_n, 那么除了第一次走n步,其余的走n步都是对第一次过程的重复,所以如果m\ge 2_n,则m=n+(m\%n). 这样m就缩小到10^5级别了

复杂度分析

  • 划分group: O(G+N) time
  • 遍历: O(N) time (因为只有N个位置)

所以总的时间复杂度O(G+N) time
code

代码

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

using namespace std;

typedef long long ll;

int getMod(int a, int b)
{
    double c = floor(a / (double)b);

    auto tmp = a - c * b;
    return tmp;
}

typedef struct Node
{
    int pos, dir, cnt;
    vector<int> ids;
} Guest;

vector<int> solve(int n, int m, int g, vector<pair<int, int>> &clockwiseGuest, vector<pair<int, int>> &antiGuest)
{
    vector<int> consulates(n, -1);
    vector<Guest> groups;
    vector<vector<int>> guests(n * 2);
    int pos;
    for (auto guest : clockwiseGuest)
    {
        pos = getMod(guest.second + m, n);
        guests[pos].emplace_back(guest.first);
    }
    for (auto guest : antiGuest)
    {
        pos = getMod(guest.second - m, n);
        guests[pos + n].emplace_back(guest.first);
    }
    for (int i = 0; i < n * 2; ++i)
    {
        if (guests[i].empty())
            continue;
        if (i < n)
        {
            groups.emplace_back(Guest{i, -1, 0, guests[i]});
        }
        else
        {
            groups.emplace_back(Guest{i - n, 1, 0, guests[i]});
        }
    }
    int visited = 0;
    m = m > n ? n : m; 
    for (int time = m; time >= 0 && visited < n; --time)
    {
        for (int i = 0; i < groups.size(); ++i)
        {
            pos = groups[i].pos;
            if (consulates[pos] < time)
            {
                visited++;
                consulates[pos] = time;
            }
            if (consulates[pos] == time)
                groups[i].cnt++;
            groups[i].pos = getMod(pos + groups[i].dir, n);
        }
    }

    vector<int> res(g, 0);
    for (auto group : groups)
    {
        for (auto id : group.ids)
        {
            res[id] = group.cnt;
        }
    }
    return res;
}

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

        int n, g, m;
        cin >> n >> g >> m;
        vector<pair<int, int>> clockwiseGuest, antiGuest;
        for (int j = 0; j < g; j++)
        {
            int x;
            char c;
            cin >> x >> c;
            if (c == 'C')
                clockwiseGuest.emplace_back(make_pair(j, x - 1));
            else
                antiGuest.emplace_back(make_pair(j, x - 1));
        }
        auto res = solve(n, m, g, clockwiseGuest, antiGuest);
        cout << "Case #" << i << ":";
        for (auto item : res)
            cout << " " << item;
        cout << endl;
    }
    return 0;
}

C. Food Stalls

题目地址

Solution

解法

最基本的暴力解法:从n个位置选一个作为warehouse,然后从剩下的位置中选k个cost最小的作为food stall。这样的解法可以通过Test 1

当已经从n个位置选出k+1个作为修建地点时,此时cost的总和已经固定,需要做的是:最小化k个food stall到warehouse的距离。由于k+1个点被选出后,位置已经固定,则这是一个经典的“邮局选址问题”,将这k+1的点按位置从小到大排序,那么

  • warehouse建在k_1=k/2的位置时,总的距离最小.

基于这样的观察,将原本n的点按位置排序(输入的点并不是有序的,注意sample 3), warehouse可能的建造点不再是\in [0,n),而是\in [k_1,n-(k-k1)]

再注意观察,设warehouse的位置为x, 其左边的food stall a位置为x_i, 建造开销为c_i;左边的food stall b位置为x_j, 建造开销为c_j,那么a和b的开销分别为:

  • x-x_i+c_i=(c_i-x_i) + x
  • x_j-x+c_j=(x_j+c_j) + x

这么表示的好处是:当warehouse被选定后,x是固定的,那么对于左边的k_1个food stall,其开销与warehouse 无关。那么可以在左边维护大小为k_1的最大堆q1,当warehouse右移时,判断该位置的开销和堆顶元素的大小,如该位置开销较小,则堆pop, 并push当前位置入堆。

右边的过程类似。

那么就得到了一个O(nlogk) time的解法

复杂度分析

O(nlogk) time

代码

code

#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

typedef struct
{
    ll x, c;
} Node;

ll solve(ll n, ll k, vector<Node> &positions)
{
    ll k1 = k / 2;
    ll k2 = k - k1;
    priority_queue<ll> q1;
    priority_queue<p, vector<p>, greater<>> q2;
    unordered_set<ll> indexs;

    ll left = 0;
    for (ll i = 0; i < k1; ++i)
    {
        auto v = positions[i].c - positions[i].x;
        left += v;
        q1.push(v);
    }
    for (ll i = k1 + 1; i < n; ++i)
    {
        q2.push(make_pair(positions[i].c + positions[i].x, i));
    }
    ll right = 0;

    for (ll i = 0; i < k2; ++i)
    {
        auto top = q2.top();
        q2.pop();
        right += top.first;
        indexs.insert(top.second);
    }
    ll res = left + right + k1 * positions[k1].x - k2 * positions[k1].x + positions[k1].c;
    for (ll i = k1 + 1; i < n - k2; ++i)
    {
        auto cur = positions[i];
        if (!q1.empty())
        {
            auto tmp = positions[i - 1].c - positions[i - 1].x;
            if (tmp < q1.top())
            {
                left = left - q1.top() + tmp;
                q1.pop();
                q1.push(tmp);
            }
        }
        if (!indexs.empty())
        {
            if (indexs.count(i))
            {
                indexs.erase(i);
                ll t;
                do
                {
                    t = q2.top().second;
                    q2.pop();
                } while (t <= i);
                indexs.insert(t);
                right = right - positions[i].c - positions[i].x + positions[t].c + positions[t].x;
            }
        }
        res = min(res, left + right + k1 * cur.x - k2 * cur.x + cur.c);
    }
    return res;
}

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

        ll k, n;
        cin >> k >> n;
        vector<Node> positions(n);
        for (ll j = 0; j < n; ++j)
        {
            cin >> positions[j].x;
        }
        for (ll j = 0; j < n; ++j)
        {
            cin >> positions[j].c;
        }
        sort(positions.begin(), positions.end(), [](const Node &a, const Node &b) { return a.x < b.x; });
        auto res = solve(n, k, positions);
        cout << "Case #" << i << ": " << res << endl;
    }
    return 0;
}

发表评论

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