Codeforces Round #456(Div.2)

Codeforces

Contests 链接：Codeforces Round #456(Div.2)
过题数：2
排名：702/8188

A. Tricky Alchemy

题意

有三种颜色的球，一个黄色球，需要两个黄色晶体合成，一个绿色球，需要一个黄色和一个蓝色晶体合成，蓝色球需要三个蓝色晶体合成。给出黄色球的个数 $A$ 和蓝色球的个数 $B$，以及所需要的三种颜色的球，问还需要黄蓝两种颜色的球总共多少个？

数据范围

$0\leq A,B\leq10^9\\0\leq x,y,z\leq10^9$

题解

按题意计算出所需要的黄色晶体和蓝色晶体数量，减去已经有的，相加即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
LL x, y, z;
LL a, b;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%I64d%I64d", &a, &b) != EOF) {
        scanf("%I64d%I64d%I64d", &x, &y, &z);
        LL yellow = 2 * x + y;
        LL blue = y + 3 * z;
        LL ans = 0;
        LL tmp;
        tmp = yellow - a;
        if(tmp > 0) {
            ans += tmp;
        }
        tmp = blue - b;
        if(tmp > 0) {
            ans += tmp;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

B. New Year's Eve

题意

给定 $n$ 和 $k$，输出从 $1$ 到 $n$ 中，最多取 $k$ 个数字，相异或，输出能够得到的最大的数字。

数据范围

$1\leq k\leq n\leq10^{18}$

题解

如果只能选一个数字，就输出 $n$，否则输出与 $n$ 的二进制位相同的全为 $1$ 的二进制。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
LL n, k;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%I64d%I64d", &n, &k) != EOF) {
        if(k == 1) {
            printf("%I64d\n", n);
            continue;
        }
        LL nn = n;
        int dig = 0;
        while(nn != 0) {
            ++dig;
            nn >>= 1;
        }
        printf("%I64d\n", ((1LL) << (dig)) - 1);
    }
    return 0;
}

D. Fishes

题意

$Sasha$ 在一个 $n\times m$ 的鱼塘里随机撒网，这个渔网的大小为 $r\times r$。$Misha$ 想在这个鱼塘里放 $k$ 只鱼，每个格子最多只能放一只鱼，问 $Misha$ 要如何放鱼，才能够使得 $Sasha$ 捕到的鱼的期望最大，输出这个期望，精确到小数点后九位。

数据范围

$1\leq n,m\leq10^5\\1\leq r\leq\min(n,m)\\1\leq k\leq\min(n\times m,10^5))$

题解

不论鱼怎么放，计算期望公式的分母都为 $(m-r+1)\times(n-r+1)$，对于每一只放在 $(x,y)$ 位置的鱼，它对分子的贡献为 $(\min(x+r-1,n)-\max(x,r)+1)\times(\min(y+r-1,m)-\max(y,r)+1)$，而且可以确定，在鱼塘的中心位置放鱼，对分子的贡献最大，往外围依次减小，所以可以从中心开始放鱼，用优先队列进行宽搜 $k$ 步，就可以得到最大的分子，除以分母就是结果。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
struct Node {
    LL x, y;
    Node() {}
    Node(LL xx, LL yy) {
        x = xx;
        y = yy;
    }
};
bool operator<(const Node &a, const Node &b) {
    if(a.x == b.x) {
        return a.y < b.y;
    }
    return a.x < b.x;
}
LL n, m, r, k;
set<Node> st;
struct NNode {
    LL x, y;
    LL fenzi;
    NNode() {}
    NNode(LL xx, LL yy) {
        x = xx;
        y = yy;
        fenzi = (min(x + r - 1, n) - max(x, r) + 1) * (min(y + r - 1, m) - max(y, r) + 1);
    }
};
bool operator<(const NNode &a, const NNode &b) {
    return a.fenzi < b.fenzi;
}
priority_queue<NNode> que;
const int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
bool In(LL x, LL y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%I64d%I64d%I64d%I64d", &n, &m, &r, &k);
    LL fenmu = (m - r + 1) * (n - r + 1);
    LL fenzi = 0;
    que.push(NNode(n / 2 + 1, m / 2 + 1));
    st.insert(Node(n / 2 + 1, m / 2 + 1));
    while(!que.empty()) {
        NNode tmp = que.top();
        que.pop();
        fenzi += tmp.fenzi;
        --k;
        if(k == 0) {
            break;
        }
        LL x = tmp.x;
        LL y = tmp.y;
        for(int i = 0; i < 4; ++i) {
            LL xx = x + dir[i][0];
            LL yy = y + dir[i][1];
            if(In(xx, yy) && st.find(Node(xx, yy)) == st.end()) {
                que.push(NNode(xx, yy));
                st.insert(Node(xx, yy));
            }
        }
    }
    printf("%.15f\n", (double)fenzi / fenmu);
    return 0;
}