牛客网 - 北京信息科技大学第十一届程序设计竞赛

Problem A kotori和糖果

题目链接:https://ac.nowcoder.com/acm/contest/940/A/

题意:合并，求最小代价值。
思路:将一个堆二分，递归求该堆合并的最小代价值。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cnt[100005], n;
ll slove(ll x) {
    if (x <= 100000) {
        if (cnt[x])
            return cnt[x];
        if (x < 2 || !(x & (x - 1)))
            return cnt[x] = 0;
        if (x & 1)
            return cnt[x] = slove(x >> 1) + slove((x >> 1) + 1) + 1;
        return cnt[x] = slove(x >> 1) << 1;
    }
    if (x < 2 || !(x & (x - 1)))
        return 0;
    if (x & 1)
        return slove(x >> 1) + slove(x >> 1 + 1) + 1;
    return slove(x >> 1) << 1;
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &n);
        printf("%lld\n", slove(n));
    }
    return 0;
}

Problem B kotori和气球

题目链接:https://ac.nowcoder.com/acm/contest/940/B/

题意:求满足要求的m个气球的排列数。
思路:组合数学，第1个有n种选择，则剩余的m-1个都只有n-1种选择，故总的排列数为。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int MOD = 109;
int pow_(int a, int b) {
    int cnt = 1;
    while (b) {
        if (b & 1)
            cnt = cnt * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return cnt;
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    printf("%d\n", pow_(n - 1, m - 1) * n % MOD);
    return 0;
}

Problem C kotori和出道

题目链接:https://ac.nowcoder.com/acm/contest/940/C/

题意:约瑟夫环问题。
思路:数据过大不能用递归解决，打表找规律得2*(n-cnt)+1, 其中cnt为不大于n的最大2的整数幂。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int t;
    ll n;
    scanf("%d", &t);
    while (t--) {
        ll cnt = 1;
        scanf("%lld", &n);
        while (cnt << 1 <= n)
            cnt <<= 1;
        printf("%lld\n", ((n - cnt) << 1) + 1);
    }
    return 0;
}

Problem D kotori和迷宫

题目链接:https://ac.nowcoder.com/acm/contest/940/D/

题意:问能到达的出口数量和最近的出口距离。
思路:BFS。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
struct edge {
    int x, y, t;
}p;
char mp[35][35];
int n, m, cnt = 0, min_ = inf, vis[35][35];
int arr[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}}; 
void BFS(int x, int y) {
    int tx, ty;
    queue <edge> Q;
    Q.push((edge){x, y});
    while (!Q.empty()) {
        p = Q.front();
        Q.pop();
        if (mp[p.x][p.y] == 'e') {
            cnt++;
            min_ = min(min_, p.t);
            continue;
        }
        for (int i = 0; i < 4; i++) {
            tx = p.x + arr[i][0];
            ty = p.y + arr[i][1];
            if (tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty] && mp[tx][ty] != '*'){
                vis[tx][ty] = true;
                Q.push((edge){tx, ty, p.t + 1});
            }
        }
    }
}
int main() {
    int ex, ey;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %c", &mp[i][j]);
            if (mp[i][j] == 'k')
                ex = i, ey = j;
        }
    }
    BFS(ex, ey);
    if (min_ < inf)
        printf("%d %d\n", cnt, min_);
    else printf("-1\n");
    return 0;
}

Problem E kotori和素因子

题目链接:https://ac.nowcoder.com/acm/contest/940/E/

题意:每个都贡献一个素因子，保证所有的素因子互不相同，求素因子和的最小值。
思路:线性筛出1~1000之内的所有素数，然后DFS求解最小值。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1005;
const int inf = 0x3f3f3f3f;
bool isprime[MAXM];
int n, cnt = 0, min_ = inf, s[15], pre[MAXM], vis[MAXM];
void prime() {
    isprime[0] = isprime[1] = true;
    for (int i = 2; i < MAXM; i++) {
        if (!isprime[i])
            pre[cnt++] = i;
        for (int j = 0; j < cnt && i * pre[j] < MAXM; j++) {
            isprime[i *pre[j]] = true;
            if (!(i % pre[j]))
                break;
        }
    }
}
void DFS(int x, int ans) {
    if (x >= n) {
        if (min_ > ans)
            min_ = ans;
        return ;    
    }
    for (int i = 0; i < cnt; i++) {
        if (!(s[x] % pre[i]) && !vis[pre[i]]) {
            vis[pre[i]] = true;
            DFS(x + 1, ans + pre[i]);
            vis[pre[i]] = false;
        }
    }
}
int main() {
    prime();
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &s[i]);
    DFS(0, 0);
    if (min_ < inf)
        printf("%d\n", min_);
    else printf("-1\n");
    return 0;
}

Problem F kotori和n皇后

题目链接:https://ac.nowcoder.com/acm/contest/940/F/

题意:判断是否存在两个皇后可以互相攻击。
思路:利用n皇后相互攻击的规律，利用set求解。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
set <int> setr, setc, set45, set135;
bool Judge(int x, int y) {
    if (setr.count(x) || setc.count(y) || set45.count(x - y) || set135.count(x + y))
        return true;
    return false;
}
int main() {
    int n, m, t, x, y, min_ = inf;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x, &y);
        if (min_ >= inf) {
            if (Judge(x, y))
                min_ = i;
            setr.insert(x);
            setc.insert(y);
            set45.insert(x - y);
            set135.insert(x + y);
        }
    }
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &m);
        if (m >= min_)
            printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

Problem G kotori和抽卡（二）

题目链接:https://ac.nowcoder.com/acm/contest/940/G/

题意:抽n次恰好m张R卡。
思路:二项分布，

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    double ans = 1.0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n - m; i++)
        ans *= 0.2 * (n - i + 1) / i;
    for (int i = 0; i < m; i++)
        ans *= 0.8;
    printf("%.4lf\n", ans);
    return 0;
}

Problem H andy和购物

题目链接:https://ac.nowcoder.com/acm/contest/940/H/

题意:n个价格有n个折扣，求打折后的最小花费。
思路:贪心，用小的价钱打大的折。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
int prc[1010];
double dsc[1010];
int main() {
    int t, n;
    scanf("%d", &t);
    while(t--) {
        double res = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &prc[i]);
        for (int i = 0; i < n; i++)
            scanf("%lf", &dsc[i]);
        sort(prc, prc + n);
        sort(dsc, dsc + n);
        for (int i = 0; i < n; i++)
            res += prc[i] * dsc[n - i - 1];
        printf("%.3lf\n", res);
    }
   return 0;
}

Problem I andy种树

题目链接:https://ac.nowcoder.com/acm/contest/940/I/

题意:求q次浇水后，n棵树的最终高度。
思路:差分。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
int pre[100005];
int main() {
    int t, n, l, r;
    scanf("%d%d", &n, &t);
    while(t--) {
        scanf("%d%d", &l, &r);
        pre[l]++;
        pre[r + 1]--;
    }
    for (int i = 1; i <= n; i++) {
        pre[i] += pre[i - 1];
        printf("%d%c", pre[i], "\n "[i != n]);
    }
    return 0;
}

Problem J andy的树被砍了

题目链接:https://ac.nowcoder.com/acm/contest/940/J/

题意:每天都要种树，每天也要砍树，求n棵树将在哪天被砍死。
思路:对位置i，应该找i~n+1中c[i]前缀和超过h[j]的最小位置。因此要求出c的前缀和c，二分查找c[j-1]=h[j]的最小位置。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
long long c[N], h[N];
int slove(int l, int r, long long k) {
    int mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (c[mid] >= k)
            r = mid - 1;
        else l = mid + 1;
    }
    return l;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &h[i]);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &c[i]);
        c[i] += c[i - 1];
    }
    c[n + 1] = c[n] + N;
    for (int i = 1; i <= n; i++)
        printf("%d%c", slove(i, n + 1, c[i - 1] + h[i]), "\n "[i != n]);
    return 0;
}