正文

2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018) - 4.28

IP云
IP云V管理员/0 阅读
12/02
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

赛后补了几道

赛中我就写了两个...

A - Altruistic AmphibiansGym - 101933A

看了眼榜没几个人做。就没看。

最后发现就是一个DP（但是我觉得复杂度有点迷）

题意：$n$只青蛙有参数$l,w,h$分别表示弹跳力，体重，身高，在一口深为$d$的井里

一只青蛙不能承受比他重的重量，问最多有多少只能出去（达到高度严格大于d）

重的肯定比轻的晚出去，那么轻的肯定由重的来转移，所以先排序，从重到轻的排

$dp_{i}$表示体重为i最高能叠多高 瞎jb转移一下就好了 

#include <cstdio>

#include <algorithm>

#include <cstring>

#define ll long long

using namespace std;

inline int read() {

    int x = , f = ; char ch = getchar();

    while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }

    while (ch >= '' && ch <= '') { x = x *  + ch - ''; ch = getchar(); }

    return x * f;

}

const int N = 1e5 + ;

const int M = 1e8 + ;

struct P {

    int l, w, h;

    bool operator < (const P &rhs) const {

        return w > rhs.w;

    }

} p[N];

int dp[M], n, d, ans;

int main() {

    n = read(), d = read();

    for (int i = ; i <= n; i++) p[i].l = read(), p[i].w = read(), p[i].h = read();

    ans = ;

    sort(p + , p + n + );

    for (int i = ; i <= n; i++) {

        if (dp[p[i].w] + p[i].l > d) ans++;

        for (int j = p[i].w + ; j < min(p[i].w * , M); j++) {

            dp[j - p[i].w] = max(dp[j-p[i].w], dp[j] + p[i].h);

        }

    }

    printf("%d\n", ans);

    return ;

}

B - Baby Bites Gym - 101933B 
#include <cstdio>

#include <cstring>

using namespace std;

const int N = ;

int a[N];

int n;

char s[N];

int main() {

    scanf("%d", &n);

    bool ans = true;

    for (int i = ; i <= n; i++) {

        scanf("%s", s);

        int len = strlen(s);

        if (s[] == 'm') a[i] = i;

        else {

            int x = ;

            for (int j = ; j < len; j++) x = x *  + s[j] - '';

            a[i] = x;

            if (x != i) {

                ans = false;

            }

        }

    }

    puts(ans?"makes sense":"something is fishy");

    return ;

}

C - Code Cleanups Gym - 101933C

阅读理解题啊。自己瞎糊了一发。读不下去。就丢给队友了。

不管了。

E - Explosion Exploit Gym - 101933E

题意：分别有$n,m$个士兵，每个士兵有一个血量，有d个攻击，等概率分给每一个士兵。

问敌方士兵全死（m）的概率是多少

队友过的。学习了新知识，概率记忆化+状压

用一个long long来表示状态

unordered_map来存状态对应的概率 再回溯搜索即可 tql 

#include <bits/stdc++.h>

#define ll long long

using namespace std;

inline int read() {

    int x = , f = ; char ch = getchar();

    while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }

    while (ch >= '' && ch <= '') { x = x *  + ch - ''; ch = getchar(); }

    return x * f;

}

unordered_map<ll, double> mp;

int a[][];

ll getsta() {

    ll ret = ;

    for (int i = ; i <= ; i++) ret = ret *  + 1LL * a[][i];

    for (int i = ; i <= ; i++) ret = ret *  + 1LL * a[][i];

    return ret;

}

double dfs(ll sta, int d) {

    if (mp.count(sta)) return mp[sta];

    if (sta < ) return ;

    if (d == ) return ;

    int sum = ;

    for (int i = ; i < ; i++)

        for (int j = ; j <= ; j++)

            sum += a[i][j];

    double ret = ;

    for (int i = ; i < ; i++) {

        for (int j = ; j <= ; j++) {

            if (!a[i][j]) continue;

            a[i][j]--;

            a[i][j-]++;

            ll s = getsta();

            double res = dfs(s, d - );

            a[i][j]++;

            a[i][j-]--;

            mp[s] = res;

            ret += a[i][j] * 1.0 / sum * res;

        }

    }

    return ret;

}

int main() {

    int n = read(), m = read(), d = read();

    for (int i = , x; i <= n; i++) x = read(), a[][x]++;

    for (int i = , x; i <= m; i++) x = read(), a[][x]++;

    double res = dfs(getsta(), d);

    printf("%.8f\n", res);

    return ;

}

H - House Lawn Gym - 101933H

题意：有m台机器，每台机器有名字，价格p，每分钟能工作多少c，充一次电能工作多久t，充电需要多久r

有l面积的地待作，问平均每周能工作一次的机器中价格最小的那个，相同的按输入顺序输出

队友把10080说成10800能忍？

平均一下直接就把充电需要的时间给平均进来 得到每分钟工作多少的p'

再用$l/p'$和10080比就得出答案了

可能难就难在输入部分吧。 

#include <bits/stdc++.h>

using namespace std;

struct Node

{

    string name;

    int p , c, t, r;

    double cc;

}b[];

bool vis[];

int main()

{

    ios::sync_with_stdio(false);

    int m;

    int l;

    cin >> l >> m;

    string a;

    getline(cin,a);

    for(int i=;i<=m;i++)

    {

        getline(cin,a);

        int sta = ;

        b[i].name = "";

        b[i].p = b[i].c = b[i].r = b[i].t = ;

        for(int j=;j<a.length();j++)

        {

            if(a[j]==',')

            {

                sta++;

                continue;

            }

            if(sta == )

            {

                b[i].name+=a[j];

            }

            if(sta == )

            {

                b[i].p*=;

                b[i].p+=a[j]-'';

            }

            if(sta == )

            {

                b[i].c*=;

                b[i].c+=a[j]-'';

            }

            if(sta == )

            {

                b[i].t*=;

                b[i].t+=a[j]-'';

            }

            if(sta == )

            {

                b[i].r*=;

                b[i].r+=a[j]-'';

            }

        }

    }

    int ans = 1e9;

    for (int i = ; i <= m; i++) {

        b[i].cc = (b[i].c * b[i].t) * 1.0 / (b[i].t + b[i].r);

        if (l / b[i].cc <= ) {

            ans = min(ans, b[i].p);

            vis[i] = ;

        }

    }

    if (ans == (int)1e9) puts("no such mower");

    else {

        for (int i = ; i <= m; i++) {

            if (vis[i] && ans == b[i].p) {

                cout << b[i].name << '\n';

            }

        }

    }

    return ;

}

J - Jumbled String Gym - 101933J

题意： 0 1串 给你00出现的次数a 01出现的次数b 10出现的次数c 11出现的次数d

问能否构造出01串

WA了好几发 一度崩溃

首先由a d能推出0和1的个数 必定是一个C(n, 2) 把a和d乘二开根 和加一相乘是否等于2a和2d来判断

第二部分

用两个数组表示

$a_{i}$表示第i个0后面出现了几个1

$b_{i}$表示第i个0前面出现了几个1

必定有$a_{i} + b_{i} = cnt_{1}$        $a_{i}\geq a_{i+1}$        $b_{i}\leq b_{i+1}$

$\sum ^{cnt_{0}}_{i=1}a_{i} = b$            $\sum ^{cnt_{0}}_{i=1}b_{i} = c$

所以$b + c = cnt_{0}\times cnt_{1}$才有解

随便举几个例子发现贪心的构造均能满足答案

如样例 3 4 2 1

得到$cnt_{0} = 3$   $cnt_{1} = 2$

$a_{i}$ : 2 2 0

$b_{i}$ : 0 0 2

得到 00110 也符合

所以直接构造就完了

不过要注意

0 0 0 0直接输出0或1就可以了

a为0或d为0的情况 如果$b + c = 0$ 那么对应的0的个数或1的个数为0 否则才为1

然后瞎jb输出就完了 

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

inline int read() {

    int x = , f = ; char ch = getchar();

    while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar();}

    while (ch >= '' && ch <= '') { x = x *  + ch - ; ch = getchar(); }

    return x * f;

}

int main() {

    int a = read(), b = read(), c = read(), d = read();

    int sqra = sqrt( * a), sqrd = sqrt( * d);

    bool ans = true;

    if ((a + b + c + d) == ) {

        puts("");

        return ;

    }

    if (sqra * (sqra + ) != a *  || sqrd * (sqrd + ) != d * ) {

        ans = false;

    } else {

        int cnt0 = sqra, cnt1 = sqrd;

        cnt0++, cnt1++;

        if (cnt1 ==  && (b + c) == ) cnt1 = ;

        if (cnt0 ==  && (b + c) == ) cnt0 = ;

        //printf("%d %d\n", cnt0, cnt1);

        if (b + c != cnt0 * cnt1) {

            ans = false;

        } else {

            if (cnt1 == ) {

                while (cnt0--) putchar('');

                return ;

            }

            if (cnt0 == ) {

                while (cnt1--) putchar('');

                return ;

            }

            int k = b / cnt1;

            for (int i = cnt0; i > cnt0 - k; i--) putchar('');

            cnt0 -= k;

            k = b - k * cnt1;

            if (k) {

                k = cnt1 - k;

                for (int i = cnt1; i > cnt1 - k; i--) putchar('');

                cnt1 -= k;

                putchar(''), cnt0--;

            }

            while (cnt1--) putchar('');

            while (cnt0--) putchar('');

            return ;

        }

    }

    if (!ans) puts("impossible");

    return ;

}

K - King's Colors Gym - 101933K

题意：一棵树n个节点，k种颜色，问有多少种方案用上k个颜色并且相邻两节点颜色不同

我以为要用树形dp做，赛后看题解才明白是个容斥。

用k种的情况是$k\times \left( k-1\right) ^{n-1}$然后其中包含了只用了k-1种 只用了k-2种...的情况

容斥一下就好了 

#include <bits/stdc++.h>

#define ll long long

using namespace std;

inline ll read() {

    ll x = , f = ; char ch = getchar();

    while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }

    while (ch >= '' && ch <= '') { x = x *  + ch - ''; ch = getchar(); }

    return x * f;

}

const ll mod = 1e9 + ;

const int N = ;

ll C[N][N];

void init() {

    for (int i = ; i < N; i++) C[i][] = , C[i][] = i;

    for (int i = ; i < N; i++)

        for (int j = ; j <= i; j++)

            C[i][j] = (C[i-][j-] + C[i-][j]) % mod;

}

ll qm(ll a, ll b) {

    ll res = ;

    while (b) {

        if (b & ) res = res * a % mod;

        a = a * a % mod;

        b >>= ;

    }

    return res;

}

int main() {

    init();

    ll n = read(), k = read();

    for (int i = ; i < n; i++) read();

    ll ans = , flag = ;

    for (int i = k; i >= ; i--) {

        ll temp = flag * i * qm((ll)i - , n - ) % mod * C[k][i];

        ans = (ans + temp + mod) % mod;

        flag = -flag;

    }

    printf("%lld\n", ans);

    return ;

}

相关阅读

目录[+]