牛客小白月赛40
2021/11/7 23:40:29
本文主要是介绍牛客小白月赛40,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A.数字游戏
题意:
我们可以对一个非零数的二进制进行以下操作:
1.若二进制中有奇数个1,我们将其二进制最低位取反
2.若二进制中有偶数个1,我们将其二进制中非前导0最高位取反。
问给你个数x,需要操作几次变成0.
思路:
先把数转换为二进制,通过枚举找到规律如下:
令该数为n,其二进制中1的个数为x。
1.若n为0,ans = 0。
2.若n为偶数,且x也为偶数,则ans = 2 * x。
3.若n为偶数,且x为奇数,则ans = 2 * x - 2。
4.若n为奇数,且x为奇数,则ans = 2 * x - 1。
5.若n为奇数,且x为偶数,则ans = 2 * x + 1。
代码:
#include <bits/stdc++.h> typedef long long LL; using namespace std; int work(LL n) { int ans = 0; while(n) { if(n % 2 == 1) ans ++; n /= 2; } return ans; } void solve() { LL n; scanf("%lld",&n); int ans = 0; int x = work(n); if(n == 0){ ans = 0; } else if(x % 2 == 0){ if(n % 2 == 0) ans = 2 * x; else ans = 2 * x - 2; } else { if(n % 2 == 0){ ans = 2 * x + 1; }else{ ans = 2 * x - 1; } } printf("%d\n",ans); } int main() { int T = 1; scanf("%d",&T); while(T -- ) { solve(); } return 0; }
B.跳跳跳
题意:
有一个n个格子呈环状分布,每个格子都有一个权值a[i],dd可以选择任意一个格子开始跳,每次只能跳到其当前位置左边或者右边最近的且未被跳过的位置,每次获得 k * a[i]的得分,k为当前跳跃次数,a[i]为当前格子上的权值。问如何跳使得总得分最大,求出最大总分。
思路:
这是一个区间dp。dd左右跳形成一个个区间,我们令dp[i][j]表示从编号为i的格子跳到编号为j的格子中得分最大。
很明显状态转移只有两种情况:
1.从dp[i +1][j] ——> dp[i[j]
2.从dp[i][j - 1] ——> dp[i][j]
所以 dp[i][j] = max(dp[i + 1][j] + a[i] * (j - i + 1), dp[i][j - 1] + a[j] * (j - i + 1));
然后枚举下长度为n的区间,寻找下最大值就OK。
本题是环形难以处理需要不断取模,我们可以将原数组复制成原来的两倍再加以处理。
其次是从状态转移方程来看,想要计算出dp[i][j],先必须要计算出dp[i +1][j]和dp[i][j - 1],所以外层循环要从大到小枚举,内层循环需要从小到大枚举。
代码:
#include <bits/stdc++.h> using namespace std; typedef long long LL; int n; int a[4010]; LL dp[4010][4010]; int main() { cin >> n; for(int i = 1; i <= n; i ++ ) cin >> a[i], a[i + n] = a[i]; for(int i = 1; i <= 2 * n; i ++ ) dp[i][i] = a[i]; for(int i = 2 * n; i >= 1; i -- ) for(int j = i + 1; j <= n + i - 1; j ++ ) dp[i][j] = max(dp[i + 1][j] + a[i] * (j - i + 1), dp[i][j - 1] + a[j] * (j - i + 1)); LL ans = -1; for(int i = 1; i <= n + 1; i ++ ) ans = max(ans, dp[i][n + i - 1]); cout << ans << endl; return 0; }
C.数字匹配
题意:
对于任意两个正整数x,y(x≠y),当且仅当x,y的二进制非前导零部分最大连续重合位数≥k时,x,y是匹配的。
让你寻找1~n中x与y的匹配数,x < y。
思路:
暴力处理1~n中所有数的二进制,再暴力查找匹配的x,y的数目。
代码:
#include <bits/stdc++.h> using namespace std; int n, k; string a[2010]; vector<int> binary(int n) { vector<int>q; while(n) { q.push_back(n % 2); n /= 2; } reverse(q.begin(),q.end()); return q; } bool check(int x, int y) { for(int i = 0; i + k <= a[x].length(); i ++ ) for(int j = 0; j + k <= a[y].length(); j ++ ) if(a[x].substr(i, k) == a[y].substr(j, k)) return true; return false; } int main() { scanf("%d %d",&n, &k); for(int i = 1; i <= n; i ++ ) { vector<int>q = binary(i); for(int j = 0; j < q.size(); j ++ ) a[i] += (q[j] + '0'); } int ans = 0; for(int i = 1; i <= n; i ++ ) for(int j = i + 1; j <= n; j ++ ) if(check(i, j)) ans ++; cout << ans << endl; return 0; }
D.优美字符串
题意:
给你个字符串,问你至少需要插入多少字符使得相邻的两个字符串不相等。
思路:
暴力枚举,统计出有多少相邻两个字符相等的数目。
#include <bits/stdc++.h> typedef long long LL; using namespace std; string s; void solve() { cin >> s; int ans = 0; for(int i = 0; i + 1 < s.length(); i ++ ) { if(s[i + 1] == s[i]) ans ++; } cout << ans + s.length() << endl; } int main() { int T = 1; ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin >> T; while(T -- ) { solve(); } return 0; }
E.分组
题意:
给你n个同学,每个同学都有个声部,让你把他们分为m组,要满足每一组的声部都一样,求出所有组中的最大人数最小。若不能分组,输出”-1“。
思路:
若声部个数大于组数,无法进行分组, 输出-1。剩余情况,二分查找最小值即可。
代码:
#include <bits/stdc++.h> using namespace std; int n, m; int a[100010]; bool st[100010]; map<int,int>mp; bool check(int mid) { int qwq = 0; for(auto it : mp){ if(it.second % mid == 0){ qwq += it.second / mid; }else{ qwq = qwq + (it.second / mid) + 1; } } if(qwq > m) return false; return true; } int main() { cin >> n >> m; int cnt = 0; for(int i = 1; i <= n; i ++ ) { cin >> a[i]; if(st[a[i]] == false) { st[a[i]] = true; cnt ++; } mp[a[i]] ++; } if(cnt > m){ cout << -1 << endl; }else{ int l = 1, r = n; while(l < r) { int mid = (l + r) >> 1; if(check(mid)) r = mid; else l = mid + 1; } cout << l << endl; } return 0; }
F.过桥
题意:
有n个浮块,dd站在第一个浮块上,每个浮块上有一个权值,dd在第i个浮块上,可以跳到i + k(k <= a[i])个浮块上,若i + a[i] < 1, 就只能移动到1浮块上,问dd最少移动几次就能到达n,如果无法到达输出-1。
思路:
我们开一个f数组,记录到每个浮块的最小次数,然后跑一边BFS即可。若f[n]为无穷大,则无法到达。否则,输出f[n]。
#include <bits/stdc++.h> using namespace std; int n; int a[20100]; int f[20100]; int main() { cin >> n; for(int i = 1; i <= n; i ++ ) cin >> a[i]; memset(f, 0x3f, sizeof f); queue<int>q; f[1] = 0; q.push(1); while(!q.empty()) { int tt = q.front(); q.pop(); if(a[tt] > 0) { for(int i = tt + 1; i <= tt + a[tt]; i ++ ) { if(f[tt] + 1 < f[i]) { f[i] = f[tt] + 1; q.push(i); } } } else{ int x = max(tt + a[tt], 1); for(int i = 1; i <= x; i ++ ) { if(f[tt] + 1 < f[i] ) { f[i] = f[tt] + 1; q.push(i); } } } } if(f[n] == 0x3f3f3f3f) puts("-1"); else cout << f[n] << endl; return 0; }
G.遥控
题意:
集训队每个人都有一个温度诉求a[i],当 |a[i] - k| <= p时,算达到诉求,问dd把集训队内部的温度控制为多少,才能让更多的人达到诉求。
思路:
预处理出每个温度下,队员达到诉求的人数,再暴力枚举温度,不断取在某个温度下达到诉求的人数的最大值。
代码:
#include <bits/stdc++.h> using namespace std; const int N = 1000100; int n, p; int a[N]; int b[N]; int sum[N]; int main() { cin >> n >> p; for(int i = 1; i <= n; i ++ ) { cin >> a[i]; b[a[i]] ++; } sum[1] = b[1]; for(int i = 2; i <= 1000000; i ++ ) sum[i] = sum[i - 1] + b[i]; int ans = -1; for(int i = p + 1; i <= n - p; i ++ ) ans = max(ans, sum[i + p] - sum[i - p - 1]); cout << ans << endl; return 0; }
H.来点gcd
题意:
给你一个集合S,和一个数x,问你是否能找到S的一个子集,使S中所有元素的gcd等于x。
思路:
若一个集合所有元素的gcd是x,则这个集合中的元素都是x的倍数,暴力查找出集合S中的x的倍数,然后一起取gcd,若为x,则存在,否则不存在。
若集合中x的倍数不存在,显然答案也是不存在的。
代码:
#include <bits/stdc++.h> using namespace std; const int N = 1000100; int t; int n, m; int a[N]; bool st[1000010]; void solve() { cin >> n >> m; for(int i = 1; i <= n; i ++ ) st[i] = false; for(int i = 1; i <= n; i ++ ) { scanf("%d",&a[i]); st[a[i]] = true; } while(m -- ) { int x; scanf("%d",&x); vector<int> ans; for(int i = x; i <= n; i += x) if(st[i] == true) ans.push_back(i); if((ans.size() == 1 && ans[0] != x) || !ans.size()) puts("NO"); else if(ans.size() == 1) puts("YES"); else { int qwq = __gcd(ans[0], ans[1]); for(int i = 2; i < ans.size(); i ++ ) qwq = __gcd(ans[i], qwq); if(qwq == x) puts("YES"); else puts("NO"); } } } int main() { scanf("%d",&t); while(t -- ) { solve(); } return 0; }
I.体操队形
题意:
给你个数组a[i],体操队形要满足第i个人要站在a[i]的人的前面,问有几种站法?
思路:
暴力枚举所有站法,判断是否合法就行。
代码:
#include <bits/stdc++.h> using namespace std; int n; int a[100]; int b[15]; bool check() { int c[15]; for(int i = 1; i <= n; i ++ ) { for(int j = 0; j < n; j ++ ) { if(b[j] == i) c[i] = j; } } for(int i = 1; i <= n; i ++ ) if(c[i] > c[a[i]]) return false; return true; } int main() { cin >> n; for(int i = 1; i <= n; i ++ ) cin >> a[i]; for(int i = 0; i < n; i ++ ) b[i] = i + 1; int ans = 0; do { if(check()) ans ++; }while(next_permutation(b, b + n)); cout << ans << endl; // system("pause"); return 0; }
这篇关于牛客小白月赛40的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南