本文共 6673 字，大约阅读时间需要 22 分钟。

Problem A 

题目链接:

题意:合并，求最小代价值。

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

Accepted Code:

#include 
   
    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 

题目链接:

题意:求满足要求的m个气球的排列数。

思路:组合数学，第1个有n种选择，则剩余的m-1个都只有n-1种选择，故总的排列数为。

Accepted Code:

#include 
   
    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 

题目链接:

题意:约瑟夫环问题。

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

Accepted Code:

#include 
   
    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 

题目链接:

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

思路:BFS。

Accepted Code:

#include 
   
    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 
    
      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 

题目链接:

题意:每个都贡献一个素因子，保证所有的素因子互不相同，求素因子和的最小值。

思路:线性筛出1~1000之内的所有素数，然后DFS求解最小值。

Accepted Code:

#include 
   
    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 

题目链接:

题意:判断是否存在两个皇后可以互相攻击。

思路:利用n皇后相互攻击的规律，利用set求解。

Accepted Code:

#include 
   
    using namespace std;const int inf = 0x3f3f3f3f;set 
    
      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 

题目链接:

题意:抽n次恰好m张R卡。

思路:二项分布，

Accepted Code:

#include 
   
    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 

题目链接:

题意:n个价格有n个折扣，求打折后的最小花费。

思路:贪心，用小的价钱打大的折。

Accepted Code:

#include 
   
    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 

题目链接:

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

思路:差分。

Accepted Code:

#include 
   
    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 

题目链接:

题意:每天都要种树，每天也要砍树，求n棵树将在哪天被砍死。

思路:对位置i，应该找i~n+1中c[i]前缀和超过h[j]的最小位置。因此要求出c的前缀和c，二分查找c[j-1]=h[j]的最小位置。

Accepted Code:

#include 
   
    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;}
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/94487181 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！