冻葱Tewi
一个菜鸡。
冻葱Tewi
【题解】队内训练题解 – NCPC 2014

如题目所示,这是一次实验室训练赛的部分题解。这三道题的题解由我们小队负责,我在整理排版完之后以一种谜之”物尽其用”的想法发在了这里。算是水文章吧。

比赛复现地址:

Code Forces Gym 100502

Virtual Judge 295591

C – Catalan Square

题目大意

数学题,求​ \(\frac {C^{n+1}_{2(n+1)}} {n+2}, 0 ≤ n ≤ 5000​\)

题意分析

使用Java乱搞。

代码示例

import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt() + 1; // 注意这里加了1
        BigInteger ans = BigInteger.valueOf(1);
        for (int i = n + 1; i <= 2 * n; ++i)
            ans = ans.multiply(BigInteger.valueOf(i));
        for (int i = 2; i <= n; ++i)
            ans = ans.divide(BigInteger.valueOf(i));

        ans = ans.divide(BigInteger.valueOf(n + 1));
        System.out.println(ans);
    }
}

D – Dice Game

题目大意

投两个骰子,点数之和大的人胜利。

Emma和Gunnar各有两个骰子,给出每个骰子可投出点数的区间,求谁赢的几率大。

(所有骰子的点数不大于100。)

题意分析

因为发现点数的数据范围很小,直接暴力预处理出所有可能的结果。再比较两人的平均点数就可以得出答案。

代码示例

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int ga1, ga2, gb1, gb2;
    int ea1, ea2, eb1, eb2;
    cin >> ga1 >> ga2 >> gb1 >> gb2 >> ea1 >> ea2 >> eb1 >> eb2;
    ll e = 0, g = 0, et = 0, gt = 0;
    for (int i = ga1; i <= ga2; ++i)
        for (int j = gb1; j <= gb2; ++j)
            g += i + j, ++gt;
    for (int i = ea1; i <= ea2; ++i)
        for (int j = eb1; j <= eb2; ++j)
            e += i + j, ++et;

    if (e * gt > et * g)
        puts("Emma");
    else if (e * gt < et * g)
        puts("Gunnar");
    else
        puts("Tie");
    return 0;
}

E – Opening Ceremony

题目大意

n栋房子,每栋房子的层数不尽相同。我们要用一种加农炮摧毁所有的房子。

对于每次操作,我们可以:

  1. 竖直方向,完全摧毁一栋房子;
  2. 水平方向,摧毁所有房子的某一层,上方房子下落。

求摧毁所有房子所需的最小操作次数。

题意分析

可以发现,房子的位置对答案没有影响,所以可以先从低到高排序。接着,对于某一层房子,有两种选择:水平摧毁 和 竖直摧毁。

设将前半部分房子被水平摧毁,后半部分房子竖直摧毁,设f[i]为以i为分界点时需要的操作次数,可以得到:$$ans = min(f[ i ]), i ∈ [1, n]​$$

对于\(f[i]​\)​,有$$f[i] = h[i] + (n – i)​$$​ 其中,​\(h[i]​\)是前半部分最高的建筑,前半部分需要的操作次数等于它的高度,​\(n-i\)是后半部分的房子总数,即后半部分需要的操作次数。

到此,代码便很容易写出。

代码示例

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
int h[MAXN], n;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin>>n; for (int i = 1; i <= n; i++) cin>>h[i];
    
    sort(h + 1, h + n + 1, [](int a, int b)->bool{return a < b;});
        
    int ans = n;
    for (int i = 1; i <= n; i++)
    {
        ans = min(ans, h[i] + n - i);
    }
    cout<<ans<<"\n";
    return 0;
}
赞赏
本站采用BY-NC-SA-4.0 国际许可协议, 转载请保留出处。
https://dctewi.com/wp-content/uploads/2019/02/head-croped-small-middle-300x300.jpg

冻葱Tewi

文章作者

这个站点的蒟蒻站长~欢迎大家来晃悠!

发表评论

textsms
account_circle
email

冻葱Tewi

【题解】队内训练题解 – NCPC 2014
这是一次实验室训练赛的部分题解。这三道题的题解由我们小队负责,我在整理排版完之后以一种谜之"物尽其用"的想法发在了这里。 其实就是在水文章()
扫描二维码继续阅读
2019-04-16
标签云
隐藏
变装