牛客网 - 北京信息科技大学第十一届程序设计竞赛
发布日期:2021-07-01 00:18:53
浏览次数:2
分类:技术文章
本文共 6673 字,大约阅读时间需要 22 分钟。
Problem A
题目链接:
题意:合并,求最小代价值。
思路:将一个堆二分,递归求该堆合并的最小代价值。Accepted Code:
#includeusing 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:
#includeusing 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:
#includeusing 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:
#includeusing 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:
#includeusing 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:
#includeusing 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:
#includeusing 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:
#includeusing 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:
#includeusing 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:
#includeusing 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月22日 19时00分38秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Flink Runtime(9)-- 自己编译Flink
2019-05-01
Flink Runtime(10)-- Flink编译报错集锦
2019-05-01
Flink API 通用基本概念(11)
2019-05-01
Flink DataStream API概述(12)
2019-05-01
Flink Operator概述(13)
2019-05-01
Flink Time概述(14)
2019-05-01
Flink Window概述(15)
2019-05-01
Flink Operators之CoGroup和Join概述(16)
2019-05-01
Flink Operators之Process Function(17)
2019-05-01
Flink 异步I/O访问外部数据(18)
2019-05-01
深入理解python--线程、进程与协程(1)
2019-05-01
Flink中增量聚合函数和全量聚合函数的关系
2019-05-01
HIVE自定义函数--UDF函数(用户自定义函数)详解
2019-05-01
Java中访问控制符的具体用法
2019-05-01
Java包重点总结
2019-05-01
创建线程究竟该用第几种方式
2019-05-01
Java--流重点总结初稿
2019-05-01
Java高级部分流---换个角度思考流
2019-05-01
如何解决电脑ip地址冲突的问题
2019-05-01
Win下如何查看本地计算机的网络端口被哪个应用程序所占用
2019-05-01